-樹(shù)和二叉樹(shù)練習(xí)題及答案

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

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

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

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

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

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

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

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

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

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

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

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

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

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