《精編國家開放大學電大《數(shù)據(jù)結構》網(wǎng)絡課形考任務3作業(yè)及答案》由會員分享，可在線閱讀，更多相關《精編國家開放大學電大《數(shù)據(jù)結構》網(wǎng)絡課形考任務3作業(yè)及答案（9頁珍藏版）》請在裝配圖網(wǎng)上搜索。
1、國家開放大學電大《數(shù)據(jù)結構》網(wǎng)絡課形考任務3作業(yè)及答案
形考任務3
一、單項選擇題（每小題2分，共38分）
題目1
假定一棵二叉樹中，雙分支結點數(shù)為15,單分支結點數(shù)為30,則葉子結點數(shù)為（）o
選擇一項：
A. 47
B. 16
C. 17
D. 15
題目2
二叉樹第k層上最多有（）個結點。
選擇一項：
A. 2k-l
B. 2k-l
C. 2k-l
D. 2k
題目3
將含有150個結點的完全二叉樹從根這一層開始，每一層從左到右依次對結點進行編號，根結點的編號為1,則編號為
69的結點的雙親結點的編號為（）o
選擇一項：
A. 36
B. 35
2、
C. 34
D. 33
題目4
如果將給定的一組數(shù)據(jù)作為葉子數(shù)值，所構造出的二叉樹的帶權路徑長度最小，則該樹稱為（）o
選擇一項：
A. 二叉樹
B. 哈夫曼樹
C. 完全二叉樹
D. 平衡二叉樹
在一棵度具有5層的滿二叉樹中結點總數(shù)為（）o
選擇一項：
A. 16
B. 32
C. 31
D. 33
題目6
一棵完全二叉樹共有6層，且第6層上有6個結點，該樹共有（）個結點。
選擇一項：
A. 31
B. 37
C. 38
D. 72
題目7
利用3、6、8、12這四個值作為葉子結點的權，生成一棵哈夫曼樹，該樹中所有葉子結點中的最長帶權路徑長度
3、為（）。
選擇一項：
A. 18
B. 16
C. 30
D. 12
題目8
在一棵樹中，（）沒有前驅(qū)結點。
選擇一項：
A. 樹根結點
B. 葉結點
C. 空結點
D. 分支結點
題目9
設一棵采用鏈式存儲的二叉樹，除葉結點外每個結點度數(shù)都為2,該樹結點中共有20個指針域為空，則該樹有（ ）
個葉結點。
選擇一項：
C. 21
D. 22
題目10
在一個圖G中，所有頂點的度數(shù)之和等于所有邊數(shù)之和的（）倍。
選擇一項：
A. 2
B. 1
C. 4
D. 1/2
題目11
鄰接表是圖的一種（）o
選擇一項：
A. 鏈式存儲結構
B.
4、 順序存儲結構
C. 散列存儲結構
D. 索引存儲結構
題目12
圖的深度優(yōu)先遍歷算法類似于二叉樹的（）遍歷。
選擇一項：
A. 先序
B. 后序
C. 層次
D. 中序
題目13
已知下圖所示的一個圖，若從頂點VI出發(fā)，按深度優(yōu)先搜索法進行遍歷，則可能得到的一種頂點序列為（）。
選擇一項：
A. V1V2V4V5V8V3V6V7
B. V1V3V6V7V2V4V5V8
C. V1V2V4V8V3V5V6V7
D. V1V2V4V8V5V3V6V7
題目14
已知如下圖所示的一個圖，若從頂點a出發(fā)，按廣度優(yōu)先搜索法進行遍歷，則可能得到的一種頂點序列為（ ）o
5、
選擇一項：
A. aedfcb
B. abecdf
C. aebcfd
D. aecbdf
題目15
圖狀結構中數(shù)據(jù)元素的位置之間存在（ ）的關系。
選擇一項：
A. 一對多
B. 多對多
C. 每一個元素都有一個且只有一個直接前驅(qū)和一個直接后繼
D. 一對一
題目16
在一棵二叉樹中，若編號為i的結點存在右孩子，則右孩子的順序編號為（ ）o
選擇一項：
A. 2i+l
B. 2i-l
C. 2i
D. 2i+2
題目17
一棵具有16個結點的完全二叉樹，共有（ ）層。（設根結點在第一層）
選擇一項：
A. 7
B. 5
C. 6
D. 4
6、
題目18
對二叉排序樹進行（
）遍歷，可以使遍歷所得到的序列是有序序列。
選擇一項:
A. 按層次
B. 中序
C. 前序
D. 后序
)o
已知一個圖的邊數(shù)為m則該圖的所有頂點的度數(shù)之和為（
選擇一項：
A. m/2
B. m
C. 2m
D. 2m+l
二、判斷題（每小題1分，共10分）
題目20
一棵二叉樹的葉結點（終端結點）數(shù)為5,單分支結點數(shù)為2,該樹共有11個結點。
選擇一項：
對
錯
題目21
一棵有14個結點的完全二叉樹，則它的最高層上有7個結點。
選擇一項：
對
錯
題目22
一棵二叉樹有6個葉結點，則該樹總共有1
7、1個結點。
選擇一項：
對
錯
題目23
根據(jù)搜索方法的不同，圖的遍歷有.先序；中序；后序三種方法。
選擇一項：
對
錯
題目24
對于一棵具有n個結點的二叉樹，其相應的鏈式存儲結構中共有n-1個指針域空。
選擇一項：
對
錯
設一棵完全二叉樹，其最高層上最右邊的葉結點的編號為奇數(shù)，該葉結點的雙親結點的編號為10,該完全二叉樹 一共有21個結點。
選擇一項：
對
錯
題目26
設一棵完全二叉樹，其最高層上最右邊的葉結點的編號為偶數(shù)，該葉結點的雙親結點的編號為9,該完全二叉樹一 共有19個結點。
選擇一項：
對
錯
題目27
按照二叉樹的遞歸定義，
8、對二叉樹遍歷的常用算法有深度優(yōu)先遍歷和深度優(yōu)先遍兩種方法。
選擇一項：
對
錯
題目28
一棵有8個權重值構造的哈夫曼數(shù)，共有17個結點。
選擇一項：
對
錯
題目29
一棵有7個葉結點的二叉樹，其1度結點數(shù)的個數(shù)為2,則該樹共有15個結點。
選擇一項：
對
錯
三、程序填空題（每空6分，共12分。請點擊正確選項，然后拖拽至相應的方框上）
題目30
以下程序是后序遍歷二叉樹的遞歸算法的程序,完成程序中空格部分（樹結構中左、右指針域分別為left和right, 數(shù)據(jù)域data為字符型，BT指向根結點）。完成程序中空格部分。
void
inorder (str
9、uct BTreeNode *BT)
(
if( BTI=NULL)
(
lnarder(BT->left);
lnorder(BT-> right) v
printff,BT->data) v
利用上逑程序?qū)ψ髨D進行后序遍歷，結果是 d.e.b.f.c.a
題目31
以下程序是中序遍歷二叉樹的遞歸算法的程序,完成程序中空格部分（樹結構中左、右指針域分別為left和right, 數(shù)據(jù)域data為字符型，BT指向根結點）。
void Inorder (struct BTreeNode *BT)
lnarder(BT->left)；｝
printf(,%cM,BT->dat
10、a) rlght) v .
利用上述程序?qū)τ覉D進行中序遍歷，結果是 d.b.e.a.f.c
四、綜合應用題（每小題8分，5題，共40分）
題目32
（1 ）以3,4/5,89,作為葉結點的權,杓造F昭夫受利?正捌的帶枝路徑長度為 B
A.64 B.65 C. 62 D. 66
《2）權重為3的葉結點的哈夫曼漏碼為V .
A.010 BD101 C.000 D.0111
題目33
(1 )以2 3 4 7 , 8 9作為口十結點的權 構母一觸夫曼枸 該柯的希權路徑長度為B € ?
-
A.66 B.80 C.62 D::07
⑵權重值為
11、4的葉結點的哈夫曼編碼為C #八
A.0001 B. 1110 C.001 D.：110
題目34
(1)已知某二叉樹的后序遍歷序列是debc*中序遍歷序列是dbeac,該二叉樹的根結點是【， / Ae B c c； b D a
皿)先序遍用序列是C： ▼ / ,
A. e.0xc.d,a C. a.b.d.e.c D. a.c.b.d.e,
題目35
(1)已知某二叉樹的先序遍歷序列是沖曲，中序遍用序列是eadcb,該二叉樹的根結點是d S 5 i
A/e: B-C IC.b Df.a
(2 )后序遍歷序列為I A # 力.
A, e.0,b.c,a B. c,a4bHd
12、,e C a.Dtd.8.c D. a.c.b.d.e；
題目36
(1)以結定權重值5,金17. 18< 25, 30,為葉結點，建立一禪哈夫曼樹，該樹的中序遍歷序列為B ?
A.5, 11, 28, 6, 17, 58, 3。. 101, 18, 43, 25
4 3, 25
C.5,
Ih 6, 28, 10I> 58, 30< 17.
18,
43. 25
lb 6, 28, 17, 58, 30, 10h
18f 25, 43.
D. S, lb 6, 2& 17，5& 30, IDb
(2)權.重值為6的葉結點的哈夫曼為I)e ?
A. 1DD1 B.D11 C.001 D.00D1
精編國家開放大學電大《數(shù)據(jù)結構》網(wǎng)絡課形考任務3作業(yè)及答案
