習題6樹和二叉樹

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

2、二叉樹中所包含的結(jié)點數(shù)至少為_。A.2hB.2h-lC.2h+lD.h+1對一個滿二叉樹，m個樹葉，n個結(jié)點，深度為h,則_A_。A.n=h+mB.h+m=2nC.m=h-1D.n=2h-1任何一棵二叉樹的葉結(jié)點在先序、中序和后序遍歷序列中的相對次序_A_。不發(fā)生改變B.發(fā)生改變C.不能確定D.以上都不對如果某二叉樹的前根次序遍歷結(jié)果為stuwv,中序遍歷為uwtvs，那么該二叉樹的后序為_C_。A.uwvtsB.vwutsC.wuvtsD.wutsv二叉樹的前序遍歷序列中，任意一個結(jié)點均處在其子女結(jié)點的前面，這種說法_A_A.正確B.錯誤某二叉樹的前序遍歷結(jié)點訪問順序是abdgcefh，中序

3、遍歷的結(jié)點訪問順序是dgbaechf，則其后序遍歷的結(jié)點訪問順序是D。A.bdgcefhaB.gdbecfhaC.bdgaechfD.gdbehfca在一非空二叉樹的中序遍歷序列中，根結(jié)點的右邊_A_。A.只有右子樹上的所有結(jié)點B.只有右子樹上的部分結(jié)點C.只有左子樹上的部分結(jié)點D.只有左子樹上的所有結(jié)點如圖6.1所示二叉樹的中序遍歷序列是_B_。A.abcdgefB.dfebagcC.dbaefcgD.defbagc6.1一棵二叉樹如圖6.2所示，其中序遍歷的序列為B。A.abdgcefhB.dgbaechfC.gdbehfcaD.abcdefgh設a,b為一棵二叉樹上的兩個結(jié)點，在中序遍歷

4、時，a在b前的條件是BoAa在b的右方Ba在b的左方Ca是b的祖先Da是b的子孫已知某二叉樹的后序遍歷序列是dabec,中序遍歷序列是debac,它的前序遍歷序列是_D_。A.acbedB.decabC.deabcD.cedba實現(xiàn)任意二叉樹的后序遍歷的非遞歸算法而不使用棧結(jié)構,最佳方案是二叉樹采用_C_存儲結(jié)構。A.二叉鏈表B.廣義表存儲結(jié)構C.三叉鏈表D.順序存儲結(jié)構圖6.3B.無序數(shù)據(jù)元素D.元素之間無聯(lián)系的數(shù)據(jù)24.樹的基本遍歷策略可分為先根遍歷和后根遍歷；二叉樹的基本遍歷策略可分為先序遍歷、中序遍歷和后序遍歷。這里,我們把由樹轉(zhuǎn)化得到的二叉樹叫做這棵數(shù)對應的二叉樹。結(jié)論_A_是正確的

5、。樹的先根遍歷序列與其對應的二叉樹的先序遍歷序列相同樹的后根遍歷序列與其對應的二叉樹的后序遍歷序列相同樹的先根遍歷序列與其對應的二叉樹的中序遍歷序列相同以上都不對25.樹最適合用來表示_C_。A.有序數(shù)據(jù)元素C.元素之間具有分支層次關系的數(shù)據(jù)6.2填空題（將正確的答案填在相應的空中）有一棵樹如圖6.5所示,回答下面的問題：這棵樹的根結(jié)點是_k0_；這棵樹的葉子結(jié)點是；結(jié)點k3的度是_2_；這棵樹的度是_3_；這棵樹的深度是_4_；結(jié)點k3的子女是_k5,k6_結(jié)點k3的父結(jié)點是_k1_；指出樹和二叉樹的三個主要差別：樹的結(jié)點個數(shù)至少為1,而二叉樹的結(jié)點個數(shù)可以為0樹中結(jié)點的最大度數(shù)沒有限制,而

6、二叉樹結(jié)點的最大度數(shù)為2樹的結(jié)點無左、右之分，而二叉樹的結(jié)點有左、右之分從概念上講,樹與二叉樹是兩種不同的數(shù)據(jù)結(jié)構,將樹轉(zhuǎn)化為二叉樹的基本目的是_樹可采用二叉樹的存儲結(jié)構并利用二叉樹的已有算法解決樹的有關問題_。一棵二叉樹的結(jié)點數(shù)據(jù)采用順序存儲結(jié)構，存儲于數(shù)組t中，如圖6.6所示，則該二6.9叉樹的鏈接表示形式為。123456789101112131415161718192021eafdgcjlhb圖6.6一棵二叉樹的順序存儲數(shù)組t深度為k的完全二叉樹至少有_2k-1_個結(jié)點。至多有_2k-1_個結(jié)點，若按自上而下，從左到右次序給結(jié)點編號(從1開始)，則編號最小的葉子結(jié)點的編號是_lk-2+l

7、。在一棵二叉樹中，度為零的結(jié)點的個數(shù)為n0，度為2的結(jié)點的個數(shù)為n2，則有n0=_n2+1_。一棵二叉樹的第iG21)層最多有_2i-1_個結(jié)點；一棵有n(n0)個結(jié)點的滿二叉樹共有_(n+1)/2_個葉子和_(n-1)/2_個非終端結(jié)點。結(jié)點最少的樹為_只有一個結(jié)點的樹_，結(jié)點最少的二叉樹為_空的二叉樹_。10.由如圖6.7所示的二叉樹，回答以下問題：現(xiàn)有按中序遍歷二叉樹的結(jié)果為abc，問有_5種不同形態(tài)的二叉樹可以得到這一其中序遍歷序列為_dgbaechif_其前序遍歷序列為_abdgcefhi_其后序遍歷序列為_gdbeihfca_6.3簡答題1.根據(jù)二叉樹的定義，具有三個結(jié)點的二叉樹有

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