本文格式為Word版，下載可任意編輯——《樹和二叉樹》習題一、選擇題

1．對于先序遍歷和中序遍歷結果一致的二叉樹為（BF）；對于先序遍歷和后序遍歷結果一致的二叉樹為（B）

A.一般二叉樹B.只有根結點的二叉樹C.根結點無左孩子的二叉樹D.根結點無右孩子的二叉樹E.所有結點只有左孩子的二叉樹F.所有結點只有右孩子的二叉樹。

2．以下關于哈夫曼樹的表達錯誤的是(D)。

A．哈夫曼樹的根結點的權值等于所有葉結點的權值之和B．具有n個葉結點的哈夫曼樹共有2n-l個結點C．哈夫曼樹是帶權外路徑長度最短的二叉樹D．哈夫曼樹一個結點的度可以是0、1或2

3．設T2是由樹T轉換得到的二叉樹，則T中結點的后序序列是T2結點的(B)。A．先序序列B．中序序列C．后序序列D．層次序列4．設有一個度為3的樹，其葉結點數為n0，度為1的結點數為nl，度為2的結點數為n2，度為3的結點數為n3，則n0與nl，n2，n3滿足關系（B）。A．n0=n2+1B．n0=n2+2*n3+1C．n0=n2+n3+1D．n0=nl+n2+n3

二、填空題

1．一棵有124個葉結點的完全二叉樹，最多有______248__個結點。在有n個結點的哈夫曼樹中，其葉子結點數為__2/N+1_______。

2．若一棵二叉樹具有12個度為2的結點，6個度為1的結點，則度為0的結點個數是_____13__。

3．已知某二叉樹的先序序列為ABDECF，中序序列為DBEAFC。則其后序序列為_____DEBFCA_____。

4.二叉樹結點數n與邊數e的關系為__N=E+1__________。

5.己知二叉排序樹的先序序列，___能_____唯一確定該二叉排序樹。

6.完全二叉樹采用_順序__存儲結構，滿足存儲空間少，便利的查找任意結點的雙親與孩子。

三、綜合題

1．設有n個結點的二叉樹，度為2的結點數為n2,度為l的結點數為n1，葉結點數為n0，試分別寫出哈夫曼樹、完全二叉樹和單枝二叉樹n1的取值。

答案：哈夫曼樹：0在哈夫曼樹中，只能有度為0或2的結點是嚴格二叉樹完全二叉樹：當n為奇數時，度為1的結點樹為0當n為偶數時，度為1的結點樹為1單支二叉樹：n1=n-1

2．找出滿足以下條件的二叉樹：（1）先序和中序的訪問序列一致；

根節點沒有左孩子的二叉樹或者只有根結點（2）中序和后序的訪問序列一致；只有左孩子的二叉樹

（3）先序和后序的訪問序列一致；只有根節點的二叉樹

3．已知二叉樹的中序遍歷序列為DEBAFCG，后序遍歷序列為EDBFGCA，試畫出該二叉樹。A

BC

DGFE

4.可以生成下圖所示的二叉排序樹的關鍵字初始序列有幾種？試寫出其中的任意4種。

分析過程：{8，4，？，？，？}2^3=6{8,9,4,?,?}22+6=8

5.設al，a2，a3是不同的關鍵字，且al6．以權值分別為3,4,7,9,20的a,b,c,d,e五個元素作為葉結點構造二叉樹，回復：

（1）如何構造路徑長度最短的二叉樹，圖示出一棵路徑長度最短二叉樹，并計算出路徑長度

分析過程：最短路徑長度，所以為完全二叉樹：（不考慮權值）347

920

（9+20）*3+（3+4+7）*2=115

（2）如何構造帶權路徑長度最短的二叉樹，圖示出一棵帶權路徑長度最短的二叉樹，并計算出帶權路徑長度432320

149

77

34

最短帶權路徑：3*4+4*4+7*3+9*2+20*1=87

7．已知4個字符A,B,C,D的哈夫曼編碼分別是1，01，000，001。以下01串是由以上4個字母構成的一

段文本的哈夫曼編碼：1001000011011010011010011。請將上述01串還原為編碼前的文本，以字符在文本中出現的次數為權值，求出這棵樹的帶權路徑長度。1001000011011010011010011ADCBABABDABDAA