《樹和二叉樹》習題

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

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

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

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

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

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

二、填空題

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

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

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

4.二叉樹結(jié)點數(shù)n與邊數(shù)e的關(guān)系為__N=E+1__________。

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

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

三、綜合題

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

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

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

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

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

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

BC

DGFE

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

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

5.設(shè)al，a2，a3是不同的關(guān)鍵字，且al6．以權(quán)值分別為3,4,7,9,20的a,b,c,d,e五個元素作為葉結(jié)點構(gòu)造二叉樹，回復(fù)：

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

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

920

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

（2）如何構(gòu)造帶權(quán)路徑長度最短的二叉樹，圖示出一棵帶權(quán)路徑長度最短的二叉樹，并計算出帶權(quán)路徑長度432320

149

77

34

最短帶權(quán)路徑：3*4+4*4+7*3+9*2+20*1=87

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

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