數(shù)據(jù)結(jié)構(gòu) 樹和二叉樹 習(xí)題

1、樹與二叉樹一.選擇題1. 假定在一棵二叉樹中，雙分支結(jié)點(diǎn)數(shù)為15，單分支結(jié)點(diǎn)數(shù)為30個(gè)，則葉子結(jié)點(diǎn)數(shù)為（）個(gè)。A15B16C17D472. 按照二叉樹的定義，具有3個(gè)結(jié)點(diǎn)的不同形狀的二叉樹有（）種。A. 3B. 4C. 5D. 63. 按照二叉樹的定義，具有3個(gè)不同數(shù)據(jù)結(jié)點(diǎn)的不同的二叉樹有（）種。A. 5B. 6C. 30D. 324. 深度為5的二叉樹至多有（）個(gè)結(jié)點(diǎn)。 深度為n的二叉樹結(jié)點(diǎn)至多有2n-1A. 16B. 32C. 31D. 105. 設(shè)高度為h的二叉樹上只有度為0和度為2的結(jié)點(diǎn)，則此類二叉樹中所包含的結(jié)點(diǎn)數(shù)至少為（）。A. 2hB. 2h-1C. 2h+1D. h+16. 對(duì)

2、一個(gè)滿二叉樹 滿二叉樹是除最后一層無任何子節(jié)點(diǎn)外，每一層上的所有結(jié)點(diǎn)都有兩個(gè)子結(jié)點(diǎn)的二叉樹，m個(gè)樹葉，n個(gè)結(jié)點(diǎn)，深度為h，則（）。A. n=h+m 對(duì)于深度為h的滿二叉樹，n=20+21+2h-1=2h-1，m=2h-1。故而n=h+m。B. h+m=2n C. m=h-1 D. n=2 h-17. 任何一棵二叉樹的葉結(jié)點(diǎn)在先序.中序和后序遍歷序列中的相對(duì)次序（）。A.不發(fā)生改變B.發(fā)生改變C.不能確定D.以上都不對(duì)8. 如果某二叉樹的前根次序遍歷結(jié)果為stuwv，中序遍歷為uwtvs，那么該二叉樹的后序?yàn)椋ǎ?A. uwvtsB. vwutsC. wuvtsD. wutsv9. 某二叉樹的

3、前序遍歷結(jié)點(diǎn)訪問順序是abdgcefh，中序遍歷的結(jié)點(diǎn)訪問順序是dgbaechf，則其后序遍歷的結(jié)點(diǎn)訪問順序是（）。A. bdgcefhaB. gdbecfhaC. bdgaechfD. gdbehfca10. 在一非空二叉樹的中序遍歷序列中，根結(jié)點(diǎn)的右邊（）。A. 只有右子樹上的所有結(jié)點(diǎn)B. 只有右子樹上的部分結(jié)點(diǎn)C. 只有左子樹上的部分結(jié)點(diǎn)D. 只有左子樹上的所有結(jié)點(diǎn)11. 樹的基本遍歷策略可分為先根遍歷和后根遍歷；二叉樹的基本遍歷策略可分為先序遍歷.中序遍歷和后序遍歷。這里，我們把由樹轉(zhuǎn)化得到的二叉樹 樹轉(zhuǎn)化為二叉樹的基本方法是把所有兄弟結(jié)點(diǎn)都用線連起來，然后去掉雙親到子女的連線，只留下

4、雙親到第一個(gè)子女的連線。因此原來的兄弟關(guān)系就變?yōu)殡p親與右孩子的關(guān)系。叫做這棵數(shù)對(duì)應(yīng)的二叉樹。結(jié)論（）是正確的。A.樹的先根遍歷序列與其對(duì)應(yīng)的二叉樹的先序遍歷序列相同B.樹的后根遍歷序列與其對(duì)應(yīng)的二叉樹的后序遍歷序列相同C.樹的先根遍歷序列與其對(duì)應(yīng)的二叉樹的中序遍歷序列相同D.以上都不對(duì)12. 如圖所示二叉樹的中序遍歷序列是（）。A. abcdgefB. dfebagcC. dbaefcgD. defbagc13. 一棵二叉樹如圖所示，其中序遍歷的序列為（）。A. abdgcefhB. dgbaechfC. gdbehfcaD. abcdefgh14. 設(shè)a,b為一棵二叉樹上的兩個(gè)結(jié)點(diǎn)，在中序遍

5、歷時(shí)，a在b前的條件是（）。Aa在b的右方Ba在b的左方Ca是b的祖先Da是b的子孫15. 已知某二叉樹的后序遍歷序列是dabec，中序遍歷序列是debac，它的前序遍歷序列是（）。A. acbedB. decabC. deabcD. cedba16. 如下圖所示的4棵二叉樹，（）不是完全二叉樹 深度為k的有n個(gè)結(jié)點(diǎn)的二叉樹，當(dāng)且僅當(dāng)其每一個(gè)結(jié)點(diǎn)都與深度為k的滿二叉樹中編號(hào)從1至n的結(jié)點(diǎn)一一對(duì)應(yīng)時(shí)，成為完全二叉樹。即除第 h 層外，其它各層 (1h-1) 的結(jié)點(diǎn)數(shù)都達(dá)到最大個(gè)數(shù)，第 h 層所有的結(jié)點(diǎn)都連續(xù)集中在最左邊。ABCD17. 實(shí)現(xiàn)任意二叉樹的后序遍歷的非遞歸算法而不使用棧結(jié)構(gòu)，最佳方案

6、是二叉樹采用（）存儲(chǔ)結(jié)構(gòu)。A. 二叉鏈表B. 廣義表存儲(chǔ)結(jié)構(gòu)C. 三叉鏈表 三叉鏈表是二叉樹的另一種主要的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。三叉鏈表與二叉鏈表的主要區(qū)別在于，它的結(jié)點(diǎn)比二叉鏈表的結(jié)點(diǎn)多一個(gè)指針域，該域用于存儲(chǔ)一個(gè)指向本結(jié)點(diǎn)雙親的指針。三叉鏈表的結(jié)點(diǎn)形式如下D. 順序存儲(chǔ)結(jié)構(gòu)18. 樹最適合用來表示（）。A. 有序數(shù)據(jù)元素B. 無序數(shù)據(jù)元素C. 元素之間具有分支層次關(guān)系的數(shù)據(jù)D. 元素之間無聯(lián)系的數(shù)據(jù)19. 某二叉樹結(jié)點(diǎn)的中序序列為A.B.C.D.E.F.G，后序序列為B.D.C.A.F.G.E，則其左子樹中結(jié)點(diǎn)數(shù)目為（）。A. 3B. 2C. 4D. 520. 二叉樹是非線性數(shù)據(jù)結(jié)構(gòu)，所以（）。A

7、.它不能用順序存儲(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)都不能使用 21. 具有n(n>0)個(gè)結(jié)點(diǎn)的完全二叉樹的深度 K層完全二叉樹，就是前（K-1）層為滿二叉樹，第K層均為葉結(jié)點(diǎn)，可以不滿。所以結(jié)點(diǎn)與深度的關(guān)系為：2K-1-1<n 2K-1。所以K = log2(n) +1為（）。A. log2(n)B. 10（log2(n)）+1C. log2(n) +1D. log2(n)+122. 把一棵樹轉(zhuǎn)換為二叉樹后，這棵二叉樹的形態(tài)是（）。A.唯一的B.有多種C.有多種，但根結(jié)點(diǎn)都沒有左孩子D.有多種，但根結(jié)

8、點(diǎn)都沒有右孩子23. 線索二叉樹是一種（）結(jié)構(gòu) 邏輯結(jié)構(gòu)：集合、線性、樹和圖物理結(jié)構(gòu)：線性存儲(chǔ)和非線性存儲(chǔ) 線性存儲(chǔ)結(jié)構(gòu)有順序、鏈接、索引、散列4種結(jié)構(gòu) 非線性存儲(chǔ)結(jié)構(gòu)有：樹形存儲(chǔ)結(jié)構(gòu)、圖形存儲(chǔ)結(jié)構(gòu)。A 邏輯B 邏輯和存儲(chǔ)C 物理D線性24. 將一棵有100個(gè)結(jié)點(diǎn)的完全二叉樹從根這一層開始，每一層從左到右依次對(duì)結(jié)點(diǎn)進(jìn)行編號(hào)，根結(jié)點(diǎn)編號(hào)為1，則編號(hào)為49的結(jié)點(diǎn)的左孩子的編號(hào)為（）。 A.98B.99C.50D.4825. 設(shè)森林F中有三棵樹，第一.第二和第三棵樹的結(jié)點(diǎn)個(gè)數(shù)分別為M1.M2和M3。與森林F對(duì)應(yīng)的二叉樹根結(jié)點(diǎn)的右子樹上的結(jié)點(diǎn)個(gè)數(shù)是（）。AM1BM1+M2CM3DM2+M326. 將一

9、棵有100個(gè)結(jié)點(diǎn)的完全二叉樹從根開始，每一層從左到右依次對(duì)結(jié)點(diǎn)進(jìn)行編號(hào)，根結(jié)點(diǎn)編號(hào)為1，則編號(hào)最大的非葉結(jié)點(diǎn)的編號(hào)為（）。 A.48B.49C.50D.5127. 引入二叉線索樹的目的是（）。A.加快查找結(jié)點(diǎn)的前驅(qū)或后繼的速度B.為了能在二叉樹中方便的進(jìn)行插入與刪除C.為了能方便的找到雙親     D.使二叉樹的遍歷結(jié)果唯一28. 若一棵二叉樹具有10個(gè)度為2的結(jié)點(diǎn)，5個(gè)度為1的結(jié)點(diǎn)，則度為0的結(jié)點(diǎn)個(gè)數(shù)是（）。 二叉樹有如下性質(zhì)：N0 = N2 +1，葉子節(jié)點(diǎn)個(gè)數(shù)等于度為2的節(jié)點(diǎn)個(gè)數(shù)+1A9B11C15D不確定 29. 一棵樹深度為K的完全二叉樹至少有（

10、）個(gè)結(jié)點(diǎn)A2k 1B. 2k-1-1C. 2k-1D. 2k30. 一棵二叉樹的前序遍歷序列為ABCDEFG，它的中序遍歷序列可能是（）。ACABDEFGBABCDEFGCDACEFBGDADCFEG  31. 有關(guān)二叉樹下列說法正確的是（）。A二叉樹的度為2B一棵二叉樹的度可以小于2C二叉樹中至少有一個(gè)結(jié)點(diǎn)的度為2D二叉樹中任何一個(gè)結(jié)點(diǎn)的度都為232. 一個(gè)具有1025個(gè)結(jié)點(diǎn)的二叉樹的高h(yuǎn)為（）。A11B10C11至1025之間D10至1024之間33. 對(duì)于有n 個(gè)結(jié)點(diǎn)的二叉樹, 其高度為（）。Anlog2nBlog2nCëlog2n+1D不確定34. 已知某

11、二叉樹的后序遍歷序列是dabec, 中序遍歷序列是debac ,它的先序遍歷是（）。AacbedBdecabCdeabcDcedba   35. 若二叉樹采用二叉鏈表存儲(chǔ)結(jié)構(gòu)，要交換其所有分支結(jié)點(diǎn)左.右子樹的位置，利用（）遍歷方法最合適。A前序B中序C后序D按層次36. 在下列存儲(chǔ)形式中，（）一個(gè)不是樹的存儲(chǔ)形式？ A雙親表示法B孩子鏈表表示法 C孩子兄弟表示法D順序存儲(chǔ)表示法37. 在下列關(guān)于二叉樹的敘述中，正確的是（）。只有一個(gè)結(jié)點(diǎn)的二叉樹度為0; 二叉樹的度為2； 二叉樹的左右子樹可任意交換;深度為K的完全二叉樹的結(jié)點(diǎn)個(gè)數(shù)小于或等于深度相同的滿二叉樹。ABC

12、D38. 若x是二叉中序線索樹中一個(gè)不為根的有左孩子的結(jié)點(diǎn)則x的前驅(qū)為（）。A.X的雙親B.X的右子樹中最左的結(jié)點(diǎn) C.X的左子樹中最右結(jié)點(diǎn)D.X的左子樹中最右葉結(jié)點(diǎn) 39. 在二叉樹結(jié)點(diǎn)的先序序列，中序序列和后序序列中，所有葉子結(jié)點(diǎn)的先后順序（）。A都不相同B完全相同C先序和中序相同，而與后序不同D中序和后序相同，而與先序不同40. 在線索化二叉樹中，t所指結(jié)點(diǎn)沒有右子樹的充要條件是（）。A.t->Rtag=1 rtag=1 時(shí)rchild指向后繼；ltag=0 時(shí)lchild指向左子女；ltag=1 時(shí)lchild指向前驅(qū)；rtag=0 時(shí)rchild指向右子女；

13、B.t->Rchild=NULLC.t->Rtag=1 && t->Rchild=NULLD.以上都不對(duì)41. 設(shè)高度為h的二叉樹上只有度為0和度為2的結(jié)點(diǎn)，則此類二叉樹中所包含的結(jié)點(diǎn)數(shù)至少為（）。A2hB2h-1C2h+1Dh+142. 如右圖所示二叉樹的中序遍歷序列是（）。AabcdgefBdfebagcCdbaefcgDdefbagc43. 設(shè)a和b為一棵二叉樹上的兩個(gè)結(jié)點(diǎn)，在中序遍歷時(shí)a在b前的條件是（）。Aa是b的左孩子Bb是a的右孩子Ca是b左子樹上結(jié)點(diǎn)或b是a右子樹上結(jié)點(diǎn)D以上三項(xiàng)均可44. 假定在一棵二叉樹中，雙分支結(jié)點(diǎn)數(shù)為15，單分支結(jié)點(diǎn)數(shù)為

14、30，則葉子結(jié)點(diǎn)數(shù)為（）個(gè)。A45B15C16D3145. 設(shè)哈夫曼樹中的葉子結(jié)點(diǎn)總數(shù)為m，若用二叉鏈表作為存儲(chǔ)結(jié)構(gòu)，則該哈夫曼樹中總共有（）個(gè)空指針域。A2m-1B2mC2m+1D4m46. 二叉樹的第k層的結(jié)點(diǎn)數(shù)最多為（）。A2k-1B2K+1C2K-1D2K-147. 設(shè)某棵二叉樹中有2000個(gè)結(jié)點(diǎn)，則該二叉樹的最小高度為（）。A9B10C11D1248. 一棵有n個(gè)結(jié)點(diǎn)的樹，在把它轉(zhuǎn)換成對(duì)應(yīng)的二叉樹后，該二叉樹根結(jié)點(diǎn)的左子樹上共有（）個(gè)結(jié)點(diǎn)。An-2Bn-1Cn+1Dn+249. 對(duì)于一棵深度為4的三叉樹，最多有（）個(gè)結(jié)點(diǎn)。A30B36C40D5450. 設(shè)結(jié)點(diǎn)A有3個(gè)兄弟結(jié)點(diǎn)且結(jié)點(diǎn)B

15、為結(jié)點(diǎn)A的雙親結(jié)點(diǎn)，則結(jié)點(diǎn)B的度數(shù)數(shù)為（）。A3B4C5D151. 關(guān)于哈夫曼樹，下列說法正確的是( )。A在哈夫曼樹中，權(quán)值相同的葉子結(jié)點(diǎn)都在同一層上B在哈夫曼樹中，權(quán)值較大的葉子結(jié)點(diǎn)一般離根結(jié)點(diǎn)較遠(yuǎn)C哈夫曼樹是帶權(quán)路徑長(zhǎng)度最短的樹，路徑上權(quán)值較大的結(jié)點(diǎn)離根較近D在哈夫曼編碼中，當(dāng)兩個(gè)字符出現(xiàn)頻率相同時(shí)，其編碼也相同，對(duì)于這種情況應(yīng)作特殊外理二.判斷題1. 線索二叉樹是一種邏輯結(jié)構(gòu)。（×）2. 二叉樹中每個(gè)結(jié)點(diǎn)的兩棵子樹是有序的。（） 3. 深度為K的完全二叉樹至少有2K-1個(gè)結(jié)點(diǎn)。（） 4. 在哈夫曼樹中，權(quán)值最小的結(jié)點(diǎn)離根結(jié)點(diǎn)最近。（×）5. 二叉樹中每個(gè)結(jié)點(diǎn)的兩棵子

16、樹的高度差等于1。 （×） 6. 具有12個(gè)結(jié)點(diǎn)的完全二叉樹有5個(gè)度為2的結(jié)點(diǎn)。（）7. 二叉樹中每個(gè)結(jié)點(diǎn)有兩棵非空子樹或有兩棵空子樹。（×）8. 哈夫曼樹中沒有度為1的結(jié)點(diǎn)，所以必為滿二叉樹。（×）9. 二叉樹中所有結(jié)點(diǎn)個(gè)數(shù)是2k-1-1，其中k是樹的深度。（×）10. 二叉樹的遍歷操作實(shí)際上是將非線性結(jié)構(gòu)線性化的過程。（）11. 具有n個(gè)結(jié)點(diǎn)的滿二叉樹，其葉結(jié)點(diǎn)的個(gè)數(shù)為（n+1）/2。（）12. 前序和中序遍歷用線索樹方式存儲(chǔ)的二叉樹，不必使用棧。（）13. 樹的先根遍歷序列與其所轉(zhuǎn)化的二叉樹的先序遍歷序列相同。（）14. 樹的后根遍歷序列與其所轉(zhuǎn)化

17、的二叉樹的后序遍歷序列相同。（×）15. 由于二叉樹中每個(gè)結(jié)點(diǎn)的度最大為2，所以二叉樹是一種特殊的樹。（×） 16. 二叉樹中所有結(jié)點(diǎn)，如果不存在非空左子樹，則不存在非空右子樹。（×） 17. 哈夫曼樹是帶權(quán)路徑長(zhǎng)度最短的樹，路徑上權(quán)值較大的點(diǎn)離根較遠(yuǎn)。（×）18. 二叉樹的前序遍歷序列中，任意一個(gè)結(jié)點(diǎn)均處在其子女結(jié)點(diǎn)的前面。（）19. 在二叉樹結(jié)點(diǎn)的先序序列和后序序列中，所有葉子結(jié)點(diǎn)的先后順序完全相同。（）20. 用二叉鏈表法存儲(chǔ)包含n個(gè)結(jié)點(diǎn)的二叉樹，結(jié)點(diǎn)的2n個(gè)指針區(qū)域中有n+1個(gè)為空指針。（）21. 對(duì)于一棵非空二叉樹，它的根結(jié)點(diǎn)作為第一層，則它的

18、第i層上最多能有2i1個(gè)結(jié)點(diǎn)。（×）22. 若二叉樹用二叉鏈表作存貯結(jié)構(gòu)，則在n個(gè)結(jié)點(diǎn)的二叉樹鏈表中只有n1個(gè)非空指針域。（）三.填空題1. 由個(gè)結(jié)點(diǎn)所構(gòu)成的二叉樹有種形態(tài)。 2. 線索二叉樹的左線索指向其，右線索指向其。3. 一棵具有257個(gè)結(jié)點(diǎn)的完全二叉樹，它的深度為。4. 如某二叉樹有20個(gè)葉子結(jié)點(diǎn)，有30個(gè)結(jié)點(diǎn)僅有一個(gè)孩子，則該二叉樹的總結(jié)點(diǎn)數(shù)為。5. 設(shè)一棵完全二叉樹具有1000個(gè)結(jié)點(diǎn)，則此完全二叉樹有個(gè)葉子結(jié)點(diǎn)，有個(gè)度為2的結(jié)點(diǎn)，有個(gè)結(jié)點(diǎn)只有非空左子樹，有 個(gè)結(jié)點(diǎn)只有非空右子樹。6. 一棵含有n個(gè)結(jié)點(diǎn)的k叉樹，可能達(dá)到的最大深度為，最小深度為 。7. 若已知一棵二叉樹的前

19、序序列是BEFCGDH，中序序列是FEBGCHD，則它的后序序列必是。 8. 在二叉樹中，指針p所指結(jié)點(diǎn)為葉子結(jié)點(diǎn)的條件是。9. 有一棵樹如右圖所示，回答下面的問題：1) 這棵樹的根結(jié)點(diǎn)是；2) 這棵樹的葉子結(jié)點(diǎn)是；3) 結(jié)點(diǎn)k3的度是；4) 這棵樹的度是；5) 這棵樹的深度是；6) 結(jié)點(diǎn)k3的子女是；7) 結(jié)點(diǎn)k3的父結(jié)點(diǎn)是；10. 指出樹和二叉樹的三個(gè)主要差別：。11. 從概念上講，樹與二叉樹是兩種不同的數(shù)據(jù)結(jié)構(gòu)，將樹轉(zhuǎn)化為二叉樹的基本目的是。12. 一棵二叉樹的結(jié)點(diǎn)數(shù)據(jù)采用順序存儲(chǔ)結(jié)構(gòu)，存儲(chǔ)于數(shù)組t中，如下圖所示，則該二叉樹的鏈接表示形式為_。13. 深度為k的完全二叉樹至少有個(gè)結(jié)點(diǎn)。至多有個(gè)結(jié)點(diǎn)，