《數(shù)據(jù)結(jié)構(gòu)》習(xí)題集：第6章-樹和二叉樹

1、數(shù)據(jù)結(jié)構(gòu)課后練習(xí)題第 6章 樹和二叉樹6 章 樹和二叉樹一、選擇題有“遺傳關(guān)系設(shè)是的父親x可以把它的屬性遺傳表示該遺傳關(guān)系最適合的數(shù)據(jù)結(jié)構(gòu)（ B）A、向量B、樹C、圖D、二叉樹樹最適合用來表示（ B）A、有序數(shù)據(jù)元素BC、無序數(shù)據(jù)元素D、元素之間無聯(lián)系的數(shù)據(jù)樹B 的層號表示1a,2b,3d,3e,2c，對應(yīng)于下面選擇的（ C）A1a(2b(3d,3e),2c)B、a(b(D,e),c)C、a(b(d,e),c)D、a(b,d(e),c)對二叉樹的結(jié)點1 開始連續(xù)編號，要求每個結(jié)點的編號大于其左、右孩子的編號，同一結(jié)點的左右孩子中其左孩子的編號小于其右孩子的編號，則可采用（ C）次序的遍歷實現(xiàn)二

2、叉樹的結(jié)點編號。A、先序B、中序C、后序D、從根開始按層次遍歷3 個結(jié)點的二叉樹有 ）種。A3B、4C、5D、62n1n0n210度為（ E），其葉結(jié)點數(shù)為（ H ）；樹的最小高度為（ B ），其葉結(jié)點數(shù)為（ G ）；若采用鏈表存儲結(jié)構(gòu)，則有（ I ）個空鏈域。An/2B、n+1C、lognD、n22E、n +n +nF、n +nG、n +1H、1012122I、n+1J、nK、nL、n +1121對一棵滿二叉樹 個樹葉，n 個結(jié)點，深度h，則（ D）An=m+hBh+m=2nC、m=h-1D、n=2h-1設(shè)高度h 的二叉樹中只有度0 和度2 的結(jié)點，則此類二叉樹中所包含的結(jié)點數(shù)至少為（ B）

3、，至為（D）。A2hB2h-1C、2h-1D、2h-15 層的結(jié)點數(shù)最多為1）A8B16C15D、32深度5 的二叉樹至多有（ C）個結(jié)點。A16B32C31D、10124 個葉結(jié)點的完全二叉樹，最多有 ）個結(jié)點A247B248C249D、250含有129 個葉子結(jié)點的完全二叉樹，最少有（ D）個結(jié)點A254B255C256D、257假定有一棵二叉樹，雙分支結(jié)點數(shù)15，單分支結(jié)點數(shù)30，則葉子結(jié)點數(shù)為（ B）個。A15B16C17D、47R1nRi若有左子樹，則左子樹是結(jié)北京理工大學(xué)珠海學(xué)院計算機學(xué)院 “數(shù)據(jù)結(jié)構(gòu)”課程組編制 2011-3-11/7數(shù)據(jù)結(jié)構(gòu)課后練習(xí)題第 6章 樹和二叉樹點（ B

4、 ）。AR2i+1BR2iCRi/2DR2i-1在一棵非空二叉樹的中序遍歷序列中，根結(jié)點的右邊（A ）。A、只有右子樹上的所有結(jié)點只有右子樹上的部分結(jié)點C、只有左子樹上的所有結(jié)點D、只有左子樹上的部分結(jié)點任何一棵二叉樹的葉結(jié)點在先序、中序和后序遍歷中的相對次序（ A）。A、不發(fā)生改變、發(fā)生改變C、不能確定D、以上都不對設(shè)n、m 前的條件是（ C ）。An在右方Bn是祖先C、n左方D、是子孫一棵完全二叉樹按層次遍歷的序列ABCDEFGHI，則在先序遍歷中結(jié)的直接前驅(qū)為（ D），后序遍歷結(jié)點的直接后繼是（ E）。A、BB、DC、AD、IE、FF、C已知某二叉樹的后序遍歷序列dabec，中序遍歷序列

5、debac，它的前序遍歷序列是）。A、acbed、decabCdeabcD、cedba若二叉樹采用二叉鏈表作存儲結(jié)構(gòu)，要交換其所有分支結(jié)點左右子樹的位置，利用（C ）遍歷方法最合適。A、前序B、中序C、后序D、層次線索二叉樹是一種（ C ）結(jié)構(gòu)。A、邏輯B、邏輯和存儲C、物理D、線性如果T2TTT2 中結(jié)點的（ A ）。A、前序B、中序C、后序D、層次序設(shè)T是哈夫曼樹，具5個葉結(jié)點，T 的高度最高可以是（ E）。A1B2C、3D、4E、5、6由帶權(quán)8，2，5，7 的四個葉子結(jié)點構(gòu)造一棵哈夫曼樹，該樹的帶權(quán)路徑長度為（D ）。A23B37C、46D、43樹的后根遍歷序列等同于該樹對應(yīng)的二叉樹的（

6、B） 。A、先序遍歷B、中序遍歷C、后序遍歷D、層次遍歷以下說法錯誤的是（ A ）。AB、線性結(jié)構(gòu)中的一個結(jié)點至多只有一個直接后繼 C、二叉樹與樹是兩種不同的數(shù)據(jù)結(jié)構(gòu)D、樹(及一切樹形結(jié)構(gòu))是一種“分支層次”結(jié)構(gòu)以下說法錯誤的是（C ）。A、二叉樹可以是空集B、二叉樹的任一結(jié)點都有兩棵子樹C、二叉樹與樹具有相同的樹形結(jié)構(gòu)D、二叉樹中任一結(jié)點的兩棵子樹有次序之分以下說法錯誤的是（ D ）。AB、在三叉鏈表上，二叉樹的求雙親運算很容易實現(xiàn)C、在二叉鏈表上，求根，求左、右孩子等很容易實現(xiàn)D、在二叉鏈表上，求雙親運算的時間性能很好以下說法錯誤的是 ）。A、一般在哈夫曼樹中，權(quán)值越大的葉子離根結(jié)點越近B

7、、哈夫曼樹中沒有度數(shù)為1 的分支結(jié)點C、若初始森林中共有n 棵二叉樹，最終求得的哈夫曼樹共有2n-1 個結(jié)點北京理工大學(xué)珠海學(xué)院計算機學(xué)院 “數(shù)據(jù)結(jié)構(gòu)”課程組編制 2011-3-12/7數(shù)據(jù)結(jié)構(gòu)課后練習(xí)題第 6章 樹和二叉樹Dn 2n-1 次合并后才能剩下一棵最終的哈夫曼樹將含41個結(jié)點的完全二叉樹從根結(jié)點開始編號，根號，后面按從上到下、從左到右的順序?qū)Y(jié)點編號那么編號21 的雙親結(jié)點編號為（ A）。A 、10B、11C、41D 、20任何一棵二叉樹的葉結(jié)點在其先根、中根、后根遍歷序列中的相對位置（C ）。A、肯定發(fā)生變化 B、有時發(fā)生變化 C、肯定不發(fā)生變化 D、無法確定下列說法正確的是（A

8、 ）。AB、樹的先根遍歷序列與其對應(yīng)的二叉樹的后序遍歷序列相同 C、樹的后根遍歷序列與其對應(yīng)的二叉樹的前序遍歷序列相同 D下列說法中正確的是（D）。A、任何一棵二叉樹中至少有一個結(jié)點的度為2 B、任何一棵二叉樹中每個結(jié)點的度都為2C、任何一棵二叉樹中的每個結(jié)點的度肯定等于2D、任何一棵二叉樹中的每個結(jié)點的度都可以小于2于右子樹上所有結(jié)點的值?，F(xiàn)采用 ）遍歷方式就可以得到這棵二叉樹所有結(jié)點的遞減序列。A、前序B、中序C、后序D、層次對含有（ B ）個結(jié)點的非空二叉樹，采用任何一種遍歷方式，其結(jié)點訪問序列均相同。A 、0B、 1C 、2D、不存在這樣的二叉樹在圖6.2 中的二叉樹中，（C ）不是完

9、全二叉樹。哈夫曼樹的帶權(quán)路徑長度是（ B）。A、所有結(jié)點權(quán)值之和B、所有葉結(jié)點帶權(quán)路徑長度之和C、帶權(quán)結(jié)點的值D、除根以外所有結(jié)點權(quán)值之和在線索二叉樹上，線索是（B ）。A、兩個標志域B、指向結(jié)點前驅(qū)和后繼的指針C、數(shù)據(jù)域D、指向左、右子樹的指針6.3CDAA 的編碼是( BA110100B11011100C010110111D11111100北京理工大學(xué)珠海學(xué)院計算機學(xué)院 “數(shù)據(jù)結(jié)構(gòu)”課程組編制 2011-3-13/7數(shù)據(jù)結(jié)構(gòu)課后練習(xí)題第 6章 樹和二叉樹6.3 所示二叉樹，A,B,C,D 7，5，2，4 則該樹的帶權(quán)路徑長度為（C ）。A46B36C35D、都不是 所指結(jié)點沒有左子樹的充要

10、條件是（B ）。A、t-lchild=NULLB、t-ltag=1 C、t-ltag=1&t-lchild=NULLD、以上都不下列敘述中正確的是（ D）。A、二叉樹是度2 的有序樹、二叉樹中結(jié)點只有一個孩子時無左右之分C、二叉樹中必有度2 的結(jié)點D、二叉樹中結(jié)點最多有兩棵子樹，并且有左右之分下圖6.4 所示的幾種結(jié)構(gòu)中屬于樹型結(jié)構(gòu)的是（ B ）。、二、判斷題XV一棵有n 個結(jié)點的d 度樹，若用多重鏈表表示，樹中每個結(jié)點都是有d 個鏈域，則在樹的n*d 個鏈域中，有n*(d-1)+1 個是空鏈域，只有 n-1 個是非空的。VVXXVXVXVXXVVVX三、填空題在樹型結(jié)構(gòu)中，樹根結(jié)點沒有（ 雙

11、親）結(jié)點，其余每個結(jié)點有且只有（ 1）個前驅(qū)結(jié)點；葉子點沒有（ 子）結(jié)點，其余每個結(jié)點的后繼結(jié)點可以（ 是結(jié)點或葉子）。北京理工大學(xué)珠海學(xué)院計算機學(xué)院 “數(shù)據(jù)結(jié)構(gòu)”課程組編制 2011-3-14/7數(shù)據(jù)結(jié)構(gòu)課后練習(xí)題第 6章 樹和二叉樹假定一棵樹的廣義表表示A（B（E），C（F（H，I，J），G），D），則該樹的度為（ 3），樹的深度（ 4終端結(jié)點的個數(shù)（6 單分支結(jié)點的個數(shù)（ 1 雙分支結(jié)點的個數(shù)（1 三分支結(jié)點的個數(shù)為（ 2 的雙親結(jié)點為（ A ），其孩子結(jié)點為（ F,G）。設(shè)T 中除葉結(jié)點外，任意結(jié)點的度數(shù)都3，的第層結(jié)點的個數(shù)為（ 3i-1）。在具n(n=1)個結(jié)點叉樹中，有（ (n-

12、1)*k+1）個空指針。一棵含個結(jié)點叉樹，可能達到的最大深度為（n ），最小深度為（2）。一棵深度k的滿二叉樹的結(jié)點總數(shù)（ 2k一棵深度的完全二叉樹的結(jié)點總數(shù)的最小值（ 從左到右次序給結(jié)點編號（開始）則編號最小的葉子結(jié)點的編號是（），最大值為（）。設(shè)根結(jié)點的層次數(shù)0，定義樹的高度為樹中層次最大的結(jié)點的層次1，則高度的二叉樹具有的結(jié)點數(shù)目最少為（2k-1），最多為（ 2k -1）。n 個結(jié)點的完全二叉樹，若按從上到下、從左到右給結(jié)點順序編號，則編號最大的非葉結(jié)點編號為（ n/2），編號最小的葉結(jié)點編號為（ n/2 +1）。在一棵二叉樹中，度的結(jié)點個數(shù)n ，度2的結(jié)點個數(shù)n ，n =（ n2+1）

13、。020層最多有（2i-1 ）n個結(jié)點的滿二叉樹共有（ (n+1)/2 ）個葉子結(jié)點和（ (n+1)/2-1）個非終端結(jié)點。一棵完全二叉樹的5層5個結(jié)點，則共有（ 20）個結(jié)點，其中度的結(jié)點有（ 1 ）個，度的點有（10 ）個。具有n 個結(jié)點的完全二叉樹，其葉子結(jié)點的個數(shù)為（ (n+1)/2）。對于一棵具個結(jié)點的二叉樹，當(dāng)進行鏈接存儲時，其二叉鏈表中的指針域的總數(shù)為（ 2n）個，其中（ n-1）個用于鏈接孩子結(jié)點，（ n+1）個空閑。對于一棵具n 個結(jié)點的二叉樹當(dāng)它為一（ 完全 二叉樹時具有最小高度高度（ log2(n+1)當(dāng)它為一棵單支樹時具有（最大 ）高度，高度為（ n）。樹所對應(yīng)的二叉樹

14、其根結(jié)點的（ 右 ）子樹一定為空。從概念上講，樹與二叉樹是兩種不同的數(shù)據(jù)結(jié)構(gòu)，將樹轉(zhuǎn)化為二叉樹的基本目的是（ 方便編程中的調(diào)用 ）。ABCDEFGHI的直接前驅(qū)為（ I ），的直接后繼為（ F ）。某二叉樹的中序遍歷序列后序序列則該二叉樹結(jié)點的前序序列（ EACBDGF 該二叉樹對應(yīng)的森林包括（2）棵樹。在一棵二叉排序樹上按（）遍歷得到的結(jié)點序列為有序序列。由n個權(quán)值構(gòu)成的哈夫曼樹共有（ 2n-1）個結(jié)點。3，9，6，2，5 的5 個葉子結(jié)點構(gòu)成一棵哈夫曼樹，則帶權(quán)路徑長度為（ 55 ）。設(shè)是由中有n（n+1 個。四、附加判斷題1.2.3.4.5.6.7.8.9.10.樹中任意結(jié)點的子樹不必是

15、有序的。（ X樹可以看成特殊的的無向圖。（ X）可以使用雙鏈表表示樹形結(jié)構(gòu)。（ V）順序存儲方式只能用于存儲線性結(jié)構(gòu)。（ X ）完全二叉樹的某結(jié)點若無左孩子，則必為葉結(jié)點。（ V）如果一個二叉樹的結(jié)點，或者沒有子樹，或者恰有兩棵非空子樹，則此二叉樹稱為完全二叉樹。（ X包含兩個結(jié)點的所有二叉樹都是相同的。（ X）二叉樹的前序遍歷序列中，任意一個結(jié)點均處在其子樹結(jié)點的前面。（ V二叉樹的前序和后序遍歷能唯一確定一棵二叉樹。（X）二叉樹按某種順序線索化后，任一結(jié)點均有指向其前驅(qū)和后繼的線索。（ X）北京理工大學(xué)珠海學(xué)院計算機學(xué)院 “數(shù)據(jù)結(jié)構(gòu)”課程組編制 2011-3-15/7數(shù)據(jù)結(jié)構(gòu)課后練習(xí)題第

16、6章 樹和二叉樹11.中序線索二叉樹中，右線索若不為空，則一定指向其父結(jié)點。（X ）五、簡答題二叉樹:1.3 二叉樹:AA/ |BCB|CAAAAA/ /BCBBBB/CCCC2.設(shè)在樹中，結(jié)點x 是結(jié)點y (x,y) 來表示邊。已知一棵樹邊的集合為：(i,j),(i,k),(b,e),(e,i),(b,d),(a,b),(c,g),(c,f),(c,h),(a,c)并回答下列問題：ak,j,d,g,f,h哪個是g 的雙親？c哪些是g 的祖先？c,a哪些是e i,k,j哪些是f g,hb j 2,553n(n0)m m-1 。6.6 所示二叉樹的二叉鏈表、三叉鏈表和順序存儲結(jié)構(gòu)。北京理工大學(xué)珠海學(xué)院計算機學(xué)院 “數(shù)據(jù)結(jié)構(gòu)”課程組編制 2011-3-16/7數(shù)據(jù)