習(xí)題樹和二叉樹

1、習(xí)題6樹和二叉樹說明：本文檔中，凡紅色字標(biāo)出的題請?zhí)峤患堎|(zhì)作業(yè)，只寫題號和答案即可。6.1 單項選擇題1 .由于二叉樹中每個結(jié)點(diǎn)的度最大為2,所以二叉樹是一種特殊的樹，這種說法_B_OA.正確B.錯誤2 .假定在一棵二叉樹中，雙分支結(jié)點(diǎn)數(shù)為15,單分支結(jié)點(diǎn)數(shù)為 30個，則葉子結(jié)點(diǎn)數(shù)為B 個。A. 15 B. 16 C. 17 D. 473 .按照二叉樹的定義，具有3個結(jié)點(diǎn)的不同形狀的二叉樹有_C_種。A. 3B. 4 C. 5 D. 64 .按照二叉樹的定義，具有3個不同數(shù)據(jù)結(jié)點(diǎn)的不同的二叉樹有_C_種。A. 5B. 6 C. 30 D. 325 .深度為5的二叉樹至多有_C_個結(jié)點(diǎn)。A. 1

2、6 B. 32 C. 31 D. 106 .設(shè)高度為h的二叉樹上只有度為 0和度為2的結(jié)點(diǎn)，則此類二叉樹中所包含的結(jié)點(diǎn)數(shù)至少為BOA. 2hB. 2h-1 C. 2h+1 D. h+17 .對一個滿二叉樹，m個樹葉，n個結(jié)點(diǎn)，深度為h,則_A_ 。A. n=h+mB. h+m=2n C. m=h-1D. n=2 h-18 .任何一棵二叉樹的葉結(jié)點(diǎn)在先序、中序和后序遍歷序列中的相對次序_A_OA.不發(fā)生改變B.發(fā)生改變C.不能確定D.以上都不對9 .如果某二叉樹的前根次序遍歷結(jié)果為stuwv,中序遍歷為uwtvs,那么該二叉樹的后序為 _C_OA. uwvtsB. vwutsC. wuvts D

3、. wutsv10 .二叉樹的前序遍歷序列中，任意一個結(jié)點(diǎn)均處在其子女結(jié)點(diǎn)的前面，這種說法_A_。 A.正確B.錯誤11 .某二叉樹的前序遍歷結(jié)點(diǎn)訪問順序是 遍歷的結(jié)點(diǎn)訪問順序是_D_。A. bdgcefha B. gdbecfha12 .在一非空二叉樹的中序遍歷序列中， A.只有右子樹上的所有結(jié)點(diǎn) C.只有左子樹上的部分結(jié)點(diǎn)abdgcefh,中序遍歷的結(jié)點(diǎn)訪問順序是dgbaechf,C. bdgaechf 根結(jié)點(diǎn)的右邊D. gdbehfca _A_O則其后序13.如圖6.1所示二叉樹的中序遍歷序列是B.只有右子樹上的部分結(jié)點(diǎn)D.只有左子樹上的所有結(jié)點(diǎn)_B_O歷時,A.abcdgefab列為d

4、gA. gdbehfca 15.設(shè) a,b a在b前的條圖6.114. 一棵B 。16.A. acbedB. dfebagcD. defbagcC. dbaefcgabg圖6.2二叉樹如圖6.2所示，其中序遍歷的序. a在b的右方C. a是b的祖先 已知某二叉樹的后序遍歷序列是B.decab C.deabcabdgcefh B. dgbaechfD. abcdefgh為一棵二叉樹上的兩個結(jié)點(diǎn), 件是 B 。B. a在b的左方C.在中序遍D. a是b的子孫 dabec,中序遍歷序列是 D.cedbadebac,它的前序遍歷序列是_D_O_C_存儲結(jié)17 .實現(xiàn)任意二叉樹的后序遍歷的非遞歸算法而不

5、使用棧結(jié)構(gòu)，最佳方案是二叉樹采用 構(gòu)。A.二叉鏈表B.廣義表存儲結(jié)構(gòu)C.三叉鏈表 D.順序存儲結(jié)構(gòu)18 .如圖6.3所示的4棵二叉樹，_C_不是完全二叉樹。圖6.324.樹的基本遍 歷策略可分為先根 遍歷和后根遍歷；二 叉樹的基本遍歷策 略可分為先序遍歷、 中序遍歷和后序遍 歷。這里，我們把由 樹轉(zhuǎn)化得到的二叉樹叫做這棵數(shù)對應(yīng)的二叉樹。結(jié)論_A_是正確的。A.樹的先根遍歷序列與其對應(yīng)的二叉樹的先序遍歷序列相同B.樹的后根遍歷序列與其對應(yīng)的二叉樹的后序遍歷序列相同 C.樹的先根遍歷序列與其對應(yīng)的二叉樹的中序遍歷序列相同 D.以上都不對25.樹最適合用來表示 _C_。A.有序數(shù)據(jù)元素C.元素之間具

6、有分支層次關(guān)系的數(shù)據(jù)B.無序數(shù)據(jù)元素D.元素之間無聯(lián)系的數(shù)據(jù)6.2 填空題(將正確的答案填在相應(yīng)的空中)1.有一棵樹如圖6.5所示，回答下面的問題：這棵樹的卞B吉點(diǎn)是_k0_;這棵樹的葉子結(jié)點(diǎn)是； 結(jié)點(diǎn)k3的度是_2_; 這棵樹白度是_3_; 這棵樹的深度是_4_;(6)結(jié)點(diǎn)k3的子女是_k5,k6_;結(jié)點(diǎn)k3的父結(jié)點(diǎn)是_k1_;2.指出樹和二叉樹的三個主要差別：樹的結(jié)點(diǎn)個數(shù)至少為1,而二叉樹的結(jié)點(diǎn)個數(shù)可以樹中結(jié)點(diǎn)的最大度數(shù)沒有限制，而二叉樹結(jié)點(diǎn)的最大度數(shù)為2樹的結(jié)點(diǎn)無左、右之分，而二叉樹的結(jié)點(diǎn)有左、右之分3.從概念上講，樹與二叉樹是兩種不同的數(shù)據(jù)結(jié)構(gòu)，將樹轉(zhuǎn)化為二叉樹的基本目的是 叉樹的存儲

7、結(jié)構(gòu)并利用二叉樹的已有算法解決樹的有關(guān)問題。為0樹可采用4. 一棵二叉樹的結(jié)點(diǎn)數(shù)據(jù)采用順序存儲結(jié)構(gòu)，存儲于數(shù)組t中，如圖6.6所示,則該二叉樹的鏈接表示形式為圖6.6 一棵二叉樹的順序存儲數(shù)組 t5 .深度為k的完全二叉樹至少有 _2k-1_個結(jié)點(diǎn)。至多有 _2k-1_個結(jié)點(diǎn)，若按自上而下，從左到 右次序給結(jié)點(diǎn)編號(從1開始)，則編號最小的葉子結(jié)點(diǎn)的編號是_1k-2+1。6 .在一棵二叉樹中，度為零的結(jié)點(diǎn)的個數(shù)為n 0,度為2的結(jié)點(diǎn)的個數(shù)為 n 2,則有no=_n2+1_7 . 一棵二叉樹的第i (i>1)層最多有_2i-1_個結(jié)點(diǎn)；一棵有 n (n>0)個結(jié)點(diǎn)的滿二叉樹共有_(n

8、+1)/2_個葉子和_(n-1)/2個非終端結(jié)點(diǎn)。8 .結(jié)點(diǎn)最少的樹為只有一個結(jié)點(diǎn)的樹結(jié)點(diǎn)最少的二叉樹為空的二叉樹_。9 .現(xiàn)有按中序遍歷二叉樹的結(jié)果為abc,問有_5_種不同形態(tài)的二叉樹可以得到這一遍歷結(jié)果，這些二叉樹分別是。10 .由如圖6.7所示的二叉樹，回答以下問題:其中序遍歷序列為_dgbaechif_;其前序遍歷序列為_abdgcefhi_ ;其后序遍歷序列為gdbeihfca;6.3 簡答題1 .根據(jù)二叉樹的定義，具有三個結(jié)點(diǎn)的二叉樹有5種不同的形態(tài)，請將它們分別畫出。2 .假設(shè)一棵二叉樹的先序序列為 EBADCFHGIKJ中序序列為ABCDEFGHIJK 請畫出該樹。3.由如圖

9、6.7所示的二叉樹，請畫出該二叉樹對應(yīng)的森林。圖6.7 一棵二叉樹圖6.8 一棵樹4. 已知一棵樹如圖 6.8所示，轉(zhuǎn)化為一棵二叉樹，表示為 。5. 以數(shù)據(jù)集 4 ， 5， 6， 7， 10 ， 12， 18為結(jié)點(diǎn)權(quán)值，畫出構(gòu)造Huffman 樹的每一步圖示，計算其帶權(quán)路徑長度為。6. 一棵含有N個結(jié)點(diǎn)的k叉樹，可能達(dá)到的最大深度和最小深度各為多少？最大深度： h=N-k+1, 最小深度： logkN+17. 證明：一棵滿k叉樹上的葉子結(jié)點(diǎn)數(shù) n0和非葉子結(jié)點(diǎn)數(shù)n1之間滿足以下關(guān)系：n 0=(k-1)n 1 +16.4 算法設(shè)計題1 . 編寫按層次順序(同一層自左至右)遍歷二叉樹的算法。2 試編寫算法，對一棵二叉樹, 統(tǒng)計葉子的個數(shù)。3 試編寫算法，對一棵二叉樹根結(jié)點(diǎn)不變，將左、右子樹進(jìn)行交換，樹中每個結(jié)點(diǎn)的左、右子樹進(jìn) 行交換。7. 假設(shè)用于通訊的電文僅有八個字母(a,b,c,d,e,f,g,h) 組成，字母在電文中出現(xiàn)的頻率分別為0.07, 0.19, 0.02, 0.06, 0.32, 0.03, 0.