作業(yè)-樹和二叉樹

1、作業(yè)-樹和二叉樹樹（樹根結(jié)點的高度為1）一、選擇題3.以下說法錯誤的是（）。A.完全二叉樹上結(jié)點之間的父子關(guān)系可由它們 編號之間的關(guān)系來表達B.在三叉鏈表上，二叉樹的求雙親操作很容易 實現(xiàn)C.在二叉鏈表上，求根以及求左、右孩子等操 作很容易實現(xiàn)D.在二叉鏈表上，求雙親操作的時間性能很好4.以下說法錯誤的是（）。A. 一般在哈夫曼樹中，權(quán)值越大的葉子離根結(jié) 點越近B.哈夫曼樹中沒有度數(shù)為1的分支結(jié)點C.若初始森林中共有n棵二叉樹，最終求得的 哈夫曼樹共有2n-1個結(jié)點D.若初始森林中共有n棵二叉樹，進行2n-1次合并后才能剩下一棵最終的哈夫曼 樹5 .深度為6的二叉樹最多有（）個結(jié)點。A. 64

2、B. 63 C. 32 D. 316 .將含有41個結(jié)點的完全二叉樹從根結(jié)點開始編號，根為1號，后面按從上到下、從左到右的順序?qū)Y(jié)點編號，那么編號為21的雙親結(jié)點編號為（）。A. 10B. 11 C. 41 D. 207 .設(shè)深度為k的二叉樹上只有度為0和度為2 的結(jié)點，則這類二叉樹上所含結(jié)點總數(shù)最少（）個。A. k+l B. 2k C. 2k-1 D. 2k+18 .下列說法中正確的是（）。A.任何一棵二叉樹中至少有一個結(jié)點的度為2B.任何一棵二叉樹中每個結(jié)點的度都為 2C.任何一棵二叉樹中的每個結(jié)點的度肯定等于2D.任何一棵二叉樹中的每個結(jié)點的度都可以小于29 . 一棵二叉樹滿足下列條件：

3、對任意結(jié)點，若存在左、右子樹，則其值都小于它的左子樹上所有結(jié)點的值，而大于右子樹上所有結(jié)點的值?，F(xiàn)采用（）遍歷方式就可以得到這棵二叉樹所有結(jié)點的遞減序列。A.前序 B.中序 C.后序 D.層次10 .如圖6-1所示的二叉樹的中序遍歷序列是 ()。A. abcdgef B. dfebagcC. dbaefcgD. defbagcVM 11 .已知某二叉樹的后序遍歷序列是 deach中 序遍歷序列是deabq它的前序遍歷序列是（）。A. acbed B. baedc C. dceab D.cedb12 .某二叉樹的前序遍歷的結(jié)點訪問順序是 abdgcefhdgbaechf則其后序遍歷的結(jié)點訪問順序

4、是（）A. bdgcefha B. gdbecfha C. bdgechfaD. gdbehfca13.在圖6-2中的二叉樹中，（c杯是完全二叉樹。14 .樹最適合用來表示（）。A.有序數(shù)據(jù)元素B.無序數(shù)據(jù)元素C.元素之間具有分支層次關(guān)系的數(shù)據(jù)D.元素之間無聯(lián)系的數(shù)據(jù)15 .哈夫曼樹的帶權(quán)路徑長度是（）。A.所有結(jié)點權(quán)值之和B.所有葉結(jié)點帶權(quán)路徑長度之和C.帶權(quán)結(jié)點的值D.除根以外所有結(jié)點權(quán)值之和16 .設(shè)有一棵22個結(jié)點的完全二叉樹，那么整棵二叉樹有（）個度為0的結(jié)點。A. 6B. 7 C. 8 D. 1117 .已知完全二叉樹有26個結(jié)點，則整棵二叉 樹有（）個度為1的結(jié)點。A. 0B.

5、1C. 2 D. 1318 .已知如圖6-3所示的哈夫曼樹，那么電文 CDAA的編碼是（）。A. 110100 B. 11011100 C. 010110111D. 1111110019 .在n個結(jié)點的完全二叉樹中，對任一結(jié)點i（1< i< n）,i的左孩子可能是（）。A. i/2 B. 2i+1 C. 2i D.都不是20 .已給出圖6-3所示的二叉樹，A, B, C, D的權(quán)值分別為7, 5, 2, 4, 則該樹的帶權(quán)路徑長度為（）。A. 46B. 36C. 35 D.都不是21 .下列敘述中正確的是（）。A.二叉樹是度為2的有序樹B.二叉樹中結(jié)點只有一個孩子時無左右之分C.二

6、叉樹中必有度為2的結(jié)點D.二叉樹中結(jié)點最多有兩棵子樹，并且有左右 之分22.圖6-4所示的幾種結(jié)構(gòu)中屬于樹形結(jié)構(gòu)的是 (b)。二、判斷題(標紅色的是錯誤的)2 .樹和二叉樹之間最主要的差別是： 二叉樹的結(jié)點的子樹要區(qū)分為左右子樹， 即使在結(jié)點只有一棵子樹的情況下也要明確指出該子樹是左子樹還是右子樹。3 .若有一個結(jié)點是某二叉樹子樹的中序遍歷序 列中的最后一個結(jié)點，則它必須是該子樹的前序遍歷序列中的最后一 個結(jié)點。4 .二叉樹具有兩個子女的父結(jié)點，在中序遍歷 序列中，它的后繼結(jié)點最多只能有一個子女。5 .在二叉樹中，具有一個子女的父結(jié)點， 在中序遍歷中，它沒有后繼的子女結(jié)點。6 .已知二叉樹的前

7、序遍歷和后序遍歷序列不能 惟一地確定這棵樹。三、填空題1 .樹(及一切樹形結(jié)構(gòu))是一種分支層次 結(jié)構(gòu)。在樹中，H 結(jié)點沒有直接前驅(qū)。對樹上任一結(jié)點x來說，x是它的任一子樹的根結(jié)點惟一的雙親O2 . 一棵樹上的任何結(jié)點(不包括卞K本身)稱為根的 子孫。若B是A的子孫，則稱A是B的祖先。3 .二叉樹第i(i>0)層上至多有2i-1個結(jié)點。4 .深度為k(k>0)的二叉樹至多有 2k-1個結(jié)點。5 .對任何二叉樹，若度為2的節(jié)點數(shù)為n2,則葉子數(shù) n0=_n2+1 o6 .滿二叉樹上各層的節(jié)點數(shù)已達到了二叉樹可 以容納的 最大值。滿二叉樹也是 完全 二叉樹，但反之不7 .具有n個結(jié)點的完

8、全二叉樹的深度為 10g2n 取整+1。8 .二叉樹通常有 J頓序:存儲結(jié)構(gòu)和鏈式:存儲結(jié)構(gòu)兩類存儲結(jié)構(gòu)。9 .每個二叉鏈表還必須有一個指向根結(jié)點的指針，該指針具有標識二叉鏈表的作用。10 .對二叉鏈表白訪問只能從 t指針開始。11 .二叉樹有不同的鏈式存儲結(jié)構(gòu)，其中最常用 的是二叉鏈表與三叉鏈表。12 .具有100個結(jié)點的完全二叉樹的深度是713 .在 先序遍歷二叉樹的序列中，任何結(jié)點的子樹上的所有結(jié)點都是直接跟在該結(jié)點之后。14 .若一棵二叉樹的葉子數(shù)為n,則該二叉樹中左、右子樹皆非空的結(jié)點個數(shù)為n-1 o15 . 一棵樹的形狀如圖6-5所示,它的根結(jié)點是 A ,葉結(jié)點是_E, J, K,G, L, O, P, Q, R, N, I,結(jié)點H的度是3,這棵樹的度是4這棵樹的深度是 5結(jié)點F的兒子結(jié)點是J, K,結(jié)點G的父結(jié)點是 C?18.含有2n個結(jié)點的二叉樹高度至少是_n+1,至多是_2n 僅含根結(jié)點的二叉樹高度為1）。四、應(yīng)用題1 .分別寫出圖6-7所示二叉樹的前序、中序和后 序序列。3I I答：前序：ABCDEF、中序：CBEFDA和后序:CFEDBA2 .已知一棵二叉樹的中序序列和后序序列分別為BDCEAFHG 和DECBHGFA ,試畫出這棵二 叉樹，并寫出其前序遍歷序列。答：前序遍歷序列：ABCDEFGH3 .設(shè)某密碼電文由8個字母組成，a,b,c,d,e,f