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

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

一．選擇題

1．在一棵度為3的樹(shù)中，度為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．某二叉樹(shù)結(jié)點(diǎn)的中序序列為a、b、c、d、e、f、g，后序序列為b、d、c、a、f、g、e，則其左子樹(shù)中結(jié)點(diǎn)數(shù)目為（）

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

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

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

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

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

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

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

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

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

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

1．一棵樹(shù)的邊集為{,,,,,,,,,,,,},畫(huà)出這棵樹(shù)，并回復(fù)以下問(wèn)題：（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的層次號(hào)分別是什么？（9）樹(shù)的深度是多少？

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

A

AA

ABCD

BB

C

3．畫(huà)出下圖中5棵二叉樹(shù)對(duì)應(yīng)的森林AAAA

BCBB

CEFGHIJKABCDEF

CCGH

I

J

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

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

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

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

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

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

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

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

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

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

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

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

5．在具有n(n>=1)個(gè)結(jié)點(diǎn)的m次樹(shù)中，有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è)滿二叉樹(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而該滿二叉樹(shù)的葉子結(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è)二叉樹(shù)只有一根結(jié)點(diǎn)，此時(shí)2i-1=20=1，結(jié)論成立。假設(shè)i=k時(shí)結(jié)論成立，即第k層上結(jié)點(diǎn)總數(shù)最多為2k-1個(gè)。現(xiàn)證明當(dāng)i=k+1時(shí)，結(jié)論成立：

由于二叉樹(shù)中每個(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的二叉樹(shù)，其結(jié)點(diǎn)總數(shù)的最大值是將二叉樹(shù)每層上結(jié)點(diǎn)的最大值相加，所以深度為k的二叉樹(shù)的結(jié)點(diǎn)總數(shù)至多為：

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

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

故結(jié)論成立。

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

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