北京理工大學(xué)數(shù)據(jù)結(jié)構(gòu)考研例題5

1、理碩教育專注于北理工考研輔導(dǎo)本資料由理碩教育整理，理碩教育是全國唯一專注于北理工考研輔導(dǎo)的學(xué)校，相對于其它機構(gòu)理碩教育有得天獨厚的優(yōu)勢。豐富的理工內(nèi)部資料資源與人力資源確保每個學(xué)員都受益匪淺，確保理碩教育的學(xué)員初試通過率89%以上，復(fù)試通過率接近100%，理碩教育現(xiàn)開設(shè)初試專業(yè)課VIP一對一，初試專業(yè)課網(wǎng)絡(luò)小班，假期集訓(xùn)營，復(fù)試VIP一對一輔導(dǎo)，復(fù)試網(wǎng)絡(luò)小班，考前專業(yè)課網(wǎng)絡(luò)小班，滿足學(xué)員不同的需求。因為專一所以專業(yè)，理碩教育助您圓北理之夢。詳情請查閱理碩教育官網(wǎng)第 5 章 樹和二叉樹課后習(xí)題講解1. 填空題 樹是n（n0）結(jié)點的有限集合，在一棵非空樹中，有（ ）個根結(jié)點，其余的結(jié)點分成m（m0

2、）個（ ）的集合，每個集合都是根結(jié)點的子樹?！窘獯稹坑星覂H有一個，互不相交 樹中某結(jié)點的子樹的個數(shù)稱為該結(jié)點的（ ），子樹的根結(jié)點稱為該結(jié)點的（ ），該結(jié)點稱為其子樹根結(jié)點的（ ）?！窘獯稹慷?，孩子，雙親 一棵二叉樹的第i（i1）層最多有（ ）個結(jié)點；一棵有n（n>0）個結(jié)點的滿二叉樹共有（ ）個葉子結(jié)點和（ ）個非終端結(jié)點。【解答】2i-1，(n+1)/2，(n-1)/2【分析】設(shè)滿二叉樹中葉子結(jié)點的個數(shù)為n0，度為2的結(jié)點個數(shù)為n2，由于滿二叉樹中不存在度為1的結(jié)點，所以n=n0+n2；由二叉樹的性質(zhì)n0=n2+1，得n0=(n+1)/2，n2=(n-1)/2。 設(shè)高度為h的二叉樹上

3、只有度為0和度為2的結(jié)點，該二叉樹的結(jié)點數(shù)可能達到的最大值是（ ），最小值是（ ）?！窘獯稹?h -1，2h-1【分析】最小結(jié)點個數(shù)的情況是第1層有1個結(jié)點，其他層上都只有2個結(jié)點。 深度為k的二叉樹中，所含葉子的個數(shù)最多為（ ）。【解答】2k-1【分析】在滿二叉樹中葉子結(jié)點的個數(shù)達到最多。 具有100個結(jié)點的完全二叉樹的葉子結(jié)點數(shù)為（ ）。【解答】50【分析】100個結(jié)點的完全二叉樹中最后一個結(jié)點的編號為100，其雙親即最后一個分支結(jié)點的編號為50，也就是說，從編號51開始均為葉子。 已知一棵度為3的樹有2個度為1的結(jié)點，3個度為2的結(jié)點，4個度為3的結(jié)點。則該樹中有（ ）個葉子結(jié)點?！窘獯?/p>

4、】12【分析】根據(jù)二叉樹性質(zhì)3的證明過程，有n0=n2+2n3+1（n0、n2、n3分別為葉子結(jié)點、度為2的結(jié)點和度為3的結(jié)點的個數(shù)）。 某二叉樹的前序遍歷序列是ABCDEFG，中序遍歷序列是CBDAFGE，則其后序遍歷序列是（ ）?！窘獯稹緾DBGFEA【分析】根據(jù)前序遍歷序列和后序遍歷序列將該二叉樹構(gòu)造出來。 在具有n個結(jié)點的二叉鏈表中，共有（ ）個指針域，其中（ ）個指針域用于指向其左右孩子，剩下的（ ）個指針域則是空的。【解答】2n，n-1，n+1 在有n個葉子的哈夫曼樹中，葉子結(jié)點總數(shù)為（ ），分支結(jié)點總數(shù)為（ ）?！窘獯稹縩，n-1【分析】n-1個分支結(jié)點是經(jīng)過n-1次合并后得到的

5、。2. 選擇題 如果結(jié)點A有3個兄弟，B是A的雙親，則結(jié)點B的度是（）。A 1 B 2 C 3 D 4【解答】D 設(shè)二叉樹有n個結(jié)點，則其深度為（ ）。A n-1 B n C +1 D 不能確定【解答】D【分析】此題并沒有指明是完全二叉樹，則其深度最多是n，最少是 +1。 二叉樹的前序序列和后序序列正好相反，則該二叉樹一定是（ ）的二叉樹。A 空或只有一個結(jié)點 B 高度等于其結(jié)點數(shù)C 任一結(jié)點無左孩子 D 任一結(jié)點無右孩子【解答】B【分析】此題注意是序列正好相反，則左斜樹和右斜樹均滿足條件。 線索二叉樹中某結(jié)點R沒有左孩子的充要條件是（ ）。A R.lchild=NULL B R.ltag=0

6、 C R.ltag=1 D R.rchild=NULL【解答】C【分析】線索二叉樹中某結(jié)點是否有左孩子，不能通過左指針域是否為空來判斷，而要判斷左標(biāo)志是否為1。 深度為k的完全二叉樹至少有（ ）個結(jié)點，至多有（ ）個結(jié)點，具有n個結(jié)點的完全二叉樹按層序從1開始編號，則編號最小的葉子的序號是（ ）。A 2k-2+1 B 2k-1 C 2k -1 D 2k1 -1 E 2k+1 F 2k+1 -1 G 2k -1+1 H 2k【解答】B，C，A【分析】深度為k的完全二叉樹最少結(jié)點數(shù)的情況應(yīng)是第k層上只有1個結(jié)點，最多的情況是滿二叉樹，編號最小的葉子應(yīng)該是在結(jié)點數(shù)最少的情況下，葉子結(jié)點的編號。 一個

7、高度為h的滿二叉樹共有n個結(jié)點，其中有m個葉子結(jié)點，則有（ ）成立。A n=h+m B h+m=2n C m=h-1 D n=2m-1【解答】D【分析】滿二叉樹中沒有度為1的結(jié)點，所以有m個葉子結(jié)點，則度為2的結(jié)點個數(shù)為m-1。 任何一棵二叉樹的葉子結(jié)點在前序、中序、后序遍歷序列中的相對次序（ ）。A 肯定不發(fā)生改變 B 肯定發(fā)生改變 C 不能確定 D 有時發(fā)生變化【解答】A【分析】三種遍歷次序均是先左子樹后右子樹。 如果T' 是由有序樹T轉(zhuǎn)換而來的二叉樹，那么T中結(jié)點的前序序列就是T' 中結(jié)點的（ ）序列，T中結(jié)點的后序序列就是 T' 中結(jié)點的（）序列。A 前序 B

8、中序 C 后序 D 層序【解答】A，B 設(shè)森林中有4棵樹，樹中結(jié)點的個數(shù)依次為n1、n2、n3、n4，則把森林轉(zhuǎn)換成二叉樹后，其根結(jié)點的右子樹上有（ ）個結(jié)點，根結(jié)點的左子樹上有（ ）個結(jié)點。A n1-1 B n1 C n1+n2+n3 D n2+n3+n4【解答】D，A【分析】由森林轉(zhuǎn)換的二叉樹中，根結(jié)點即為第一棵樹的根結(jié)點，根結(jié)點的左子樹是由第一棵樹中除了根結(jié)點以外其余結(jié)點組成的，根結(jié)點的右子樹是由森林中除第一棵樹外其他樹轉(zhuǎn)換來的。 討論樹、森林和二叉樹的關(guān)系，目的是為了（ ）。A 借助二叉樹上的運算方法去實現(xiàn)對樹的一些運算B 將樹、森林按二叉樹的存儲方式進行存儲并利用二叉樹的算法解決樹的

9、有關(guān)問題C 將樹、森林轉(zhuǎn)換成二叉樹D 體現(xiàn)一種技巧，沒有什么實際意義【解答】B3. 判斷題 在線索二叉樹中，任一結(jié)點均有指向其前趨和后繼的線索?！窘獯稹垮e。某結(jié)點是否有前驅(qū)或后繼的線索，取決于該結(jié)點的標(biāo)志域是否為1。 在二叉樹的前序遍歷序列中，任意一個結(jié)點均處在其子女的前面?！窘獯稹繉?。由前序遍歷的操作定義可知。 二叉樹是度為2的樹?！窘獯稹垮e。二叉樹和樹是兩種不同的樹結(jié)構(gòu)，例如，左斜樹是一棵二叉樹，但它的度為1。 由樹轉(zhuǎn)換成二叉樹，其根結(jié)點的右子樹總是空的?！窘獯稹繉?。因為根結(jié)點無兄弟結(jié)點。 用一維數(shù)組存儲二叉樹時，總是以前序遍歷存儲結(jié)點?！窘獯稹垮e。二叉樹的順序存儲結(jié)構(gòu)是按層序存儲的，一般

10、適合存儲完全二叉樹。4證明：對任一滿二叉樹，其分枝數(shù)B2(n0-1) 。（其中，n0為終端結(jié)點數(shù)）【解答】因為在滿二叉樹中沒有度為1的結(jié)點，所以有：n=n0+n2 設(shè)B為樹中分枝數(shù)，則n=B+1所以B=n0 +n2-1再由二叉樹性質(zhì)：n0=n2+1代入上式有：B=n0+n0-1-1=2(n0-1)5證明：已知一棵二叉樹的前序序列和中序序列，則可唯一確定該二叉樹?！窘獯稹孔C明采用歸納法。設(shè)二叉樹的前序遍歷序列為a1a2a3 an，中序遍歷序列為b1b2b3 bn。當(dāng)n=1時，前序遍歷序列為a1，中序遍歷序列為b1，二叉樹只有一個根結(jié)點，所以，a1= b1，可以唯一確定該二叉樹；假設(shè)當(dāng)n<=

11、k時，前序遍歷序列a1a2a3 ak和中序遍歷序列b1b2b3 bk可唯一確定該二叉樹，下面證明當(dāng)n=k+1時，前序遍歷序列a1a2a3 akak+1和中序遍歷序列b1b2b3 bk bk+1可唯一確定一棵二叉樹。在前序遍歷序列中第一個訪問的一定是根結(jié)點，即二叉樹的根結(jié)點是a1，在中序遍歷序列中查找值為a1的結(jié)點，假設(shè)為bi，則a1=bi且b1b2 bi-1是對根結(jié)點a1的左子樹進行中序遍歷的結(jié)果，前序遍歷序列a2a3 ai是對根結(jié)點a1的左子樹進行前序遍歷的結(jié)果，由歸納假設(shè)，前序遍歷序列a2a3 ai和中序遍歷序列b1b2 bi-1唯一確定了根結(jié)點的左子樹，同樣可證前序遍歷序列ai+1ai+

12、2 ak+1和中序遍歷序列bi+1bi+2 bk+1唯一確定了根結(jié)點的右子樹。6已知一棵度為m的樹中有：n1個度為1的結(jié)點，n2個度為2的結(jié)點，nm個度為m的結(jié)點，問該樹中共有多少個葉子結(jié)點？ 【解答】設(shè)該樹的總結(jié)點數(shù)為n，則n=n0+n1+n2+nm 又：n=分枝數(shù)+1=0×n0+1×n1+2×n2+m×nm+1由上述兩式可得：n0= n2+2n3+(m-1)nm+17已知二叉樹的中序和后序序列分別為CBEDAFIGH和CEDBIFHGA，試構(gòu)造該二叉樹?！窘獯稹慷鏄涞臉?gòu)造過程如圖5-12 所示。 8對給定的一組權(quán)值W（5，2，9，11，8，3，7）

13、，試構(gòu)造相應(yīng)的哈夫曼樹，并計算它的帶權(quán)路徑長度。【解答】構(gòu)造的哈夫曼樹如圖5-13所示。 樹的帶權(quán)路徑長度為：WPL=2×4+3×4+5×3+7×3+8×3+9×2+11×2=1209已知某字符串S中共有8種字符，各種字符分別出現(xiàn)2次、1次、4次、5次、7次、3次、4次和9次，對該字符串用0，1進行前綴編碼，問該字符串的編碼至少有多少位?！窘獯稹恳愿髯址霈F(xiàn)的次數(shù)作為葉子結(jié)點的權(quán)值構(gòu)造的哈夫曼編碼樹如圖5-14所示。其帶權(quán)路徑長度=2×5+1×5+3×4+5×3+9×2+4&

14、#215;3+4×3+7×2=98，所以，該字符串的編碼長度至少為98位。  10算法設(shè)計 設(shè)計算法求二叉樹的結(jié)點個數(shù)。【解答】本算法不是要打印每個結(jié)點的值，而是求出結(jié)點的個數(shù)。所以可將遍歷算法中的“訪問”操作改為“計數(shù)操作”，將結(jié)點的數(shù)目累加到一個全局變量中，每個結(jié)點累加一次即完成了結(jié)點個數(shù)的求解。具體算法如下： 設(shè)計算法按前序次序打印二叉樹中的葉子結(jié)點?！窘獯稹勘舅惴ǖ囊笈c前序遍歷算法既有相同之處，又有不同之處。相同之處是打印次序均為前序，不同之處是此處不是打印每個結(jié)點的值，而是打印出其中的葉子結(jié)點，即為有條件打印。為此，將前序遍歷算法中的訪問操作改為條件打

15、印即可。算法如下：  設(shè)計算法求二叉樹的深度?！窘獯稹慨?dāng)二叉樹為空時，深度為0；若二叉樹不為空，深度應(yīng)是其左右子樹深度的最大值加1，而其左右子樹深度的求解又可通過遞歸調(diào)用本算法來完成。具體算法如下： 編寫算法，要求輸出二叉樹后序遍歷序列的逆序?！窘獯稹恳氲玫胶笮虻哪嫘?，只要按照后序遍歷相反的順序即可，即先訪問根結(jié)點，再遍歷根結(jié)點的右子樹，最后遍歷根結(jié)點的左子樹。注意和前序遍歷的區(qū)別，具體算法如下： 以二叉鏈表為存儲結(jié)構(gòu)，編寫算法求二叉樹中結(jié)點x的雙親?！窘獯稹繉Χ骀湵磉M行遍歷，在遍歷的過程中查找結(jié)點x并記載其雙親。具體算法如下： 以二叉鏈表為存儲結(jié)構(gòu)，在二叉樹中刪除以值x為根結(jié)點

16、的子樹。【解答】對二叉鏈表進行遍歷，在遍歷的過程中查找結(jié)點x并記載其雙親，然后將結(jié)點x的雙親結(jié)點中指向結(jié)點x的指針置空。具體算法如下： 一棵具有n個結(jié)點的二叉樹采用順序存儲結(jié)構(gòu)，編寫算法對該二叉樹進行前序遍歷?！窘獯稹堪凑疹}目要求，設(shè)置一個工作棧以完成對該樹的非遞歸算法，思路如下： 每訪問一個結(jié)點，將此結(jié)點壓棧，查看此結(jié)點是否有左子樹，若有，訪問左子樹，重復(fù)執(zhí)行該過程直到左子樹為空。 從棧彈出一個結(jié)點，如果此結(jié)點有右子樹，訪問右子樹執(zhí)行步驟，否則重復(fù)執(zhí)行步驟。具體算法如下： 編寫算法交換二叉樹中所有結(jié)點的左右子樹?！窘獯稹繉Χ鏄溥M行后序遍歷，在遍歷過程中訪問某結(jié)點時交換該結(jié)點的左右子樹。具體

17、算法如下： 以孩子兄弟表示法做存儲結(jié)構(gòu)，求樹中結(jié)點x的第i個孩子?！窘獯稹肯仍阪湵碇羞M行遍歷，在遍歷過程中查找值等于x的結(jié)點，然后由此結(jié)點的最左孩子域firstchild找到值為x結(jié)點的第一個孩子，再沿右兄弟域rightsib找到值為x結(jié)點的第i個孩子并返回指向這個孩子的指針。樹的孩子兄弟表示法中的結(jié)點結(jié)構(gòu)定義如下：template struct TNodeT data;TNode *firstchild, *rightsib;具體算法如下：學(xué)習(xí)自測及答案1前序遍歷和中序遍歷結(jié)果相同的二叉樹是（ ）。A 根結(jié)點無左孩子的二叉樹 B 根結(jié)點無右孩子的二叉樹C 所有結(jié)點只有左子樹的二叉樹 D 所有

18、結(jié)點只有右子樹的二叉樹【解答】D1前序遍歷和中序遍歷結(jié)果相同的二叉樹是（ ）。 A 根結(jié)點無左孩子的二叉樹 B 根結(jié)點無右孩子的二叉樹 C 所有結(jié)點只有左子樹的二叉樹 D 所有結(jié)點只有右子樹的二叉樹【解答】D 2由權(quán)值為3, 8, 6, 2, 5的葉子結(jié)點生成一棵哈夫曼樹，其帶權(quán)路徑長度為（ ）。A 24 B 48 C 53 D 72【解答】C 3用順序存儲的方法將完全二叉樹中的所有結(jié)點逐層存放在數(shù)組A1 An中，結(jié)點Ai若有左子樹，則左子樹的根結(jié)點是（ ）。 A A2i-1 B A2i+1 C Ai/2 D A2i【解答】D4對任何一棵二叉樹T，如果其終端結(jié)點的個數(shù)為n0，度為2的結(jié)點個數(shù)為

19、n2，則（ ）。A n0=n2-1 B n0=n2 C n0=n2+1 D 沒有規(guī)律【解答】C5一棵滿二叉樹中共有n個結(jié)點，其中有m個葉子結(jié)點，深度為h，則（ ）。A n=h+m B h+m=2n C m=h-1 D n=2h-1【解答】D 6對于完全二叉樹中的任一結(jié)點，若其右分支下的子孫的最大層次為h，則其左分支下的子孫的最大層次為（ ）。A h B h+1 C h或h+1 D 任意【解答】C7假定一棵度為3的樹中結(jié)點數(shù)為50，則其最小高度應(yīng)為 。A 3 B 4 C 5 D 6【解答】C8在線索二叉樹中，一個結(jié)點是葉子結(jié)點的充要條件為（ ）。A 左線索標(biāo)志為0，右線索標(biāo)志為1 B 左線索標(biāo)志為1，右線索標(biāo)志為0C 左、右線索標(biāo)志均為0 D 左、右線索標(biāo)志均為1【解答】C9對于一棵具有n個結(jié)點的樹，其所有結(jié)點的度之和為（ ）?！窘獯稹縩-110在順序存儲的二叉樹中，編號為i和j的兩個結(jié)點處在同一層的條件是（ ）?！窘獯稹?