6.3練習(xí)題及參考答案

1、6.3練習(xí)題及參考答案6.3.1 練習(xí)題一.選擇題1 .有一“遺傳”關(guān)系：設(shè)x是y的父親，則x可以把它的屬性遺傳給y。表示該遺傳關(guān)系最合適的數(shù)據(jù)結(jié)構(gòu)為（）A. 向量B. 樹C. 圖D 二叉樹2樹最合適用來表示（）A. 有序數(shù)據(jù)元素C. 無序數(shù)據(jù)元素B. 元素之間具有分支層次關(guān)系的數(shù)據(jù)D. 元素之間無聯(lián)系的數(shù)據(jù) .3.樹B的層號(hào)表示為1a,2b,3d,3e,2c,對(duì)應(yīng)于下面選擇的（）A. 1a（2b（3d,3e）,2c）B.a（b（D.,e）,c）C. a（b（d,e）,c）D.a（b,d（e）,c）4. 對(duì)二叉樹的結(jié)點(diǎn)從1 開始連續(xù)編號(hào)，要求每個(gè)結(jié)點(diǎn)的編號(hào)大于其左，右孩子的編號(hào)，同一結(jié)點(diǎn)的左，

2、右孩子中，其左孩子編號(hào)小于其右孩子編號(hào)，則可采用（）次序的遍歷實(shí)現(xiàn)二叉樹的結(jié)點(diǎn)編號(hào)。A. 先序 B. 中序 C. 后序 D. 從根開始按層次遍歷5. 假定一棵三叉樹的結(jié)點(diǎn)為50，則它的最小高度為（）A. 3 B. 4 C 5 D 66. 在一棵具有 K 層的滿三叉樹中，結(jié)點(diǎn)總數(shù)為（）A. （3k-1）/2B. 3k-1C. （3k-1）/3 D. 3k7. 按照二叉樹的定義，具有3 個(gè)結(jié)點(diǎn)的二叉樹有（）種。A. 3 B. 4 C. 5 D. 6 8在一棵有n個(gè)結(jié)點(diǎn)的二叉樹中，若度為 2的結(jié)點(diǎn)數(shù)為n2,度為一的結(jié)點(diǎn)數(shù)為 n1,度為0的；樹的最小高度為（）,其葉結(jié)點(diǎn)結(jié)點(diǎn)數(shù)為n0,則樹的最大高度為（

3、），其葉結(jié)點(diǎn)數(shù)為（）數(shù)為（ ）；若采用鏈表存儲(chǔ)結(jié)構(gòu)，則有（）個(gè)空鏈域。A. n/2B. log 2 n+1C . log2 n D. nE n0 + n1 + n2F. n1 + n2 G. n2+ 1H. 1I. n + 1 J. n1 K. n2 L. n1 + 1n個(gè)結(jié)點(diǎn)，深度為h,則C. m = h -1 D. n = 2h（）。-19. 對(duì)一個(gè)滿二叉樹, m 個(gè)樹葉,A. n = h + m B. h + m = 2n10. 設(shè)高度為 h 的二叉樹中只有度為 0 和度為 2 的結(jié)點(diǎn),則此類二叉樹中所包含的結(jié)點(diǎn)數(shù)至 少為（）,至多為（） 。F.2h-1 G. 2h+1 +1 H.2h+

4、1A. 2h B. 2h -1 C. 2h + 1 D. h +1 E. 2h-111. 在一棵二叉樹上第 5 層的結(jié)點(diǎn)數(shù)最多為（） 。（假設(shè)根結(jié)點(diǎn)的層數(shù)為 0）A. 8 B. 16 C. 15 D. 3212. 深度為 5 的二叉樹至多有（） 個(gè)結(jié)點(diǎn)。A. 16 B. 32 C. 31 D. 1013. 一棵有 124 個(gè)葉結(jié)點(diǎn)的完全二叉樹,最多有（） 個(gè)結(jié)點(diǎn)。A. 247 B. 248 C. 249 D. 250 E. 25114. 含有 129 個(gè)葉結(jié)點(diǎn)的完全二叉樹,最多有（）個(gè)結(jié)點(diǎn)。A. 254 B.255 C.256 D. 257 E. 25815. 假定在一棵二叉樹中,雙分支結(jié)點(diǎn)數(shù)

5、為15,單分支結(jié)點(diǎn)數(shù)為 30 個(gè),則葉子結(jié)點(diǎn)數(shù)為（）個(gè)。A. 15 B. 16 C. 17 D. 47R1n中，結(jié)點(diǎn)Ri若有左16用順序存儲(chǔ)的方法將完全二叉樹中所有結(jié)點(diǎn)逐層存放在數(shù)組 子樹，則左子樹是結(jié)點(diǎn)（）。A.R2i+1 B. R2i C. Ri/2 D. R2i -117.在一非空二叉樹的中序遍歷序列中，根結(jié)點(diǎn)的左邊（）A .只有右子樹上的所有結(jié)點(diǎn)B.只有右子樹上的部分結(jié)點(diǎn)C.只有左子樹上的部分結(jié)點(diǎn)D.只有左子樹上的所有結(jié)點(diǎn)18 .任何一棵二叉樹的葉結(jié)點(diǎn)在先序，中序和后序遍歷中的相對(duì)次序（）。A 不發(fā)生改變B.發(fā)生改變 C.不能確定D.以上都不對(duì)19. 設(shè)n,m為一棵樹上的兩個(gè)結(jié)點(diǎn)，在中

6、序遍歷時(shí)，n在m前的條件是（）。A. n在m右方 B。 n是m祖先 C。 n在m左方 D。n是m 子孫20. 一棵完全二叉樹按層次遍歷的序列為ABCDEFGHI，則在先序遍歷中結(jié)點(diǎn)E的直接前趨為（），后序遍歷中結(jié)點(diǎn)B的直接后繼是（）。（1） B（ 2） D（ 3） A （4） I （5） F （6） C21. 已知某二叉樹的后序遍歷是d a b e c，中序遍歷序列是 d e b a c，它的前序遍歷序列是（）。A. acbed B. decab C. deabc D .cedba22. 若二叉樹采用二叉鏈表作存儲(chǔ)結(jié)構(gòu)，要交換其所有分支結(jié)點(diǎn)左右子樹的位置，利用（） 遍歷方法最合適。A前序 B。

7、中序 C后序 D層次23. 欲實(shí)現(xiàn)任意二叉樹的后序遍歷的非遞歸算法而不必使用棧結(jié)構(gòu)，最佳方案是二叉樹采用 （）存儲(chǔ)結(jié)構(gòu)。A三叉鏈表B。廣義表C。二叉鏈表 Do 順序24. 在線索化二叉樹中，T所指結(jié)點(diǎn)沒有左子樹的充要條件是（）。A.T left = NULL B. T Itag = 1 C. T Itag =1 且 T left = NULL D 以上都不對(duì)25. 線索二叉樹是一種（）結(jié)構(gòu)。A。邏輯 Bo邏輯和存儲(chǔ)C。物理D線性26. 將圖6-6中的二叉樹按中序線索化，結(jié)點(diǎn)X的右指針和Y的左指針分別指向（）。（1） A , D （2） B,C （3）D,A（4） C, A27.在下列三次次序的

8、線索二叉樹中（），對(duì)查找指定結(jié)點(diǎn)在該在次序下的后繼效果較差。28.A .前序線索樹B。中序線索樹C后序線索樹設(shè)中序線索二叉樹T是按lchild- rchild表示法存儲(chǔ)，欲確定T中結(jié)點(diǎn)p在前提下的后繼，下述說法不正確的是（）A .若p有左子女，則該后繼為p的左子女B. 若p無左子女且有右子女，則該后繼為p的右子女C. 若p無左子女且無右子女，則該后繼為p的右線索所指結(jié)點(diǎn)D. 若p無左子女，從結(jié)點(diǎn) p開始，追綜rchild鏈，直到rchild不是線索，則這時(shí)rchid （不為NULL的話）所指結(jié)點(diǎn)為該后繼。29. 樹的基本遍歷策略可分為先根遍歷和后根遍歷；二叉樹的基本遍歷策略可分為先序遍歷，中序

9、遍歷和后序遍歷。這里，把由樹轉(zhuǎn)化得到的二叉樹叫做這棵樹對(duì)應(yīng)得二叉樹。下面結(jié)論正確的是（）。A 樹的先根遍歷序列與其對(duì)應(yīng)的二叉樹的先序遍歷序列相同B 樹的后序遍歷序列與其對(duì)應(yīng)的二叉樹的后序遍歷序列相同C.樹的先根遍歷序列與其對(duì)應(yīng)的二叉樹的中序遍歷序列相同D .以上都不對(duì)30. 如果T2是由有序樹T轉(zhuǎn)換而來的二叉樹，那么T中結(jié)點(diǎn)的前序就是 T2中結(jié)點(diǎn)的（）。 A.前序 B。中序 Co后序 D層次序31. 如果T2是由有序樹T轉(zhuǎn)換而來的二叉樹，那么T中結(jié)點(diǎn)的后序就是 T2中結(jié)點(diǎn)的（）。 A.前序 B。中序 Co后序 D層次序32. 如圖6-7所示的t2是由有序樹t1轉(zhuǎn)化而來的二叉樹，那么樹 t1有（

10、）個(gè)葉結(jié)點(diǎn)。A 4 B 5 C 6 D 733. 設(shè)T是哈夫曼樹，具有 5個(gè)葉結(jié)點(diǎn)，樹T的高度最高可以是（）。A 1 B。2 C o 3D4E. 5 F 634. 由帶權(quán)為8, 2, 5, 7的四個(gè)葉子結(jié)點(diǎn)構(gòu)造一棵哈夫曼樹，該樹的帶權(quán)路徑長度為（）。A。23 B. 37 C. 46 D . 4335. 若只考慮有序樹的情形，則具有7個(gè)結(jié)點(diǎn)的不同形態(tài)的樹共有（）種。A .132 B. 154. C. 429 D. 前三者均不正確36. 樹的后根遍歷序列等同于該樹對(duì)應(yīng)的二叉樹的（）A.先序遍歷E。中序遍歷Co后序遍歷D。層次遍歷二. 填空題1.在樹形結(jié)構(gòu)中，樹根結(jié)點(diǎn)沒有 結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)有且只有

11、 個(gè)前趨結(jié)點(diǎn)；葉子結(jié)點(diǎn)沒有 結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)的后繼結(jié)點(diǎn)可以 。2 .有一棵樹如圖6-8所示，回答下面的問題。這棵樹的根點(diǎn)是 ;這棵樹的葉子結(jié)點(diǎn)是 ;結(jié)點(diǎn)k3的度是；這棵樹的度為;這棵樹的深度為 ;結(jié)點(diǎn)k3的子女是;結(jié)點(diǎn)k3的父結(jié)點(diǎn)是3 假定一棵樹的廣義表表示為 A(B(E),C(F(H,I,J),G),D),則該樹的度為；樹的深度為,終端結(jié)點(diǎn)的個(gè)數(shù)為 ，單分支結(jié)點(diǎn)的 個(gè)數(shù)為 ，雙分支結(jié)點(diǎn)的個(gè)數(shù)為 ，三分支結(jié)點(diǎn)的個(gè)數(shù)為 ,C結(jié)點(diǎn)的雙親結(jié)點(diǎn)為 ，其孩子結(jié)點(diǎn)為 和 結(jié)點(diǎn)。4. 設(shè)樹T中除葉結(jié)點(diǎn)外，任意結(jié)點(diǎn)的度數(shù)是3，則T的第i層結(jié)點(diǎn)的個(gè)數(shù)為 。(假設(shè)根結(jié)點(diǎn)的層數(shù)為 1)5. 一棵深度為h的滿k叉樹

12、有如下性質(zhì)：第 h層上的節(jié)點(diǎn)都是葉子結(jié)點(diǎn)，其余各層上 的每個(gè)結(jié)點(diǎn)都有k棵非空子樹。如果按層次順序從 1開始對(duì)全部結(jié)點(diǎn)編號(hào)，則第i層上的結(jié)點(diǎn)數(shù)目是 ;編號(hào)為n的結(jié)點(diǎn)的雙親結(jié)點(diǎn)(若存在)的編號(hào)是 ;編號(hào)為n的結(jié)點(diǎn)的第i個(gè)孩子結(jié)點(diǎn)(若存在)的編號(hào)是，編號(hào)為n的結(jié)點(diǎn)有右兄弟的條件是，其右兄弟的編號(hào)是。6. 在具有n(n 1)個(gè)結(jié)點(diǎn)的k叉樹中，有 個(gè)空指針。7 .一棵含有n個(gè)結(jié)點(diǎn)的k叉樹，可能達(dá)到的最大深度為_，最小深度為 。& 一棵深度為k的滿二叉樹的結(jié)點(diǎn)總數(shù)為 ，一棵深度為k的完全二叉樹的結(jié)點(diǎn)總數(shù)的最小值是 ，從左到右次序給結(jié)點(diǎn)編號(hào)(從 1開始)則編號(hào)最小的葉子結(jié)點(diǎn)的編號(hào)為，最大值是.9. 由a,b

13、,c三個(gè)結(jié)點(diǎn)構(gòu)成的二叉樹，共有 種不同的結(jié)構(gòu)。10. 設(shè)根結(jié)點(diǎn)的層次數(shù)為0,定義樹的高度為樹中層次最大的結(jié)點(diǎn)的層次加1 ,則高度為k的二叉樹具有的結(jié)點(diǎn)數(shù)目，最少為 ,最多是.11. N個(gè)結(jié)點(diǎn)的完全二叉樹，按從上到下的，從左到右給結(jié)點(diǎn)順序編號(hào)，則編號(hào)最大的非葉結(jié)點(diǎn)編號(hào)為，編號(hào)最小的葉結(jié)點(diǎn)為。12. 在一棵二叉樹中，度為0的結(jié)點(diǎn)個(gè)數(shù)為n0,度為2的結(jié)點(diǎn)個(gè)數(shù)為n2,則n0=.13. 棵二叉樹的第i (i 1)層最多有 個(gè)結(jié)點(diǎn)，一棵樹有n(n0)個(gè)結(jié)點(diǎn)的 滿二叉樹共有個(gè)葉子和_非最高非終端結(jié)點(diǎn)。14. 一棵完全二叉樹的第5層有5個(gè)結(jié)點(diǎn)，則共有 個(gè)結(jié)點(diǎn)，其中度為1的結(jié)點(diǎn)有個(gè)，度為0的結(jié)點(diǎn)有 個(gè)。15 .

14、具有n個(gè)結(jié)點(diǎn)的完全二叉樹，其葉結(jié)點(diǎn)的個(gè)數(shù)是 .16. 對(duì)一棵具有 n個(gè)結(jié)點(diǎn)的二叉樹，當(dāng)進(jìn)行鏈接存儲(chǔ)時(shí)，其二叉鏈表中的指針域的總數(shù)為個(gè)，其中 個(gè)用于連接孩子結(jié)點(diǎn)， 個(gè)空閑著。17. 對(duì)于一棵具有 n個(gè)結(jié)點(diǎn)的二叉樹，當(dāng)它為一棵 二叉樹時(shí)具有最小高度，高度為，當(dāng)它為一棵單支樹具有 高度，高度為 。18. 樹所對(duì)應(yīng)得二叉樹其根結(jié)點(diǎn)的 子樹一定為空。19. 從概念上講，樹與二叉樹是兩種不同的數(shù)據(jù)結(jié)構(gòu)，將樹轉(zhuǎn)化成二叉樹的基本目標(biāo)是.20. 結(jié)點(diǎn)最少的樹為 ，結(jié)點(diǎn)最少的二叉樹是 .21. 設(shè)根結(jié)點(diǎn)的層次數(shù)為 0，定義樹的高度為樹中層次最大的結(jié)點(diǎn)層次加1,則高度 為k,內(nèi)部結(jié)點(diǎn)的度數(shù)為 1的二叉樹有 棵。22

15、. 一棵完全二叉樹按層次遍歷的序列為ABCDEFGHI,則在先序遍歷中結(jié)點(diǎn) E的直接前趨為，后序遍歷中結(jié)點(diǎn)B的直接后繼是.。23. 某二叉樹的中序遍歷序列為 ABCDEFG，后序序列為 BDCAFGE，則該二叉樹結(jié)點(diǎn)的前序序列為,該二叉樹對(duì)應(yīng)的森林包括 棵樹。24. 用一維數(shù)組存放的一棵完全二叉樹如圖所示。123456789101112ABCDEFGHIJKL則后序遍歷該二叉樹時(shí)結(jié)點(diǎn)訪問的順序?yàn)?25. 在一棵二叉排列樹上按 遍歷得到的結(jié)點(diǎn)序列是一個(gè)有序序列。26. 由n個(gè)權(quán)值構(gòu)成的哈夫曼樹共有 個(gè)結(jié)點(diǎn)。27. 由帶權(quán)為3, 9, 6, 2, 5的5個(gè)葉子結(jié)點(diǎn)構(gòu)成一棵哈夫曼樹，則帶權(quán)路徑長度為

16、 28. 設(shè)F是一個(gè)森林，B是由F轉(zhuǎn)換得到的二叉樹，F(xiàn)中有n個(gè)非終端結(jié)點(diǎn)，則B中右指針 域?yàn)榭盏慕Y(jié)點(diǎn)有個(gè)。6.3.2練習(xí)題參考答案一. 選擇題1. B2. B3. C4. C5. C6. A7. C 8. E,G,B,G,I 9. D10. B ,F 11. B12. C13. B14. D15. B16. B17. A18.A19. C 20.(5)21. D22. C23. A24. B25.C26. (3)27. C28. C29. A30. A31. B 32. C 33. D ,E34. D 35.A36.B.填空1.前趨；1;后繼；任意多個(gè)。2. k1 k2,k5,k7,k423 4 k5, k6 k13. 346114. 3i-1i 1 n 2 k5. ki- (n-1)*k+i+1i 工 nk+1(n=0,1,2,) n+1k6. n(k-1) +17. n , logk(n( k-1)+1)8. 2k-1 2k-1 2k-