第五章樹和二叉樹習(xí)題

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

一．選擇題

1．在一棵度為3的樹中，度為3的結(jié)點(diǎn)數(shù)為2個(gè)，度為2的結(jié)點(diǎn)數(shù)為1個(gè)，度為1的結(jié)點(diǎn)數(shù)為2個(gè)，那么度為0的結(jié)點(diǎn)數(shù)為（）

A．4個(gè)B．5個(gè)C．6個(gè)D．7個(gè)

2．某二叉樹結(jié)點(diǎn)的中序序列為a、b、c、d、e、f、g，后序序列為b、d、c、a、f、g、e，則其左子樹中結(jié)點(diǎn)數(shù)目為（）

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

3．設(shè)森林F中有三棵樹，第一、其次和第三棵樹的結(jié)點(diǎn)個(gè)數(shù)分別為M1、M2和M3。與森林F對應(yīng)的二叉樹根結(jié)點(diǎn)的左子樹上的結(jié)點(diǎn)個(gè)數(shù)是（）

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

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

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

7．一個(gè)完全二叉樹上有1001個(gè)結(jié)點(diǎn)，其中葉子結(jié)點(diǎn)的個(gè)數(shù)是（）A．250B．501C．254D。5058．在高度為h的完全二叉樹中（）

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

4.在順序存儲的二叉樹中，編號為i和j的兩個(gè)結(jié)點(diǎn)處在同一層上的條件是（）

5．若一個(gè)二叉樹的葉子結(jié)點(diǎn)是某子樹的中序遍歷序列中的最終一個(gè)結(jié)點(diǎn)，則它必是該子樹的（）序列中的最終一個(gè)結(jié)點(diǎn)。

6．若以{4，5，6，7，8}作為葉子結(jié)點(diǎn)的權(quán)值構(gòu)造哈夫曼樹，則其帶權(quán)路徑長度是（），各結(jié)點(diǎn)對應(yīng)的哈夫曼編碼為（）。三．分析構(gòu)造題

1．一棵樹的邊集為{,,,,,,,,,,,,},畫出這棵樹，并回復(fù)以下問題：（1）哪個(gè)是根結(jié)點(diǎn)？（2）哪個(gè)是葉子結(jié)點(diǎn)？

（3）哪個(gè)是結(jié)點(diǎn)G的雙親？（4）哪些是結(jié)點(diǎn)G的祖先？（5）哪些是結(jié)點(diǎn)G的孩子？（6）哪些是結(jié)點(diǎn)E的子孫？

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

（10）以結(jié)點(diǎn)C為根的子樹的深度是多少？2．畫出下圖4棵樹分別對應(yīng)的二叉樹。

A

AA

ABCD

BB

C

3．畫出下圖中5棵二叉樹對應(yīng)的森林AAAA

BCBB

CEFGHIJKABCDEF

CCGH

I

J

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

A為4、7、5、2、9，試畫出對應(yīng)的哈夫曼樹（請按左子樹根結(jié)點(diǎn)的權(quán)值小于等

CB于右子樹根結(jié)點(diǎn)的權(quán)值的次序構(gòu)造），并求出每個(gè)字符的哈夫曼編碼。

5．對于右圖所示的二叉樹FG（1）畫出它的順序存儲結(jié)構(gòu)圖

IJ（2）將它轉(zhuǎn)換成森林

6．已知二叉樹有50個(gè)葉子結(jié)點(diǎn)，則該二叉樹的總結(jié)點(diǎn)數(shù)至少應(yīng)有多少個(gè)？7．具有n個(gè)結(jié)點(diǎn)的滿二叉樹的葉子結(jié)點(diǎn)的個(gè)數(shù)是多少？

8．用一維數(shù)組存放一棵完全二叉樹：ABCDEFGHIJKL。寫出后序遍歷該二叉樹的訪問結(jié)點(diǎn)序列。

9．以數(shù)據(jù)集{2，5，7，9，13}為權(quán)值構(gòu)造一棵哈夫曼樹，并計(jì)算其帶權(quán)路徑長度。四．算法設(shè)計(jì)題

1．二叉樹采用鏈?zhǔn)酱鎯Y(jié)構(gòu)，試設(shè)計(jì)一個(gè)算法計(jì)算一棵給定二叉樹的所有結(jié)點(diǎn)數(shù)。

2.二叉樹采用鏈?zhǔn)酱鎯Y(jié)構(gòu)，設(shè)計(jì)一個(gè)算法把樹b的左、右子樹進(jìn)行交換，要求不破壞原二叉樹。

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

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

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

一．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．設(shè)度為0、1、2的結(jié)點(diǎn)個(gè)數(shù)及總結(jié)點(diǎn)數(shù)分別為n0、n1、9．3601n2和n，則有

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

0101n2=49

7139故：n-1=n1+2*49n=n1+99所以當(dāng)n1=0時(shí)，n最017少，即n至少有99個(gè)結(jié)點(diǎn)。

257．設(shè)滿二叉樹的高度為h，則：總結(jié)點(diǎn)數(shù)n=1+2+4++2^(h-1)=2*2(h-1)-1，WPL=（2+5）*3+（7+9+13）*2=97而該滿二叉樹的葉子結(jié)點(diǎn)個(gè)數(shù)為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．當(dāng)i=1時(shí)，整個(gè)二叉樹只有一根結(jié)點(diǎn)，此時(shí)2i-1=20=1，結(jié)論成立。假設(shè)i=k時(shí)結(jié)論成立，即第k層上結(jié)點(diǎn)總數(shù)最多為2k-1個(gè)?，F(xiàn)證明當(dāng)i=k+1時(shí)，結(jié)論成立：

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

2．由于深度為k的二叉樹，其結(jié)點(diǎn)總數(shù)的最大值是將二叉樹每層上結(jié)點(diǎn)的最大值相加，所以深度為k的二叉樹的結(jié)點(diǎn)總數(shù)至多為：

?i?1k第i層上的最大結(jié)點(diǎn)個(gè)數(shù)=

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

故結(jié)論成立。

3.證明：設(shè)二叉樹中結(jié)點(diǎn)總數(shù)為n，n1為二叉樹中度為1的結(jié)點(diǎn)總數(shù)。由于二叉樹中所有結(jié)點(diǎn)的度小于等于2，所以有n=n0+n1+n2

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