數(shù)據(jù)結(jié)構(gòu)課后習(xí)題(第6章)

【課后習(xí)題】第6章樹和二叉樹

網(wǎng)絡(luò)工程2010級（）班學(xué)號：姓名：

題號一二三四五總分

得分

一、填空題（每空1分，共16分）

1.從邏輯結(jié)構(gòu)看，樹是典型的O

2.設(shè)一棵完全二叉樹具有999個結(jié)點(diǎn)，則此完全二叉樹有個葉子結(jié)點(diǎn)，有

個度為2的結(jié)點(diǎn)，有個度為1的結(jié)點(diǎn)。

3.由n個權(quán)值構(gòu)成的哈夫曼樹共有個結(jié)點(diǎn)。

4.在線索化二叉樹中，T所指結(jié)點(diǎn)沒有左子樹的充要條件是o

5.在非空樹上，沒有直接前趨。

6.深度為k的二叉樹最多有結(jié)點(diǎn)，最少有個結(jié)點(diǎn)。

7.若按層次順序?qū)⒁豢糜衝個結(jié)點(diǎn)的完全二叉樹的所有結(jié)點(diǎn)從1到n編號，那么當(dāng)i為

且小于n時，結(jié)點(diǎn)i的右兄弟是結(jié)點(diǎn),否則結(jié)點(diǎn)i沒有右兄弟。

8.N個結(jié)點(diǎn)的二叉樹采用二叉鏈表存放，共有空鏈域個數(shù)為o

9.一棵深度為7的滿二叉樹有個非終端結(jié)點(diǎn)。

10.將一棵樹轉(zhuǎn)換為二叉樹表示后,該二叉樹的根結(jié)點(diǎn)沒有。

11.采用二叉樹來表示樹時，樹的先根次序遍歷結(jié)果與其對應(yīng)的二叉樹的遍歷結(jié)

果是??樣的。

12.一棵Huffman樹是帶權(quán)路徑長度最短的二叉樹，權(quán)值______的外結(jié)點(diǎn)離根較遠(yuǎn)。

二、判斷題（如果正確，在對應(yīng)位置打“y'，否則打“x”。每題0.5分，共5分）

12345678910

1.對于一棵非空二叉樹，它的根結(jié)點(diǎn)作為第一層，則它的第i層上最多能有2-1個結(jié)點(diǎn)。

2.二叉樹的前序遍歷并不能唯一確定這棵樹，但是，如果我們還知道該二叉樹的根結(jié)點(diǎn)

是那一個，則可以確定這棵二叉樹。

3.一棵樹中的葉子結(jié)點(diǎn)數(shù)一定等于與其對應(yīng)的二叉樹中的葉子結(jié)點(diǎn)數(shù)。

4.度W2的樹就是二叉樹。

5.一棵Huffman樹是帶權(quán)路徑長度最短的二叉樹，權(quán)值較大的外結(jié)點(diǎn)離根較遠(yuǎn)。

6.采用二叉樹來表示樹時，樹的先根次序遍歷結(jié)果與其對應(yīng)的二叉樹的前序遍歷結(jié)果是

一樣的。

7.不存在有偶數(shù)個結(jié)點(diǎn)的滿二叉樹。

8.滿二叉樹一定是完全二叉樹，而完全二叉樹不一定是滿二叉樹。

9.已知二叉樹的前序遍歷順序和中序遍歷順序，可以惟一確定一棵二叉樹：

10.已知二叉樹的前序遍歷順序和后序遍歷順序，不能惟一確定一棵二叉樹；

三、單項(xiàng)選擇（請將正確答案的代號填寫在下表對應(yīng)題號下面。每題1分，共30分）

題號123-156789101112131415

答案

題號161718192021222324252627282930

答案

1.樹的后根遍歷序列等同于該樹對應(yīng)的二叉樹的（）.

A）.先序序列B）.中序序列C）.后序序列D）層次序列

2.設(shè)一棵二叉樹中，度為1的結(jié)點(diǎn)數(shù)為9,則該二叉樹的葉結(jié)點(diǎn)的數(shù)目是（）。

A)10B)llC)12D)不確定

3.哈夫曼算法可以用于（）。

A）動態(tài)存儲管理B）表達(dá)式求值

0數(shù)據(jù)通信的二進(jìn)制編碼D）城市間的交通網(wǎng)設(shè)計(jì)

4.在按層次遍歷二叉樹的算法中,需要借助的輔助數(shù)據(jù)結(jié)構(gòu)是（

A.隊(duì)列B.棧C.線性表D.有序表

5.在任意一棵二叉樹的前序序列和后序序列中，各葉子之間的相對次序關(guān)系（

A.不一定相同B.都相同C.都不相同D.互為逆序

6.由下列三棵樹組成的森林換成一棵二叉樹為（）。

7.若采用孩子兄弟鏈表作為樹的存儲結(jié)構(gòu)，則樹的后序遍歷應(yīng)采用二叉樹的（）。

A.層次遍歷算法B.前序遍歷算法C.中序遍歷算法D.后序遍歷算法

8.哈夫曼樹是訪問葉結(jié)點(diǎn)的外部路徑長（）的二叉樹。

A.最短；B.最長C.可變D.不定；

9.三個結(jié)點(diǎn)可以構(gòu)成（）種不同形狀的樹。

A.2；B.3C.4D.5；

10.三個結(jié)點(diǎn)可以構(gòu)成（）種不同形狀的二叉樹。

A.無窮B.3C.4D.5；

11.?棵有16個結(jié)點(diǎn)的完全二叉樹，對它按層編號，則對編號為7的結(jié)點(diǎn)X,它的雙親

結(jié)點(diǎn)及右孩子結(jié)點(diǎn)的編號分別為（）。

A.2,14B.2,15C.3,14D.3,15；

12.深度為k的二叉樹最多有（）結(jié)點(diǎn)。

A.2kB.2-1；C.2kHD.k2；

13.具有100個結(jié)點(diǎn)的完全二叉樹的深度為（）。

A.6B.7；C.8D.9；

14.葉結(jié)點(diǎn)個數(shù)比度為2的結(jié)點(diǎn)的個數(shù)多一個，該性質(zhì)只適用于（）。

A.完全二叉樹B.滿二叉樹C.樹D.所有二叉樹；

15.具有n個結(jié)點(diǎn)的完全二叉樹的深度為（）。

A.「Iog2n1+1B.LloginJ+l；C.log2nD.Llog2nJ；

16.設(shè)森林F中有三棵樹，第?、第二和第三棵樹的結(jié)點(diǎn)個數(shù)分別為Ml、M2和M3。與森

林F對應(yīng)的二叉樹根結(jié)點(diǎn)的右子樹上的結(jié)點(diǎn)個數(shù)是（）

A）MlB）M1+M2C）M2+M3D）M3；

17.二叉樹按二叉鏈表存儲，每個結(jié)點(diǎn)包含三個域（Ichild.data,rchild）,若p指針

指向二叉樹的根結(jié)點(diǎn),經(jīng)過運(yùn)算while（p->lchild!-Null）p=p->lchiId,則（）。

A.p指向二叉樹的最右下方的結(jié)點(diǎn)B.p指向二叉樹的最左下方的結(jié)點(diǎn)；

C.p仍指向根點(diǎn)D.p為null；

18.如果圖1所示為一棵二叉樹，則其中序遍歷序?yàn)椋ǎ﹐

A^abcdefghB、abdfceghC、fdbghecaD、bfdagehc；

圖1

19.對任何一棵二叉樹，若nO,nl,n2分別是度為0,1,2的結(jié)點(diǎn)的個數(shù)，則n0=（）

A.nl+lB.n2+lC.nl+n2D.2nl+1

20.如圖2所示為一線索化二叉樹，其線索化是按（）進(jìn)行的。

A、先序B、中序C、后序；D、結(jié)點(diǎn)生成順序；

B%、(C

21.如果圖3表示一棵二叉樹，且葉子結(jié)點(diǎn)d、g、h和i的權(quán)分別為4、10、6、12,則

該樹的帶權(quán)路徑長度為（）。

22.如果圖3所示是二叉樹表示的森林，則組成該森林的樹的根結(jié)點(diǎn)有（）。

A、a結(jié)點(diǎn)B、a結(jié)點(diǎn)和c結(jié)點(diǎn)；

C、b結(jié)點(diǎn)和c結(jié)點(diǎn)D、a結(jié)點(diǎn)、b結(jié)點(diǎn)和c結(jié)點(diǎn);

23.對圖3進(jìn)行廣度優(yōu)先搜索，則其搜索結(jié)點(diǎn)順序?yàn)椋ǎ?/p>

A、abcdefghi；B、abdegcfhi；C、dbgeahfic；D、dgebhifca。

24.如果圖4所示二叉樹表示一棵樹，則在該樹中結(jié)點(diǎn)d的雙親結(jié)點(diǎn)是（）。

A、a結(jié)點(diǎn):B、b結(jié)點(diǎn)C、c結(jié)點(diǎn)D、空;

圖4

25.已知某非空二叉樹采用順序存儲結(jié)構(gòu)，樹中結(jié)點(diǎn)的數(shù)據(jù)信息依次存放在一個一維數(shù)組

中，即ABCDDFEDDGDDHDD,該二叉樹的中序遍歷序列為（）

A）GD,B,A,F,H,C,EB）GB,D,A,F,H,C,E

C）B,G>D,A,F,H,C,ED）B,D,QA,F,H,C,E

26.對一棵深度為k且具有2k-l個結(jié)點(diǎn)的編號完全二叉樹，其非葉子結(jié)點(diǎn)i的右兒子結(jié)

點(diǎn)（）。

A、一定不存在；B、不?一定存在；

C、一定存在且編號為2i+l；D、一定存在且編號為2i。

27.若由森林轉(zhuǎn)化得到的二叉樹是非空的二叉樹，則二叉樹形狀是（）。

A.根結(jié)點(diǎn)無右子樹的二叉樹B.根結(jié)點(diǎn)無左子樹的二叉樹

C.根結(jié)點(diǎn)可能有左子樹和右子樹：D.各結(jié)點(diǎn)只有一個兒子和二叉樹：

28.把一棵樹轉(zhuǎn)換為二叉樹后，這棵二叉樹的形態(tài)是（）

A）唯一的，且根結(jié)點(diǎn)都沒有左孩子B）有多種，且根結(jié)點(diǎn)都沒有右孩子

C）唯一的，且根結(jié)點(diǎn)都沒有右孩子D）有多種，且根結(jié)點(diǎn)都沒有左孩子

29.已知二叉樹的先序序列為ABDEFC,中序序列為DBEAFC,則后序序列為（）

A.DEBAFCB.DEFBCAC.DEBCFAD.DEBFCA

30.某二叉樹的后序序列和中序序列正好相同，則該二叉樹一定是（）的二叉樹。

A.空或只有一個結(jié)點(diǎn)B.高度等于其結(jié)點(diǎn)數(shù)

C.空或任一結(jié)點(diǎn)無左孩子D.空或任一結(jié)點(diǎn)無右孩子

四、簡答及應(yīng)用題（共27分）

1.（6分）已知二叉樹的先序序列和中序序列分別為ABCDEFGHIJ和BCDAFEHJIG?

（1）畫出該二叉樹；

（2）畫出與（1）求得的二叉樹對應(yīng)的森林。

2.（3分）設(shè)二叉樹后根遍歷的結(jié)果為BCA,畫出所有可得到這一結(jié)果的二叉樹。

3.（4分）試說明一棵二叉樹無論進(jìn)行前序、中序或后序遍歷，其葉子結(jié)點(diǎn)的相對次序都不

會發(fā)生改變。

4、（3分）簡要說明下列算法的功能。

輸入：n個權(quán)值｛W1,W2,……，Wn）；

輸出：只包含一棵樹的集F；

過程：

⑴根據(jù)給定的n個權(quán)值｛W1,W2,……，WJ構(gòu)成n棵二叉樹集合F=｛「，T2,……，

%｝,其中每棵二叉樹Tj中只有?個帶權(quán)為Wj的根結(jié)點(diǎn)，其左右子樹均為空；

⑵在F中選取兩棵根結(jié)點(diǎn)權(quán)值最小的樹作為左右子樹,來構(gòu)造一棵新的二叉樹且置新二

叉樹根結(jié)點(diǎn)的權(quán)值為其左右子樹上根結(jié)點(diǎn)權(quán)值之和；

⑶在F中刪除這兩棵樹；

⑷重復(fù)⑵利⑶步，直到F中只有一棵樹為止；

⑸返回F。

算法的功能是：

5.（3分）給定如圖所示二叉樹T,請畫出與其對應(yīng)的中序線索二叉樹。

6.（8分）假設(shè)通信電文使用的字符集為｛C1,C2,C3,C4,C5,C6,C7｝，各字符在電文中出現(xiàn)的頻度

分別為：｛16,2,4,19,40,11,8｝,試為這7個字符設(shè)計(jì)哈夫曼編碼。清先畫出你所構(gòu)

造的哈夫曼樹（要求樹中左孩子結(jié)點(diǎn)的權(quán)值小于右孩子結(jié)點(diǎn)的權(quán)值），然后分別寫出每個字符

對應(yīng)的編碼，并求出該編碼的平均碼長（寫出計(jì)算公式及結(jié)果）。

(1)哈夫曼樹:

⑵

字符C1C2C3C4C5C6C7

權(quán)值16241940118

編碼

(3)平均碼長=

五、算法分析與設(shè)計(jì)(22分)

已知二叉樹的存儲結(jié)構(gòu)為二叉鏈表，其類型定義如下：

typedefstructBitNode

{elemtypedata;

structBitNode*lchild,*rchild;}*BinTree;

(以下各題基于上述定義)

1.(8分)計(jì)算二叉樹中葉子結(jié)點(diǎn)數(shù)的算法：請?jiān)诳瞻滋幪钊脒m當(dāng)?shù)膬?nèi)容

intCountLeaf(BinTreebt)

{/*開始時，bt為根結(jié)點(diǎn)所在鏈結(jié)點(diǎn)的指針，返回值為bt的葉子數(shù)*/

if(①)return0;

if(bt->lchild==NULL&&②)return1;

return(CountLeaf(③)+CountLeaf(④)):

2.(8分)計(jì)算二叉樹的深度的算法：請?jiān)诳瞻滋幪钊脒m當(dāng)?shù)膬?nèi)容

/*其中：max()函數(shù)可求出兩個整數(shù)中的較大值*/

intdepth(BinTreeT)

{if(!T)

Return⑤;

else

return(⑥+max(depth(⑦),depth(⑧)));}

3.(6分)閱讀算法用2,并回答下列問題：

⑴對于如圖所示的二叉樹，畫出執(zhí)行算法f32的結(jié)果；

(2)簡述算法abc的功能。

BinTreeabc(BinTreebtl)

(

BinTreebt2;

if(btl==NULL)

bt2=NULL;

else{

bt2=(BitNode*)malloc(sizeof(BiTNode));

bt2->data=bt1->data;

bt2->rchild=abc(bt1->lchild);

bt2->lchild=abc(bt1->rchild);

returnbt2;

楚雄師院計(jì)科系網(wǎng)絡(luò)工程2010級《算法與數(shù)據(jù)結(jié)構(gòu)》課后習(xí)題（第6章）參考答案

【課后習(xí)題】第6章樹和二叉樹（參考答案）

一、填空題（每空1分，共16分）

1.從邏輯結(jié)構(gòu)看，樹是典型的樹型結(jié)構(gòu)。

2.設(shè)?棵完全二叉樹具有999個結(jié)點(diǎn)，則此完全二叉樹有500個葉子結(jié)點(diǎn)，有499個

度為2的結(jié)點(diǎn)，有—L個度為1的結(jié)點(diǎn)。

3.由n個權(quán)值構(gòu)成的哈夫曼樹共有2NT個結(jié)點(diǎn)。

4.在線索化二叉樹中，T所指結(jié)點(diǎn)沒有左子樹的充要條件是T->ltag=l。

5.在非空樹上，根沒有直接前趨。

6.深度為k的二叉樹最多有2匚1結(jié)點(diǎn),最少有—個結(jié)點(diǎn)。

7.若按層次順序?qū)⒁豢糜衝個結(jié)點(diǎn)的完全二叉樹的所有結(jié)點(diǎn)從1到n編號，那么當(dāng)i為

偶數(shù)且小于n時,結(jié)點(diǎn)i的右兄弟是結(jié)點(diǎn)i+1,否則結(jié)點(diǎn)i沒有右兄弟。

8.N個結(jié)點(diǎn)的二叉樹采用二叉鏈表存放，共有空鏈域個數(shù)為N+lo

9.一棵深度為7的滿二叉樹有里個非終端結(jié)點(diǎn)。

10.將棵樹轉(zhuǎn)換為二叉樹表示后,該二叉樹的根結(jié)點(diǎn)沒有右了樹。

11.采用二叉樹來表示樹時，樹的先根次序遍歷結(jié)果與其對應(yīng)的二叉樹的人吐遍歷結(jié)果

是一樣的。

12.一棵Huffman樹是帶權(quán)路徑長度最短的二叉樹，權(quán)值較小的外結(jié)點(diǎn)離根較遠(yuǎn)。

二、判斷題（如果正確，在對應(yīng)位置打“Y”，否則打“X”。每題0.5分，共5分）

12345678910

XXXXX7qqq

三、單項(xiàng)選擇（請將正確答案的代號填寫在下表對應(yīng)題號下面。每題1分，共30分）

題號123456789101112131415

答案BDCABACAADDBBDB

題號161718192021222324252627282930

答案CBDBCBBAACCCCCD

四、簡答及應(yīng)用題（共27分）

1.（6分）（1）畫出該二叉樹;

楚雄師院計(jì)科系網(wǎng)絡(luò)工程2010級《算法與數(shù)據(jù)結(jié)構(gòu)》課后習(xí)題（第6章）參考答案

（2）畫出與（1）求得的二叉樹對應(yīng)的森林。

2.（3分）設(shè)二叉樹后根遍歷的結(jié)果為BCA,畫出所有可得到這一結(jié)果的二叉樹。

3.（4分）答：因?yàn)闊o論在前序、中序或后序遍歷中，都規(guī)定先遍歷左子樹，再遍歷右子樹,

所以一棵二叉樹無論進(jìn)行前序、中序或后序遍歷，其葉子結(jié)點(diǎn)的相對次序都不會發(fā)生改變。

4、（3分）算法的功能是構(gòu)造最優(yōu)二叉樹。

5.（3分）給定如圖所示二叉樹T,請畫出與其對應(yīng)的中序線索二叉樹。

6.(8分)

字符C1C2C3C4C5C6C7

權(quán)值16241940118

編碼110101001010111101001011

平均碼長=(16*3+2*5+4*5+19*3+40*1+11*3+8*4)/100=2.4

哈夫曼樹

楚雄師院計(jì)科系網(wǎng)絡(luò)工程2010級《算法與數(shù)據(jù)結(jié)構(gòu)》課后習(xí)題（第6章）參考答案

00

五、算法分析與設(shè)計(jì)(22分)

1.①bt==NULL②bt->rchild==NULL(3)bt->lchild④bt->rchild

2.⑤。⑥1(7)T->lchild⑧T->rchild

3.(1)

算法abc的功能：將二叉樹btl復(fù)制到M2,復(fù)制時，將btl的所結(jié)點(diǎn)的左子樹復(fù)制到bt2

對應(yīng)的右子樹;將btl的所有結(jié)點(diǎn)的右子樹復(fù)制到bt2對應(yīng)的左子樹.

楚雄師院計(jì)科系網(wǎng)絡(luò)工程2010級《算法與數(shù)據(jù)結(jié)構(gòu)》課后習(xí)題（第6章）參考答案

【課后習(xí)題】第6章樹和二叉樹（參考答案）

網(wǎng)絡(luò)工程2010級（）班學(xué)號：姓名：

題號—?二三四五總分

得分165302722100

一、填空題（每空1分，共16分）

1.從邏輯結(jié)構(gòu)看，樹是典型的樹型結(jié)構(gòu)。

2.設(shè)?棵完全二叉樹具有999個結(jié)點(diǎn)，則此完全二叉樹有500個葉子結(jié)點(diǎn)，有499個

度為2的結(jié)點(diǎn)，有—L個度為1的結(jié)點(diǎn)。

3.由n個權(quán)侑構(gòu)成的哈夫曼樹共有2NT個結(jié)點(diǎn)。

4.在線索化二叉樹中，T所指結(jié)點(diǎn)沒有左子樹的充要條件是T->ltag=l。

5.在非空樹上，根沒有直接前趨。

6.深度為k的二叉樹最多有2匚1結(jié)點(diǎn),最少有上個結(jié)點(diǎn)。

7.若按層次順序?qū)⒁豢糜衝個結(jié)點(diǎn)的完全二叉樹的所有結(jié)點(diǎn)從1到n編號，那么當(dāng)i為

偶數(shù)且小于n時,結(jié)點(diǎn)i的右兄弟是結(jié)點(diǎn)i+1,否則結(jié)點(diǎn)i沒有右兄弟。

8.N個結(jié)點(diǎn)的二叉樹采用二叉鏈表存放，共有空鏈域個數(shù)為N+1。

9.一棵深度為7的滿二叉樹有工個非終端結(jié)點(diǎn)。

10.將?棵樹轉(zhuǎn)換為二叉樹友示后，該二叉樹的根結(jié)點(diǎn)沒有右了?樹。

11.采用二叉樹來表示樹時，樹的先根次序遍歷結(jié)果與其對應(yīng)的二叉樹的先序遍歷結(jié)果

是一樣的。

12.一棵Huffman樹是帶權(quán)路徑長度最短的二叉樹，權(quán)值較小的外結(jié)點(diǎn)離根較遠(yuǎn)。

2.二叉樹的前序遍歷并不能唯一確定這棵樹，但是，如果我們還知道該二叉樹的根結(jié)

點(diǎn)是那一個，則可以確定這棵二叉樹。

3.一棵樹中的葉子結(jié)點(diǎn)數(shù)一定等于與其對應(yīng)的二叉樹中的葉子結(jié)點(diǎn)數(shù)。

4.度W2的樹就是二叉樹。

5.一棵Huffman樹是帶權(quán)路徑長度最短的二叉樹，權(quán)值較大的外結(jié)點(diǎn)離根較遠(yuǎn)。

楚雄師院計(jì)科系網(wǎng)絡(luò)工程2010級《算法與數(shù)據(jù)結(jié)構(gòu)》課后習(xí)題（第6章）參考答案

6.采用二叉樹來表示樹時，樹的先根次序遍歷結(jié)果與其對應(yīng)的二叉樹的前序遍歷結(jié)果

是?樣的。

7.不存在有偶數(shù)個結(jié)點(diǎn)的滿二叉樹。

8.滿二叉樹一定是完全二叉樹，而完全二叉樹不一定是滿二叉樹。

9.已知二叉樹的前序遍歷順序和中序遍歷順序，可以惟一確定一棵二叉樹；

10.已知二叉樹的前序遍歷順序和后序遍歷順序，不能惟一確定一棵二叉樹；

三、單項(xiàng)選擇（請將正確答案的代號填寫在下表對應(yīng)題號下面。每題1分，共30分）

題號123-156789101112131415

答案BDCABACAADDBBDB

題號161718192021222324252627282930

答案CBDBCBBAACCCCCD

1.樹的后根遍歷序列等同于該樹對應(yīng)的二叉樹的（）.

A）.先序序列B）.中序序列C）.后序序列D）層次序列

2.設(shè)一棵二叉樹中，度為1的結(jié)點(diǎn)數(shù)為9,則該二叉樹的葉結(jié)點(diǎn)的數(shù)目是（）。

A）10B）llC）12D）不確定

3.哈夫曼算法可以用于（）。

A）動態(tài)存儲管理B）表達(dá)式求值

0數(shù)據(jù)通信的二進(jìn)制編碼D）城市間的交通網(wǎng)設(shè)計(jì)

4.在按層次遍歷二叉樹的算法中,需要借助的輔助數(shù)據(jù)結(jié)構(gòu)是（）。

A.隊(duì)列B.棧C.線性表D.有序表

5.在任意一棵二叉樹的前序序列和后序序列中，各葉子之間的相對次序關(guān)系（）。

A.不一定相同B.都相同C.都不相同D.互為逆序

6.由下列三棵樹組成的森林換成一棵二叉樹為（）。

楚雄師院計(jì)科系網(wǎng)絡(luò)工程2010級《算法與數(shù)據(jù)結(jié)構(gòu)》課后習(xí)題（第6章）參考答案

7.若采用孩子兄弟鏈表作為樹的存儲結(jié)構(gòu),則樹的后序遍歷應(yīng)采用二叉樹的（）。

A.層次遍歷算法B.前序遍歷算法C.中序遍歷算法D.后序遍歷算法

8.哈夫曼樹是訪問葉結(jié)點(diǎn)的外部路徑長（）的二叉樹。

A.最短；B,最長C.可變D.不定;

9.三個結(jié)點(diǎn)可以構(gòu)成（）種不同形狀的樹。

A.2；B.3C.4D.5；

10.三個結(jié)點(diǎn)可以構(gòu)成（）種不同形狀的二叉樹。

A.無窮B.3C.4D.5；

11.一棵有16個結(jié)點(diǎn)的完全二叉樹，對它按層編號，則對編號為7的結(jié)點(diǎn)X,它的雙親結(jié)

點(diǎn)及右孩子結(jié)點(diǎn)的編號分別為（）。

A.2,14B.2,15C.3,14D.3,15；

12.深度為k的二叉樹最多有（）結(jié)點(diǎn)。

A.2kB.2-1；C.2卜,1）.k2；

13.具有100個結(jié)點(diǎn)的完全二叉樹的深度為（）。

A.6B.7；C.8D.9；

14.葉結(jié)點(diǎn)個數(shù)比度為2的結(jié)點(diǎn)的個數(shù)多一個，該性質(zhì)只適用于（）。

A.完全二叉樹B.滿二叉樹C.樹D.所有二叉樹；

15.具有n個結(jié)點(diǎn)的完全二叉樹的深度為（）。

A.「Iog2n]+1B.Llog2nJ+l；C.log2nD.Llog2nJ；

16.設(shè)森林F中有三棵樹，第一、第二和第三棵樹的結(jié)點(diǎn)個數(shù)分別為Ml、M2和M3。與森

林F對應(yīng)的二叉樹根結(jié)點(diǎn)的右子樹上的結(jié)點(diǎn)個數(shù)是（）

A）MlB）M1+M2C）M2+M3D）M3；

17.二叉樹按二叉鏈表存儲，每個結(jié)點(diǎn)包含三個域（Ichild.data、rchild）,若p指針

指向二叉樹的根結(jié)點(diǎn)，經(jīng)過運(yùn)算while（p->lchild!=Null）p=p->lchild,則（）?

A.p指向二叉樹的最右下方的結(jié)點(diǎn)B.p指向二叉樹的最左下方的結(jié)點(diǎn)；

C.p仍指向根點(diǎn)D.p為null；

18.如果圖1所示為一棵二叉樹，則其中序遍歷序?yàn)椋?o

A、abcdefghB、abdfceghC、fdbghecaD、bfdagehc；

圖1

19.對任何一棵二叉樹，若nO,nl,n2分別是度為0,1,2的結(jié)點(diǎn)的個數(shù)，則n0=（）

A.nl+IB.n2+lC.nl+n2D.2nl+1

楚雄師院計(jì)科系網(wǎng)絡(luò)工程2010級《算法與數(shù)據(jù)結(jié)構(gòu)》課后習(xí)題（第6章）參考答案

20.如圖2所示為一線索化二叉樹，其線索化是按（）進(jìn)行的。

A、先序B、中序C、后序；I）、結(jié)點(diǎn)生成順序；

圖2

21.如果圖3表示一棵二叉樹，且葉子結(jié)點(diǎn)d、g、h和i的權(quán)分別為4、10、6、12,則該

樹的帶權(quán)路徑長度為（）。

A、32B、92C、36D、8；

22.如果圖3所示是二叉樹表示的森林，則組成該森林的樹的根結(jié)點(diǎn)有（）。

A、a結(jié)點(diǎn)B、a結(jié)點(diǎn)和c結(jié)點(diǎn)；

C、b結(jié)點(diǎn)和c結(jié)點(diǎn)D、a結(jié)點(diǎn)、b結(jié)點(diǎn)和c結(jié)點(diǎn)；

23.對圖3進(jìn)行廣度優(yōu)先搜索，則其搜索結(jié)點(diǎn)順序?yàn)椋ǎ?/p>

A、abcdefghi；B、abdegcfhi；C>dbgeahfic；D、dgebhifca。

24.如果圖4所示二叉樹表示一棵樹，則在該樹中結(jié)點(diǎn)d的雙親結(jié)點(diǎn)是（）。

A、a結(jié)點(diǎn)；B、b結(jié)點(diǎn)C、c結(jié)點(diǎn)D、空；

圖4

楚雄師院計(jì)科系網(wǎng)絡(luò)工程2010級《算法與數(shù)據(jù)結(jié)構(gòu)》課后習(xí)題（第6章）參考答案

25.已知某非空二叉樹采用順序存儲結(jié)構(gòu)，樹中結(jié)點(diǎn)的數(shù)據(jù)信息依次存放在一個一維數(shù)組

中，即ABCDDFEDDGDDH口口，該二叉樹的中序遍歷序列為（）

A）GD,B,A,F,H,C,EB）GB,D,A,F,H,C,E

C）B,G,D,A,F,H,C,ED）B,D,QA,F,H,C,E

26.對一棵深度為k且具有2k-l個結(jié)點(diǎn)的編號完全二叉樹，其非葉子結(jié)點(diǎn)i的右兒子結(jié)

點(diǎn)（）。

A、一定不存在；B、不??定存在；

C、一定存在且編號為2i+l；D、一定存在且編號為2i。

27.若由森林轉(zhuǎn)化得到的二叉樹是非空的二叉樹，則二叉樹形狀是（）。

A.根結(jié)點(diǎn)無右子樹的二叉樹B.根結(jié)點(diǎn)無左子樹的二叉樹

C.根結(jié)點(diǎn)可能有左子樹和右子樹；D.各結(jié)點(diǎn)只有一個兒子和二叉樹；

28.把一棵樹轉(zhuǎn)換為二叉樹后，這棵二叉樹的形態(tài)是（）

A）唯一的，且根結(jié)點(diǎn)都沒有左孩子B）有多種，且根結(jié)點(diǎn)都沒有右孩子

C）唯一的，且根結(jié)點(diǎn)都沒有右孩子D）有多種，且根結(jié)點(diǎn)都沒有左孩子

29.已知二叉樹的先序序列為ABDEFC,中序序列為DBEAFC,則后序序列為（）

A.DEBAFCB.DEFBCAC.DEBCFAD.DEBFCA

30.某二叉樹的后序序列和中序序列正好相同，則該二叉樹一定是（）的二叉樹。

A.空或只有一個結(jié)點(diǎn)B.高度等于其結(jié)點(diǎn)數(shù)

C.空或任一結(jié)點(diǎn)無左孩子D.空或任一結(jié)點(diǎn)無右孩子

四、簡答及應(yīng)用題（共27分）

1.（6分）已知二叉樹的先序序列和中序序列分別為ABCDEFGHIJ和BCDAFEHJIG。

（1）畫出該二叉樹；

（2）畫出與（1）求得的二叉樹對應(yīng)的森林。

楚雄師院計(jì)科系網(wǎng)絡(luò)工程2010級《算法與數(shù)據(jù)結(jié)構(gòu)》課后習(xí)題（第6章）參考答案

3.（3分）設(shè)二叉樹后根遍歷的結(jié)果為BCA,畫出所有可得到這一結(jié)果的二叉樹。

4.（4分）試說明一棵二叉樹無論進(jìn)行前序、中序或后序遍歷，其葉子結(jié)點(diǎn)的相對次序都不

會發(fā)生改變。

答：因?yàn)闊o論在前序、中序或后序遍歷中，都規(guī)定先遍歷左子樹，再遍歷右子樹，所以

一棵二叉樹無論進(jìn)行前序、中序或后序遍歷，其葉子結(jié)點(diǎn)的相對次序都不會發(fā)生改變。

5、（3分）簡要說明下列算法的功能。

輸入：n個權(quán)值｛W“W2,……,Wn）；

輸出：只包含一棵樹的集F；

過程：

⑴根據(jù)給定的n個權(quán)值｛W1,W2,……，WJ構(gòu)成n棵二叉樹集合F=｛「，T2,……，

%｝,其中每棵二叉樹Tj中只有?個帶權(quán)為Wj的根結(jié)點(diǎn)，其左右子樹均為空；

⑵在F中選取兩棵根結(jié)點(diǎn)權(quán)值最小的樹作為左右子樹,來構(gòu)造一棵新的二叉樹且置新二

叉樹根結(jié)點(diǎn)的權(quán)值為其左右子樹上根結(jié)點(diǎn)權(quán)值之和；

⑶在F中刪除這兩棵樹；

⑷重復(fù)⑵利⑶步，直到F中只有一棵樹為止；

⑸返回F。

算法的功能是構(gòu)造最優(yōu)二叉樹。

6.（3分）給定如圖所示二叉樹T,請畫出與其對應(yīng)的中序線索二叉樹。

楚雄師院計(jì)科系網(wǎng)絡(luò)工程2010級《算法與數(shù)據(jù)結(jié)構(gòu)》課后習(xí)題（第6章）參考答案

7.（8分）假設(shè)通信電文使用的字符集為{C1,C2,C3,C4,C5,C6,C7}，各字符在電文中出現(xiàn)的頻度

分別為：{16,2,4,19,40,11,8},試為這7個字符設(shè)計(jì)哈夫曼編碼。請先畫出你所構(gòu)

造的哈夫曼樹（要求樹中左孩子結(jié)點(diǎn)的權(quán)值小于右孩子結(jié)點(diǎn)的權(quán)值），然后分別寫出每個字符

對應(yīng)的編碼，并求出該編碼的平均碼長（寫出計(jì)算公式及結(jié)果）。

字符C1C2C3C4C5