《精編國家開放大學(xué)電大《數(shù)據(jù)結(jié)構(gòu)》網(wǎng)絡(luò)課形考任務(wù)4作業(yè)及答案》由會員分享，可在線閱讀，更多相關(guān)《精編國家開放大學(xué)電大《數(shù)據(jù)結(jié)構(gòu)》網(wǎng)絡(luò)課形考任務(wù)4作業(yè)及答案（11頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、國家開放大學(xué)電大《數(shù)據(jù)結(jié)構(gòu)》網(wǎng)絡(luò)課形考任務(wù)4作業(yè)及答案 形考任務(wù)4 一、單項選擇題（每小題2分，共40分） 題目1 對線性表進行二分查找時，要求線性表必須（）o 選擇一項： A. 以鏈接存儲方式 B. 以鏈接存儲方式，旦數(shù)據(jù)元素有序 C. 以順序存儲方式 D. 以順序存儲方式，且數(shù)據(jù)元素有序 題目2 采用順序查找方法查找長度為n的線性表時，每個元素的平均查找長度為（）。 選擇一項： A. n B. （n-l）/2 C. n/2 D. （n+1） /2 題目3 有一個長度為10的有序表，按折半查找對該表進行查找，在等概率情況下查找成功的平均比較次數(shù)為（）。

2、選擇一項： A. 29/9 B. 29/10 C. 26/10 D. 31/10 題目4 已知一個有序表為｛11, 22, 33, 44, 55, 66, 77, 88, 99）,則順序查找元素55需要比較（）次。 選擇一項： A. 6 B. 3 C. 5 D. 4 題目5 有數(shù)據(jù)（53, 30, 37, 12, 45, 24, 96）,從空二叉樹開始逐個插入數(shù)據(jù)來形成二叉排序樹，若希望高度最小，應(yīng)該選擇的序 列是（）o 選擇一項： 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 對于順序存儲的有序表{5, 12, 20, 26, 37, 42, 46, 50, 64},若采用折半查找，則查找元素26的比較次數(shù)是（）。 選擇一項： A. 4 B. 6 C. 3 D. 5 題目7 在所有的排序方法中，關(guān)鍵字比較的次數(shù)與記錄初始排列秩序無關(guān)的是（）o 選擇一項： A. 希爾排序 B. 直接選擇排序 C. 冒泡排序 D. 直接插入排序 題目8 從未排序序列中依次取出元素與已經(jīng)排好序的序列中的元素作比較。將其放入已排序序列的正

4、確的位置上，此方法稱 為（）。 選擇一項： A. 插入排序 B. 選擇排序 C. 歸并排序 D. 交換排序 題目9 依次將每兩個相鄰的有序表合并成一個有序表的排序方法稱為（）o 選擇一項： A. 交換排序 B. 歸并排序 C. 插入排序 D. 選擇排序 題目10 當(dāng)兩個元素出現(xiàn)逆序的時候就交換位置，這種排序方法稱為（）。 選擇一項： A. 選擇排序 B. 插入排序 C. 歸并排序 D. 交換排序 題目11 每次把待排序的區(qū)間劃分為左、右兩個子區(qū)間，其中左區(qū)間中記錄的關(guān)鍵字均小于等于基準記錄的關(guān)鍵字，右區(qū)間中 記錄的關(guān)鍵字均大于等于基準記錄的關(guān)鍵字，這

5、種排序稱為（）。 選擇一項： A. 插入排序 B. 快速排序 C. 堆排序 D. 歸并排序 題目12 一組記錄的關(guān)鍵字序列為（46, 20, 30, 79, 56, 38, 40, 84,90,110）,利用快速排序，以第一個關(guān)鍵字為分割元素,經(jīng) 過一次劃分后結(jié)果為（）o 選擇一項： 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時，經(jīng)（ ）次比較后查找成功。 選擇一項： A. 5 B. 3 C. 2 D. 4 題目14 對序列（49, 38, 65, 97, 76, 13, 47, 50）采用直接插入排序法進行排序，要把第七個元素47插入到已排序中，為 尋找插入的合適位置需要進行（）次元素間的比較。 選擇一項： A. 3 B. 4 C. 6 D. 5 題目15 排序方法中，從未排序序列中挑選元素，并將其依次放入已排序序列（初始為空）的一端

7、的方法，稱為（）排序。 選擇一項： A. 插入 B. 快速 C. 歸并 D. 選擇 題目16 一組記錄的關(guān)鍵字序列為（26, 59, 36, 18, 20, 25）,利用堆排序的方法建立的初始小根堆為（）。 選擇一項： 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個長度為2

8、的有序表，按歸并 排序的方法對該序列進行一趟歸并后的結(jié)果為（）o 選擇一項： 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個數(shù)據(jù)元素為（54, 28, 16, 34, 73, 62, 95, 60, 26, 43）,對該數(shù)列從小到大排序，經(jīng)過一趟冒泡排序后 的

9、序列為（）o 選擇一項： 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）,利用快速排序，以第一個關(guān)鍵字為分割元素，經(jīng)過一次劃分后

10、 結(jié)果為（）0 選擇一項： 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）,利用堆排序（堆頂元素是最小元素）的方法建立的初始堆為（ ）。 選擇一項： 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分。請點擊正確選項，然后拖拽至相應(yīng)的方框上） 題目21 以下函數(shù)是二叉排序樹的查找算法，若二叉樹為空，則返回根結(jié)點的指針，否則，返回值是指向樹結(jié)點的結(jié)構(gòu)指 針P （查找成功p指向查到的樹結(jié)點，不成功p指向為NULL）完成程序中的空格 typedef struct Bnode { Int key; struct Bnode *1汛 struct Bnode ^ight; } Bnode;- Bnode *BSea

12、rch(Bnode *bt, Int k) r 于按收二叉排序閔的1艮結(jié)點的指針，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[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)畫出對上述直詼進行t斤半查找所對應(yīng)的判定樹，為了成功查 找到元素M,需要依次與元素 危# V進行比較. 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頁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)對關(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)對關(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 ⑵用冒泡法對上述序列排序，經(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 ）對上述序^利用直控插入排字.逐次插入過程中，共進行了 口=力：欠元素間的比較. A. 8 B； 11 C D:10