數(shù)據(jù)結(jié)構(gòu)練習(xí)樹

1、數(shù)據(jù)結(jié)構(gòu)練習(xí)第六章 樹一、選擇題1 . 樹最適合用來表示（）。A. 有序數(shù)據(jù)元素B.無序數(shù)據(jù)元素C.元素之間具有分支層次關(guān)系的數(shù)據(jù)D.元素之間無聯(lián)系的數(shù)據(jù)2 . 二叉樹的第k 層的結(jié)點數(shù)最多為（ ）.A 2k-1B.2K+1C.2K-1D. 2 k-13 .設(shè)哈夫曼樹中的葉子結(jié)點總數(shù)為m若用二叉鏈表作為存儲結(jié)構(gòu)，則該哈夫曼樹中總共有（）個空指針域。A. 2m-1B. 2mC. 2m+1D. 4m4 設(shè)某棵二叉樹的中序遍歷序列為ABCD， 前序遍歷序列為CABD， 則后序遍歷該二叉樹得到序列為（） 。A. BADC B. BCDAC. CDABD. CBDA5 . 設(shè)某棵二叉樹中有2000 個結(jié)

2、點，則該二叉樹的最小高度為（） 。A. 9B. 10C. 11 D. 126 .設(shè)一棵二叉樹的深度為k,則該二叉樹中最多有（）個結(jié)點。A. 2k-1B .2 kC. 2k-1D. 2 k-17 .設(shè)某二叉樹中度數(shù)為0的結(jié)點數(shù)為N）,度數(shù)為1的結(jié)點數(shù)為N,度數(shù)為2的 結(jié)點數(shù)為N,則下列等式成立的是（）。A. N 0=N1+1B. N0=Nl+N2C. N0=N2+1D. N 0=2N1+l8 .設(shè)一棵m叉樹中度數(shù)為0的結(jié)點數(shù)為N）,度數(shù)為1的結(jié)點數(shù)為N,，度 數(shù)為m的結(jié)點數(shù)為Nm則Nd=（）。A. N1+N+Nm B. l+N 2+2N+3N+（m-1）NmC. N2+2N+3N+（m-1）Nm

3、D. 2N1+3N+（m+1）Nm9設(shè)一組權(quán)值集合W=2， 3， 4， 5， 6，則由該權(quán)值集合構(gòu)造的哈夫曼樹中帶權(quán)路徑長度之和為（） 。A. 20 B. 30C. 40D. 4510 設(shè)二叉樹的先序遍歷序列和后序遍歷序列正好相反，則該二叉樹滿足的條件是（ ） 。A. 空或只有一個結(jié)點B. 高度等于其結(jié)點數(shù)C. 任一結(jié)點無左孩子D. 任一結(jié)點無右孩子11設(shè)某棵三叉樹中有40 個結(jié)點，則該三叉樹的最小高度為（） 。A. 3B. 4C. 5D. 612深度為k 的完全二叉樹中最少有（）個結(jié)點。A. 2 k-1-1 B. 2 k-1 C. 2k-1+1 D. 2k-113設(shè)某哈夫曼樹中有199 個結(jié)

4、點，則該哈夫曼樹中有（）個葉子結(jié)點。A. 99B. 100 C. 101 D. 10214 設(shè)按照從上到下、從左到右的順序從1 開始對完全二叉樹進行順序編號，則編號為 i 結(jié)點的左孩子結(jié)點的編號為（） 。A. 2i+1B. 2i C. i/2D. 2i-115設(shè)某棵二叉樹的高度為10，則該二叉樹上葉子結(jié)點最多有（） 。A. 20 B. 256C. 512 D. 102416設(shè)一棵完全二叉樹中有65 個結(jié)點，則該完全二叉樹的深度為（A. 8B. 7C. 6D. 517設(shè)一棵三叉樹中有2 個度數(shù)為1 的結(jié)點，2 個度數(shù)為2 的結(jié)點， 2 個度數(shù)為3 的結(jié)點，則該三叉鏈權(quán)中有（）個度數(shù)為0 的結(jié)點。

5、A. 5B. 6C. 7D. 818 .設(shè)無向圖 G 中的邊的集合 E=（a , b） , （a, e） , （a, c） , （b , e）, （e , d）,（d ， f） ， （f ， c） ，則從頂點a 出發(fā)進行深度優(yōu)先遍歷可以得到的一種頂點序列為（ ） 。A. aedfcb B. acfebd C. aebcfdD.aedfbc19 .設(shè)F是由T1、T2和T3三棵樹組成的森林，與F對應(yīng)的二叉樹為B, T1、T2 和T3的結(jié)點數(shù)分別為N1、N2和N3,則二叉樹B的根結(jié)點的左子樹的結(jié)點數(shù)為 （）。A. N1-1 B. N2-1C. N2+N3D. N1+N320 設(shè)在一棵度數(shù)為3 的樹中

6、， 度數(shù)為 3 的結(jié)點數(shù)有2 個， 度數(shù)為 2 的結(jié)點數(shù)有1 個，度數(shù)為1 的結(jié)點數(shù)有2 個，那么度數(shù)為0 的結(jié)點數(shù)有（）個。A. 4 B. 5C. 6D. 721.設(shè)一棵m叉樹中有N個度數(shù)為1的結(jié)點，N個度數(shù)為2的結(jié)點，Nm 個度數(shù)為m的結(jié)點，則該樹中共有（）個葉子結(jié)點。mmmmA. （i 1）Ni B.NiC.NiD. 1 （i 1）Nii1i1i2i222設(shè)一組權(quán)值集合W=（15， 3， 14， 2， 6， 9， 16， 17），要求根據(jù)這些權(quán)值集合構(gòu)造一棵哈夫曼樹，則這棵哈夫曼樹的帶權(quán)路徑長度為（） 。A.129 B. 219C. 189D. 22923設(shè)某棵二叉樹中只有度數(shù)為0 和度

7、數(shù)為2 的結(jié)點且度數(shù)為0 的結(jié)點數(shù)為n，則這棵二叉中共有（）個結(jié)點。A. 2n B. n+lC. 2n-1D. 2n+l24 由權(quán)值分別為3,6,7,2,5 的葉子結(jié)點生成一棵哈夫曼樹，它的帶權(quán)路徑長度為（ ） 。A 51B 23 C 53D 7425在一棵二叉樹中，第4 層上的結(jié)點數(shù)最多為（） 。A 31B 8C 15 D 1626二叉樹上葉結(jié)點數(shù)等于（） 。A.分支結(jié)點數(shù)加1 B .單分支結(jié)點數(shù)加1C.雙分支2點數(shù)加1 D .雙分支結(jié)點數(shù)減127 .對某二叉樹進行前序遍歷的結(jié)果為 ABDEFC中序遍歷的結(jié)果為DBFEAC則后序周游的結(jié)果為（）A DBFEACB DFEBCAC BDFECA

8、D BDEFAC28 將含 100 個結(jié)點的完全二叉樹從根這一層開始，每層上從左到右依次對結(jié)點編號，根結(jié)點的編號為1 o編號為49的結(jié)點X的雙殺編號為（）A 24 B. 25C.23D.無法確定29含有n 個結(jié)點的二叉樹采用二叉鏈表存儲時，空指針域的個數(shù)為（）A.n-1 B.nC.n+1D.n+230在一棵深度為H 的完全二叉樹中，所含結(jié)點的個數(shù)不少于（）A.2 H-1-1H-1B.2C.2H-1D.231 .某二叉樹的先根遍歷序列和后根遍歷序列正好相反，則該二叉樹具有的特征 是（）A.高度等于其結(jié)點數(shù)B.任一結(jié)點無左孩子C.任一結(jié)點無右孩子D.空或只有一個結(jié)點32 .在完全二叉樹中，若一個結(jié)

9、點是葉結(jié)點，則它沒有 （）A.左孩子結(jié)點B.C.左孩子結(jié)點和右孩子結(jié)點 結(jié)點33.除根結(jié)點外，樹上每個結(jié)點（A.可有任意多個孩子、一個雙親 C.可有一個孩子、任意多個雙親 34.題9圖中樹的度為（）右孩子結(jié)點D.左孩子結(jié)點，右孩子結(jié)點和兄弟）B.可有任意多個孩子、任意多個雙親D.只有一個孩子、一個雙親A.2B.3C.5D.835 .高度為h的完全二叉樹中，結(jié)點數(shù)最多為（）A. 2h-1B.2h+1C.2h-1D.2 h36 .由m棵結(jié)點數(shù)為n的樹組成的森林，將其轉(zhuǎn)化為一棵二叉樹，則該二叉樹中根結(jié)點的右子樹上具有的結(jié)點個數(shù)是（）A. mnB.mn-1 C.n（m-1）D.m（n-1）37 .含有

10、10個結(jié)點的二叉樹中，度為 0的結(jié)點數(shù)為4,則度為2的結(jié)點數(shù)為A.3B.4C.5D.638 .對一棵有100個結(jié)點的完全二叉樹按層編號，則編號為49的結(jié)點，它的父結(jié)點的編號為（）A.24B.25C.98D.9939 .可以惟一地轉(zhuǎn)化成一棵一般樹的二叉樹的特點是（）A.根結(jié)點無左孩子B.根結(jié)點無右孩子C.根結(jié)點有兩個孩子D.根結(jié)點沒有孩子40 .關(guān)于二叉樹性質(zhì)的描述，正確的是（）A.二叉樹結(jié)點的個數(shù)可以為0B.二叉樹至少含有一個根結(jié)點C.二叉樹若存在兩個結(jié)點，則必有一個為根，另一個為左孩子D.二叉樹若存在三個結(jié)點，則必有一個為根，另兩個分別為左、右孩子41 .具有4個結(jié)點的二叉樹可有（）A.4種

11、形態(tài)B.7種形態(tài)C.10種形態(tài) D.11 種形態(tài)42 . 一棵有16結(jié)點的完全二叉樹，對它按層編號，則對編號為7的結(jié)點X,它的雙親結(jié)點及右孩子結(jié)點的編號分別為（）A. 2, 14B. 2, 15C. 3, 14D. 3, 1543具有2000 個結(jié)點的二叉樹，其高度至少為(A 9B 10C 11D 1244 .如果結(jié)點A有3個兄弟，而且B為A的雙親，則B是度為()A 3B 4C 5D 145 .二叉樹第i(i >1)層最多有()個結(jié)點。A 2i B 2iC 2i-1D 2i -146 .如果樹的結(jié)點有4個兄弟，而且B為A的雙親，則B的度為()A 3 B 4C 5D 147設(shè)一棵二叉樹共有

12、20 個度為 2 的結(jié)點，則葉子結(jié)點共有()個。A 40B 19 C 20D 2148一棵完全二叉樹中根結(jié)點的編號為1，而且23 號結(jié)點有左孩子但沒有右孩子，則完全二叉樹共有()個結(jié)點。A 24 B 45C 46D 4749一棵深度為k 的滿二叉樹有()個結(jié)點。A 2k -1 B 2k-1C 2k D 2k50 一棵完全二叉樹的結(jié)點按層次遍歷從1開始編號，如果編號為m的結(jié)點有雙親，則雙親的編號為() 。A. 2XmB. m/2C m 1D m-151 由權(quán)值分別為3,8,6,2,5 的葉子結(jié)點生成一棵哈夫曼樹，它的帶權(quán)路徑長度為( ) 。A、 24 B 、 48 C 、 72D、5352從二叉

13、搜索樹中查找一個元素時，其時間復(fù)雜度大致為() 。2A O(n) B O(1)C O(log 2n)D O(n 2)53向二叉搜索樹中插入一個元素時，其時間復(fù)雜度大致為() 。A O(1)BO(log 2n ) C O(n) D O(nlog2n)54根據(jù)n 個元素建立一棵二叉搜索樹時，其時間復(fù)雜度大致為() 。A O(n) B O(log 2n )C O(n2)DO(nlog2n)55從堆中刪除一個元素的時間復(fù)雜度為() 。A O(1) B O(n)C O(log 2n)D O( nlog 2n)56向堆中插入一個元素的時間復(fù)雜度為() 。A O(log 2n)B 、 O(n) C 、 O(

14、1) D 、 O( nlog 2n)57 由權(quán)值分別為3,8,6,2,5 的葉子結(jié)點生成一棵哈夫曼樹，它的帶權(quán)路徑長度為( ) 。A 24 B 48 C 72D 5358由權(quán)值分別為11， 8， 6， 2， 5的葉子結(jié)點生成一棵哈夫曼樹，它的帶權(quán)路徑長度為()A24 B 71 C 48 D 5359設(shè)F 是一個森林，B 是由F 轉(zhuǎn)換得到的二叉樹，F(xiàn) 中有 n 個非葉結(jié)點，則B中右指針域為空的結(jié)點有()個。A n-1B nC n+1D n+260具有65 個結(jié)點的完全二叉樹的高度為() 。 (根的層次號為0)A 8B 7C 6D 561有關(guān)二叉樹下列說法正確的是（B ）A.二叉樹的度為2 B .

15、 一棵二叉樹的度可以小于 2C.二叉樹中至少有一個結(jié)點的度為 2 D .二叉樹中任何一個結(jié)點的度都為262.設(shè)樹T的度為4,其中度為1,2,3和4的結(jié)點個數(shù)分別為4,2,1,1,則T中的葉子數(shù)為（D ）。A 5 B 6 C 7 D 863已知一算術(shù)表達式的中綴表達式為a-（b+c/d）*e ，其后綴形式為（ D） 。A. - a+b*c/d B. - a+b*cd/e C. -+*abc/de D. abcd/+e*-64.設(shè)森林F對應(yīng)的二叉樹為B,它有m個結(jié)點，B的根為p,p的右子樹結(jié)點個數(shù)為n,森林F中第一棵樹的結(jié)點個數(shù)是（A ）A m-n B m-n-1 C n+1 D 條件不足，無法確

16、定65若一棵二叉樹具有10 個度為 2 的結(jié)點， 5 個度為 1 的結(jié)點，則度為0 的結(jié)點個數(shù)是（B ）A 9 B 11 C 15 D 不確定66在一棵三元樹中度為3 的結(jié)點數(shù)為2 個，度為2 的結(jié)點數(shù)為1 個，度為1的結(jié)點數(shù)為2 個，則度為0 的結(jié)點數(shù)為（C ）個。A 4 B 5C 6 D 767.設(shè)森林F中有三棵樹，第一，第二，第三棵樹的結(jié)點個數(shù)分別為M1, M2和M3與森林F對應(yīng)的二叉樹根結(jié)點的右子樹上的結(jié)點個數(shù)是（ D ）。A M1 B M1+M2 C M3 D M2+M368已知一棵完全二叉樹中共有626 個結(jié)點，葉子結(jié)點的個數(shù)應(yīng)為（ C ） 。A. 311 B. 312 C. 31

17、3 D. 314 E.其它69有關(guān)二叉樹下列說法正確的是（B ）A.二叉樹的度為2B. 一棵二叉樹的度可以小于 2C.二叉樹中至少有一個結(jié)點的度為2 D .二叉樹中任何一個結(jié)點的度都為 270二叉樹的第I 層上最多含有結(jié)點數(shù)為（C）A 2I B 2 I-1 -1 C 2 I-1 D 2I -171一個具有1025 個結(jié)點的二叉樹的高h 為（ C ）A 11 B 10 C 11 至 1025之間 D 10 至 1024之間72在一棵高度為k 的滿二叉樹中，結(jié)點總數(shù)為（C ）A 2k-1B 2kC 2k-1D log2 k +173有n（ n> 0）個分枝結(jié)點的滿二叉樹的深度是（C ） 。A

18、.n2-1B. log 2（n+1）+1C.log 2（n+1）D. log 2（n-1）74 對二叉樹的結(jié)點從1 開始進行連續(xù)編號，要求每個結(jié)點的編號大于其左、右孩子的編號，同一結(jié)點的左右孩子中，其左孩子的編號小于其右孩子的編號，可采用 （ C） 次序的遍歷實現(xiàn)編號。A.先序B. 中序 C. 后序 D.從根開始按層次遍歷75樹的后根遍歷序列等同于該樹對應(yīng)的二叉樹的（ B ）A. 先序序列B. 中序序列C. 后序序列76在下列存儲形式中，哪一個不是樹的存儲形式？（D ）A.雙親表示法B .孩子鏈表表示法C.孩子兄弟表示法D .順序存儲表示法 77高度為h（h>0） 的滿二叉樹對應(yīng)的森林由

19、（ D ） 棵樹構(gòu)成。A. 1 B. log2 h C. h/2 D. h78 .某二叉樹結(jié)點的中序序列為 BDAEC市序序列為DBEFCA,U該二叉樹對應(yīng)的 森林包括(C) 棵樹。A.1B.2C.3D.479 .二叉樹的先序遍歷和中序遍歷如下：先序遍歷：EFHIGJK中序遍歷:HFIEJKG。該二叉樹根的右子樹的根是：CA. E B. FC. GD. H80 .將一棵樹t轉(zhuǎn)換為孩子一兄弟鏈表表示的二叉樹 h,則t的后根序遍歷是h 的( B )A.前序遍歷 B .中序遍歷C .后序遍歷81 對任意一棵樹，設(shè)它有n 個結(jié)點，這n 個結(jié)點的度數(shù)之和為( C ) 。A.n B.n-2C.n-1D.n

20、+182一棵非空的二叉樹的先序序列和后序序列正好相反，則該二叉樹一定滿足( C) 。A.其中任意一個結(jié)點均無左孩子B.其中任意一個結(jié)點均無右孩子C.其中只有一個葉子結(jié)點D. 其中度為2的結(jié)點最多為一個83 在二叉樹結(jié)點的先序序列，中序序列和后序序列中，所有葉子結(jié)點的先后順序( B )A.都不相同B.完全相同C.先序和中序相同，而與后序不同 D.中序和后序相同，而與先序不同84某二叉樹的先序序列和后序序列正好相反，則該二叉樹一定是( B ) 的二叉樹A.空或只有一個結(jié)點B.高度等于其結(jié)點數(shù)C.任一結(jié)點無左孩子D.任一結(jié)點無右孩子85在完全二叉樹中，若一個結(jié)點是葉結(jié)點，則它沒( C ) 。A.左子

21、結(jié)點B .右子結(jié)點C.左子結(jié)點和右子結(jié)點D .左子結(jié)點，右子結(jié)點和兄弟結(jié)點86二叉樹在線索化后，仍不能有效求解的問題是(D)。A. 先序線索二叉樹中求先序后繼B. 中序線索二叉樹中求中序后繼C.中序線索二叉樹中求中序前驅(qū) D.后序線索二叉樹中求后序后繼87由3 個結(jié)點可以構(gòu)造出多少種不同的有向樹？(A )A 2B 3C 4 D 588 下述二叉樹中, 哪一種滿足性質(zhì): 從任一結(jié)點出發(fā)到根的路徑上所經(jīng)過的結(jié)點序列按其關(guān)鍵字有序(D)。A.二叉排序樹B .哈夫曼樹C . AVL樹D .堆89一棵Huffman 樹共有215個結(jié)點，對其進行Huffman 編碼，共能得到(B )個不同的碼字； A.

22、107 B. 108C. 214 D. 21590下述編碼中哪一個不是前綴碼(B )。A.(00,01,10,11)B.(0,1,00,11)C.(0,10,110,111)D.(1,01,000,001)91.設(shè)X是樹T中的一個非根結(jié)點，B是T所對應(yīng)的二叉樹。在B中，X是其雙 親的右孩子，下列結(jié)論正確的是( D) 。A.在樹T中，X是其雙親的第一個孩子B. 在樹T中，X 一定無右邊兄弟C.在樹T中，X 一定是葉子結(jié)點D. 在樹T中，X 一定有左邊兄弟92一顆完全二叉樹上有1001 個結(jié)點，其中葉子結(jié)點的個數(shù)是(B )A250B 501C254D50093一顆有124 個葉結(jié)點的完全二叉樹，最

23、多有（B ）個結(jié)點A247B 248C249D25194一棵具有n 個結(jié)點的完全二叉樹的樹高度（深度）是（A ）A logn +1 B logn+1 C logn D logn-195已知某二叉樹的后序遍歷序列是dabec, 中序遍歷序列是debac , 它的前序遍歷是（D ） 。A acbed B decab C deabc D cedba96二叉樹的第I 層上最多含有結(jié)點數(shù)為（C）A 2IB 2 I-1 -1 C 2 I-1 D 2I -1二、填空題1假定一棵樹的廣義表表示為A（C，D（E，F(xiàn)，G），H（I ，J） ，則樹中所含的結(jié)點數(shù)為 個，樹的深度為 ，樹的度為 。 9 ， 3 ， 3

24、2若用鏈表存儲一棵二叉樹時，每個結(jié)點除數(shù)據(jù)域外，還有指向左孩子和右孩子的兩個指針。在這種存儲結(jié)構(gòu)中，n 個結(jié)點的二叉樹共有個指針域，其中有 個指針域是存放了地址，有 個指針是空指針。2n ， n-1 ，n+13 . 中序遍歷二叉排序樹所得到的序列是序列（填有序或無序） 。 有序4 .設(shè)某棵二叉樹中度數(shù)為0的結(jié)點數(shù)為N0,度數(shù)為1的結(jié)點數(shù)為N1,則該二叉樹中度數(shù)為2 的結(jié)點數(shù)為； 若采用二叉鏈表作為該二叉樹的存儲結(jié)構(gòu)，則該二叉樹中共有個空指針域。N0-1 ， 2N0+N15設(shè)一棵完全二叉樹中有500 個結(jié)點，則該二叉樹的深度為；若用二叉鏈表作為該完全二叉樹的存儲結(jié)構(gòu)，則共有 個空指針域。9， 5

25、016 設(shè)哈夫曼樹中共有n 個結(jié)點， 則該哈夫曼樹中有個度數(shù)為 1 的結(jié)點。07 遍歷二叉排序樹中的結(jié)點可以得到一個遞增的關(guān)鍵字序列 （填先序、中序或后序）。中序8設(shè)有n 個結(jié)點的完全二叉樹，如果按照從自上到下、從左到右從1 開始順序編號，則第i個結(jié)點的雙親結(jié)點編號為，右孩子結(jié)點的編號為。i/2， 2i+19深度為k 的完全二叉樹中最少有個結(jié)點。2k-110 設(shè)哈夫曼樹中共有99個結(jié)點， 則該樹中有個葉子結(jié)點； 若采用二叉鏈表作為存儲結(jié)構(gòu)，則該樹中有個空指針域。50， 5111 .設(shè)前序遍歷某二叉樹的序列為 ABCD中序遍歷該二叉樹的序列為 BADC則后序遍歷該二叉樹的序列為。 BDCA12

26、.設(shè)一棵完全二叉樹的順序存儲結(jié)構(gòu)中存儲數(shù)據(jù)元素為ABCDEF則該二叉樹的前序遍歷序列為， 中序遍歷序列為， 后序遍歷序列為。 ABDEC，F(xiàn) DBEAF，C DEBFCA13設(shè)一棵完全二叉樹有128 個結(jié)點，則該完全二叉樹的深度為，有個葉子結(jié)點。8， 64141516 設(shè)一棵m叉樹脂的結(jié)點數(shù)為n,用多重鏈表表示其存儲結(jié)構(gòu)，則該樹中有個空指針域。 n(m-1)+117下面程序段的功能是建立二叉樹的算法，請在下劃線處填上正確的內(nèi)容。typedefstructnodeintdata;structnode*lchild;bitree;void createbitree(bitree *&bt)

27、scanf( “ %c” ,& ch);if(ch='#') ;elsebt=(bitree*)malloc(sizeof(bitree);bt->data=ch;createbitree(bt->rchild); struct node *rchild ， bt=0 ， createbitree(bt->lchild)18 設(shè)某棵完全二叉樹中有100 個結(jié)點， 則該二叉樹中有個葉子結(jié)點。 5019 .設(shè)一棵二叉樹的中序遍歷序列為BDCA后序遍歷序列為DBAC則這棵二叉樹的前序序列為。 CBDA20設(shè)用于通信的電文僅由8 個字母組成，字母在電文中出現(xiàn)的

28、頻率分別為7、20 、 2、 6、 32、 3、 21、 10，根據(jù)這些頻率作為權(quán)值構(gòu)造哈夫曼樹，則這棵哈夫曼樹的高度為。 621 .設(shè)某棵二叉樹的中序遍歷序列為ABCD后序遍歷序列為BADC則其前序遍歷序列為 。 CABD22 完全二叉樹中第5 層上最少有個結(jié)點， 最多有 個結(jié)點。1， 1623設(shè)一棵三叉樹中有50 個度數(shù)為0 的結(jié)點， 21 個度數(shù)為2 的結(jié)點，則該二叉樹中度數(shù)為3 的結(jié)點數(shù)有個。 1424高度為h 的完全二叉樹中最少有個結(jié)點，最多有 個結(jié)點。2h-1， 2h-125.設(shè)一棵二叉樹的前序序列為 ABC則有種不同的二叉樹可以得到這種序列。526設(shè)二叉樹中度數(shù)為0 的結(jié)點數(shù)為5

29、0，度數(shù)為1 的結(jié)點數(shù)為30，則該二叉樹中總共有個結(jié)點數(shù)。12927設(shè)二叉樹中結(jié)點的兩個指針域分別為lchild 和 rchild ，則判斷指針變量p所指向的結(jié)點為葉子結(jié)點的條件是p->lchild=0&&p->rchild=028若對一棵二叉樹的結(jié)點編號從0 開始順序編碼，按順序存儲，把編號為0的結(jié)點存儲到a0 中，其余類推，則ai 元素的左孩子元素為，右孩子元素為，雙親元素 (i>0) 為 。 2i+1 、 2i+2、 (i -1)/229假定一棵樹的廣義表表示為A(B(C(D,E),F,G(H,I,J),K) ，則度為3、 2、 1、0 的結(jié)點數(shù)分別為、

30、 、 和 個。2、 2、 0、 73031假定一棵二叉樹廣義表表示為a(b(c,d) ， e(,f) ，則對它進行的先序遍歷結(jié) 果 為 ， 中 序 遍 歷 結(jié) 果 為 ， 后 序 遍 歷 結(jié) 果 為, 按層遍歷結(jié)果為 a b c d e f , c b d a e f , c d b f e a , a b e c d f32 .在一棵高度為h的3叉樹中，最多含有 結(jié)點。(3 h-1)/233 .假定一棵二叉樹的結(jié)點數(shù)為 18,則它的最小深度為 ,最大深度為。 5,1834 .在一棵二叉搜索樹中，每個分支結(jié)點的左子樹上所有的結(jié)點的值一定 該結(jié)點的值，右子樹上所有結(jié)點的值一定 該結(jié)點的值。小于，

31、大于35 .對一棵深度為10的滿二叉樹按層編號，則編號為51的結(jié)點，它的雙親結(jié)點 編號為 25。36 .具有n個葉子結(jié)點的哈夫曼樹，其結(jié)點總數(shù)為2nl 。37 . 一棵具有n個結(jié)點的樹，所有非終端結(jié)點的度均為 k,則該樹中葉子結(jié)點個數(shù)為 n-(n_1)/k_ _。解：獲為0的*點個數(shù)為n。，度為k的結(jié)點個數(shù)為聯(lián)立方程：n o+nk=n= no=n-(n-1)/kk*n k=n-1=>nk=(n-1)/k38 .某二叉樹的后根遍歷序列為 abd,中根遍歷序列為adb,則它的先根遍歷序 列為 dab 。39 .深度為15的滿二叉樹上，第11層有 210個結(jié)點。40 .對一棵有100個結(jié)點的完

32、全二叉樹按層編號，則編號為 49的結(jié)點，它的左 孩子的編號為 98。41 .設(shè)F、C是二叉樹中的兩個結(jié)點，若 F是C的祖先結(jié)點，則在采用后根遍歷 方法遍歷該二叉樹時，F(xiàn)和C的位置關(guān)系為：F必定在C的 、后面。42 .若用后根遍歷法遍歷題21圖所示的二叉樹，其輸出序列為 DBFHGECA 。題21圖43 .有4個結(jié)點且深度為4的二叉樹的形態(tài)共有2 種。44 .某二叉樹的先根遍歷序列為IJKLMNO中根遍歷序列為JLKINMO則該二叉樹中根結(jié)點的右孩子是M.。45 .三個結(jié)點可構(gòu)成_5種不同形態(tài)的二叉樹。46 .對于一棵具有n個結(jié)點的二叉樹，當進行鏈接存儲時，其二叉鏈表中的指針域的總數(shù)為2n個，其

33、中 n-1 個用于鏈接孩子結(jié)點。47 .設(shè)一棵二叉樹中度為2的結(jié)點數(shù)為10,則該樹的葉子數(shù)為1148 .如圖所示的二叉樹，若按后根遍歷，則其輸出序列為 DBFHGECA% ©® ©49 .深度為k的滿二叉樹其葉子結(jié)點個數(shù)共有2k-1個。50 .二叉樹通常采用順序存儲和二叉鏈表存儲兩種存儲結(jié)構(gòu)表示。51 .前序序列和中序序列相同的二叉樹為沒有左子樹的二叉樹。52 .具有64個結(jié)點的完全二叉樹的深度為 7 。53 .已知二叉樹中的葉子樹為50,僅有一個孩子的結(jié)點數(shù)為 30,則總結(jié)點數(shù)為。 129;54 .后序序列和中序序列相同的二叉樹為 沒有右子樹的二叉樹、 后序序列

34、和前序序列相同的二叉樹為只有根的二叉樹；。55 .如果指針p指向一棵二叉樹的一個結(jié)點，則判斷p沒有左孩子的邏輯表達式為。 P->lchild=NULL ;56 .設(shè)一顆完全二叉樹共有50個葉子結(jié)點，則它共有個度為2的結(jié)點。4957 .二叉機t采用序遍歷可以得到結(jié)點的有序序列。中58 .在一棵二叉樹上第5層的結(jié)點數(shù)最多為 o 1659 .總共三層的完全二叉樹，其結(jié)點數(shù)至少有 個，至多有個。4、/60 .二叉樹的遍歷方法有 、。 先序 、 中序 、 后序 、 層次61 .二叉樹的存儲結(jié)構(gòu)有、結(jié)構(gòu)表示。順序 存儲 、二叉鏈表存儲、三叉鏈表存儲62 . 一棵哈夫曼樹有5個葉子結(jié)點組成，該哈夫曼樹

35、總共有 個結(jié)點。963 .對于一棵具有n個結(jié)點的樹，該樹中所有結(jié)點的度數(shù)之和為 。 n-164 .假定一棵三叉樹的結(jié)點個數(shù)為50,則它的最小深度為 ,最大深度為。 5、5065 .在一棵三叉在t中，度為3的結(jié)點數(shù)有2個，度為2的結(jié)點數(shù)有1個，度為1 的結(jié)點數(shù)為2個，那么度為0的結(jié)點數(shù)有個。666 . 一棵深度為5的滿二叉樹中的結(jié)點數(shù)為 個，一棵深度為3的滿三叉樹中的結(jié)點數(shù)為 個。31、2167 .假定一棵樹的廣義表表示為 A(B(C,D(E,F,G),H(I,J),則樹中所含的結(jié)點 數(shù)為個，樹的深度為 ,樹的度為。 10、4、368 .假定一棵樹的廣義表表示為 A(B(C,D(E,F,G),H

36、(I,J),則度為3、2、1、0的結(jié)點數(shù)分別為?口個。2、1、1、669 .假定一棵樹的廣義表表示為 A(B(C,D(E,F,G),H(I,J),則結(jié)點H的雙親結(jié)點為,孩子2$點為 o B I和J70在一棵二叉樹中，假定雙分支結(jié)點數(shù)為5 個，單分支結(jié)點數(shù)為6 個，則葉子結(jié)點數(shù)為 個。 671對于一棵二叉樹，若一個結(jié)點的編號為i ，則它的左孩子結(jié)點的編號為， 右孩子結(jié)點的編號為， 雙親結(jié)點的編號為。 2i 、 2i+1 、i/272在一棵二叉樹中，第5 層上的結(jié)點數(shù)最多為。 1673假定一棵二叉樹的結(jié)點數(shù)為18，則它的最小深度為，最大深度為。 5、 1874一棵二叉樹的廣義表表示為a(b(c,d

37、),e(f(,g) ，則 e 結(jié)點的雙親結(jié)點為,左孩子結(jié)點為,右孩子結(jié)點為 o a、f、空結(jié)點(即無右孩子結(jié)點)75. 一棵二叉樹的廣義表表示為a(b(c,d),e(f(,g) ，它含有雙親結(jié)點個，單分支結(jié)點個，葉子結(jié)點 個。4、 2、 376. 假定一棵二叉樹順序存儲在一維數(shù)組a 中，則 ai 元素的左孩子元素為，右孩子元素為 ，雙親元素 (i>1) 為 。 a2*i 、a2*i+1 、 ai/277假定一棵二叉樹順序存儲在一維數(shù)組a 中，但讓編號為1 的結(jié)點存入a0元素中，讓編號為2 的結(jié)點存入a1 元素中，其余類推，則編號為i 結(jié)點的左孩子結(jié)點對應(yīng)的存儲位置為， 若編號為i 結(jié)點的

38、存儲位置用j 表示， 則其左孩子結(jié)點對應(yīng)的存儲位置為。 2i-1 、 2j+178 若對一棵二叉樹從0 開始進行結(jié)點編號，并按此編號把它順序存儲到一維數(shù)組 a 中，即編號為0 的結(jié)點存儲到a0 中，其余類推，則ai 元素的左孩子元素為 ， 右孩子元素為， 雙親元素 (i>0) 為 。 A2*i+1 、a2*i+2 、 ai/279對于一棵具有n 個結(jié)點的二叉樹，對應(yīng)二叉鏈表中指針總數(shù)為個，其中 個用于指向孩子結(jié)點， 個指針空閑著。2n、 n-1 、 n+180一棵二叉樹廣義表表示為a(b(d(,h),c(e,f(g,i(k) ，該樹的結(jié)點數(shù)為個，深度為 。 10、 581假定一棵二叉樹廣

39、義表表示為a(b(c),d(e,f) ，則對它進行的先序遍歷結(jié)果 為 ， 中 序 遍 歷 結(jié) 果 為 ， 后 序 遍 歷 結(jié) 果 為， 按層遍歷結(jié)果為。 abcdef、 cbaedf、 cbefda 、 abdcef82假定一棵普通樹的廣義表表示為a(b(e),c(f(h,i,j),g),d) ，則先根遍歷結(jié)果為 ，按層遍歷結(jié)果為 。 abecfhijgd 、 abcdefghij83 在一棵二叉搜索樹中，每個分支結(jié)點的左子樹上所有結(jié)點的值一定該結(jié)點的值，右子樹上所有結(jié)點的值一定該結(jié)點的值。 小于、 大于等于84 對一棵二叉搜索樹進行中序遍歷時，得到的結(jié)點序列是一個。 按升序排列的有序序列85

40、 從一棵二叉搜索樹中查找一個元素時，若元素的值等于根結(jié)點的值，則表明，若元素的值小于根結(jié)點的值，則繼續(xù)向 查找，若元素的大于根結(jié)點的值，則繼續(xù)向查找。 找到、左子樹、右子樹86在一個堆的順序存儲中，若一個元素的下標為i ，則它的左孩子元素的下標為 ，右孩子元素的下標為 。 2i+1 、 2i+287 在一個小根堆中，堆頂結(jié)點的值是所有結(jié)點中的， 在一個大根堆中，堆頂結(jié)點的值是所有結(jié)點中的。 最小值、最大值88 .當從一個小根堆中刪除一個元素時，需要把 元素填補到 位置，然后再按條件把它逐層 調(diào)整。堆尾、堆頂、向下89 .假定一棵樹的廣義表表示為 A (B (C, D (E, F, G), H

41、(I, J),則樹中 所含的結(jié)點數(shù)為 個，樹的深度為 ，樹的度為,結(jié)點H的雙親結(jié)點為，孩子結(jié)點為。 10、3、3、R I和J;90 .樹在計算機內(nèi)的表示方式有(1) ,(2) ,(3)。(1)雙親鏈表表示法(2) 孩子鏈表表示法(3)孩子兄弟表示法91 .已知一棵度為3的樹有2個度為1的結(jié)點，3個度為2的結(jié)點，4個度為3 的結(jié)點，則該樹有個葉子2點。1292 .深度為H的完全二叉樹至少有(1) 個結(jié)點;至多有(2) 個結(jié)點:H和結(jié) 點總數(shù) N之間的關(guān)系是(3。 (1)2 H-1 (2)2 H-1 (3)H= log2N+193 .在順序存儲的二叉樹中，編號為 i和j的兩個結(jié)點處在同一層的條件是

42、0用順序存儲結(jié)構(gòu)存儲二叉樹時,要按完全二叉樹的形式存儲,非完全二叉樹存儲 時，要加“虛結(jié)點”。設(shè)編號為i和j的結(jié)點在順序存儲中的下標為 s和t , 則結(jié)點i和j在同一層上的條件是log 2s = log 2t。94 . 一棵有n個結(jié)點的滿二叉樹有(1)個度為1的結(jié)點、有(2)個分枝(非終端)結(jié)點和(3)個葉子,該滿二叉樹的深度為 (4) 0 (1)0 (2)(n-1)/2 或 n/2(3)(n+1)/2 (4) log2(n+1)95 .設(shè)只含根結(jié)點的二叉樹的高度為0,則高度為k的二叉樹的最大結(jié)點數(shù)為，最小結(jié)點數(shù)為。(1) 2 K+1-1k+196 .已知二叉樹有50個葉子結(jié)點，則該二叉樹的總

43、結(jié)點數(shù)至少是 。9997 . 一個深度為k的，具有最少結(jié)點數(shù)的完全二叉樹按層次，(同層次從左到右) 用自然數(shù)依此對結(jié)點編號，則編號最小的葉子的序號是 ；編號是i的結(jié)點 所在的層次號是 (根所在的層次號規(guī)定為1層)。(1)2 k-2+1 (第k層1個結(jié)點，總結(jié)點個數(shù)是2H,其雙親是2H-1/2=2。(2) log 2i +198 .完全二叉樹中，結(jié)點個數(shù)為n,則編號最大的分支結(jié)點的編號為 。 n/2 99 .對于一個具有n個結(jié)點的二元樹，當它為一棵(1)二元樹時具有最小高度, 當它為一棵(2)時，具有最大高度。(1)完全 (2) 只有一個葉子結(jié)點的二叉 樹100. n (n大于1)個結(jié)點的各棵樹

44、中，具深度最小的那棵樹的深度是(1)0它共有(2) 個葉子結(jié)點和(3) 個非葉子結(jié)點、其中深度最大的那棵樹的深度 是(4),它共有(5) 個葉子結(jié)點和(6)個非葉子結(jié)點。(1)2 (2) n-1(3) 1 (4) n (5) 1 (6) n-1101 .某二叉樹的后序遍歷序列是 dabec,中序遍歷序列是debac,前序遍歷序列 是 o cedba102 .現(xiàn)有按中序遍歷二叉樹的結(jié)果為abc,問有_(1)_種不同的二叉樹可以得到這一遍歷結(jié)果，這些二叉樹分別是(2)0 (1)5(2)略103 .在一棵存儲結(jié)構(gòu)為三叉鏈表的二叉樹中，若有一個結(jié)點是它的雙親的左子 女，且它的雙親有右子女，則這個結(jié)點在

45、后序遍歷中的后繼結(jié)點是 。雙親 的右子樹中最左下的葉子結(jié)點104 . 一棵左子樹為空的二叉樹在先序線索化后，其中的空鏈域的個數(shù)為：。2105 .若以4, 5, 6, 7, 8作為葉子結(jié)點的權(quán)值構(gòu)造哈夫曼樹，則其帶權(quán)路徑長 度是。69106 .已知完全二叉樹的第7層有20個結(jié)點，則整個完全二叉樹的葉子結(jié)點數(shù)是。42107 .樹有三種常用的存儲結(jié)構(gòu)，即孩子鏈表法、孩子兄弟鏈表法和.雙親表示法108 .所謂二叉排序樹是指滿足如下條件的二叉樹：其中每個結(jié)點的值 于其左子樹中任意結(jié)點的值， 于其右子樹中任意結(jié)點的值。 大于，小于109 .深度為k的二叉樹至多有一2k-1 個結(jié)點.最少有2k-1-1個結(jié)點

46、。三、判斷題1 .()滿二叉樹一定是完全二叉樹，完全二叉樹不一定是滿二叉樹。T2 .()設(shè)一棵二叉樹的先序序列和后序序列，則能夠唯一確定出該二叉樹的形狀。F3 .()設(shè)一棵樹T可以轉(zhuǎn)化成二叉樹BT,則二叉樹BT中一定沒有右子樹。T4 .()完全二叉樹中的葉子結(jié)點只可能在最后兩層中出現(xiàn)。T5 .()哈夫曼樹中沒有度數(shù)為1的結(jié)點。T6 .()由樹轉(zhuǎn)化成二叉樹，該二叉樹的右子樹不一定為空。F7 .()若一個葉子結(jié)點是某二叉樹的中序遍歷序列的最后一個結(jié)點，則它必是該二叉樹的先序遍歷序列中的最后一個結(jié)點。T8 .()若有一個葉子結(jié)點是某子樹的中序遍歷的最后一個結(jié)點，則它必是該子 樹的先序遍歷的最后一個結(jié)

47、點。V9 .()任意一棵滿二叉樹一定也是完全二叉樹。V;10 .()完全二叉樹未必是滿二叉樹。 V;11 .() 二叉排序樹采用先序遍歷可以得到結(jié)點的有序序列。x ;12 .()滿二叉樹的葉子結(jié)點一定都在最后一層。 V13 .()完全二叉樹的葉子結(jié)點可能都在最后一層。V14 .() 一棵滿二叉樹一定是一棵完全二叉樹。V15 .()葉子結(jié)點的度不一定為00 X16 .()哈夫曼樹得到的帶權(quán)路徑長度一定是最小的。V17 .()在霍夫曼編碼中，當兩個字符出現(xiàn)的頻率相同時，其編碼也相同，對于 這種情況應(yīng)當特殊處理。 X18 .()由樹轉(zhuǎn)化成二叉樹，其根的右子女指針總是空的。V19 .()具有10個葉結(jié)

48、點的二叉樹中，有9個度為2的結(jié)點。V20 .()二叉樹以后序遍歷序列與前序遍歷序列反映的同樣的信息(他們反映的 信息不獨立)。V21 .()高度為h (h>0)的完全二叉樹對應(yīng)的森林所含的樹的個數(shù)一定是hox22 .()如果約定樹中結(jié)點的度數(shù)不超過 2,則它實際上就是一棵二叉樹.X23 .()完全二叉樹的前序序列中，若結(jié)點 u在結(jié)點v之前，則u一定是v的 祖先。X24 .()采用二叉鏈表作存儲結(jié)構(gòu)，樹的前序遍歷和其相應(yīng)的二叉樹的前序遍 歷的結(jié)果是一樣的。V25 .()任何二叉樹的后序線索樹進行后序遍歷時都必須用棧。X26 .()樹的父鏈表示法其實就是用數(shù)組表示樹的存儲結(jié)構(gòu)。V27 .()

49、完全二叉樹中，若一個結(jié)點沒有左孩子，則它必是樹葉。V28 .() 一般來說，若深度為k的n個結(jié)點的二叉樹只有最小路徑長度，那么 從根結(jié)點到第k-1層具有最多的結(jié)點數(shù)為2k-1-1 ,余下的n-2k-1+1個結(jié)點在第k 層的任一位置上。V29 .() 一棵樹中的葉子數(shù)一定等于與其對應(yīng)的二叉樹的葉子數(shù)。X30 .()用六叉鏈表表示30個結(jié)點的六叉樹，則樹中共有151個空指針。V31 .()樹有先根遍歷和后根遍歷，樹可以轉(zhuǎn)化為對應(yīng)的二叉樹，樹的后根遍 歷與其對應(yīng)的二叉樹的后根遍歷相同。X32 .()在二叉樹中插入結(jié)點，則此二叉樹便不再是二叉樹了。X33 .()非空的二叉樹一定滿足：某結(jié)點若有左孩子，

50、則其中序前驅(qū)一定沒有 右孩子V34 .()樹的數(shù)組表示法(單鏈或父鏈表示法)中兄弟結(jié)點的編號不一定是連續(xù)的。V35 . ( ) Huffman樹度為1的結(jié)點數(shù)等于度為2和0的結(jié)點數(shù)之差。X36 .()深度為k具有n個結(jié)點的完全二叉樹，具編號最小的葉結(jié)點序號為2k-2 +1。X37 .()若從二叉樹的任一結(jié)點出發(fā)，到根的路徑上所經(jīng)過的結(jié)點序列按其關(guān) 鍵字有序，則該二叉樹一定是哈夫曼樹。x38 .()二叉樹按照某種順序線索化之后，任一個結(jié)點均有指向其前驅(qū)結(jié)點或 者后繼結(jié)點的線索。x39 .()哈夫曼樹無左右子樹之分。X40 .()不用遞歸就不能實現(xiàn)二叉樹的前序遍歷。X41 .() 一棵非空的二叉樹

51、的后序遍歷序列的最后一個元素是其最右下結(jié)點。X42 .()不使用遞歸也能實現(xiàn)二叉樹的前序、中序和后序遍歷。V43 .() 一棵有n個結(jié)點的二叉樹，從上到下，從左到右用自然數(shù)依次給予編 號，則編號為i的結(jié)點的左兒子的編號為2i(2i< n),右兒子是2i+1 (2i+1<n) x44 .()二叉樹是樹的特殊形式。X四、簡答題1 . Huffman樹是否唯一？請舉例說明。2 .畫出題30圖所示的二叉樹的二叉鏈表存儲結(jié)構(gòu)BDAFEHGCO題30圖3 .已知一棵二叉樹的中根遍歷序列和后根遍歷序列分別為 DBFHGEC獨畫出這棵二叉樹。4 .分別寫出題29圖中二叉樹的先根、中根、后根遍歷序列

52、先根遍歷 ABCDFGHE中根 BADGFHCE后根 BGHFDECA5 .試米用類C語百，給出二叉樹的二叉1Struct bitreeDatatype data;Struct bitree * Ichild;Struct bitree * rchild;Bitree;6 .回出卜列一叉樹的一叉鏈表表示圖。Z © ,鏈表結(jié)構(gòu)描述。（6分）/ A 1 X. rTZ1 X ABA/C©®©7.已知一棵二叉樹的中序序列和后序序列分別是 出這棵二叉樹。/ Xva g a AhaBDCEAFHG DECBHGFMUDEH8 .給出下圖所示的二叉樹的中序遍歷結(jié)果。DBAFGEC9 .給出下圖所示的二叉樹的先序、中序、后序的遍歷結(jié)果ABDCEFGDBAFGECDBGFECA先中后10 .已知一棵二叉樹的中序遍歷結(jié)果為 DBHEAFICG前序遍歷結(jié)果為ABDEHCFIG畫出該二叉樹11 .已知一棵完全二叉樹的順序存儲結(jié)構(gòu)如下表所示，試畫出該完全二叉樹的邏輯示意圖。卜標 0