第五章??????? 樹形結(jié)構(gòu)

一、選擇題

1．已知一算術(shù)表達式的中綴形式為 A+B*C-D/E，后綴形式為ABC*+DE/-，其前綴形式為(D??? )

A．-A+B*C/DE?????? B.-A+B*CD/E????? C．-+*ABC/DE?????????? D. -+A*BC/DE

2．算術(shù)表達式a+b*（c+d/e）轉(zhuǎn)為后綴表達式后為（? B??）??????????

????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????? A．ab+cde/*??? B．abcde/+*+????? C．abcde/*++??? D．abcde*/++

3. 設(shè)有一表示算術(shù)表達式的二叉樹（見下圖），

它所表示的算術(shù)表達式是（ C?? ）

A. A*B+C/(D*E)+(F-G)? B. (A*B+C)/(D*E)+(F-G)?

C. (A*B+C)/(D*E+（F-G）)?? D. A*B+C/D*E+F-G

4. 設(shè)樹T的度為4，其中度為1，2，3和4的結(jié)點個數(shù)分別為4，2，1，1? 則T中的葉子數(shù)為（? D? ）

A．5??????????? B．6????????? C．7?????????? D．8

5. 在下述結(jié)論中，正確的是（ D?? ）

①只有一個結(jié)點的二叉樹的度為0;? ②二叉樹的度為2；? ③二叉樹的左右子樹可任意交換;

④深度為K的完全二叉樹的結(jié)點個數(shù)小于或等于深度相同的滿二叉樹。

A．①②③??????? B．②③④????? C．②④?????? D．①④

6. 設(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．條件不足，無法確定

7.? 樹是結(jié)點的有限集合，它（ (1）)根結(jié)點，記為T。其余結(jié)點分成為m（m>0）個(（2）)的集合T1，T2， …，Ｔm，每個集合又都是樹，此時結(jié)點T稱為Ti的父結(jié)點，Ti稱為T的子結(jié)點（1≤i≤m）。一個結(jié)點的子結(jié)點個數(shù)稱為該結(jié)點的( （3） )。二叉樹與樹是兩個不同的概念，二叉樹也是結(jié)點的有限集合，它(（4）)根結(jié)點。可以把樹的根結(jié)點的層數(shù)定義為1，其他結(jié)點的層數(shù)等于其父結(jié)點所在層數(shù)加上1。令T是一棵二叉樹，Ki和Kj是T中子結(jié)點數(shù)小于2的結(jié)點中的任意兩個，它們所在的層數(shù)分別為λKi和λKj，當關(guān)系式│λKi-λKj│≤1一定成立時，則稱T為一棵（(5)）。供選擇的答案：CACAC

（1）(4) A. 有0個或1個? B. 有0個或多個? C. 有且只有一個??? D. 有1個或1個以上

（2） A. 互不相交?? B.允許相交???? C.允許葉結(jié)點相交? D.允許樹枝結(jié)點相交

（3） A. 權(quán)???????? B.維數(shù)???????? C.次數(shù)??????????? D.序

（5） A. 豐滿樹???? B.查找樹?????? C.平衡樹?? D.完全樹

8．若一棵二叉樹具有10個度為2的結(jié)點，5個度為1的結(jié)點，則度為0的結(jié)點個數(shù)是（B? ）

A．9??????????? B．11??? ?????C．15?????? D．不確定

9．在一棵三元樹中度為3的結(jié)點數(shù)為2個，度為2的結(jié)點數(shù)為1個，度為1的結(jié)點數(shù)為2個，則度為0的結(jié)點數(shù)為（C?? ）個

A．4???????????? B．5????????? C．6????? D．7?

10．設(shè)森林F中有三棵樹，第一，第二，第三棵樹的結(jié)點個數(shù)分別為M1，M2和M3。與森林F對應(yīng)的二叉樹根結(jié)點的右子樹上的結(jié)點個數(shù)是（? D? ）。

A．M1????????? B．M1+M2?????? C．M3?????????? D．M2+M3

11．具有10個葉結(jié)點的二叉樹中有（ B ）個度為2的結(jié)點，

A．8?????????? B．9???????????? C．10????????? D．ll

12．一棵完全二叉樹上有1001個結(jié)點，其中葉子結(jié)點的個數(shù)是（ E??）

A． 250??B． 500??? C．254???? D．505????? E．以上答案都不對???

13. 設(shè)給定權(quán)值總數(shù)有n 個，其哈夫曼樹的結(jié)點總數(shù)為(? D? )

A．不確定??????? B．2n???????? C．2n+1???????? D．2n-1

14. 有n個葉子的哈夫曼樹的結(jié)點總數(shù)為（ D?? ）。

A．不確定????????? B．2n????????? C．2n+1????????? D．2n-1

15．若度為m的哈夫曼樹中，其葉結(jié)點個數(shù)為n，則非葉結(jié)點的個數(shù)為（C ）。

A．n-1????? B．?n/m?-1?????? C．é(n-1)/(m-1)ù???? D． én/(m-1)ù-1?? E．é(n+1)/(m+1)ù-1

16. 有關(guān)二叉樹下列說法正確的是（B??? ）

A．二叉樹的度為2?????????????????? B．一棵二叉樹的度可以小于2????????????????????????????????????????????????????????????????????????????????

C．二叉樹中至少有一個結(jié)點的度為2?? D．二叉樹中任何一個結(jié)點的度都為2

17．二叉樹的第I層上最多含有結(jié)點數(shù)為（ C ）

A．2^I ?????????B． 2^I-1-1?????????? C． 2^I-1??????????? D．2^I ?-1

18. 一個具有1025個結(jié)點的二叉樹的高h為（? C? ）

A．11????? ????B．10??????? C．11至1025之間????? D．10至1024之間

19．一棵二叉樹高度為h,所有結(jié)點的度或為0，或為2，則這棵二叉樹最少有(? B? )結(jié)點

A．2h???? B．2h-1??????? C．2h+1???????? D．h+1??

20．對于有n 個結(jié)點的二叉樹, 其高度為（? D? ）

A．nlog₂n????? B．log₂n????????? C．?log₂n?|+1?????? D．不確定

21. 一棵具有 n個結(jié)點的完全二叉樹的樹高度（深度）是（ A? ?）

A．?logn?+1?????? B．logn+1??????? C．?logn?????? D．logn-1

22．深度為h的滿m叉樹的第k層有（ A ）個結(jié)點。(1=<k=<h)

A．m^k-1 ???????????B．m^k-1????????? C．m^h-1????? D．m^h-1

23．在一棵高度為k的滿二叉樹中，結(jié)點總數(shù)為（? C? ）

A．2^{k-1???????????} B．2^{k????????????} C．2^k-1???????D．?log2^k?+1

24．高度為 K的二叉樹最大的結(jié)點數(shù)為（? C? ）。

A．2^k? ???? B．2^{k-1????????? C}．2^k -1 ?????? ?D．2^k-1-1

25. 一棵樹高為K的完全二叉樹至少有（?C? ）個結(jié)點

A．2^k –1?????????? B. 2^k-1 –1???????? C. 2^k-1??????D. 2^k

26. 將有關(guān)二叉樹的概念推廣到三叉樹，則一棵有244個結(jié)點的完全三叉樹的高度（C）

A．4?????????? B．5?????????? C．6?????????? D．7

27. 利用二叉鏈表存儲樹，則根結(jié)點的右指針是（ C?? ）。

A．指向最左孩子??????? B．指向最右孩子???????? C．空??????? D．非空

28．對二叉樹的結(jié)點從1開始進行連續(xù)編號，要求每個結(jié)點的編號大于其左、右孩子的編號，同一結(jié)點的左右孩子中，其左孩子的編號小于其右孩子的編號，可采用(? C? )次序的遍歷實現(xiàn)編號。

A．先序?????????? B. 中序????????? C. 后序 B???????? D. 從根開始按層次遍歷

29．樹的后根遍歷序列等同于該樹對應(yīng)的二叉樹的(??? ).

A. 先序序列??????????????????B. 中序序列??????????? C. 后序序列

30．若二叉樹采用二叉鏈表存儲結(jié)構(gòu)，要交換其所有分支結(jié)點左、右子樹的位置，利用( C?? )遍歷方法最合適。

A．前序???? B．中序????? C．后序????? D．按層次

31．在下列存儲形式中，哪一個不是樹的存儲形式？（ D?? ）】

A．雙親表示法? B．孩子鏈表表示法 C．孩子兄弟表示法 D．順序存儲表示法

32．一棵二叉樹的前序遍歷序列為ABCDEFG，它的中序遍歷序列可能是（B?? ）

A．CABDEFG?? ????????B．ABCDEFG?????? C．DACEFBG?????????? D．ADCFEG????

33．已知一棵二叉樹的前序遍歷結(jié)果為ABCDEF,中序遍歷結(jié)果為CBAEDF,則后序遍歷的結(jié)果為（?A? ）。

A．CBEFDA?????? B． FEDCBA?????? C． CBEDFA?????? D．不定???

34．已知某二叉樹的后序遍歷序列是dabec, 中序遍歷序列是debac ,? 它的前序遍歷是（ D?? ）。

????? A．acbed?????? B．decab? ??C．deabc????? D．cedba???

35. 某二叉樹中序序列為A,B,C,D,E,F,G，后序序列為B,D,C,A,F,G,E 則前序序列是：B

A．E,G,F,A,C,D,B????? B．E,A,C,B,D,G,F????? C．E,A,G,C,F,B,D????? D．上面的都不對

36. 上題的二叉樹對應(yīng)的森林包括多少棵樹（? B? ）

A．l???????? B．2?????? C．3??? D．概念上是錯誤的?

37．二叉樹的先序遍歷和中序遍歷如下： 先序遍歷：EFHIGJK；中序遍歷: HFIEJKG 。該二叉樹根的右子樹的根是： C

A、 E???????? B、 F　????C、 G　????? D、 H??

38．將一棵樹t 轉(zhuǎn)換為孩子—兄弟鏈表表示的二叉樹h，則t的后根序遍歷是h 的

A．前序遍歷???? B．中序遍歷????? C．后序遍歷（? B? ）

39. 某二叉樹T有n個結(jié)點，設(shè)按某種順序?qū)中的每個結(jié)點進行編號，編號為1，2，… ，n，且有如下性質(zhì)：T中任一結(jié)點V，其編號等于左子樹上的最小編號減1，而V的右子樹的結(jié)點中，其最小編號等于V左子樹上結(jié)點的最大編號加1。這時是按( B??)編號的。

A.中序遍歷序列 B.前序遍歷序列 C.后序遍歷序列? D.層次順序

40．下面的說法中正確的是（ B?? ）.

（1）任何一棵二叉樹的葉子結(jié)點在三種遍歷中的相對次序不變；

（2）按二叉樹定義，具有三個結(jié)點的二叉樹共有6種。

A．(1)(2)?? B．(1)?? C．(2)??? D．(1)、(2)都錯?

41．對于前序遍歷與中序遍歷結(jié)果相同的二叉樹為（1）F;

對于前序遍歷和后序遍歷結(jié)果相同的二叉樹為（2）。B

A．一般二叉樹???B．只有根結(jié)點的二叉樹????C．根結(jié)點無左孩子的二叉樹

D．根結(jié)點無右孩子的二叉樹?E．所有結(jié)點只有左子數(shù)的二叉樹 F．所有結(jié)點只有右子樹的二叉樹

42．C一棵非空的二叉樹的先序遍歷序列與后序遍歷序列正好相反，則該二叉樹一定滿足（??? ）

A．所有的結(jié)點均無左孩子B．所有的結(jié)點均無右孩子C．只有一個葉子結(jié)點D．是任意一棵二叉樹

43．在二叉樹結(jié)點的先序序列，中序序列和后序序列中，所有葉子結(jié)點的先后順序（ B?? ）

A．都不相同　　B．完全相同??C．先序和中序相同，而與后序不同　

?D．中序和后序相同，而與先序不同?

44．某二叉樹的前序序列和后序序列正好相反，則該二叉樹一定是（C）的二叉樹。

A．空或只有一個結(jié)點??? B．任一結(jié)點無左子樹??? C．高度等于其結(jié)點數(shù)??? D．任一結(jié)點無右子樹

45．在完全二叉樹中，若一個結(jié)點是葉結(jié)點，則它沒（? C? ）。

??? A．左子結(jié)點??? B．右子結(jié)點　? C．左子結(jié)點和右子結(jié)點??? D．左子結(jié)點，右子結(jié)點和兄弟結(jié)點

46．在下列情況中，可稱為二叉樹的是（?? B ）

??? A．每個結(jié)點至多有兩棵子樹的樹????B. 哈夫曼樹???C．每個結(jié)點至多有兩棵子樹的有序樹?

? D. 每個結(jié)點只有一棵右子樹???????? E．以上答案都不對?

47. 一棵左子樹為空的二叉樹在先序線索化后，其中空的鏈域的個數(shù)是：(?? D )

A．不確定???????? B. 0??????? C.1??????? D. 2??

48. 一棵左右子樹均不空的二叉樹在先序線索化后，其中空的鏈域的個數(shù)是：(B??? )。

A. 0??????????? B. 1??????? C. 2????????? D. 不確定

49. 若X是二叉中序線索樹中一個有左孩子的結(jié)點，且X不為根，則x的前驅(qū)為(??? C)

A.X的雙親? B.X的右子樹中最左的結(jié)點? C.X的左子樹中最右結(jié)點? D.X的左子樹中最右葉結(jié)點

50. 引入二叉線索樹的目的是（? A? ）

A．加快查找結(jié)點的前驅(qū)或后繼的速度??B．為了能在二叉樹中方便的進行插入與刪除

C．為了能方便的找到雙親????? D．使二叉樹的遍歷結(jié)果唯一

?

二、判斷題

×1. 二叉樹是度為2的有序樹。

×2.完全二叉樹一定存在度為1的結(jié)點。

×3. 對于有N個結(jié)點的二叉樹，其高度為log₂n。

√4．深度為K的二叉樹中結(jié)點總數(shù)≤2^k-1。

√5. 二叉樹以后序遍歷序列與前序遍歷序列反映的同樣的信息(他們反映的信息不獨立）。

√6. 二叉樹的遍歷結(jié)果不是唯一的.

√7. 二叉樹的遍歷只是為了在應(yīng)用中找到一種線性次序。

√9. 一個樹的葉結(jié)點，在前序遍歷和后序遍歷下，皆以相同的相對位置出現(xiàn)。

×10. 二叉樹的前序遍歷并不能唯一確定這棵樹，但是，如果我們還知道該樹的根結(jié)點是那一個，則可以確定這棵二叉樹。

×11. 一棵一般樹的結(jié)點的前序遍歷和后序遍歷分別與它相應(yīng)二叉樹的結(jié)點前序遍歷和后序遍歷是一致的。

×13．用樹的前序遍歷和中序遍歷可以導(dǎo)出樹的后序遍歷。

√14．采用二叉鏈表作存儲結(jié)構(gòu)，樹的前序遍歷和其相應(yīng)的二叉樹的前序遍歷的結(jié)果是一樣的。

×15. 用一維數(shù)組存儲二叉樹時，總是以前序遍歷順序存儲結(jié)點。

√22．完全二叉樹中，若一個結(jié)點沒有左孩子，則它必是樹葉。

×23. 二叉樹只能用二叉鏈表表示。

×24. 一棵有n個結(jié)點的二叉樹，從上到下，從左到右用自然數(shù)依次給予編號，則編號為i的結(jié)點的左兒子的編號為2i(2i< n)，右兒子是2i+1（2i+1<n）。

25. 給定一棵樹，可以找到唯一的一棵二叉樹與之對應(yīng)。

×26. 一棵樹中的葉子數(shù)一定等于與其對應(yīng)的二叉樹的葉子數(shù)。

×39．度為二的樹就是二叉樹。

×40．深度為k具有n個結(jié)點的完全二叉樹，其編號最小的結(jié)點序號為 ?2^k-2?+1。

41.下面二叉樹的定義只有一個是正確的，請在正確的地方畫“√”。

（1）它是由一個根和兩株互不相交的、稱為左子樹和右子樹的二叉樹組成。

（2）（a）在一株二叉樹的級i上，最大結(jié)點數(shù)是2^i-1（i≥1）

（b）在一棵深度為k的二叉樹中，最大結(jié)點數(shù)是2^k-1+1（k≥1）。

√（3）二叉樹是結(jié)點的集合，滿足如下條件：

（a）它或者是空集；

（b）或者是由一個根和兩個互不相交的、稱為左子樹和右子樹的二叉樹組成。

×46. 一棵哈夫曼樹的帶權(quán)路徑長度等于其中所有分支結(jié)點的權(quán)值之和。

×47. 哈夫曼樹無左右子樹之分。

×48．當一棵具有n個葉子結(jié)點的二叉樹的WPL值為最小時，稱其樹為Huffman樹，且其二叉樹的形狀必是唯一的。

√49．哈夫曼樹是帶權(quán)路徑長度最短的樹，路徑上權(quán)值較大的結(jié)點離根較近。

√50. 用鏈表（llink-rlink）存儲包含n個結(jié)點的二叉樹時，結(jié)點的2n個指針區(qū)域中有n+1個空指針。(? )

?

三、填空題

1．二叉樹由_(1)根節(jié)點__，__(2)左子樹_，_(3)右子樹__三個基本單元組成。

4．中綴式a+b*3+4*（c-d）對應(yīng)的前綴式為__(1)++a*b3*4-cd_，若a=1，b=2，c=3，d=4，則后綴式db/cc*a-b*+的運算結(jié)果為_(218)__。

5．二叉樹中某一結(jié)點左子樹的深度減去右子樹的深度稱為該結(jié)點的__平衡因子__。

6．具有256個結(jié)點的完全二叉樹的深度為_9_____。

7．已知一棵度為3的樹有2個度為1的結(jié)點，3個度為2的結(jié)點，4個度為3的結(jié)點，則該樹有__12____個葉子結(jié)點。

8．深度為k的完全二叉樹至少有___(1)2^k-1____個結(jié)點，至多有___(2) 2^k-1____個結(jié)點。

9．深度為H 的完全二叉樹至少有_(1) 2^？H-1____個結(jié)點；至多有_(2) 2^H-1____個結(jié)點；H和結(jié)點總數(shù)N之間的關(guān)系是(3)_H=[log₂N] +1_向下取整。

10．在順序存儲的二叉樹中，編號為i和j的兩個結(jié)點處在同一層的條件是______。

11．在完全二叉樹中，編號為i和j的兩個結(jié)點處于同一層的條件是_[log₂i]= [log₂j]_____。

12．一棵有n個結(jié)點的滿二叉樹有_0_(1)_個度為1的結(jié)點、有__(2)（n-1）/2_個分支（非 終端）結(jié)點和__(3)（n+1）、2_個葉子，該滿二叉樹的深度為_(4) [log₂n]+1? 向下取整__。

13．假設(shè)根結(jié)點的層數(shù)為１，具有ｎ個結(jié)點的二叉樹的最大高度是__n____。

14．在一棵二叉樹中，度為零的結(jié)點的個數(shù)為N0,度為2的結(jié)點的個數(shù)為N2,則有N0 =__N2+1____

15．設(shè)只含根結(jié)點的二叉樹的高度為0，則高度為k的二叉樹的最大結(jié)點數(shù)為_2^k+1-1______,最小結(jié)點數(shù)為____k+1__。

16．設(shè)有N個結(jié)點的完全二叉樹順序存放在向量A[1:N]中，其下標值最大的分支結(jié)點為___[N/2]向下取整___。

17．高度為K的完全二叉樹至少有__2^k-2____個葉子結(jié)點。

18．高度為8的完全二叉樹至少有___64___個葉子結(jié)點。

19．已知二叉樹有50個葉子結(jié)點，則該二叉樹的總結(jié)點數(shù)至少是___99___。

30．8層完全二叉樹至少有__128____個結(jié)點，擁有100個結(jié)點的完全二叉樹的最大層數(shù)為___7___。

31．含4個度為2的結(jié)點和5個葉子結(jié)點的二叉樹，可有___0至多個___個度為1的結(jié)點。

?

四、應(yīng)用題

1．從概念上講，樹，森林和二叉樹是三種不同的數(shù)據(jù)結(jié)構(gòu)，將樹，森林轉(zhuǎn)化為二叉樹的基本目的是什么，并指出樹和二叉樹的主要區(qū)別。

樹的孩子兄弟鏈表表示法和二叉樹二叉鏈表表示法，本質(zhì)是一樣的，只是解釋不同，也就是說樹（樹是森林的特例，即森林中只有一棵樹的特殊情況）可用二叉樹唯一表示，并可使用二叉樹的一些算法去解決樹和森林中的問題。

樹和二叉樹的區(qū)別有三：一是二叉樹的度至多為2，樹無此限制；二是二叉樹有左右子樹之分，即使在只有一個分枝的情況下， 也必須指出是左子樹還是右子樹，樹無此限制；三是二叉樹允許為空，樹一般不允許為空（個別書上允許為空）。

?

2．樹和二叉樹之間有什么樣的區(qū)別與聯(lián)系？

3．已知一棵二叉樹的對稱序和后序序列如下：

對稱序：GLDHBEIACJFK?? 后序：? LGHDIEBJKFCA

(1) 出這棵二叉樹：

(2) 轉(zhuǎn)換為對應(yīng)的森林：

4．設(shè)某二叉樹的前序遍歷序列為:ABCDEFGGI，中序遍歷序列為:BCAEDGHFI：

（1）試畫出該二叉樹；

（2）寫出由給定的二叉樹的前序遍歷序列和中序遍歷序列構(gòu)造出該二叉樹的算法。

（1）已知二叉樹的先序序列:? CBHEGAF,?? 中序序列: HBGEACF, 試構(gòu)造該二叉樹

（2）已知二叉樹按中序排列為BFDAEGC，按前序排列為ABDFCEG，要求畫出該二叉樹。

（3）已知一棵二叉樹的前序序列A,B,D,C,E,F，中序序列B,D,A,E,F,C. 畫出這棵二叉樹。

（4）已知一棵二叉樹的前序遍歷結(jié)果是：ABCDEFGHIJ,中序遍歷的結(jié)果是：BCEDAGHJIF,試畫出這棵二叉樹。

（5）已知二叉樹BT各結(jié)點的先序、中序遍歷序列分別為ABCDEGF和CBAEDF，試畫出該二叉樹。

轉(zhuǎn)載于:https://www.cnblogs.com/wwj9413/archive/2011/12/22/2638669.html

總結(jié)

以上是生活随笔為你收集整理的数据结构之【树形结构】复习题的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。