第5章_樹與二叉樹習(xí)題解析

1、精選文檔習(xí)題五 樹與二叉樹1一、選擇題1、一棵非空的二叉樹的先序遍歷序列與后序遍歷序列正好相反，則該二叉樹肯定滿足 。A、全部的結(jié)點均無左孩子 B、全部的結(jié)點均無右孩子C、只有一個葉子結(jié)點 D、是任意一棵二叉樹2、一棵完全二叉樹上有1001個結(jié)點，其中葉子結(jié)點的個數(shù)是 。 A、250 B、500 C、254 D、505 E、以上答案都不對3、以下說法正確的是 。A、若一個樹葉是某二叉樹前序遍歷序列中的最終一個結(jié)點，則它必是該子樹后序遍歷序列中的最終一個結(jié)點B、若一個樹葉是某二叉樹前序遍歷序列中的最終一個結(jié)點，則它必是該子樹中序遍歷序列中的最終一個結(jié)點C、在二叉樹中，具有兩個子女的父結(jié)點，在中序

2、遍歷序列中，它的后繼結(jié)點最多只能有一個子女結(jié)點D、在二叉樹中，具有一個子女的父結(jié)點，在中序遍歷序列中，它沒有后繼子女結(jié)點4、以下說法錯誤的是 C 。A、哈夫曼樹是帶權(quán)路徑長度最短得數(shù)，路徑上權(quán)值較大的結(jié)點離根較近B、若一個二叉樹的樹葉是某子樹中序遍歷序列中的第一個結(jié)點，則它必是該子樹后序遍歷序列中的第一個結(jié)點C、已知二叉樹的前序遍歷和后序遍歷并不能唯一地確定這棵樹,由于不知道樹的根結(jié)點是哪一個D、在前序遍歷二叉樹的序列中,任何結(jié)點其子樹的全部結(jié)點都是直接跟在該結(jié)點之后的5、一棵有124個葉結(jié)點的完全二叉樹，最多有 個結(jié)點。 A、247 B、248 C、249 D、250 E、2516、任何一棵

3、二叉樹的葉結(jié)點在前（先）序、中序和后序遍歷序列中的相對次序 。 A、不發(fā)生變化 B、發(fā)生變化 C、不能確定7、設(shè)a、b為一棵二叉樹上的兩個結(jié)點。在中序遍歷時，a在b前面的條件是 。A、a在b的右方 B、a在b的左方 C、a是b的祖先D、a是b的子孫8、設(shè)深度為k的二叉樹上只有度為0和度為2的結(jié)點，則這類二叉樹上所含的結(jié)點總數(shù)為 。 A、k+1 B、2k C、2k-1 D、2k+19、設(shè)有13個值，用它們組成一棵哈夫曼樹，則該哈夫曼樹共有 個結(jié)點。 A、13 B、12 C、26 D、2510、下面幾個符號串編碼集合中，不是前綴編碼的是 。A、0，10，110，1111 B、11，10，001，1

4、01，0001C、00，010，0110，1000 D、b,c,aa,ac,aba,abb,abc11、欲實現(xiàn)任意二叉樹的后序遍歷的非遞歸算法而不使用棧結(jié)構(gòu)，最佳的方案是二叉樹接受 存儲結(jié)構(gòu)。 A、三叉鏈表 B、廣義表 C、二叉鏈表 D、挨次表12、以下說法錯誤的是 。A、存在這樣的二叉樹，對它接受任何次序遍歷其結(jié)點訪問序列均相同B、二叉樹是樹的特殊情形C、由樹轉(zhuǎn)換成二叉樹，其根結(jié)點的右子樹總是空的D、在二叉樹只有一棵子樹的狀況下也要明確指出該子樹是左子樹還是右子樹13、樹的基本遍歷策略可分為先根遍歷和后根遍歷，二叉樹的基本遍歷策略可分為先序、中序和后序三種遍歷。我們把由樹轉(zhuǎn)化得到的二叉樹稱該

5、樹對應(yīng)的二叉樹，則下面 是正確的。A、樹的先根遍歷序列與其對應(yīng)的二叉樹先序遍歷序列相同B、樹的后根遍歷序列與其對應(yīng)的二叉樹后序遍歷序列相同C、樹的先根遍歷序列與其對應(yīng)的二叉樹中序遍歷序列相同D、以上都不對14、若以二叉樹的任一結(jié)點動身到根的路徑上所經(jīng)過的結(jié)點序列按其關(guān)鍵字有序。則該二叉樹是 。 A、二叉排序樹 B、哈夫曼樹 C、堆15、下列有關(guān)二叉樹的說法正確的是 。 A、二叉樹的度為2 B、一棵二叉樹度可以小于2C、二叉樹中至少有一個結(jié)點的度為2 D、二叉樹中任一個結(jié)點的度都為216、某二叉樹中序序列為ABCDEFG，后序序列為BDCAFGE，則前序序列是 。 A、EGFACDB B、EAC

6、BDGFC、EAGCFBD D、上面的都不對17、對二叉排序樹進行 遍歷，可以得到該二叉樹全部結(jié)點構(gòu)成的排序序列。 A、前序 B、中序 C、后序 D、按層次18、由二叉樹的前序和后序遍歷序列 唯一地確定這棵二叉樹。 A、能 B、不能19、在一棵度為3的樹中，度為3的結(jié)點數(shù)為2個，度為2的結(jié)點數(shù)為1個，度為1的結(jié)點數(shù)為2個，則度為0的結(jié)點數(shù)為 個。 A、4 B、5 C、6 D、720、在一棵深度為h的完全二叉樹中，所含結(jié)點的個數(shù)不小于 。 A、2h B、2h+1 C、2h-1 D、2h-121、在一棵具有n個結(jié)點的二叉樹第i層上，最多具有 個結(jié)點。 A、2i B、2i+1 C、2i-1 D、2n

7、22、在下列狀況中，可稱為二叉樹的是 。 A、每個結(jié)點至多有兩棵子樹的樹 B、哈夫曼樹C、每個結(jié)點至多有兩棵子樹的有序樹 D、每個結(jié)點只有一棵右子樹E、以上答案都不對二、填空題1、8層完全二叉樹至少有 128 個結(jié)點，擁有100個結(jié)點的完全二叉樹的最大層數(shù)為 7 。2、樹在計算機內(nèi)的表示方式有 雙親表示法 、 孩子表示法 、 孩子兄弟表示法 。3、一棵有n個結(jié)點的滿二叉樹有 0 個度為1的結(jié)點，有 n/2 個分支（非終端）結(jié)點和 n/2+1 個葉子，該滿二叉樹的深度為 log2n+1 。4、若一個二叉樹的葉子結(jié)點是某子樹的中序遍歷序列中的最終一個結(jié)點，則它必是孩子樹的 前序遍歷 序列中的最終一

8、個結(jié)點。5、一棵共有n個結(jié)點的樹，其中全部分支結(jié)點的度均為k，則該樹中的葉子結(jié)點個數(shù)為 （n（k-1）+1）/k 。6、深度為k（設(shè)根的層數(shù)為1）的完全二叉樹至少有 2k-1 個結(jié)點，至多有 2k-1 個結(jié)點。7、設(shè)只包含根結(jié)點的二叉樹高度為0，則高度為k的二叉樹最大結(jié)點數(shù)為 2k+1-1 ，最小結(jié)點數(shù)為 k+1 。8、一棵完全二叉樹有999個結(jié)點，它的深度為 10 。9、對于一棵具有n個結(jié)點的樹，該樹中全部結(jié)點的度數(shù)之和為 n-1 。10、有n個結(jié)點并且其高度為n的二叉樹有 2n-1 個。11、一棵具有n個結(jié)點的二叉樹，若它有n0個葉子結(jié)點，則該二叉樹上度為1的結(jié)點n1= n-2n0+1 。

9、12、若一棵二叉樹的葉子數(shù)為n0，則該二叉樹中左、右子樹皆非空的結(jié)點個數(shù)為 n0-1 。13、設(shè)n0為哈夫曼樹的葉子結(jié)點數(shù)目，則該哈夫曼樹共有 2n0-1 個結(jié)點。14、若以4、5、6、7、8作為葉子結(jié)點的權(quán)值構(gòu)造哈夫曼樹，則其帶權(quán)路徑長度是 69 。三、推斷題1、完全二叉樹的某結(jié)點若無左孩子，則它必是葉結(jié)點。 （對 ）2、存在這樣的二叉樹，對它接受任何次序的遍歷，結(jié)果相同。（ 對 ）3、二叉樹就是結(jié)點度為2的樹。（ 錯 ）4、二叉樹中不存在度大于2的結(jié)點，當(dāng)某個結(jié)點只有一棵子樹時無所謂左、右子樹。（ 錯 ）5、已知二叉樹的前序遍歷序列和后序遍歷序列并不能唯一地確定這棵樹，由于不知道樹的根結(jié)點

10、是哪一個。（錯 ）6、在哈夫曼編碼中，當(dāng)兩個字符消滅的頻率相同時，其編碼也相同，對于這種狀況應(yīng)作特殊處理。（錯 ）7、中序遍歷一棵二叉排序樹的結(jié)點就可得到排好序的結(jié)點序列。（對 ）8、將一棵樹轉(zhuǎn)換成二叉樹后，根結(jié)點沒有左子樹。（錯 ）9、用樹的前序遍歷和中序遍歷可以導(dǎo)出樹的后序遍歷。（對 ）10、哈夫曼樹是帶權(quán)路徑長度最短的樹，路徑上權(quán)值較大的結(jié)點離根較近。（ 對 ）11、不使用遞歸也能實現(xiàn)二叉樹前序、中序和后序遍歷。（ 對 ）習(xí)題五 樹與二叉樹21. 填空題 樹是n（n0）結(jié)點的有限集合，在一棵非空樹中，有（ ）個根結(jié)點，其余的結(jié)點分成m（m0）個（）的集合，每個集合都是根結(jié)點的子樹?！窘獯?/p>

11、】有且僅有一個，互不相交 樹中某結(jié)點的子樹的個數(shù)稱為該結(jié)點的（ ），子樹的根結(jié)點稱為該結(jié)點的（ ），該結(jié)點稱為其子樹根結(jié)點的（ ）。【解答】度，孩子，雙親 一棵二叉樹的第i（i1）層最多有（ ）個結(jié)點；一棵有n（n0）個結(jié)點的滿二叉樹共有（）個葉子結(jié)點和（ ）個非終端結(jié)點?！窘獯稹?i-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的二叉樹上只有度為0和度為2的結(jié)點，該二叉樹的結(jié)點數(shù)可能達到的最大值是

12、（ ），最小值是（ ）。【解答】2h -1，2h-1【分析】最小結(jié)點個數(shù)的狀況是第1層有1個結(jié)點，其他層上都只有2個結(jié)點。 深度為k的二叉樹中，所含葉子的個數(shù)最多為（ ）?！窘獯稹?k-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é)點?！窘獯稹?2【分析】依據(jù)二叉樹性質(zhì)3的證明過程，有n0=n2+2n

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

14、BIFHGA，試構(gòu)造該二叉樹。對給定的一組權(quán)值W（5，2，9，11，8，3，7），試構(gòu)造相應(yīng)的哈夫曼樹，并計算它的帶權(quán)路徑長度。【解答】構(gòu)造的哈夫曼樹如圖5-13所示。樹的帶權(quán)路徑長度為：WPL=24+34+53+73+83+92+112=120二叉樹先根序、后根序、中根序遍歷的速算法（解題技巧）經(jīng)過爭辯我找出了一種不用畫圖，由先（后）根序遍歷和中根序遍歷快速確定遍歷結(jié)果的方法。謹以此文獻給智商與我同級而又不得不爭辯算法的伴侶。抽象思維太差，用例子來說明吧。下面這個是后根遍歷的算法。例1：已知某二叉樹的先根序遍歷為ABCDEFG,中根序遍歷為CDBAFEG，則它的后根序遍歷為_解法如下：1、確

15、定樹根。由先序遍歷知道，樹根為A。2、分別左、右子樹。由中根序遍歷知，A左面的為CDB左子樹結(jié)點，右面的FEG為右子樹結(jié)點。把先根序遍歷也分成左、右子樹結(jié)點，BCD、EFG。前根序遍歷BCDEFG中根序遍歷CDBFEG3、分別把先根序遍歷左、右子樹結(jié)點抄過來，寫的時候要從右往左寫，本例中，依次寫下B、C、D、，E、F、G，結(jié)果是DCB GFE。當(dāng)然不是簡潔到這種程序。上面只是個原理。抄的過程應(yīng)當(dāng)是這樣的：盯著前根序的，瞅著中根序的。假如要抄的先根序中的結(jié)點在中根序中是最左/右邊，則直接抄過來；假如不是，則把這個結(jié)點左邊的結(jié)點先放記在右根序的最左邊，然后連續(xù)抄。本題的結(jié)果是DCB,FGE,A,

16、即DCBFGEA。上面這個例子太短，看不出“貓膩”來。再舉個結(jié)點多一點兒的。例2：已知某二叉樹的先根序遍歷為ABCDEFGHIJK,中根序遍歷為CEDFBAHKJIG，則它的后根序遍歷為_按上面的方法：前根序遍歷BCDEF GHIJK中根序遍歷CEDFB HKJIG依次抄得前根序的結(jié)點：F、E(E在中根序遍歷中不靠邊，所以先放在后根遍序歷中左子樹結(jié)點最左邊)、D、C同理，把右子樹也抄過來。因此，寫下結(jié)點的過程依次是：假如還是不太懂，你可以試著做一下下面的例子：已知二叉樹前序遍歷 ABCDEFGHIJK，中序遍歷 CEDFBAHGKJI，求后序遍歷。解：(1)以根結(jié)點A分左、右子樹結(jié)點， BCDEF GHIJK CEDFB HGKJI(2)寫左子樹，盯著前序，從右到左開頭寫DCB（在中序中，B靠右邊，C靠左邊