習題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設(shè)高度為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設(shè)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é)構(gòu),最佳方案是二叉樹采用_C_存儲結(jié)構(gòu)。A.二叉鏈表B.廣義表存儲結(jié)構(gòu)C.三叉鏈表D.順序存儲結(jié)構(gòu)圖6.3B.無序數(shù)據(jù)元素D.元素之間無聯(lián)系的數(shù)據(jù)24.樹的基本遍歷策略可分為先根遍歷和后根遍歷；二叉樹的基本遍歷策略可分為先序遍歷、中序遍歷和后序遍歷。這里,我們把由樹轉(zhuǎn)化得到的二叉樹叫做這棵數(shù)對應(yīng)的二叉樹。結(jié)論_A_是正確的

5、。樹的先根遍歷序列與其對應(yīng)的二叉樹的先序遍歷序列相同樹的后根遍歷序列與其對應(yīng)的二叉樹的后序遍歷序列相同樹的先根遍歷序列與其對應(yīng)的二叉樹的中序遍歷序列相同以上都不對25.樹最適合用來表示_C_。A.有序數(shù)據(jù)元素C.元素之間具有分支層次關(guān)系的數(shù)據(jù)6.2填空題（將正確的答案填在相應(yīng)的空中）有一棵樹如圖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é)構(gòu),將樹轉(zhuǎn)化為二叉樹的基本目的是_樹可采用二叉樹的存儲結(jié)構(gòu)并利用二叉樹的已有算法解決樹的有關(guān)問題_。一棵二叉樹的結(jié)點數(shù)據(jù)采用順序存儲結(jié)構(gòu)，存儲于數(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所示的二叉樹，請畫出該二叉樹對應(yīng)的森林。已知一棵樹如圖6.8所示，轉(zhuǎn)化為一棵二叉樹，表示為假設(shè)一棵二叉樹的先序序列為EBADCFHGIKJ和中序序列為ABCDEFGHIJK。5.以數(shù)據(jù)集4，5，6，7，10，12，18為結(jié)點權(quán)值，畫出構(gòu)造Huffman樹的每一步圖示，計算其帶權(quán)路徑長度為。圖&1&Huffrnan樹6.一棵含有N個結(jié)點的k叉樹，可能達到的最大深度和最小深度各為多少?最大深度：h=N-k+l,最小深度：logkN+17證明:一棵滿k叉樹上的葉子結(jié)點數(shù)n和非葉子結(jié)點數(shù)n之間滿足以下關(guān)系：01n=(k-1)n+1016.4算法設(shè)計題1.編寫按層次順序(同一層自左至右)遍歷二叉樹的算法。2試編寫算法，對一棵二叉樹,統(tǒng)計葉子的個數(shù)。3試編寫算法，對一棵二叉樹根結(jié)點不變，將左、右子樹進行交換，樹中每個結(jié)點的左、右子樹進行交換。假設(shè)用于通訊的電文僅有八個字母(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