第五章樹和二叉樹習題

本文格式為Word版，下載可任意編輯——第五章樹和二叉樹習題第五章樹和二叉樹

一．選擇題

1．在一棵度為3的樹中，度為3的結點數為2個，度為2的結點數為1個，度為1的結點數為2個，那么度為0的結點數為（）

A．4個B．5個C．6個D．7個

2．某二叉樹結點的中序序列為a、b、c、d、e、f、g，后序序列為b、d、c、a、f、g、e，則其左子樹中結點數目為（）

A．3B．2C．4D．5

3．設森林F中有三棵樹，第一、其次和第三棵樹的結點個數分別為M1、M2和M3。與森林F對應的二叉樹根結點的左子樹上的結點個數是（）

A．M1B．M1+M2C．M3D．M2+M34。對于一棵具有n個結點、度為4的樹來說，（）A．樹的高度至多是n-3B．樹的高度至多是n-3

C．第i層上至多有4*(i-1)個結點D．至少在某一層上正好有4個結點5．在以下存儲結構中，（）不是樹的存儲形式

A．雙親表示法B．孩子鏈表示法C．孩子兄弟鏈表示法D．順序存儲表示法6．二叉樹若用順序方法存儲，則以下4種運算中的（）最簡單實現(xiàn)。A．先序遍歷二叉樹B．判斷兩個指定結點是不是在同一層上C．層次遍歷二叉樹D．根據結點的值查找其存儲位置

7．一個完全二叉樹上有1001個結點，其中葉子結點的個數是（）A．250B．501C．254D。5058．在高度為h的完全二叉樹中（）

A．度為0的結點都在第h層上B．第I(1=0）的二叉樹中至多有()個結點，至少有（）個結點。3．N個結點的二叉樹中假使有m個樹葉，則一定有（）個度為1的結點，（）個度為2的結點。

4.在順序存儲的二叉樹中，編號為i和j的兩個結點處在同一層上的條件是（）

5．若一個二叉樹的葉子結點是某子樹的中序遍歷序列中的最終一個結點，則它必是該子樹的（）序列中的最終一個結點。

6．若以{4，5，6，7，8}作為葉子結點的權值構造哈夫曼樹，則其帶權路徑長度是（），各結點對應的哈夫曼編碼為（）。三．分析構造題

1．一棵樹的邊集為{,,,,,,,,,,,,},畫出這棵樹，并回復以下問題：（1）哪個是根結點？（2）哪個是葉子結點？

（3）哪個是結點G的雙親？（4）哪些是結點G的祖先？（5）哪些是結點G的孩子？（6）哪些是結點E的子孫？

（7）哪些是結點E的兄弟？哪些是結點F的兄弟？（8）結點B和N的層次號分別是什么？（9）樹的深度是多少？

（10）以結點C為根的子樹的深度是多少？2．畫出下圖4棵樹分別對應的二叉樹。

A

AA

ABCD

BB

C

3．畫出下圖中5棵二叉樹對應的森林AAAA

BCBB

CEFGHIJKABCDEF

CCGH

I

J

4．有一份電文中共使用5個字符，A、B、C、D、E，它們的出現(xiàn)頻率依次

A為4、7、5、2、9，試畫出對應的哈夫曼樹（請按左子樹根結點的權值小于等

CB于右子樹根結點的權值的次序構造），并求出每個字符的哈夫曼編碼。

5．對于右圖所示的二叉樹FG（1）畫出它的順序存儲結構圖

IJ（2）將它轉換成森林

6．已知二叉樹有50個葉子結點，則該二叉樹的總結點數至少應有多少個？7．具有n個結點的滿二叉樹的葉子結點的個數是多少？

8．用一維數組存放一棵完全二叉樹：ABCDEFGHIJKL。寫出后序遍歷該二叉樹的訪問結點序列。

9．以數據集{2，5，7，9，13}為權值構造一棵哈夫曼樹，并計算其帶權路徑長度。四．算法設計題

1．二叉樹采用鏈式存儲結構，試設計一個算法計算一棵給定二叉樹的所有結點數。

2.二叉樹采用鏈式存儲結構，設計一個算法把樹b的左、右子樹進行交換，要求不破壞原二叉樹。

3．已知一棵高度為k的具有n個結點的二叉樹，按順序方式存儲，編寫將二叉樹中最大序號葉子結點的祖先結點全部打印輸出的算法。五．證明題

1．在二叉樹的第i層上至多有2i-1個結點(i≥1)。2．深度為k的二叉樹至多有2k-1個結點（k≥1）3．對任意一棵二叉樹T，若終端結點數為n0，而其度數為2的結點數為n2，則n0=n2+1。4．具有n個結點的完全二叉樹的深度為?㏒2n?+1。

5．在具有n(n>=1)個結點的m次樹中，有n(m-1)+1個指針域是空的。參考答案

一．CCAADCBCBACCD二．1．42．2h-1h3．N-2m+1m-1

4．?log2i???log2j?

5．先序序列

BDEIMABBCCCEDFIJKGH

NFJACGKHL6．69010、011、10、11、00三．1．

(1)A(2)D、M、N、F、J、K、L(3)C(4)A、C(5)J、K(6)I、M、N

(7)D,G、H(8)2，5(9)5(10)32．

AABA3．

4.ABAABCABCHFIBCDGJEC0110c1601a4b7271161e9a:001b:10c:01d:000e:11

5．（1）AA（2）BIFCJGBCFGIJ50d2

6．設度為0、1、2的結點個數及總結點數分別為n0、n1、9．3601n2和n，則有

1422N0=50，n=n0+n1+n2，n-1=n1+2*n2，由這三個式子得：

0101n2=49

7139故：n-1=n1+2*49n=n1+99所以當n1=0時，n最017少，即n至少有99個結點。

257．設滿二叉樹的高度為h，則：總結點數n=1+2+4++2^(h-1)=2*2(h-1)-1，WPL=（2+5）*3+（7+9+13）*2=97而該滿二叉樹的葉子結點個數為2^（h-1）=(n+1)/28．HIDJKEBLFGCA四．

1.intnodes(Btree*b)2．Voidswap1(BTNode*b,BTNode*{if(b==null)If(b==NULL)B1=null;Return(0);ElseElse{b1=(BTNode*)malloc(sizeof(BTNode));{num1=nodes(b.lchile);B1.data=b.data;Num2=nodes(b.rchile);Swap1(b.lchild,b1.rchild);Return(num1+num2+1);Swap1(b.rchild,b1.lchild);}}}}

3．Voidpath(elemtypesqtree[],intk)Printf(“%c〞,sqtree[i]);{inti=po(2,k)-1;//求2k-1}While(i>1Printf(“\\n〞);While(i>1)}{i=i/2;

五．

1．當i=1時，整個二叉樹只有一根結點，此時2i-1=20=1，結論成立。假設i=k時結論成立，即第k層上結點總數最多為2k-1個?，F(xiàn)證明當i=k+1時，結論成立：

由于二叉樹中每個結點的度最大為2，則第k+1層的結點總數最多為第k層上結點最大數的2倍，即2×2k-1=2(k+1)-1，故結論成立。

2．由于深度為k的二叉樹，其結點總數的最大值是將二叉樹每層上結點的最大值相加，所以深度為k的二叉樹的結點總數至多為：

?i?1k第i層上的最大結點個數=

?i?1k2i-1=2k-1

故結論成立。

3.證明：設二叉樹中結點總數為n，n1為二叉樹中度為1的結點總數。由于二叉樹中所有結點的度小于等于2，所以有n=n0+n1+n2

設二叉樹中分支數目為B，由于除根結點外，每個結點均對應一個進入它的分支，所以有：n=B+1。又由于二叉樹中的分支都是由度為1和度為2的結點發(fā)出，所以分支數目為：B=n1+2n2