數(shù)據(jù)結構樹考試習題

1、第五章 樹11 不含任何結點的空樹( ) A）是一棵樹 B）是一棵二叉樹 ）既不是樹也不是二叉樹 D）是一棵樹也是一棵二叉樹12二叉樹是非線性數(shù)據(jù)結構，所以( ) A）它不能用順序存儲結構存儲; B）它不能用鏈式存儲結構存儲; C）順序存儲結構和鏈式存儲結構都能存儲; D）順序存儲結構和鏈式存儲結構都不能使用 13把一棵樹轉(zhuǎn)換為二叉樹后，這棵二叉樹的形態(tài)是( ) A）唯一的 B）有多種 C）有多種，但根結點都沒有左孩子 D）有多種，但根結點都沒有右孩子9. 11 ， 8 ， 6 ， 2 ， 5 的葉子結點生成一棵哈夫曼樹，它的帶權路徑長度為（ ） A) 24 B) 72 C) 48 D) 53

2、 10.一棵含18個結點的二叉樹的高度至少為( )A) 3 B) 4 C) 6 D) 511.下面的二叉樹中，( C )不是完全二叉樹。 10. 設結點x和結點y是二叉樹T中的任意兩個結點，若在前序序列中x在y之前，而在中序序列中x在y之后，則x和y的關系是（ ） A）x是y的左兄弟 B）x是y的右兄弟 C）y是x的祖先 D）y是x的孩子11.設二叉樹根結點的層次為1，所有含有15個結點的二叉樹中，最小高度是（ ）A） 6 B） 5 C） 4 D） 37 下列陳述中正確的是（ ）A） 二叉樹是度為2的有序樹 B） 二叉樹中結點只有一個孩子時無左右之分C） 二叉樹中必有度為2的結點 D） 二叉樹

3、中最多只有兩棵子樹，并且有左右之分8. 樹最適合用來表示（ ）A） 有序數(shù)據(jù)元素 B） 無序數(shù)據(jù)元素 C） 元素之間具有分支層次關系的數(shù)據(jù) D） 元素之間無聯(lián)系的元素9. 3個結點有（ ）不同形態(tài)的二叉樹A） 2 B） 3 C） 4 D） 56二叉樹是非線性數(shù)據(jù)結構，( ) A）它不能用順序存儲結構存儲; B）它不能用鏈式存儲結構存儲; C）順序存儲結構和鏈式存儲結構都能存儲; D）順序存儲結構和鏈式存儲結構都不能使用 7二叉樹上葉結點數(shù)等于( )A ) 分支結點數(shù)加1 B ) 單分支結點數(shù)加1 C ) 雙分支結點數(shù)加1 D ) 雙分支結點數(shù)減18如將一棵有n個結點的完全二叉樹按順序存放方式，

4、存放在下標編號為0,1,n-1的一維數(shù)組中，設某結點下標為k(k0)，則其雙親結點的下標是( ) A ) (k-1)/2 B ) (k+1)/2 C ) k/2 D ) k-18. 樹最適合用來表示（ ）。A有序數(shù)據(jù)元素 B無序數(shù)據(jù)元素 C. 元素之間具有分支層次關系的數(shù)據(jù) D元素之間無聯(lián)系的元素10.有64個結點的完全二叉樹的深度為( ) (根的層次為第1層)。A. 8 B. 7 C. 6 D. 511.在一棵度為3的樹中，度為3的結點有2個，度為2的結點有1個，度為1的結點有個，那么，該樹有（ ）個葉子結點。A. 4 B. 5 C. 6 D. 79.一個二叉樹按順序方式存儲在一個維數(shù)組中，

5、如圖0 1 2 3 4 5 6 7 8 9 10 11 12 13 14ABCDEFGHIJ則結點E在二叉樹的第（ ）層。(假設樹根所在層為第1層)A、2 B、3 C、4 D、510. 由權值分別為 11 ， 8 ， 6 ， 2 ， 5 的葉子結點生成一棵哈夫曼樹，它的帶權路徑長度為（ ） A 24 B 71 C 48 D 538. 二叉樹上葉結點數(shù)等于（ ）。A分支結點數(shù)加1 B單分支結點數(shù)加1 C雙分支結點數(shù)加1 D雙分支結點數(shù)減18. 某二叉樹的先序序列和后序序列正好相同，則該二叉樹一定是( )的二叉樹。 A.空或只有一個結點 B.高度等于其結點數(shù) C.任一結點無左孩子 D.任一結點無右

6、孩子9. 在有n個結點的二叉鏈表中，值為空的鏈域的個數(shù)為( ) A. n-1 B. 2n-1 C. n+1 D. 2n+110. 一棵含18個結點的二叉樹的高度至少為()A. 8 B. 7 C. 6 D. 511. 深度優(yōu)先遍歷類似于二叉樹的( )A.先序遍歷 B. 中序遍歷 C. 后序遍歷 D. 層次遍歷9. 一棵124個葉結點的完全二叉樹，最多應有()個結點。A.245B.246C.247D.24810. 后綴表達式“ 5 6*3 2 + -”的值為（ ）。A.15 B.25 C.30 D.3511. 由權值分別為 11 ， 8 ， 6 ， 2 ， 5 的葉子結點生成一棵哈夫曼樹，它的帶權

7、路徑長度為（ ） A. 24 B. 71 C. 48 D. 537. 對一個滿二叉樹，m個樹葉, n個結點, 深度為為h, 則（ ）。A. n=2h-1 B.h+m=2n C.m=h-1 D. n=h+m8. 在一棵二叉樹的二叉鏈表中，空指針域數(shù)等于非空指針域數(shù)加( )。A.2 B.1 C.0 D.-19. 若完全二叉樹的結點總個數(shù)為100（結點編號從1開始編號，按層序編號），則第58個結點的度為（ ）A.2 B.1 C.0 D.不確定10. 已知完全二叉樹的第9層有240個結點，則該完全二叉樹的結點數(shù)是（）A.494 B.495 C.496 D.497二、填空題1. 一棵深度為5的二叉樹，至

8、多有_個結點。316.圖的存儲結構有_和_，遍歷圖有_、_等方法。鄰接矩陣 鄰接表 深度優(yōu)先 廣度優(yōu)先7.深度為的完全二叉樹最多有 個結點。8.若按層序?qū)ι疃葹榈耐耆鏄渲腥拷Y點從開始編號，則葉子結點可能的最小編號為 。6.設有樹如圖所示，則結點的度為_，層次為_，樹的度為_，樹的高度為_。結點的度為， 層次為， 樹的度為，高度為7.深度為的完全二叉樹至少有_個結點，最多有_個結點。，7.對于一棵具有n個結點的二叉樹，當進行鏈接存儲時，其二叉鏈表中的指針域的總數(shù)為_個，其中_個用于鏈接孩子結點，_個空閑著。2n，n-1，n+12. 后綴表達式“2 10 + 5 * 6 9 /”的值為 。6

9、3.由n個權值構成的哈夫曼樹共有 個結點。2n-16.在一棵樹中， _ 結點沒有后繼結點。葉4后綴表達式“2 10 + 5 * 6 9 /”的計算結果為 。64.一棵深度為7的二叉樹，最多有 個結點。1275.若一棵樹的括號表示為A(B,C(E,F(G),D),該樹的葉子結點個數(shù)為_ ，該樹的度為_ ，該樹的深度為_。4、3、46.在有n個葉子結點的哈夫曼樹中，總結點數(shù)是_。2n-11. 深度為4的完全二叉樹最少有_個結點，最多有_個結點。8156. 假定一棵樹的廣義表表示為A(B(C(D,E),F,G(H,I,J),K)，則度為3、2、1、0的結點數(shù)分別為_、_、_和_個。22076. 若結

10、點A有其他三個兄弟,B是A的雙親結點,B的度是_。47. 一棵二叉樹有67個結點，這些結點的度要么是0，要么是2。這棵二叉樹中度為2的結點有_個。338. 一棵深度為7的二叉樹，最多有 個結點。127三、應用題1、名詞解釋：樹，子樹，結點的度，葉子結點，孩子，雙親，兄弟，深度，有序樹，森林，二叉樹，遍歷二叉樹，樹的帶權路徑長度，哈夫曼樹。2、描述二叉樹的性質(zhì)。3、從概念上講，樹、森林和二叉樹是三種不同的數(shù)據(jù)結構，將樹、森林轉(zhuǎn)換為二叉樹的基本目的是什么？指出樹和二叉樹的主要區(qū)別。4、已知一棵樹邊的結點為,，試畫出這棵樹,并回答下列問題：（1）哪個是根結點？（2）哪些是葉子結點？（3）哪個是結點G

11、的雙親？（4）哪些是結點G的祖先？（5）哪些是結點G的孩子？（6）哪些是結點E的子孫？（7）哪些是結點E的兄弟？哪些是結點F的兄弟？（8）結點B和N的層次號分別是什么？（9）樹的深度是多少？5、試分別畫出具有3個結點的樹和3個結點的二叉樹的所有不同形態(tài)。6、已知一棵度為k的樹中有n1個度為1的結點，n2個度為2的結點，nk個度為k 的結點，問該樹中有多少個葉子結點？7、已知在一棵含有n 個結點的樹中，只有度為k 的分支結點和度為0的葉子結點。試求該樹含有的葉子結點的數(shù)目。8、有n個結點的二叉樹，已知葉子結點個數(shù)為n0，寫出求度為1的結點的個數(shù)n1的計算公式；若此樹是深度為k的完全二叉樹，寫出n

12、為最小的公式；若二叉樹中僅有度為0和度為2的結點，寫出求該二叉樹結點個數(shù)n的公式。9、假設n 和m 為二叉樹中兩結點，用“1”，“0”或“”（分別表示肯定、恰恰相反或者不一定）填寫下表：前序遍歷時n在m前?中序遍歷時n在m前?后序遍歷時n在m前?n在m左方n在m右方n是m祖先n是m子孫注：如果（1）離a 和b最近的共同祖先p存在，且（2）a在p的左子樹中，b在p的右子樹中，則稱a在b的左方（即b在a的右方）。10、找出所有滿足下列條件的二叉樹：（a）它們在先序遍歷和中序遍歷時，得到的結點訪問序列相同；（b）它們在后序遍歷和中序遍歷時，得到的結點訪問序列相同；（c）它們在先序遍歷和后序遍歷時，得

13、到的結點訪問序列相同；11、分別畫出和下列樹對應的各個二叉樹：12、畫出和下列二叉樹相應的森林：13、畫出和下列已知序列對應的樹T：樹的先根次序訪問序列為GFKDAIEBCHJ；樹的后根次序訪問序列為CBEFDGAJIKLH。14、假設一棵二叉樹的中序序列為DCBGEAHFIJK和后序序列為DCEGBFHKJIA。請畫出該樹。15、假設一棵二叉樹的層序序列為ABCDEFGHIJ和中序序列為DBGEHJACIF。請畫出該樹。16、編寫遞歸算法，在二叉樹中求位于先序序列中第k個位置的結點的值。17、編寫遞歸算法，計算二叉樹中葉子結點的數(shù)目。5. 用于通信的電文僅由a、b、c、d、e、f、g、h等8

14、個字母組成，字母在電文中出現(xiàn)的頻率分別為：007、0.19、0.02、0.06、0.32、0.03、0.21、0.10。試構造相應的哈夫曼樹并為這些字母設計哈夫曼編碼。（9分）得到的編碼如下 ： a:0010 b:10 c:00000 d:0001 e:01 f:00001 g:11 h:0011 此題答案不唯一。5. 設先序遍歷某個樹的結點次序為ABDEHCFGI，中序遍歷該樹的結點次序為DBEHAFCIG,要求畫出這個二叉樹，并寫出此二叉樹的后序遍歷。（10分）后序：DHFBFIGCA6. 給定一組權值（5，9，11，2，7，16），試設計相應的哈夫曼樹，并計算帶權路徑長度. （9分）答案

15、：50 92030111614 7 7 2 5帶權路徑長度=（9+11+16）*2+7*3+（2+5）*4=1211.已知一組關鍵字為25,18,46,2,53,39,32,4,74,67,60,11。按表中的元素順序依次插入到一棵初始為空的二叉排序樹中,畫出該二叉排序樹,并求在等概率的情況下查找成功的平均查找長度。（10分）答案：1設先序遍歷某個樹的結點次序為ABDEHCFGI，中序遍歷該樹的結點次序為DBEHAFCIG,要求畫出這個二叉樹,并寫出該樹的后序遍歷的結點次序。(6分)ABCDEFGHI1. .后序:DHEBFIGCA1已知一棵樹二叉如下，請寫出按前序、中序、后序和層次遍歷時得到

16、的結點序列。（8分）AB CD E FG H前序：中序：后序：層次：各遍歷次序如下前序：，中序：，后序：，層次：，4. 已知一棵完全二叉樹共有999個結點，試求：(寫出詳細的分析過程) （9分）1、樹的高度（深度） 2、葉子結點的數(shù)目3、度為1的結點數(shù)目深度：10 葉子節(jié)點數(shù)目：500 度為1的節(jié)點數(shù)目：01.試寫出如圖所示的二叉樹分別按先序、中序、后序遍歷時得到的結點序列。答：DLR：A B D F J G K C E H I L MLDR: B F J D G K A C H E L I MLRD：J F K G D B H L M I E C A.請將下圖所示的森林森林轉(zhuǎn)換為所對應的二叉

17、樹。ABDEFCGHJIKNOMLBGDCHKEIFJLMNOA圖5-164將關鍵碼53，78，65，17，87，09，81，45，23依次插入到一棵初始為空的二叉搜索樹中，畫出每插入一個關鍵碼后的二叉搜索樹。答案53785365785353786517537865178753786517870953786517870981455378651787098145231.已知一棵二叉樹的中序遍歷序列為： dfebagc，先序遍歷序列為：abdefcg，請畫出這棵二叉樹 2.設用于通信的電文由個字母組成，字母在電文中出現(xiàn)的頻率分別為0.16、0.38、0.01、0.06、0.24、0.11、0.04

18、，試為這個字母設計赫夫曼編碼。赫夫曼樹：赫夫曼編碼：（0.15）：（0.39）：（0.01）：（0.06）：（0.24）：（0.11）：（0.04）：1. 已知用一維數(shù)組存放的一棵完全二叉樹：ABCDEFGHIJKL，寫出該二叉樹的先序、中序和后序遍歷序列。先序序列：ABDHIEJKCFLG中序序列：HDIBJEKALFCG后序序列：HIDJKEBLFGCA50 92030111614 7 7 2 52. 給定一組權值（5，9，11，2，7，16），試設計相應的哈夫曼樹，并計算WPL.答案：wpl=（9+11+16）*2+7*3+（2+5）*4=1211.已知某二叉樹的前序序列為EBADCFH

19、GI，中序序列為ABCDEFGHI，請給出二叉樹的后序列。答案：后序序列:ACDBGIHFE2在一份電文中共使用五種字符：A，G，F(xiàn)，U，Y，Z，它們的出現(xiàn)頻率依次為12,9,18,7,14，11，求出每個字符的哈夫曼編碼。 71 0 130 41 0 1 0 1 16 Y(14) 23 F(18) 0 1 0 1 G(9) U(7) A(12) Z(11) 哈夫曼樹A：100 G：000 F：11U：001 Y：01 Z：101（或0、1 相反） （8分）注意：答案不唯一。3. 已知一棵完全二叉樹共有1001個結點，試求：(寫出詳細的分析過程) （9分）1、樹的高度（深度） 2、葉子結點的數(shù)

20、目3、度為1的結點數(shù)目深度：10 葉子節(jié)點數(shù)目：501 度為1的節(jié)點數(shù)目：04. 試給下圖所示二叉樹的前序、中序和后序遍歷序列。若一棵二叉樹的前序遍歷序列為：A B D E G C F，中序遍歷序列為：D B E G A C F，試畫出此二叉樹。（10分）前序：ABDEGHCF中序：DBGEHAFC后序：DGHEBFCA5. 一組密文原碼由字符A, B, C, D, E, F, G組成，其出現(xiàn)的頻率分別是9, 11, 5, 7, 8, 2, 3，設計相應的哈夫曼樹并對7個字符編碼。（8分）哈夫曼樹略。編碼方案：A：00 B：10 C：010 D：110 E：111 F：0110 G：0111（

21、此題答案不唯一）四、綜合題2. 在二叉樹的鏈式存儲結構中，結點類型定義如下：typedef struct node ElemType data; struct node *lchild,*rchild; BTNode;以下算法是計算二叉數(shù)深度的遞歸算法，試補充完整。int BtreeDepth (BTreeNode *BT) /BT是根結點 if (BT=NULL) return 0；elseint dep1,dep2； /dep1、dep2分別為根結點左子樹、右子樹高度dep1= ；dep2= ；if (dep1dep2) return ；elsereturn ；2. BtreeDepth（

22、BT-lchild）BtreeDepth（BT-rchild）dep1+1dep2+12.編寫算法求二叉樹的深度（高度）。2. int BTNodeDepth(BTNode *b)/求二叉樹b的深度 int lchilddep,rchilddep; if (b=NULL) return(0); /空樹的高度為0 else lchilddep=BTNodeDepth(b-lchild);/求左子樹的高度為lchilddep rchilddep=BTNodeDepth(b-rchild);/求右子樹的高度為rchilddepreturn (lchilddeprchilddep)? (lchildd

23、ep+1):(rchilddep+1); 1.二叉樹中結點定義如下，試編寫算法，求二叉樹中結點的個數(shù)。typedef struct nodeElemType data;/數(shù)據(jù)元素struct node *lchild;/指向左孩子struct node *rchild;/指向右孩子 BTNode;int Nodes(BTNode *b)/求二叉樹b的結點個數(shù)int num1,num2;if (b=NULL)return 0; else if (b-lchild=NULL & b-rchild=NULL) return 1; else num1=Nodes(b-lchild); num2=Nodes(b-rchild); return (num1+num2+1);2.