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的層號表示為1a,2b,3d,3e,2c,對應(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. 對二叉樹的結(jié)點從1 開始連續(xù)編號，要求每個結(jié)點的編號大于其左，右孩子的編號，同一結(jié)點的左，

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

3、），其葉結(jié)點數(shù)為（）數(shù)為（ ）；若采用鏈表存儲結(jié)構(gòu)，則有（）個空鏈域。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個結(jié)點，深度為h,則C. m = h -1 D. n = 2h（）。-19. 對一個滿二叉樹, m 個樹葉,A. n = h + m B. h + m = 2n10. 設(shè)高度為 h 的二叉樹中只有度為 0 和度為 2 的結(jié)點,則此類二叉樹中所包含的結(jié)點數(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é)點數(shù)最多為（） 。（假設(shè)根結(jié)點的層數(shù)為 0）A. 8 B. 16 C. 15 D. 3212. 深度為 5 的二叉樹至多有（） 個結(jié)點。A. 16 B. 32 C. 31 D. 1013. 一棵有 124 個葉結(jié)點的完全二叉樹,最多有（） 個結(jié)點。A. 247 B. 248 C. 249 D. 250 E. 25114. 含有 129 個葉結(jié)點的完全二叉樹,最多有（）個結(jié)點。A. 254 B.255 C.256 D. 257 E. 25815. 假定在一棵二叉樹中,雙分支結(jié)點數(shù)

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

6、序遍歷時，n在m前的條件是（）。A. n在m右方 B。 n是m祖先 C。 n在m左方 D。n是m 子孫20. 一棵完全二叉樹按層次遍歷的序列為ABCDEFGHI，則在先序遍歷中結(jié)點E的直接前趨為（），后序遍歷中結(jié)點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. 若二叉樹采用二叉鏈表作存儲結(jié)構(gòu)，要交換其所有分支結(jié)點左右子樹的位置，利用（） 遍歷方法最合適。A前序 B。

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

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

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

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

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

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

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

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

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

16、 28. 設(shè)F是一個森林，B是由F轉(zhuǎn)換得到的二叉樹，F(xiàn)中有n個非終端結(jié)點，則B中右指針 域為空的結(jié)點有個。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;后繼；任意多個。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-