線性數(shù)學(xué)試題解答6-閱讀頁(yè)
2024-09-24 21:16本頁(yè)面
【正文】 0 ??????? ?? ??mi inin 68 試分別找出滿足以下條件的所有二叉樹 : (1) 二叉樹的前序序列與中序序列相同 。 (3) 二叉樹的前序序列與后序序列相同。 69 若用二叉鏈表作為二叉樹的存儲(chǔ)表示，試針對(duì)以下問(wèn)題編寫遞歸算法： (1) 統(tǒng)計(jì)二叉樹中葉結(jié)點(diǎn)的個(gè)數(shù)。 【解答】 (1) 統(tǒng)計(jì)二叉樹中葉結(jié)點(diǎn)個(gè)數(shù) int BinaryTreeType :: leaf ( BinTreeNodeType * ptr ) { if ( ptr == NULL ) return 0。amp。 else return leaf ( ptrleftChild ) + leaf ( ptrrightChild )。 if ( ptrleftChild != NULL || ptrrightChild != NULL ) { temp = ptrleftChild。 ptrrightChild = temp。 exchange ( ptrrightChild )。 611 試用判定樹的方法給出在中序線索化二叉樹上： 【解答】 (1) 搜索指定結(jié)點(diǎn)的在中序下的后繼。 找 q 的右子樹中在中序下的第一個(gè)結(jié)點(diǎn)的程序?yàn)椋? p = qrightChild。 // p 即為 q 的后繼 (2) 搜索指定結(jié)點(diǎn)的在前序下的后繼。 qrightThread == 1? = ≠ qrightChild == NULL ? = q 無(wú)后繼 ≠ q 的后繼為 qrightChild q 的后繼為 q 的右子樹中中序下的第一個(gè)結(jié)點(diǎn) qleftThread == 0 ? = q 的后繼為 qleftChild ≠ qrightThread == 0 ? = q 的后繼為 qrightChild ≠ p = q。amp。 if ( prightChild ==NULL ) q 無(wú)后繼 。找到后立即返回它的地址。試設(shè)計(jì)一個(gè)算法，從 T[0]開(kāi)始順序讀出各結(jié)點(diǎn)的值，建立該二叉樹的二叉鏈表表示。 operator ( istreamamp。 t ) { int n。 in n。 for ( int i = 0。 i++ ) in A[i]。 //以數(shù)組建立一棵二叉樹 delete [ ] A。 } template class Type void BinaryTreeType :: ConstructTree ( Type T[ ], int n, int i, BinTreeNodeType *amp。利用引用型參數(shù) ptr 將形參的值帶回實(shí)參。 else { ptr = new BinTreeNodeType ( T[i] )。 ConstructTree ( T, n, 2*i+2, ptrrightChild )。 【解答】以最小堆為例： 616 請(qǐng)畫出右圖所示的樹所對(duì)應(yīng)的二叉樹。如果我們采用靜態(tài)二叉鏈表作為森林的存儲(chǔ)表示，同時(shí)按森林的先根次序依次安放森林的所有結(jié)點(diǎn)，則可以在它們的結(jié)點(diǎn)中用只有一個(gè)二進(jìn)位的標(biāo)志 ltag 代替 llink，用 rtag代替 rlink。試給出這種表示的結(jié)構(gòu)定義，并設(shè)計(jì)一個(gè)算法，將用這種表示存儲(chǔ)的森林轉(zhuǎn)換成用 llink rlink 表示的森林。 //結(jié)點(diǎn)數(shù)據(jù) int llink, rlink。 //結(jié)點(diǎn)數(shù)據(jù) int ltag, rtag。 //存儲(chǔ)左子女 右兄弟鏈表的向量 DoublyTagNode Type *U。 //向量中最大元素個(gè)數(shù)和當(dāng)前元素個(gè)數(shù) public: dstaticlinkList ( int Maxsz ) : MaxSize ( Maxsz ), CurrentSize (0) { V = new LchRsibNode Type [Maxsz]。 } } (2) 森林的雙標(biāo)記先根次序表示向左子女 右兄弟鏈表先根次序表示的轉(zhuǎn)換 void staticlinkListType :: DtagFLchRsibF ( ) { Stackint st。 for ( int i = 0。 i++ ) { switch ( U[i].ltag ) { case 0 : switch ( U[i].rtag ) { case 0 : V[i].llink = V[i].rlink = 1。 ( )。 } break。 V[i].rlink = i + 1。 } break。 V[i].rlink = 1。 case 1 : V[i].llink = i + 1。 } } } } 618 二叉樹的雙序遍歷 (Doubleorder traversal)是指：對(duì)于二叉樹的每一個(gè)結(jié)點(diǎn)來(lái)說(shuō)，先訪問(wèn)這個(gè)結(jié)點(diǎn)，再按雙序遍歷它的左子樹，然后再一次訪問(wèn)這個(gè)結(jié)點(diǎn)，接下來(lái)按雙序遍歷它的右子樹。 【解答】 template class Type void BinaryTreeType :: Double_order ( BinTreeNodeType *current ){ if ( current != NULL ) { cout currentdata 39。 Double_order ( currentleftChild )。 39。 } } 619 已知一棵二叉樹的前序遍歷的結(jié)果是 ABECDFGHIJ, 中序遍歷的結(jié)果是 EBCDAFHIGJ, 試畫出這棵二叉樹。 試問(wèn)利用樹的先根次序遍歷結(jié)果和后根次序遍歷結(jié)果能否唯一確定一棵樹 ? 舉例說(shuō)明。 621 給定權(quán)值集合 {15, 03, 14, 02, 06, 09, 16, 17}, 構(gòu)造相應(yīng)的霍夫曼樹 , 并計(jì)算它的帶權(quán)外部路徑長(zhǎng)度。 622 假定用于通信的電文僅由 8個(gè)字母 c1, c2, c3, c4, c5, c6, c7, c8 組成 , 各字母在電文中出現(xiàn)的頻率分別為 5, 25, 3, 6, 10, 11, 36, 4。 【解答】已知字母集 { c1, c2, c3, c4, c5, c6, c7, c8 }，頻率 {5, 25, 3, 6, 10, 11, 36, 4 }， 則 Huffman 編碼為 c1 c2 c3 c4 c5 c6 c7 c8 0110 10 0000 0111 001 010 11 0001 電文總碼數(shù)為 4 * 5 + 2 * 25 + 4 * 3 + 4 * 6 + 3 * 10 + 3 * 11 + 2 * 36 + 4 * 4 = 257 623 給定一組權(quán)值 : 23, 15, 66, 07, 11, 45, 33, 52, 39, 26, 58, 試構(gòu)造一棵具有最小帶權(quán)外部路徑長(zhǎng)度的擴(kuò)充 4 叉樹 , 要求該 4 叉樹中所有內(nèi)部結(jié)點(diǎn)的度都是 4, 所有外部結(jié)點(diǎn)的度都是 0。設(shè)內(nèi)結(jié)點(diǎn)個(gè)數(shù)為 n4，外結(jié)點(diǎn)個(gè)數(shù)為 n0，則可證明有關(guān)系 n0 = 3 * n4 + 1。此時(shí)內(nèi)結(jié)點(diǎn)個(gè)數(shù) n4 = 4。 此樹的帶權(quán)路徑長(zhǎng)度 WPL = 375 + 82 + 169 + 18 = 64
公司管理相關(guān)推薦
鄂ICP備17016276號(hào)-1