樹和二叉樹習(xí)題及答案

1、一、 填空題1. 不相交的樹的聚集稱之為 森林 。2. 從概念上講，樹與二叉樹是兩種不同的數(shù)據(jù)結(jié)構(gòu)，將樹轉(zhuǎn)化為二叉樹的基本目的是_樹可采用孩子-兄弟鏈表（二叉鏈表）做存儲(chǔ)結(jié)構(gòu)，目的是利用二叉樹的已有算法解決樹的有關(guān)問題。3. 深度為k的完全二叉樹至少有2 k-1個(gè)結(jié)點(diǎn)。至多有2 k-1個(gè)結(jié)點(diǎn)，若按自上而下，從左到右次序給結(jié)點(diǎn)編號(hào)（從1開始），則編號(hào)最小的葉子結(jié)點(diǎn)的編號(hào)是2 k-2+1。4. 在一棵二叉樹中，度為零的結(jié)點(diǎn)的個(gè)數(shù)為n 0，度為2的結(jié)點(diǎn)的個(gè)數(shù)為 n 2，則有n0= n2+1。5. 一棵二叉樹的第i（i1）層最多有2 i-1個(gè)結(jié)點(diǎn)；一棵有n（n0）個(gè)結(jié)點(diǎn)的滿二叉樹共有（n+1）/2個(gè)葉

2、子和（n-1） /2個(gè)非終端結(jié)點(diǎn)。6. 現(xiàn)有按中序遍歷二叉樹的結(jié)果為abc，問有5種不同形態(tài)的二叉樹可以得到這一遍歷結(jié)果。7. 哈夫曼樹 是帶權(quán)路徑最小的二叉樹。 8. 前綴編碼是指任一個(gè)字符的編碼都 不是 另一個(gè)字符編碼的前綴的一種編碼方法，是設(shè)計(jì)不等長編碼的前提。9. 以給定的數(shù)據(jù)集合4，5，6，7，10，12，18為結(jié)點(diǎn)權(quán)值構(gòu)造的Huffman樹的加權(quán)路徑長度是 165 。10. 樹被定義為連通而不具有 回路 的（無向）圖。11. 若一棵根樹的每個(gè)結(jié)點(diǎn)最多只有 兩個(gè) 孩子，且孩子又有 左、右 之分，次序不能顛倒，則稱此根樹為 二叉樹 。12. 高度為k，且有 個(gè)結(jié)點(diǎn)的二叉樹稱為 二叉樹。

3、 2k-1 滿13. 帶權(quán)路徑長度最小的二叉樹稱為最優(yōu)二叉樹，它又被稱為 樹。 Huffman 14. 在一棵根樹中，樹根是 為零的結(jié)點(diǎn)，而 為零的結(jié)點(diǎn)是 結(jié)點(diǎn)。 入度 出度 樹葉15. Huffman樹中，結(jié)點(diǎn)的帶權(quán)路徑長度是指由 到 之間的路徑長度與結(jié)點(diǎn)權(quán)值的乘積。 結(jié)點(diǎn) 樹根16. 滿二叉樹是指高度為k，且有 個(gè)結(jié)點(diǎn)的二叉樹。二叉樹的每一層i上，最多有 個(gè)結(jié)點(diǎn)。 2k-1 2i-1二、單選題1. 具有10個(gè)葉結(jié)點(diǎn)的二叉樹中有 (B) 個(gè)度為2的結(jié)點(diǎn)。(A)8(B)9(C)10(D)112 對(duì)二叉樹的結(jié)點(diǎn)從1開始進(jìn)行連續(xù)編號(hào)，要求每個(gè)結(jié)點(diǎn)的編號(hào)大于其左右孩子的編號(hào)，同一結(jié)點(diǎn)的左右孩子中，其

4、左孩子的編號(hào)小于其右孩子的編號(hào)，則可采用_（3）次序的遍歷實(shí)現(xiàn)編號(hào)。（1）先序 （2）中序（3）后序 （4）從根開始按層遍歷3. 由2、3、4、7作為結(jié)點(diǎn)權(quán)值構(gòu)造的樹的加權(quán)路徑長度 B 。 A、33 B、30 C、36 D、40 4. 高度為6的滿二叉樹，總共有的結(jié)點(diǎn)數(shù)是 B 。 A、15 B、63 C、20 D、25 5. 下面描述根樹轉(zhuǎn)換成二叉樹的特性中，正確的是 C 。 A、根樹轉(zhuǎn)換成的二叉樹是唯一的，二叉樹的根結(jié)點(diǎn)有左、右孩子。 B、根樹轉(zhuǎn)換成的二叉樹是不唯一的，二叉樹的根結(jié)點(diǎn)只有左孩子。 C、根樹轉(zhuǎn)換成的二叉樹是唯一的，二叉樹的根結(jié)點(diǎn)只有左孩子。 D、根樹轉(zhuǎn)換成的二叉樹是不唯一的，二

5、叉樹的根結(jié)點(diǎn)有左、右孩子。6. 如圖所示的4棵二叉樹中，不是完全二叉樹的是 。 A、 B、 C、 D、 C7.某二叉樹先序遍歷的結(jié)點(diǎn)序列是abdgcefh，中序遍歷的結(jié)點(diǎn)序列是dgbaechf，則其后序遍歷的結(jié)點(diǎn)序列是 D 。 A、bdgcefha B、gdbecfha C、bdgaechf D、gdbehfca8. 已知二叉樹按中序遍歷所得到的結(jié)點(diǎn)序列為DCBGEAHFIJK， 按后序遍歷所得到的結(jié)點(diǎn)序列為DCEGBFHKJIA， 按先序遍歷所得到的結(jié)點(diǎn)序列為 ABCDGEIHFJK 。9. 設(shè)n，m為一棵二叉樹上的兩個(gè)結(jié)點(diǎn)，在中序遍歷時(shí)，n在m前的條件是 C 。 A、n在m右方 B、n是m

6、祖先 C、n在m左方 D、n是m子孫10. 二叉樹第i 層結(jié)點(diǎn)的結(jié)點(diǎn)個(gè)數(shù)最多是（設(shè)根的層數(shù)為1） ：A A）2i-1 B）2i-1 C）2i D） 2i-1 11. 樹的后根遍歷序列等同于該樹對(duì)應(yīng)的二叉樹的： B A）先序序列 B）中序序列 C）后序序列12. 樹最適合用來表示_C_。 A. 有序數(shù)據(jù)元素 B. 無序數(shù)據(jù)元素 C. 元素之間具有分支層次關(guān)系的數(shù)據(jù)D. 元素之間無聯(lián)系的數(shù)據(jù)13. 由于二叉樹中每個(gè)結(jié)點(diǎn)的度最大為2，所以二叉樹是一種特殊的樹，這種說法_B_。 A. 正確 B. 錯(cuò)誤14. 假定在一棵二叉樹中，雙分支結(jié)點(diǎn)數(shù)為15，單分支結(jié)點(diǎn)數(shù)為30個(gè)，則葉子結(jié)點(diǎn)數(shù)為B 個(gè)。 A15

7、B16 C17 D4715. 按照二叉樹的定義，具有3個(gè)結(jié)點(diǎn)的不同形狀的二叉樹有_C_種。 A. 3 B. 4 C. 5 D. 616. 深度為5的二叉樹至多有_C_個(gè)結(jié)點(diǎn)。 A. 16 B. 32 C. 31 D. 1017. 對(duì)一個(gè)滿二叉樹，m個(gè)樹葉，n個(gè)結(jié)點(diǎn)，深度為h，則_D_ 。 A. n=h+m B. h+m=2n C. m=h-1 D. n=2 h-118. 任何一棵二叉樹的葉結(jié)點(diǎn)在先序、中序和后序遍歷序列中的相對(duì)次序_A_。 A.不發(fā)生改變 B.發(fā)生改變 C.不能確定 D.以上都不對(duì)19. 如果某二叉樹的前根次序遍歷結(jié)果為stuwv，中序遍歷為uwtvs，那么該二叉樹的后序?yàn)開C

8、_。 A. uwvts B. vwuts C. wuvts D. wutsv20. 二叉樹的前序遍歷序列中，任意一個(gè)結(jié)點(diǎn)均處在其子女結(jié)點(diǎn)的前面，這種說法_A_。 A. 正確 B. 錯(cuò)誤21. 在一非空二叉樹的中序遍歷序列中，根結(jié)點(diǎn)的右邊_A_。 A. 只有右子樹上的所有結(jié)點(diǎn) B. 只有右子樹上的部分結(jié)點(diǎn) C. 只有左子樹上的部分結(jié)點(diǎn) D. 只有左子樹上的所有結(jié)點(diǎn)22. 已知某二叉樹的后序遍歷序列是dabec，中序遍歷序列是debac，它的前序遍歷序列是_D_。 A. acbed B. decab C. deabc D. cedba23. 實(shí)現(xiàn)任意二叉樹的后序遍歷的非遞歸算法而不使用棧結(jié)構(gòu)，最佳

9、方案是二叉樹采用_C_存儲(chǔ)結(jié)構(gòu)。A. 二叉鏈表B. 廣義表存儲(chǔ)結(jié)構(gòu) C. 三叉鏈表D. 順序存儲(chǔ)結(jié)構(gòu)24. 在線索化二叉樹中，t所指結(jié)點(diǎn)沒有左子樹的充要條件是_B_。 A. tleft=NULL B. tltag=1 C. tltag=1且tleft=NULL D. 以上都不對(duì)25. 二叉樹按某種順序線索化后，任一結(jié)點(diǎn)均有指向其前驅(qū)和后續(xù)的線索，這種說法_B_。 A. 正確 B. 錯(cuò)誤26. 樹的基本遍歷策略可分為先根遍歷和后根遍歷；二叉樹的基本遍歷策略可分為先序遍歷、中序遍歷和后序遍歷。這里，我們把由樹轉(zhuǎn)化得到的二叉樹叫做這棵數(shù)對(duì)應(yīng)的二叉樹。結(jié)論_A_是正確的。 A.樹的先根遍歷序列與其對(duì)應(yīng)

10、的二叉樹的先序遍歷序列相同 B.樹的后根遍歷序列與其對(duì)應(yīng)的二叉樹的后序遍歷序列相同 C.樹的先根遍歷序列與其對(duì)應(yīng)的二叉樹的中序遍歷序列相同 D.以上都不對(duì)6.42統(tǒng)計(jì)二叉樹中葉子結(jié)點(diǎn)的個(gè)數(shù)（先序遍歷）typedef struct BiTnode ElemType data; BiTnode *rchild；*lchild; BiTnode,*BiTree; Void CountLeaf（BiTree T，int &count） if（T） if（！T -Lchild） & &（ ！T -Rchild）) Count+；/計(jì)數(shù)器加1 CountLeaf（ T -Lchild，count）； Co

11、untLeaf（ T -Rchild，count）； .43交換所有結(jié)點(diǎn)的左右子樹typedef struct BiTnode ElemType data; BiTnode *rchild；*lchild; BiTnode,*BiTree; void Bitree_Revolute(Bitree T)if(T) T-lchildT-rchild; /交換左右子樹if(T-lchild) Bitree_Revolute(T-lchild);if(T-rchild) Bitree_Revolute(T-rchild); /左右子樹再分別交換各自的左右子樹/Bitree_Revolute 6-1 列

12、出右圖所示二叉樹的葉結(jié)點(diǎn)、分支結(jié)點(diǎn)和每個(gè)結(jié)點(diǎn)的層次。【解答】二叉樹的葉結(jié)點(diǎn)有、。分支結(jié)點(diǎn)有、。結(jié)點(diǎn)的層次為1；結(jié)點(diǎn)、的層次為2；結(jié)點(diǎn)、的層次為3；結(jié)點(diǎn)、的層次為4；結(jié)點(diǎn)的層次為5。6-2 使用 (1) 順序表示和 (2) 二叉鏈表表示法，分別畫出右圖所示二叉樹的存儲(chǔ)表示。0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 順序表示 二叉鏈表表示 6-3 請(qǐng)畫出右圖所示的樹所對(duì)應(yīng)的二叉樹。1【解答】12254433對(duì)應(yīng)二叉樹5766887 6-4 已知一棵二叉樹的前序遍歷的結(jié)果是ABECDFGHIJ, 中序遍歷的結(jié)果是EBCDAFHIGJ, 試畫出這棵二

13、叉樹?！窘獯稹慨?dāng)前序序列為ABECDFGHIJ，中序序列為EBCDAFHIGJ時(shí)，逐步形成二叉樹的過程如下圖所示： AAAAFBBFFBGECGECHIGJCDEFHIGJHDJHIJDIEBCD6-5給定權(quán)值集合15, 03, 14, 02, 06, 09, 16, 17, 構(gòu)造相應(yīng)的霍夫曼樹, 并計(jì)算它的帶權(quán)外部路徑長度。【解答】()05171609061415F：17160906021415020303()171609141520161415()17110911060502030605()332029020329161720()16171109151414110915050606050203020382()4933()4933172920161716292014110915110915140605060503020302此樹的帶權(quán)路徑長度WPL = 229。6-6 假定用于通信的電文僅由8個(gè)字母c1, c2, c3, c4, c5, c6, c7, c8組成, 各字母在電文中出現(xiàn)的頻率分別為5, 25, 3, 6, 10, 11, 36, 4。試為這8個(gè)字母設(shè)計(jì)不等長Huffman編碼, 并給出該電文的總碼數(shù)。【解答】已知字母集 c1, c2, c3, c4, c5, c6, c7, c8 ，頻率 5, 25, 3, 6,