習(xí)題6樹和二叉樹

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

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

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

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

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

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

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

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