數據結構課后習題(第6章)

2024年2月13日發(作者：陽光怎么形容)

楚雄師院計科系 網絡工程2010級 《算法與數據結構》課后習題（第6章）

【課后習題】第6章 樹和二叉樹

網絡工程2010級（ ）班

學號： 姓名：

題 號

得 分

一

二

三

四

五

總分

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

1. 從邏輯結構看，樹是典型的 。

2. 設一棵完全二叉樹具有999個結點，則此完全二叉樹有 個葉子結點，有

個度為2的結點，有 個度為1的結點。

3. 由n個權值構成的哈夫曼樹共有 個結點 。

4. 在線索化二叉樹中，T所指結點沒有左子樹的充要條件是 。

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

6. 深度為k的二叉樹最多有 結點，最少有 個結點。

7. 若按層次順序將一棵有n個結點的完全二叉樹的所有結點從1到n編號，那么當i為

且小于n時，結點i的右兄弟是結點 ，否則結點i沒有右兄弟。

8. N個結點的二叉樹采用二叉鏈表存放，共有空鏈域個數為 。

9. 一棵深度為7的滿二叉樹有___ ___個非終端結點。

10. 將一棵樹轉換為二叉樹表示后,該二叉樹的根結點沒有 。

11. 采用二叉樹來表示樹時，樹的先根次序遍歷結果與其對應的二叉樹的 遍歷結果是一樣的。

12. 一棵Huffman樹是帶權路徑長度最短的二叉樹，權值 的外結點離根較遠。

二、判斷題（如果正確，在對應位置打“?”，否則打“?”。每題0.5分，共5分)

1

2

3

4

5

6

7

8

9

10

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

2. 二叉樹的前序遍歷并不能唯一確定這棵樹，但是，如果我們還知道該二叉樹的根結點是那一個，則可以確定這棵二叉樹。

3. 一棵樹中的葉子結點數一定等于與其對應的二叉樹中的葉子結點數。

4. 度≤2的樹就是二叉樹。

5. 一棵Huffman樹是帶權路徑長度最短的二叉樹，權值較大的外結點離根較遠。

第 1 頁

楚雄師院計科系 網絡工程2010級 《算法與數據結構》課后習題（第6章）

6. 采用二叉樹來表示樹時，樹的先根次序遍歷結果與其對應的二叉樹的前序遍歷結果是一樣的。

7. 不存在有偶數個結點的滿二叉樹。

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

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

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

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

題號

答案

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

題號 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

答案

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

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

2. 設一棵二叉樹中，度為1的結點數為9，則該二叉樹的葉結點的數目是( )。

A)10 B)11 C)12 D)不確定

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

A) 動態存儲管理 B) 表達式求值

C) 數據通信的二進制編碼 D) 城市間的交通網設計

4. 在按層次遍歷二叉樹的算法中，需要借助的輔助數據結構是（ ）。

A．隊列 B．棧 C．線性表 D．有序表

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

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

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

第 2 頁

楚雄師院計科系 網絡工程2010級 《算法與數據結構》課后習題（第6章）

7. 若采用孩子兄弟鏈表作為樹的存儲結構，則樹的后序遍歷應采用二叉樹的（ ）。

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

8. 哈夫曼樹是訪問葉結點的外部路徑長（ ）的二叉樹。

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

9. 三個結點可以構成（ ）種不同形狀的樹。

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

10. 三個結點可以構成（ ）種不同形狀的二叉樹。

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

11. 一棵有16個結點的完全二叉樹，對它按層編號，則對編號為7的結點X，它的雙親結點及右孩子結點的編號分別為（ ）。

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

12. 深度為k的二叉樹最多有（ ）結點。

kkk-1 2A.2 B.2-1； C.2 D.k；

13. 具有100個結點的完全二叉樹的深度為（ ）。

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

14. 葉結點個數比度為2的結點的個數多一個，該性質只適用于（ ）。

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

15. 具有n個結點的完全二叉樹的深度為（ ）。

A. ?log2n?+1 B. ?log2n?+1； C. log2n D. ?log2n? ；

16. 設森林F中有三棵樹，第一、第二和第三棵樹的結點個數分別為M1、M2和M3。與森林F對應的二叉樹根結點的右子樹上的結點個數是( )

A）M1 B）M1+M2 C）M2+M3 D）M3；

17. 二叉樹按二叉鏈表存儲，每個結點包含三個域（lchild、data、rchild），若p指針指向二叉樹的根結點，經過運算while（p->lchild!=Nu11）p=p->lchild，則（ ）。

A. p指向二叉樹的最右下方的結點 B. p指向二叉樹的最左下方的結點；

C. p仍指向根點 D. p為null；

18. 如果圖1所示為一棵二叉樹，則其中序遍歷序為（ ）。

A、abcdefgh B、abdfcegh C、fdbgheca D、bfdagehc；

f g h

b c

a

d e

圖1

19. 對任何一棵二叉樹，若n0，n1，n2分別是度為0，1，2的結點的個數，則n0=( )

A.n1+1 B. n2+1 C. n1+n2 D.2n1+1

第 3 頁

楚雄師院計科系 網絡工程2010級 《算法與數據結構》課后習題（第6章）

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

A、先序 B、中序 C、后序； D、結點生成順序；

21. 如果圖3表示一棵二叉樹，且葉子結點d、g、h和i的權分別為4、10、6、12，則該樹的帶權路徑長度為（ ）。

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

g

圖3

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

A、a結點 B、a結點和c結點；

C、b結點和c結點 D、a結點、b結點和c結點；

23. 對圖3進行廣度優先搜索，則其搜索結點順序為（ ）。

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

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

A、a結點； B、b結點 C、c結點 D、空；

d

圖4

第 4 頁

A

B

D

F G

圖2

C

E

H

a

b

d e

h

f

i

c

a

b

c

楚雄師院計科系 網絡工程2010級 《算法與數據結構》課后習題（第6章）

25. 已知某非空二叉樹采用順序存儲結構，樹中結點的數據信息依次存放在一個一維數組中，即ABC□DFE□□G□□H□□，該二叉樹的中序遍歷序列為( )

A) G,D,B,A,F,H,C,E B) G,B,D,A,F,H,C,E

C) B,G,D,A,F,H,C,E D) B,D,G,A,F,H,C,E

26. 對一棵深度為k且具有2 -1個結點的編號完全二叉樹，其非葉子結點i的右兒子結點（ ）。

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

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

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

A.根結點無右子樹的二叉樹 B.根結點無左子樹的二叉樹

C.根結點可能有左子樹和右子樹； D.各結點只有一個兒子和二叉樹；

28. 把一棵樹轉換為二叉樹后，這棵二叉樹的形態是 ( )

A) 唯一的，且根結點都沒有左孩子 Ｂ）有多種，且根結點都沒有右孩子

Ｃ）唯一的，且根結點都沒有右孩子 Ｄ）有多種，且根結點都沒有左孩子

29. 已知二叉樹的先序序列為ABDEFC，中序序列為DBEAFC，則后序序列為( )

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

A. 空或只有一個結點 B.高度等于其結點數

C. 空或任一結點無左孩子 D. 空或任一結點無右孩子

四、 簡答及應用題 （共27分）

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

（1）畫出該二叉樹；

（2）畫出與（1）求得的二叉樹對應的森林。

2.(3分）設二叉樹后根遍歷的結果為BCA，畫出所有可得到這一結果的二叉樹。

3.（4分）試說明一棵二叉樹無論進行前序、中序或后序遍歷，其葉子結點的相對次序都不第 5 頁

k

楚雄師院計科系 網絡工程2010級 《算法與數據結構》課后習題（第6章）

會發生改變。

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

輸入：n個權值{W1，W2，……，Wn}；

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

過程：

⑴根據給定的n個權值{W1，W2，……，Wn}構成n棵二叉樹集合F={T1，T2，……，Tn}，其中每棵二叉樹Ti中只有一個帶權為Wi的根結點，其左右子樹均為空；

⑵在F中選取兩棵根結點權值最小的樹作為左右子樹，來構造一棵新的二叉樹且置新二叉樹根結點的權值為其左右子樹上根結點權值之和；

⑶在F中刪除這兩棵樹；

⑷重復⑵和⑶步，直到F中只有一棵樹為止；

⑸返回F。

算法的功能是：

5.

（3分）給定如圖所示二叉樹T，請畫出與其對應的中序線索二叉樹。

d

g

h i

b

e f

c

a

6.(8分)假設通信電文使用的字符集為{C1,C2,C3,C4,C5,C6,C7 }，各字符在電文中出現的頻度分別為：{16，2，4，19，40，11，8}，試為這7個字符設計哈夫曼編碼。請先畫出你所構造的哈夫曼樹(要求樹中左孩子結點的權值小于右孩子結點的權值)，然后分別寫出每個字符對應的編碼,并求出該編碼的平均碼長（寫出計算公式及結果）。

第 6 頁

楚雄師院計科系 網絡工程2010級 《算法與數據結構》課后習題（第6章）

(1)哈夫曼樹:

(2)

字符

權值

編碼

C1

16

C2

2

C3

4

C4

19

C5

40

C6

11

C7

8

(3)平均碼長=

五、算法分析與設計(22分)

已知二叉樹的存儲結構為二叉鏈表，其類型定義如下：

typedef struct BitNode

{elemtype data;

struct BitNode *lchild, *rchild;}*BinTree;

（以下各題基于上述定義）

1.(8分)計算二叉樹中葉子結點數的算法：請在空白處填入適當的內容

int CountLeaf（BinTree bt）

{/*開始時，bt為根結點所在鏈結點的指針，返回值為bt的葉子數*/

if (① ) return 0;

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

return (CountLeaf (③ )+CountLeaf (④ ));

}

2. (8分)計算二叉樹的深度的算法：請在空白處填入適當的內容

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

第 7 頁

楚雄師院計科系 網絡工程2010級 《算法與數據結構》課后習題（第6章）

int depth(BinTree T)

{if( ！T )

Return ⑤ ;

el

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

3. (6分)閱讀算法F32，并回答下列問題：

(1)對于如圖所示的二叉樹，畫出執行算法f32的結果；

（2）簡述算法abc的功能。

BinTree abc(BinTree bt1)

{

BinTree bt2;

if(bt1==NULL)

bt2=NULL;

el {

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

bt2->data=bt1->data;

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

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

}

return bt2;

}

第 8 頁

楚雄師院計科系 網絡工程2010級 《算法與數據結構》課后習題（第6章）參考答案

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

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

1. 從邏輯結構看，樹是典型的 樹型結構 。

2. 設一棵完全二叉樹具有999個結點，則此完全二叉樹有 500個葉子結點，有 499 個度為2的結點，有 0 個度為1的結點。

3. 由n個權值構成的哈夫曼樹共有 2N-1 個結點 。

4. 在線索化二叉樹中，T所指結點沒有左子樹的充要條件是 T->ltag=1 。

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

k6. 深度為k的二叉樹最多有 2-1 結點，最少有 k 個結點。

7. 若按層次順序將一棵有n個結點的完全二叉樹的所有結點從1到n編號，那么當i為

偶數 且小于n時，結點i的右兄弟是結點 i+1 ，否則結點i沒有右兄弟。

8. N個結點的二叉樹采用二叉鏈表存放，共有空鏈域個數為 N+1 。

9. 一棵深度為7的滿二叉樹有_63_個非終端結點。

10. 將一棵樹轉換為二叉樹表示后,該二叉樹的根結點沒有 右子樹 。

11. 采用二叉樹來表示樹時，樹的先根次序遍歷結果與其對應的二叉樹的 先序 遍歷結果是一樣的。

12. 一棵Huffman樹是帶權路徑長度最短的二叉樹，權值 較小 的外結點離根較遠。

二、判斷題（如果正確，在對應位置打“?”，否則打“?”。每題0.5分，共5分)

1

X

2

X

3

X

4

X

5

X

6

?

7

?

8

?

9

?

10

?

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

題號

答案

1 2 3

C

4

A

5

B

6 7 8

A

9

A

10 11 12 13 14 15

D D B B D B B D A C

題號 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

答案 C B D B C B B A A C C C C C D

四、 簡答及應用題 （共27分）

1．（6分）（1）畫出該二叉樹；第 1 頁

楚雄師院計科系 網絡工程2010級 《算法與數據結構》課后習題（第6章）參考答案

A

（2）畫出與（1）求得的二叉樹對應的森林。

B

E

G

C

F

A

E

H

D

I

B C D

F

J

2.(3分）設二叉樹后根遍歷的結果為BCA，畫出所有可得到這一結果的二叉樹。

3.（4分）答：因為無論在前序、中序或后序遍歷中，都規定先遍歷左子樹，再遍歷右子樹，所以一棵二叉樹無論進行前序、中序或后序遍歷，其葉子結點的相對次序都不會發生改變。4、（3分）算法的功能是構造最優二叉樹。

5.

（3分）給定如圖所示二叉樹T，請畫出與其對應的中序線索二叉樹。

a

b c

d e f

g h i

6.(8分)

字符

C1 C2 C3 C4 C5 C6 C7

權值

16 2 4 19 40 11 8

編碼

110 10100 10101 111 0 100 1011

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

哈夫曼樹

第 2 頁

G

H

I

J

楚雄師院計科系 網絡工程2010級 《算法與數據結構》課后習題（第6章）參考答案

100

40

60

25 35

11

14

16

19

6

8

2

4

五、算法分析與設計(22分)

1.① bt==NULL ② bt->rchild==NULL ③ bt->lchild ④ bt->rchild

2.⑤ 0 ⑥ 1 ⑦ T->lchild ⑧ T->rchild

3.(1)

算法abc的功能: 將二叉樹bt1復制到bt2,復制時,將bt1的所結點的左子樹復制到bt2對應的右子樹;將bt1的所有結點的右子樹復制到bt2對應的左子樹.

第 3 頁

楚雄師院計科系 網絡工程2010級 《算法與數據結構》課后習題（第6章）參考答案

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

網絡工程2010級（ ）班

學號： 姓名：

題 號

得 分

一

16

二

5

三

30

四

27

五

22

總分

100

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

1. 從邏輯結構看，樹是典型的 樹型結構 。

2. 設一棵完全二叉樹具有999個結點，則此完全二叉樹有 500個葉子結點，有 499 個度為2的結點，有 0 個度為1的結點。

3. 由n個權值構成的哈夫曼樹共有 2N-1 個結點 。

4. 在線索化二叉樹中，T所指結點沒有左子樹的充要條件是 T->ltag=1 。

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

6. 深度為k的二叉樹最多有 2-1 結點，最少有 k 個結點。

7. 若按層次順序將一棵有n個結點的完全二叉樹的所有結點從1到n編號，那么當i為

偶數 且小于n時，結點i的右兄弟是結點 i+1 ，否則結點i沒有右兄弟。

8. N個結點的二叉樹采用二叉鏈表存放，共有空鏈域個數為 N+1 。

9. 一棵深度為7的滿二叉樹有_63_個非終端結點。

10. 將一棵樹轉換為二叉樹表示后,該二叉樹的根結點沒有 右子樹 。

11. 采用二叉樹來表示樹時，樹的先根次序遍歷結果與其對應的二叉樹的 先序 遍歷結果是一樣的。

12. 一棵Huffman樹是帶權路徑長度最短的二叉樹，權值 較小 的外結點離根較遠。

二、判斷題（如果正確，在對應位置打“?”，否則打“?”。每題0.5分，共5分)

1

X

2

X

3

X

4

X

5

X

6

?

7

?

8

?

9

?

10

?

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

2. 二叉樹的前序遍歷并不能唯一確定這棵樹，但是，如果我們還知道該二叉樹的根結點是那一個，則可以確定這棵二叉樹。

3. 一棵樹中的葉子結點數一定等于與其對應的二叉樹中的葉子結點數。

4. 度≤2的樹就是二叉樹。

5. 一棵Huffman樹是帶權路徑長度最短的二叉樹，權值較大的外結點離根較遠。

第 1 頁

楚雄師院計科系 網絡工程2010級 《算法與數據結構》課后習題（第6章）參考答案

6. 采用二叉樹來表示樹時，樹的先根次序遍歷結果與其對應的二叉樹的前序遍歷結果是一樣的。

7. 不存在有偶數個結點的滿二叉樹。

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

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

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

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

題號

答案

1 2 3

C

4

A

5

B

6 7 8

A

9

A

10 11 12 13 14 15

D D B B D B B D A C

題號 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

答案 C B D B C B B A A C C C C C D

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

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

2. 設一棵二叉樹中，度為1的結點數為9，則該二叉樹的葉結點的數目是( )。

A)10 B)11 C)12 D)不確定

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

A) 動態存儲管理 B) 表達式求值

C) 數據通信的二進制編碼 D) 城市間的交通網設計

4. 在按層次遍歷二叉樹的算法中，需要借助的輔助數據結構是（ ）。

A．隊列 B．棧 C．線性表 D．有序表

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

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

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

第 2 頁

楚雄師院計科系 網絡工程2010級 《算法與數據結構》課后習題（第6章）參考答案

7. 若采用孩子兄弟鏈表作為樹的存儲結構，則樹的后序遍歷應采用二叉樹的（ ）。

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

8. 哈夫曼樹是訪問葉結點的外部路徑長（ ）的二叉樹。

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

9. 三個結點可以構成（ ）種不同形狀的樹。

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

10. 三個結點可以構成（ ）種不同形狀的二叉樹。

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

11. 一棵有16個結點的完全二叉樹，對它按層編號，則對編號為7的結點X，它的雙親結點及右孩子結點的編號分別為（ ）。

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

12. 深度為k的二叉樹最多有（ ）結點。

kkk-1 2A.2 B.2-1； C.2 D.k；

13. 具有100個結點的完全二叉樹的深度為（ ）。

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

14. 葉結點個數比度為2的結點的個數多一個，該性質只適用于（ ）。

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

15. 具有n個結點的完全二叉樹的深度為（ ）。

A. ?log2n?+1 B. ?log2n?+1； C. log2n D. ?log2n? ；

16. 設森林F中有三棵樹，第一、第二和第三棵樹的結點個數分別為M1、M2和M3。與森林F對應的二叉樹根結點的右子樹上的結點個數是( )

A）M1 B）M1+M2 C）M2+M3 D）M3；

17. 二叉樹按二叉鏈表存儲，每個結點包含三個域（lchild、data、rchild），若p指針指向二叉樹的根結點，經過運算while（p->lchild!=Nu11）p=p->lchild，則（ ）。

A. p指向二叉樹的最右下方的結點 B. p指向二叉樹的最左下方的結點；

C. p仍指向根點 D. p為null；

18. 如果圖1所示為一棵二叉樹，則其中序遍歷序為（ ）。

A、abcdefgh B、abdfcegh C、fdbgheca D、bfdagehc；

f g h

b c

a

d e

圖1

19. 對任何一棵二叉樹，若n0，n1，n2分別是度為0，1，2的結點的個數，則n0=( )

A.n1+1 B. n2+1 C. n1+n2 D.2n1+1

第 3 頁

楚雄師院計科系 網絡工程2010級 《算法與數據結構》課后習題（第6章）參考答案

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

A、先序 B、中序 C、后序； D、結點生成順序；

21. 如果圖3表示一棵二叉樹，且葉子結點d、g、h和i的權分別為4、10、6、12，則該樹的帶權路徑長度為（ ）。

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

g

圖3

h i

d

b

e f

c

a

F G

圖2

H

B

D

C

E

A

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

A、a結點 B、a結點和c結點；

C、b結點和c結點 D、a結點、b結點和c結點；

23. 對圖3進行廣度優先搜索，則其搜索結點順序為（ ）。

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

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

A、a結點； B、b結點 C、c結點 D、空；

d

圖4

第 4 頁

a

b

c

楚雄師院計科系 網絡工程2010級 《算法與數據結構》課后習題（第6章）參考答案

25. 已知某非空二叉樹采用順序存儲結構，樹中結點的數據信息依次存放在一個一維數組中，即ABC□DFE□□G□□H□□，該二叉樹的中序遍歷序列為( )

A) G,D,B,A,F,H,C,E B) G,B,D,A,F,H,C,E

C) B,G,D,A,F,H,C,E D) B,D,G,A,F,H,C,E

26. 對一棵深度為k且具有2 -1個結點的編號完全二叉樹，其非葉子結點i的右兒子結k點（ ）。

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

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

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

A.根結點無右子樹的二叉樹 B.根結點無左子樹的二叉樹

C.根結點可能有左子樹和右子樹； D.各結點只有一個兒子和二叉樹；

28. 把一棵樹轉換為二叉樹后，這棵二叉樹的形態是 ( )

A) 唯一的，且根結點都沒有左孩子 Ｂ）有多種，且根結點都沒有右孩子

Ｃ）唯一的，且根結點都沒有右孩子 Ｄ）有多種，且根結點都沒有左孩子

29. 已知二叉樹的先序序列為ABDEFC，中序序列為DBEAFC，則后序序列為(

30. 某二叉樹的后序序列和中序序列正好相同，則該二叉樹一定是( )的二叉樹。A. 空或只有一個結點 B.高度等于其結點數

C. 空或任一結點無左孩子 D. 空或任一結點無右孩子

四、 簡答及應用題 （共27分）

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

（1）畫出該二叉樹；

A

B

E

G

C

F

H

D

I

J

（2）畫出與（1）求得的二叉樹對應的森林。

第 5 頁

)

楚雄師院計科系 網絡工程2010級 《算法與數據結構》課后習題（第6章）參考答案

A

E G

H

B C D

F

I

J

3.(3分）設二叉樹后根遍歷的結果為BCA，畫出所有可得到這一結果的二叉樹。

4.（4分）試說明一棵二叉樹無論進行前序、中序或后序遍歷，其葉子結點的相對次序都不會發生改變。

答：因為無論在前序、中序或后序遍歷中，都規定先遍歷左子樹，再遍歷右子樹，所以一棵二叉樹無論進行前序、中序或后序遍歷，其葉子結點的相對次序都不會發生改變。

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

輸入：n個權值{W1，W2，……，Wn}；

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

過程：

⑴根據給定的n個權值{W1，W2，……，Wn}構成n棵二叉樹集合F={T1，T2，……，Tn}，其中每棵二叉樹Ti中只有一個帶權為Wi的根結點，其左右子樹均為空；

⑵在F中選取兩棵根結點權值最小的樹作為左右子樹，來構造一棵新的二叉樹且置新二叉樹根結點的權值為其左右子樹上根結點權值之和；

⑶在F中刪除這兩棵樹；

⑷重復⑵和⑶步，直到F中只有一棵樹為止；

⑸返回F。

算法的功能是構造最優二叉樹。

6.

（3分）給定如圖所示二叉樹T，請畫出與其對應的中序線索二叉樹。

d

g

h i

第 6 頁

a

b

e f

c

楚雄師院計科系 網絡工程2010級 《算法與數據結構》課后習題（第6章）參考答案

7.(8分)假設通信電文使用的字符集為{C1,C2,C3,C4,C5,C6,C7 }，各字符在電文中出現的頻度分別為：{16，2，4，19，40，11，8}，試為這7個字符設計哈夫曼編碼。請先畫出你所構造的哈夫曼樹(要求樹中左孩子結點的權值小于右孩子結點的權值)，然后分別寫出每個字符對應的編碼,并求出該編碼的平均碼長（寫出計算公式及結果）。

字符

權值

編碼

C1

16

110

C2

2

10100

C3

4

10101

C4

19

111

C5

40

0

C6

11

100

C7

8

1011

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

哈夫曼樹

100

40

60

25 35

11

14

16

19

6

8

2

4

五、算法分析與設計(22分)

已知二叉樹的存儲結構為二叉鏈表，其類型定義如下：

typedef struct BitNode

{elemtype data;

struct BitNode *lchild, *rchild;}*BinTree;

（以下各題基于上述定義）

1.(8分)計算二叉樹中葉子結點數的算法：請在空白處填入適當的內容

int CountLeaf（BinTree bt）

{/*開始時，bt為根結點所在鏈結點的指針，返回值為bt的葉子數*/

第 7 頁

楚雄師院計科系 網絡工程2010級 《算法與數據結構》課后習題（第6章）參考答案

if (① bt==NULL ) return 0;

if (bt->lchild==NULL &&② bt->rchild==NULL ) return 1;

return (CountLeaf (③ bt->lchild )+CountLeaf (④ bt->rchild ));

}

2. (8分)計算二叉樹的深度的算法：請在空白處填入適當的內容

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

int depth(BinTree T)

{if( ！T )

Return ⑤ 0 ;

el

return(⑥ 1 + max(depth(⑦T->lchild ),depth(⑧ T->rchild )));}

3. (6分)閱讀算法F32，并回答下列問題：

(1)對于如圖所示的二叉樹，畫出執行算法f32的結果；

（2）簡述算法abc的功能。

BinTree abc(BinTree bt1)

{

BinTree bt2;

if(bt1==NULL)

bt2=NULL;

el {

第 8 頁

楚雄師院計科系 網絡工程2010級 《算法與數據結構》課后習題（第6章）參考答案

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

bt2->data=bt1->data;

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

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

}

return bt2;

}

算法abc的功能: 將二叉樹bt1復制到bt2,復制時,將bt1的所結點的左子樹復制到bt2對應的右子樹;將bt1的所有結點的右子樹復制到bt2對應的左子樹.

-------------------------------------------------------------------------------------------------------------------

1、知二叉樹bt。設對bt進行中序線索化過程后，指向根結點的頭結點為thrt。再設該線索二叉樹最后一個結點的后續結點為thrt，第一個結點的前驅結點為thrt。簡要描述其線索二叉樹的中序遍歷過程 。

輸入：線索化二叉樹thrt

輸出：線索化二叉樹thrt的中序遍歷序列

過程

⑴指針P從根結點開始遍歷直到P指向thrt為止，每次遍歷執行⑵～⑸步；

⑵P向左分枝遍歷直到沒有左兒女結點為止；

⑶訪問當前結點P；

⑷如果P存在后繼結點（非右兒女結點），則不斷向右線索遍歷后繼結點P并訪問P結點；

⑸P指向其右結點；

⑹結束返回。

2．（3分）已知一棵樹如右圖所示,請將該樹轉化為二叉樹。

A

B

E

F

C

D

G

第 9 頁