形考作業(yè)3

一、單項選擇題（每小題2分，共38分）

1.假定一棵二叉樹中，雙分支結(jié)點(diǎn)數(shù)為15，單分支結(jié)點(diǎn)數(shù)為30，則葉子結(jié)點(diǎn)數(shù)為（ ）。

A.15 B.16 C.17 D.47

答案：B

2.二叉樹第k層上最多有（ ）個結(jié)點(diǎn)。

A.2k B.2k-1(2的K-1次方） C.2k-1（2的K次方-1） D.2k-1（2K的-1次方）

答案：B

3.將含有150個結(jié)點(diǎn)的完全二叉樹從根這一層開始，每一層從左到右依次對結(jié)點(diǎn)進(jìn)行編號，根結(jié)點(diǎn)的編號為1，則編號為69的結(jié)點(diǎn)的雙親結(jié)點(diǎn)的編號為（ ）。

A.33 B.34 C.35 D.36

答案：B

4.如果將給定的一組數(shù)據(jù)作為葉子數(shù)值，所構(gòu)造出的二叉樹的帶權(quán)路徑長度最小，則該樹稱為（ ）。

A.哈夫曼樹 B.平衡二叉樹 C.二叉樹 D.完全二叉樹

答案：A

5.在一棵度具有5層的滿二叉樹中結(jié)點(diǎn)總數(shù)為（ ）。

A.31 B.32 C.33 D.16

答案：A

6.一棵完全二叉樹共有6層，且第6層上有6個結(jié)點(diǎn)，該樹共有（ ）個結(jié)點(diǎn)。

A.38 B.72 C.31 D.37

答案：D

7.利用3、6、8、12這四個值作為葉子結(jié)點(diǎn)的權(quán)，生成一棵哈夫曼樹，該樹中所有葉子結(jié)點(diǎn)中的最長帶權(quán)路徑長度為（ ）。

A.18 B.16 C.12 D.30

答案：A

8.在一棵樹中，（ ）沒有前驅(qū)結(jié)點(diǎn)。

A.分支結(jié)點(diǎn) B.葉結(jié)點(diǎn) C.樹根結(jié)點(diǎn) D.空結(jié)點(diǎn)

答案：C

9.設(shè)一棵采用鏈?zhǔn)酱鎯Φ亩鏄洌~結(jié)點(diǎn)外每個結(jié)點(diǎn)度數(shù)都為2，該樹結(jié)點(diǎn)中共有20個指針域為空,則該樹有（ ）個葉結(jié)點(diǎn)。

A.21 B.22 C.9 D.10

答案：D

10.在一個圖G中，所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)之和的（ ）倍。

A.1/2 B.1 C.2 D.4

答案：C

11.鄰接表是圖的一種（ ）。

A.順序存儲結(jié)構(gòu) B.鏈?zhǔn)酱鎯Y(jié)構(gòu) C.索引存儲結(jié)構(gòu) D.散列存儲結(jié)構(gòu)

答案：B

12.圖的深度優(yōu)先遍歷算法類似于二叉樹的（ ）遍歷。

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

答案：A

13.已知下圖所示的一個圖，若從頂點(diǎn)V1出發(fā)，按深度優(yōu)先搜索法進(jìn)行遍歷，則可能得到的一種頂點(diǎn)序列為（ ）。

A.V1V2V4V8V3V5V6V7 B.V1V2V4V5V8V3V6V7 ?C.V1V2V4V8V5V3V6V7 D.V1V3V6V7V2V4V5V8

答案：C

14.已知如下圖所示的一個圖，若從頂點(diǎn)a出發(fā)，按廣度優(yōu)先搜索法進(jìn)行遍歷，則可能得到的一種頂點(diǎn)序列為（ ）。

A.abecdf B.aecbdf C.aebcfd ?D.aedfcb

答案：B

15.圖狀結(jié)構(gòu)中數(shù)據(jù)元素的位置之間存在（ ）的關(guān)系。

A.一對一 B.一對多 C.多對多 D.每一個元素都有一個且只有一個直接前驅(qū)和一個直接后繼

答案：C

16.在一棵二叉樹中，若編號為i的結(jié)點(diǎn)存在右孩子，則右孩子的順序編號為（ ）。

A.2i B.2i-1 C.2i+1 D.2i+2

答案：C

17.一棵具有16個結(jié)點(diǎn)的完全二叉樹，共有（ ）層。(設(shè)根結(jié)點(diǎn)在第一層)

A.7 B.5 C.6 D.4

答案：B

18.對二叉排序樹進(jìn)行（ ）遍歷，可以使遍歷所得到的序列是有序序列。

A.按層次 B.后序 C.中序 D.前序

答案：C

19.已知一個圖的邊數(shù)為m，則該圖的所有頂點(diǎn)的度數(shù)之和為（ ）。

A.2m B.m C.2m+1 D.m/2

答案：A

二、判斷題 （每小題1分，共10分）

20.一棵二叉樹的葉結(jié)點(diǎn)（終端結(jié)點(diǎn)）數(shù)為5，單分支結(jié)點(diǎn)數(shù)為2，該樹共有11個結(jié)點(diǎn)。

答案：對

21.一棵有14個結(jié)點(diǎn)的完全二叉樹，則它的最高層上有7個結(jié)點(diǎn)。

答案：對

22.一棵二叉樹有6個葉結(jié)點(diǎn)，則該樹總共有11個結(jié)點(diǎn)。

答案：錯

23.根據(jù)搜索方法的不同，圖的遍歷有．先序；中序；后序三種方法。

答案：錯

24.對于一棵具有n個結(jié)點(diǎn)的二叉樹，其相應(yīng)的鏈?zhǔn)酱鎯Y(jié)構(gòu)中共有n-1個指針域空。

答案：錯

25. 設(shè)一棵完全二叉樹，其最高層上最右邊的葉結(jié)點(diǎn)的編號為奇數(shù)，該葉結(jié)點(diǎn)的雙親結(jié)點(diǎn)的編號為10，該完全二叉樹一共有21個結(jié)點(diǎn)。

答案：對

26. 設(shè)一棵完全二叉樹，其最高層上最右邊的葉結(jié)點(diǎn)的編號為偶數(shù)，該葉結(jié)點(diǎn)的雙親結(jié)點(diǎn)的編號為9，該完全二叉樹一共有19個結(jié)點(diǎn)。

答案：錯

27.按照二叉樹的遞歸定義，對二叉樹遍歷的常用算法有深度優(yōu)先遍歷和深度優(yōu)先遍兩種方法。

答案：錯

28.一棵有8個權(quán)重值構(gòu)造的哈夫曼數(shù)，共有17個結(jié)點(diǎn)。

答案：錯

29.一棵有7個葉結(jié)點(diǎn)的二叉樹，其1度結(jié)點(diǎn)數(shù)的個數(shù)為2，則該樹共有15個結(jié)點(diǎn)。

答案：對

三、程序填空題（每空6分，共12分。請點(diǎn)擊正確選項，然后拖拽至相應(yīng)的方框上）

30.以下程序是后序遍歷二叉樹的遞歸算法的程序，完成程序中空格部分（樹結(jié)構(gòu)中左、右指針域分別為left和right，數(shù)據(jù)域data為字符型，BT指向根結(jié)點(diǎn)）。完成程序中空格部分。

void

Inorder (struct BTreeNode *BT)

{

if( BT!=NULL)

{

Inorder(BT->left);

__Inorder(BT-> right )__

__printf(“%c”,BT->data)__

}

利用上述程序?qū)ψ髨D進(jìn)行后序遍歷，結(jié)果是__d,e,b,f,c,a_;

31.以下程序是中序遍歷二叉樹的遞歸算法的程序，完成程序中空格部分（樹結(jié)構(gòu)中左、右指針域分別為left和right，數(shù)據(jù)域data為字符型，BT指向根結(jié)點(diǎn)）。

void Inorder (struct BTreeNode *BT)

{

if(BT!=NULL){

Inorder(BT->left);}

__printf(“%c”,BT->data)_;

__Inorder(BT->right)__;

}

利用上述程序?qū)τ覉D進(jìn)行中序遍歷，結(jié)果是_d,b,e,a,f,c__;

四、綜合應(yīng)用題（每小題8分，5題，共40分）

32.

（1）以3，4，5，8，9，作為葉結(jié)點(diǎn)的權(quán)，構(gòu)造一棵哈夫曼樹。該樹的帶權(quán)路徑長度為 1 .

A,64 B.65 C. 62 D. 66

答案：B

（2）權(quán)重為3的葉結(jié)點(diǎn)的哈夫曼編碼為 2 。

A.010 B.0101 C.000 D.0111

答案：C

33.

（1）以2，3，4，7，8，9作為葉結(jié)點(diǎn)的權(quán)，構(gòu)造一棵哈夫曼樹，該樹的帶權(quán)路徑長度為 1

A,66 B. 80 C. 62 D. 87

答案：B

（2）權(quán)重值為4的葉結(jié)點(diǎn)的哈夫曼編碼為 2 。

A.0001 B. 1110 C.001 D. 110

答案：C

34.

（1）已知某二叉樹的后序遍歷序列是debca，中序遍歷序列是dbeac，該二叉樹的根結(jié)點(diǎn)是 1

A. e B. c C. b D. a

答案：D

（2）先序遍歷序列是 2 。

A. e,b,c,d,a B. c,a,b,,d,e C. a,b,d,e,c D. a.c,b,d,e,

答案：C

35.

（1）已知某二叉樹的先序遍歷序列是aecdb，中序遍歷序列是eadcb，該二叉樹的根結(jié)點(diǎn)是 1 ;

A. e B. c C. b D. a

答案：D

（2）后序遍歷序列為 2 。

A. e,d,b,c,a B. c,a,b,,d,e C. a,b,d,e,c D. a.c,b,d,e,

答案：A

36.

（1）以給定權(quán)重值5，6，17，18，25，30，為葉結(jié)點(diǎn)，建立一棵哈夫曼樹,該樹的中序遍歷序列為 1

A. 5，11，28，6，17，58，30，101，18，43，25

B. 5，11，6，28，17，58，30，101，18，43，25 ?

C. 5，11，6，28，101，58，30，17，18，43，25 ?

D. 5，11，6，28，17，58，30，101，18，25，43

答案：B

（2）權(quán)重值為6的葉結(jié)點(diǎn)的哈夫曼為 2 .

A. 1001 B. 011 C.001 D.0001

答案：D

?

?