習題樹和二叉樹

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

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

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

4、gA. gdbehfca 15.設 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為一棵二叉樹上的兩個結點, 件是 B 。B. a在b的左方C.在中序遍D. a是b的子孫 dabec,中序遍歷序列是 D.cedbadebac,它的前序遍歷序列是_D_O_C_存儲結17 .實現(xiàn)任意二叉樹的后序遍歷的非遞歸算法而不

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

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

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

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

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