形考作業(yè)3
試卷總分:100 得分:100
一、單項選擇題（每小題2分，共38分）
1.假定一棵二叉樹中，雙分支結(jié)點數(shù)為15，單分支結(jié)點數(shù)為30，則葉子結(jié)點數(shù)為（ ）。
A.15
B.16
C.17
D.47
2.二叉樹第k層上最多有（ ）個結(jié)點。
A.2k
B.2k-1
C.2k-1
D.2k-1
3.將含有150個結(jié)點的完全二叉樹從根這一層開始，每一層從左到右依次對結(jié)點進(jìn)行編號，根結(jié)點的編號為1，則編號為69的結(jié)點的雙親結(jié)點的編號為（ ）。
A.33
B.34
C.35
D.36
4.如果將給定的一組數(shù)據(jù)作為葉子數(shù)值，所構(gòu)造出的二叉樹的帶權(quán)路徑長度最小，則該樹稱為（ ）。
A.哈夫曼樹
B.平衡二叉樹
C.二叉樹
D.完全二叉樹
5.在一棵度具有5層的滿二叉樹中結(jié)點總數(shù)為（ ）。
A.31
B.32
C.33
D.16
6.一棵完全二叉樹共有6層，且第6層上有6個結(jié)點，該樹共有（ ）個結(jié)點。
A.38
B.72
C.31
D.37
7.利用3、6、8、12這四個值作為葉子結(jié)點的權(quán)，生成一棵哈夫曼樹，該樹中所有葉子結(jié)點中的最長帶權(quán)路徑長度為（ ）。
A.18
B.16
C.12
D.30
8.在一棵樹中，（ ）沒有前驅(qū)結(jié)點。
A.分支結(jié)點
B.葉結(jié)點
C.樹根結(jié)點
D.空結(jié)點
9.設(shè)一棵采用鏈?zhǔn)酱鎯Φ亩鏄?，除葉結(jié)點外每個結(jié)點度數(shù)都為2，該樹結(jié)點中共有20個指針域為空,則該樹有（ ）個葉結(jié)點。
A.21
B.22
C.9
D.10
10.在一個圖G中，所有頂點的度數(shù)之和等于所有邊數(shù)之和的（ ）倍。
A.1/2
B.1
C.2
D.4
11.鄰接表是圖的一種（ ）。
A.順序存儲結(jié)構(gòu)
B.鏈?zhǔn)酱鎯Y(jié)構(gòu)
C.索引存儲結(jié)構(gòu)
D.散列存儲結(jié)構(gòu)
12.圖的深度優(yōu)先遍歷算法類似于二叉樹的（ ）遍歷。
A.先序
B.中序
C.后序
D.層次
13.已知下圖所示的一個圖，若從頂點V1出發(fā)，按深度優(yōu)先搜索法進(jìn)行遍歷，則可能得到的一種頂點序列為（ ）。
{圖}
A.V1V2V4V8V3V5V6V7
B.V1V2V4V5V8V3V6V7
C.V1V2V4V8V5V3V6V7
D.V1V3V6V7V2V4V5V8
14.已知如下圖所示的一個圖，若從頂點a出發(fā)，按廣度優(yōu)先搜索法進(jìn)行遍歷，則可能得到的一種頂點序列為（ ）。
{圖}
A.abecdf
B.aecbdf
C.aebcfd
D.aedfcb
15.圖狀結(jié)構(gòu)中數(shù)據(jù)元素的位置之間存在（ ）的關(guān)系。
A.一對一
B.一對多
C.多對多
D.每一個元素都有一個且只有一個直接前驅(qū)和一個直接后繼
16.在一棵二叉樹中，若編號為i的結(jié)點存在右孩子，則右孩子的順序編號為（ ）。
A.2i
B.2i-1
C.2i+1
D.2i+2
17.一棵具有16個結(jié)點的完全二叉樹，共有（ ）層。(設(shè)根結(jié)點在第一層)
A.7
B.5
C.6
D.4
18.對二叉排序樹進(jìn)行（ ）遍歷，可以使遍歷所得到的序列是有序序列。
A.按層次
B.后序
C.中序
D.前序
19.已知一個圖的邊數(shù)為m，則該圖的所有頂點的度數(shù)之和為（ ）。
A.2m
B.m
C.2m+1
D.m/2
二、判斷題 （每小題1分，共10分）
20.一棵二叉樹的葉結(jié)點（終端結(jié)點）數(shù)為5，單分支結(jié)點數(shù)為2，該樹共有11個結(jié)點。
21.一棵有14個結(jié)點的完全二叉樹，則它的最高層上有7個結(jié)點。
22.一棵二叉樹有6個葉結(jié)點，則該樹總共有11個結(jié)點。
23.根據(jù)搜索方法的不同，圖的遍歷有．先序；中序；后序三種方法。
24.對于一棵具有n個結(jié)點的二叉樹，其相應(yīng)的鏈?zhǔn)酱鎯Y(jié)構(gòu)中共有n-1個指針域空。
25. 設(shè)一棵完全二叉樹，其最高層上最右邊的葉結(jié)點的編號為奇數(shù)，該葉結(jié)點的雙親結(jié)點的編號為10，該完全二叉樹一共有21個結(jié)點。
26. 設(shè)一棵完全二叉樹，其最高層上最右邊的葉結(jié)點的編號為偶數(shù)，該葉結(jié)點的雙親結(jié)點的編號為9，該完全二叉樹一共有19個結(jié)點。
27.按照二叉樹的遞歸定義，對二叉樹遍歷的常用算法有深度優(yōu)先遍歷和深度優(yōu)先遍兩種方法。
28.一棵有8個權(quán)重值構(gòu)造的哈夫曼數(shù)，共有17個結(jié)點。
29.一棵有7個葉結(jié)點的二叉樹，其1度結(jié)點數(shù)的個數(shù)為2，則該樹共有15個結(jié)點。
三、程序填空題（每空6分，共12分。請點擊正確選項，然后拖拽至相應(yīng)的方框上）
30. 以下程序是后序遍歷二叉樹的遞歸算法的程序，完成程序中空格部分（樹結(jié)構(gòu)中左、右指針域分別為left和right，數(shù)據(jù)域data為字符型，BT指向根結(jié)點）。完成程序中空格部分。
{圖}
void
Inorder (struct BTreeNode *BT)
{
if( BT!=NULL)
{
Inorder(BT->left);
__(1)__
__(2)__
}
利用上述程序?qū)ψ髨D進(jìn)行后序遍歷，結(jié)果是__(3)__;
(1).選項1
(2).選項2
(3).選項3
31. 以下程序是中序遍歷二叉樹的遞歸算法的程序，完成程序中空格部分（樹結(jié)構(gòu)中左、右指針域分別為left和right，數(shù)據(jù)域data為字符型，BT指向根結(jié)點）。
void Inorder (struct BTreeNode *BT)
{
{圖}
if(BT!=NULL){
Inorder(BT->left);}
__(1)__;
__(2)__;
}
利用上述程序?qū)τ覉D進(jìn)行中序遍歷，結(jié)果是__(3)__;
(1).選項1
(2).選項2
(3).選項3
四、綜合應(yīng)用題（每小題8分，5題，共40分）
32.（1）以3，4，5，8，9，作為葉結(jié)點的權(quán)，構(gòu)造一棵哈夫曼樹。該樹的帶權(quán)路徑長度為 1 .
A,64 B.65 C. 62 D. 66
（2）權(quán)重為3的葉結(jié)點的哈夫曼編碼為 2 。
A.010 B.0101 C.000 D.0111
(1).__1__
A.A
B.B
C.C
D.D
(2).__2__
A.A
B.B
C.C
D.D
33.（1）以2，3，4，7，8，9作為葉結(jié)點的權(quán)，構(gòu)造一棵哈夫曼樹，該樹的帶權(quán)路徑長度為 1
A,66 B. 80 C. 62D. 87
（2）權(quán)重值為4的葉結(jié)點的哈夫曼編碼為 2 。
A.0001 B. 1110 C.001 D. 110
(1).__1__
A.A
B.B
C.C
D.D
(2).__2__
A.A
B.B
C.C
D.D
34.（1）已知某二叉樹的后序遍歷序列是debca，中序遍歷序列是dbeac，該二叉樹的根結(jié)點是 1
A. e B. c C.b D. a
（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,
(1).__1__
A.A
B.B
C.C
D.D
(2).__2__
A.A
B.B
C.C
D.D
35.（1）已知某二叉樹的先序遍歷序列是aecdb，中序遍歷序列是eadcb，該二叉樹的根結(jié)點是 1 ;
A. e B. c C.b D. a
（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,
(1).__1__
A.A
B.B
C.C
D.D
(2).__2__
A.A
B.B
C.C
D.D
36.（1）以給定權(quán)重值5，6，17，18，25，30，為葉結(jié)點，建立一棵哈夫曼樹,該樹的中序遍歷序列為 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
（2）權(quán)重值為6的葉結(jié)點的哈夫曼為 2 .
A.1001 B.011 C.001 D.0001
(1).__1__
A.A
B.B
C.C
D.D
(2).__2__
A.A
B.B
C.C
D.D
奧鵬，國開，廣開，電大在線，各省平臺，新疆一體化等平臺學(xué)習(xí)
詳情請咨詢QQ : 3230981406或微信:aopopenfd777
