《精編國(guó)家開放大學(xué)電大《數(shù)據(jù)結(jié)構(gòu)》網(wǎng)絡(luò)課形考任務(wù)4作業(yè)及答案》由會(huì)員分享，可在線閱讀，更多相關(guān)《精編國(guó)家開放大學(xué)電大《數(shù)據(jù)結(jié)構(gòu)》網(wǎng)絡(luò)課形考任務(wù)4作業(yè)及答案（11頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。
1、國(guó)家開放大學(xué)電大《數(shù)據(jù)結(jié)構(gòu)》網(wǎng)絡(luò)課形考任務(wù)4作業(yè)及答案
形考任務(wù)4
一、單項(xiàng)選擇題（每小題2分，共40分）
題目1
對(duì)線性表進(jìn)行二分查找時(shí)，要求線性表必須（）o
選擇一項(xiàng)：
A. 以鏈接存儲(chǔ)方式
B. 以鏈接存儲(chǔ)方式，旦數(shù)據(jù)元素有序
C. 以順序存儲(chǔ)方式
D. 以順序存儲(chǔ)方式，且數(shù)據(jù)元素有序
題目2
采用順序查找方法查找長(zhǎng)度為n的線性表時(shí)，每個(gè)元素的平均查找長(zhǎng)度為（）。
選擇一項(xiàng)：
A. n
B. （n-l）/2
C. n/2
D. （n+1） /2
題目3
有一個(gè)長(zhǎng)度為10的有序表，按折半查找對(duì)該表進(jìn)行查找，在等概率情況下查找成功的平均比較次數(shù)為（）。
2、選擇一項(xiàng)：
A. 29/9
B. 29/10
C. 26/10
D. 31/10
題目4
已知一個(gè)有序表為｛11, 22, 33, 44, 55, 66, 77, 88, 99）,則順序查找元素55需要比較（）次。
選擇一項(xiàng)：
A. 6
B. 3
C. 5
D. 4
題目5
有數(shù)據(jù)（53, 30, 37, 12, 45, 24, 96）,從空二叉樹開始逐個(gè)插入數(shù)據(jù)來形成二叉排序樹，若希望高度最小，應(yīng)該選擇的序
列是（）o
選擇一項(xiàng)：
A. 12, 24, 30, 37, 45, 53, 96
B. 30, 24, 12, 37, 45, 96, 53
C.
3、45, 24, 53, 12, 37, 96, 30
D. 37, 24, 12, 30, 53,45, 96
題目6
對(duì)于順序存儲(chǔ)的有序表{5, 12, 20, 26, 37, 42, 46, 50, 64},若采用折半查找，則查找元素26的比較次數(shù)是（）。
選擇一項(xiàng)：
A. 4
B. 6
C. 3
D. 5
題目7
在所有的排序方法中，關(guān)鍵字比較的次數(shù)與記錄初始排列秩序無關(guān)的是（）o
選擇一項(xiàng)：
A. 希爾排序
B. 直接選擇排序
C. 冒泡排序
D. 直接插入排序
題目8
從未排序序列中依次取出元素與已經(jīng)排好序的序列中的元素作比較。將其放入已排序序列的正
4、確的位置上，此方法稱 為（）。
選擇一項(xiàng)：
A. 插入排序
B. 選擇排序
C. 歸并排序
D. 交換排序
題目9
依次將每?jī)蓚€(gè)相鄰的有序表合并成一個(gè)有序表的排序方法稱為（）o
選擇一項(xiàng)：
A. 交換排序
B. 歸并排序
C. 插入排序
D. 選擇排序
題目10
當(dāng)兩個(gè)元素出現(xiàn)逆序的時(shí)候就交換位置，這種排序方法稱為（）。
選擇一項(xiàng)：
A. 選擇排序
B. 插入排序
C. 歸并排序
D. 交換排序
題目11
每次把待排序的區(qū)間劃分為左、右兩個(gè)子區(qū)間，其中左區(qū)間中記錄的關(guān)鍵字均小于等于基準(zhǔn)記錄的關(guān)鍵字，右區(qū)間中
記錄的關(guān)鍵字均大于等于基準(zhǔn)記錄的關(guān)鍵字，這
5、種排序稱為（）。
選擇一項(xiàng)：
A. 插入排序
B. 快速排序
C. 堆排序
D. 歸并排序
題目12
一組記錄的關(guān)鍵字序列為（46, 20, 30, 79, 56,
38, 40, 84,90,110）,利用快速排序，以第一個(gè)關(guān)鍵字為分割元素,經(jīng)
過一次劃分后結(jié)果為（）o
選擇一項(xiàng)：
A. 40, 20,30,38, 46, 56, 79, 84,90, 110
B. 20,30 38, 40, 46, 56, 79, 84,90, 100
C. 20,30,40, 38, 46, 79, 56, 84,90, 100
D. 30,20,40, 38, 46,
6、84, 56, 79,90, 100
題目13
在有序表｛10, 14, 34, 43, 47, 64, 75, 80, 90｝中，用折半查找法查找值80時(shí)，經(jīng)（ ）次比較后查找成功。
選擇一項(xiàng)：
A. 5
B. 3
C. 2
D. 4 題目14 對(duì)序列（49, 38, 65, 97, 76, 13, 47, 50）采用直接插入排序法進(jìn)行排序，要把第七個(gè)元素47插入到已排序中，為 尋找插入的合適位置需要進(jìn)行（）次元素間的比較。
選擇一項(xiàng)：
A. 3
B. 4
C. 6
D. 5
題目15
排序方法中，從未排序序列中挑選元素，并將其依次放入已排序序列（初始為空）的一端
7、的方法，稱為（）排序。
選擇一項(xiàng)：
A. 插入
B. 快速
C. 歸并
D. 選擇
題目16
一組記錄的關(guān)鍵字序列為（26, 59, 36, 18, 20, 25）,利用堆排序的方法建立的初始小根堆為（）。
選擇一項(xiàng)：
A. 26, 18, 59, 20, 36, 25
B. 18, 20, 25, 59, 26, 36
C. 18, 20, 36, 59,
26, 25
D. 26, 59, 36, 18,
20, 25
題目17
一組記錄的關(guān)鍵字序列為（25, 48, 16, 35, 79, 82, 23, 40, 36, 72）,其中，含有5個(gè)長(zhǎng)度為2
8、的有序表，按歸并
排序的方法對(duì)該序列進(jìn)行一趟歸并后的結(jié)果為（）o
選擇一項(xiàng)：
A. 16, 25, 35, 48,
79, 23, 36, 40, 82, 72
B. 16, 25, 35, 48,
23, 40, 79, 82, 36, 72
C. 16, 25, 48, 35,
79, 82, 23, 36, 40, 72
D. 16, 25, 35, 48,
79, 82, 23, 36, 40, 72
題目18
已知10個(gè)數(shù)據(jù)元素為（54, 28, 16, 34, 73, 62, 95, 60, 26, 43）,對(duì)該數(shù)列從小到大排序，經(jīng)過一趟冒泡排序后
的
9、序列為（）o
選擇一項(xiàng)：
A.
16,
28,
34,
54,
62,
60,
73,
26,
43,
95
B.
28,
16,
34,
54,
62,
73,
60,
26,
43,
95
C.
16,
28,
34,
54,
73,
62,
60,
26,
43,
95
D.
28,
16,
34,
54,
62,
60,
73,
26,
43,
95
題目19
一組記錄的關(guān)鍵字序列為（46, 79, 56, 38, 40, 84）,利用快速排序，以第一個(gè)關(guān)鍵字為分割元素，經(jīng)過一次劃分后
10、
結(jié)果為（）0
選擇一項(xiàng)：
A.
40,
38,
46,
84,
56,
79
B.
40,
38,
46,
79,
56,
84
C.
38,
40,
46,
56,
79,
84
D.
40,
38,
46,
56,
79,
84
題目20
一組記錄的關(guān)鍵字序列為（80, 57, 41, 39, 46, 47）,利用堆排序（堆頂元素是最小元素）的方法建立的初始堆為（ ）。
選擇一項(xiàng)：
A.
39,
80,
46,
47,
41,
57
B.
39,
46,
41,
57,
80,
47
C.
11、
41,
39,
46,
47,
57,
80
D.
39,
47,
46,
80,
41,
57
二、程序填空題（每題10分，2題，共20分。請(qǐng)點(diǎn)擊正確選項(xiàng)，然后拖拽至相應(yīng)的方框上）
題目21
以下函數(shù)是二叉排序樹的查找算法，若二叉樹為空，則返回根結(jié)點(diǎn)的指針，否則，返回值是指向樹結(jié)點(diǎn)的結(jié)構(gòu)指 針P （查找成功p指向查到的樹結(jié)點(diǎn)，不成功p指向?yàn)镹ULL）完成程序中的空格
typedef struct Bnode
{ Int key;
struct Bnode *1汛
struct Bnode ^ight;
} Bnode;-
Bnode *BSea
12、rch(Bnode *bt, Int k)
r 于按收二叉排序閔的1艮結(jié)點(diǎn)的指針，k用以挎收吏直我的關(guān)鍵字駕
{ Bnode *p;
lt(bt== ?NULL v )
return
Pebt;
whlle(p->keyi= k v)i
(：(lf(kkey)
p=p->left v ；
else： p=p->right
lf(p=NULL) break;
}
retum( p v ;：
題目22
以下程序是折半插入排序的算法
設(shè)待排序的記錄序列存放在a[l],-a[n]中，以a[0]作為輔助工作單元，程序是要把a(bǔ)[i]插入到已經(jīng)有序的序列
void b
13、insort (NODE a[ JJnt n)
irit x j jgkm
for (1=2 ; l<= n v ；I-H-)
{咐潮
(rn (stJ)/2 v
if( x=j+1;k-?)
a|k+i| 力=a[k]；
at|+1]=a[D]i
)
}
三、綜合題(每小題8分，共40分)
題目23
(1 )設(shè)查找表為27,29,55.68)畫出對(duì)上述直詼進(jìn)行t斤半查找所對(duì)應(yīng)的判定樹，為了成功查 找到元素M,需要依次與元素 危# V進(jìn)行比較.
A. 23.10.1.1
14、4 日.23,29,27.14 C..23JD.11.14 0.23.29,55,14
(2)在等柢率條件F 成功查找的平均比較次數(shù)為,
A 24/9
B 25/9
C.3
D.2 5
題目24
(1 )-組記錄的關(guān)鍵字序列為(47.80,57,39,41 .46),利用坷非序的方:曜立的初始堆為B € / (堆頂元素是剽沅素，采用捌的形式建堆).
? , ■ . ? ? ? ?** . ? ? ■ ■ ■
A. 39,41.57.80.47,46 B.39.41,45.80,47.57
C. 39.47,46,80,41,57 D.39.41,57,
15、80,46.47
(.2)輸出堆J頁(yè)j謙后,調(diào)饕后的堆為A = 八
? * ?? ? ■ ?
A.41.47^6,80,57 8.41.57.46,60.47
C 41.57.80.47,46 D .41.90,46,47,57
題目25
〈1)對(duì)關(guān)裱字序列(56,51 71,54,46 J06),利用快速排序，以第一4關(guān)鍵字為分劇元親.經(jīng)過T欠劃分后結(jié)巢 為條圳“；
A. 46,51.56,54,71^06.
C. 46,51.54,56,71,106
0,56,51.54/671.106
D. 56.51,46,54,71.106
(2) 一組記錄的美襟字序列為(60
16、.47.00.57 . 39.41 t 46.30 ).利用歸井排序的方法甕過(2.2)歸并的 暗果序列為|
A(3S 57、60, 00.47.39.41.46 ) B. (47. 60, 57. 80, 30,39.41；46 )
0,(41.57. 60. 80. 30.39.47,46 ) 0, (47,57. 60, 80, 30,39,41.46 )
題目26
(1)對(duì)關(guān)鍵字序列(36,59,46,28,30,74)采用快激E序以第f 關(guān)鍵字為分劇元素,經(jīng)過一次劃分后的免果 序列為0 = V
A.30,28,46,36,69,74
32& 30 代6,46 . 69；,
17、 74
C. 28, 30.4 , 36,69 , 74 D. 30,28,36,46.69 , 74 ⑵用冒泡法對(duì)上述序列排序，經(jīng)兩翅冒湖腌早序列為A € V .
A 3&28.3。,46.69,74
.C. 38.36,30.46,69,74
B. 36,46,28.20.6974
D.28,36M30l46r69l74
題目27
(1 ) 一組記錄的湘t字字列為做5,40.65,43 35 95｝寫出利用快速排序的方法,以第T記錄為基街導(dǎo)
到的TSSU分的結(jié)果為 GS 9 ；
A. 35 40 65 45 35 95
(B. 3540 65 4345 95
1C. 3540 4345 65 95
D. 35 40 4543 65 95
（2 ）對(duì)上述序^利用直控插入排字.逐次插入過程中，共進(jìn)行了 口=力：欠元素間的比較.
A. 8 B； 11 C D:10
精編國(guó)家開放大學(xué)電大《數(shù)據(jù)結(jié)構(gòu)》網(wǎng)絡(luò)課形考任務(wù)4作業(yè)及答案
