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