-樹和二叉樹練習題及答案

1、一、判斷題V) 1.若二叉樹用二叉鏈表作存貯結(jié)構(gòu)，則在n個結(jié)點的二叉樹鏈表中只有n-1個 非空指針域。X) 2.二叉樹中每個結(jié)點的兩棵子樹的高度差等于1。V) 3.二叉樹中每個結(jié)點的兩棵子樹是有序的。X) 4.二叉樹中每個結(jié)點有兩棵非空子樹或有兩棵空子樹。X) 5.二叉樹中所有結(jié)點個數(shù)是2k-i-1,其中k是樹的深度。(應(yīng)21)X) 6.二叉樹中所有結(jié)點，如果不存在非空左子樹，則不存在非空右子樹。X) 7.對于一棵非空二叉樹，它的根結(jié)點作為第一層，則它的第i層上最多能有2i1個結(jié)點。(應(yīng)2i-1)V) 8.用二叉鏈表法存儲包含n個結(jié)點的二叉樹，結(jié)點的2n個指針區(qū)域中有n+1個 為空指針。(V)

2、 9.具有12個結(jié)點的完全二叉樹有5個度為2的結(jié)點。(X ) 10、哈夫曼樹中沒有度為1的結(jié)點，所以必為滿二叉樹。(X )11、在哈夫曼樹中，權(quán)值最小的結(jié)點離根結(jié)點最近。(X )12、線索二叉樹是一種邏輯結(jié)構(gòu)。(V ) 13、深度為K的完全二叉樹至少有2k-1個結(jié)點。(V )14、具有n個結(jié)點的滿二叉樹，其葉結(jié)點的個數(shù)為(n+1) /2。(V )15、前序和中序遍歷用線索樹方式存儲的二叉樹，不必使用棧。(X )16、哈夫曼樹是帶權(quán)路徑長度最短的樹，路徑上權(quán)值較大的點離根較遠。(V)17、在二叉樹結(jié)點的先序序列和后序序列中，所有葉子結(jié)點的先后順序完全相同。(V) 18、二叉樹的遍歷操作實際上是將

3、非線性結(jié)構(gòu)線性化的過程(V) 19、樹的先根遍歷序列與其所轉(zhuǎn)化的二叉樹的先序遍歷序列相同。(X) 20、樹的后根遍歷序列與其所轉(zhuǎn)化的二叉樹的后序遍歷序列相同。二、填空.由3個結(jié)點所構(gòu)成的二叉樹有5_種形態(tài)。.線索二叉樹的左線索指向其前驅(qū)，右線索指向其后繼 。. 一棵具有257個結(jié)點的完全二叉樹，它的深度為 9。4、如某二叉樹有20個葉子結(jié)點，有30個結(jié)點僅有一個孩子，則該二叉樹的總結(jié)點數(shù)為69。.設(shè)一棵完全二叉樹具有1000個結(jié)點，則此完全二叉樹有500個葉子結(jié)點，有499 個度為2的結(jié)點，有 1 個結(jié)點只有非空左子樹，有 0個結(jié)點只有非空右子樹。答：最快方法：用葉子數(shù)曰n/2=500二n0-

4、1=4。另外，最后一結(jié)點為2i屬于 左葉子，右葉子是空的，所以有1個非空左子樹。完全二叉樹的特點決定不可能有左空 右不空的情況，所以非空右子樹數(shù)=0. 一棵含有n個結(jié)點的k叉樹，可能達到的最大深度為 0，最小深度為2。.若已知一棵二叉樹的前序序列是BEFCGDH,中序序列是FEBGCHD,則它的后序序列 必是 F E G H D C B。.在二叉樹中，指針p所指結(jié)點為葉子結(jié)點的條件是 p-lchild=null & p-rchlid=null 。三、選擇題.某二叉樹結(jié)點的中序序列為A、B、C、D、E、F、G,后序序列為B、D、C、A、F、G、 E,則其左子樹中結(jié)點數(shù)目為（。A） 3B） 2C）

5、 4D） 5.二叉樹是非線性數(shù)據(jù)結(jié)構(gòu)，所以（C ）。A、它不能用順序存儲結(jié)構(gòu)存儲；B、它不能用鏈式存儲結(jié)構(gòu)存儲；C、順序存儲結(jié)構(gòu)和鏈式存儲結(jié)構(gòu)都能存儲；D、順序存儲結(jié)構(gòu)和鏈式存儲結(jié)構(gòu)都不 能使用.具有n（n0）個結(jié)點的完全二叉樹的深度為（C ）。（A）促（B） L促（C） L3+1（D）l0g2（n）+1】.把一棵樹轉(zhuǎn)換為二叉樹后，這棵二叉樹的形態(tài)是（A ）。（A）唯一的（B）有多種（C）有多種，但根結(jié)點都沒有左孩子（D）有多種，但根結(jié)點都沒有右孩子.線索二叉樹是一種（C ）結(jié)構(gòu)。A.邏輯 B.邏輯和存儲C.物理D.線性6、將一棵有100個結(jié)點的完全二叉樹從根這一層開始，每一層從左到右依次對結(jié)

6、點進 行編號，根結(jié)點編號為1，則編號為49的結(jié)點的左孩子的編號為（A）A、 98B、 99C、 50D、 487、設(shè)森林F中有三棵樹，第一、第二和第三棵樹的結(jié)點個數(shù)分別為M1、M2和M3。與 森林F對應(yīng)的二叉樹根結(jié)點的右子樹上的結(jié)點個數(shù)是（D）A） M1B） M1+M2 C） M3 D） M2+M38、將一棵有100個結(jié)點的完全二叉樹從根開始，每一層從左到右依次對結(jié)點進行編號， 根結(jié)點編號為1,則編號最大的非葉結(jié)點的編號為（C）A、48B、49C、50D、519、引入二叉線索樹的目的是（A ）A、加快查找結(jié)點的前驅(qū)或后繼的速度B、為了能在二叉樹中方便的進行插入與刪除配為了能方便的找到雙親D、使

7、二叉樹的遍歷結(jié)果唯一.若一棵二叉樹具有10個度為2的結(jié)點，5個度為1的結(jié)點，則度為0的結(jié)點個數(shù)是 (B )A. 9B. 11C. 15D.不確定.一棵樹深度為K的完全二叉樹至少有( C )個結(jié)點A. 2k - 1B. 2k-1 - 1 C. 2k-1D. 2k.一棵二叉樹的前序遍歷序列為ABCDEFG,它的中序遍歷序列可能是（ B ）A. CABDEFGB. ABCDEFGC. DACEFBGD. ADCFEG.有關(guān)二叉樹下列說法正確的是（B ）A.二叉樹的度為2B. 一棵二叉樹的度可以小于2C.二叉樹中至少有一個結(jié)點的度為2D.二叉樹中任何一個結(jié)點的度都為2. 一個具有1025個結(jié)點的二叉樹

8、的高h為（ C ）A. 11B. 10C. 11 至 1025 之間D. 10 至 1024 之間. 一棵二叉樹高度為h,所有結(jié)點的度或為0,或為2,則這棵二叉樹最少有（B）結(jié)點A. 2hB. 2h-1C. 2h+1D. h+1.對于有n個結(jié)點的二叉樹，其高度為（D）A. nlog2nB. 10g2nC.10g2n+1D.不確定.已知某二叉樹的后序遍歷序列是dabec,中序遍歷序列是debac ,它的先序遍歷是（D ）。A.acbedB.decab C.deabcD.cedba.若二叉樹采用二叉鏈表存儲結(jié)構(gòu)，要交換其所有分支結(jié)點左、右子樹的位置，利用 （C）遍歷方法最合適。A.前序B.中序C.

9、后序0.按層次.在下列存儲形式中，哪一個不是樹的存儲形式？（D ）A.雙親表示法B.孩子鏈表表示法C.孩子兄弟表示法D.順序存儲表示法.在下列關(guān)于二叉樹的敘述中，正確的是（ D ）只有一個結(jié)點的二叉樹度為0;二叉樹的度為2；二叉樹的左右子樹可任 意交換;深度為K的完全二叉樹的結(jié)點個數(shù)小于或等于深度相同的滿二叉樹。A.B.C.D.若X是二叉中序線索樹中一個有左孩子的結(jié)點，且X不為根，則x的前驅(qū)為（C）A.X的雙親B.X的右子樹中最左的結(jié)點C.X的左子樹中最右結(jié)點D.X的左子樹中最右葉結(jié)點.在二叉樹結(jié)點的先序序列，中序序列和后序序列中，所有葉子結(jié)點的先后順序 （ B ）A.都不相同 B.完全相同C

10、.先序和中序相同，而與后序不同D.中序和后序相同，而與先序不同.在線索化二叉樹中，t所指結(jié)點沒有右子樹的充要條件是（A ）。A、 t-Rtag=1B、 t-Rchild=NULLC、t-Rtag=1 且 t-Rchild=NULLD、以上都不對24、設(shè)高度為h的二叉樹上只有度為0和度為2的結(jié)點，則此類二叉樹中所包含的結(jié)點數(shù)至少為（B）。A. 2hC. 2h+125、如右圖所示二叉樹的中序遍歷序列是A. abcdgef B. dfebagc C. dbaefcg 數(shù)至少為（B）。A. 2hC. 2h+125、如右圖所示二叉樹的中序遍歷序列是A. abcdgef B. dfebagc C. dba

11、efcg 26、設(shè)a和b為一棵二叉樹上的兩個結(jié)點a是b的左孩子2h-1D. h+1（B）。D. defbagc在中序遍歷時，a在b前的條件是（D）。b是a的右孩子a是b左子樹上結(jié)點或b是a右子樹上結(jié)點D.以上三項均可27、假定在一棵二叉樹中，雙分支結(jié)點數(shù)為15,單分支結(jié)點數(shù)為30,則葉子結(jié)點數(shù)為 （C）個。A. 45B. 15C. 16D. 3128、樹的基本遍歷策略可分為先根遍歷和后根遍歷；二叉樹的遍歷策略分為先序、中序 和后序遍歷。這里把由樹轉(zhuǎn)化得到的二叉樹叫做這棵樹對應(yīng)的二叉樹。以下結(jié)論（A） 是正確的。A.樹的先根遍歷序列與其對應(yīng)的二叉樹的先序遍歷序列相同B.樹的后根遍歷序列與其對應(yīng)的

12、二叉樹的后序遍歷序列相同C.樹的先根遍歷序列與其對應(yīng)的二叉樹的中序遍歷序列相同D.以上都不對29、如下圖所示的4棵二叉樹，（C）不是完全二叉樹。30、設(shè)哈夫曼樹中的葉子結(jié)點總數(shù)為m,若用二叉鏈表作為存儲結(jié)構(gòu)，則該哈夫曼樹中 總共有6）個空指針域。A. 2m-1B. 2mC. 2m+1D. 4m31、二叉樹的第k層的結(jié)點數(shù)最多為（D ）A. 2k-1B. 2K+1C. 2K-1D. 2k-132、設(shè)某棵二叉樹中有2000個結(jié)點，則該二叉樹的最小高度為（C ）。A.9B.10C.11D.1233、一棵有n個結(jié)點的樹，在把它轉(zhuǎn)換成對應(yīng)的二叉樹后，該二叉樹根結(jié)點的左子樹上 共有（B ）個結(jié)點。A. n

13、-2B. n-1C. n+1D. n+2 34、對于一棵深度為4的三叉樹，最多有（C ）個結(jié)點。A. 30B. 36C. 40D. 5435、設(shè)結(jié)點A有3個兄弟結(jié)點且結(jié)點B為結(jié)點A的雙親結(jié)點，則結(jié)點B的度數(shù)數(shù)為(B )。(A) 3(B) 4(C) 5(D) 1四、簡答題1.給定二叉樹的兩種遍歷序列，分別是：前序遍歷序列：D, A, C, E, B, H, F, G, I； 中序遍歷序列：D, C, B, E, H, A, G, I, F,試畫出二叉樹B。解：方法是：由前序先確定root,由中序可確定root的左、右子樹。然后由其左子樹 的元素集合和右子樹的集合對應(yīng)前序遍歷序列中的元素集合，可繼

14、續(xù)確定root的左右 孩子。將他們分別作為新的root,不斷遞歸，則所有元素都將被唯一確定，問題得解。 2、已知一棵二叉樹，其中序序列DBCAFGE,后序序列DCBGFEA,構(gòu)造該二叉樹。3、給定權(quán)值8, 12, 4, 5, 26, 16, 9,構(gòu)造一棵帶權(quán)路徑長度最短的二叉樹，并計算其帶權(quán)路徑長度。WPL=8 X 3+4 X 4+5 X 4+16 X 2+9 X 3+12 X 3+26 X 2 =207注:哈夫曼樹的左右子樹可以互換。4.把如圖所示的樹轉(zhuǎn)化成二叉樹。4.把如圖所示的樹轉(zhuǎn)化成二叉樹。答：注意全部兄弟之間都要連線（包括度為2的兄弟），并注意原有連線結(jié)點一律歸入 左子樹，新添連線結(jié)點一律歸入右子樹。/ A/ 1.- .、./ CI H DL.- G kM J5、畫出和下列二叉樹相應(yīng)的森林。答：注意根右邊的子樹肯定是森林，而孩子結(jié)點的右子樹均為兄弟。（100（100/ （40）19216、假設(shè)用于通信的電文僅由8個字母組成，字母在電文中出現(xiàn)的頻率分別為0.07,0.1