國(guó)家開放大學(xué)電大《數(shù)據(jù)結(jié)構(gòu)》網(wǎng)絡(luò)課形考任務(wù)4作業(yè)及答案

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. nB. （n-l）/2C. n/2D. （n+1） /2題目3有一個(gè)長(zhǎng)度為10的有序表，按折半查找對(duì)該表進(jìn)行查找，在等概率情況下查找成功的平均比較次數(shù)為（）。選擇一項(xiàng)：A. 29/9B. 29/10C. 26/10D. 31/10題目4已

2、知一個(gè)有序表為11, 22, 33, 44, 55, 66, 77, 88, 99）,則順序查找元素55需要比較（）次。選擇一項(xiàng)：A. 6B. 3C. 5D. 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, 96B. 30, 24, 12, 37, 45, 96, 53C. 45, 24, 53, 12, 37, 96, 30D. 37, 24, 12, 30, 53,45, 96題目6對(duì)于順序存儲(chǔ)的有序表5, 12, 20,

3、 26, 37, 42, 46, 50, 64,若采用折半查找，則查找元素26的比較次數(shù)是（）。選擇一項(xiàng)：A. 4B. 6C. 3D. 5題目7在所有的排序方法中，關(guān)鍵字比較的次數(shù)與記錄初始排列秩序無關(guān)的是（）o選擇一項(xiàng)：A. 希爾排序B. 直接選擇排序C. 冒泡排序D. 直接插入排序題目8從未排序序列中依次取出元素與已經(jīng)排好序的序列中的元素作比較。將其放入已排序序列的正確的位置上，此方法稱 為（）。選擇一項(xiàng)：A. 插入排序B. 選擇排序C. 歸并排序D. 交換排序題目9依次將每?jī)蓚€(gè)相鄰的有序表合并成一個(gè)有序表的排序方法稱為（）o選擇一項(xiàng)：A. 交換排序B. 歸并排序C. 插入排序D. 選擇排

4、序題目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)鍵字，這種排序稱為（）。選擇一項(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,8

5、4,90,110B. 20,3038,40,46,56,79,84,90,100C. 20,30,40,38,46,79,56,84,90,100D. 30,20,40,38,46,84,56,79,90,100題目13在有序表10, 14, 34, 43, 47, 64, 75, 80, 90中，用折半查找法查找值80時(shí)，經(jīng)（）次比較后查找成功。選擇一項(xiàng)：A. 5B. 3C. 2D. 4 題目14 對(duì)序列（49, 38, 65, 97, 76, 13, 47, 50）采用直接插入排序法進(jìn)行排序，要把第七個(gè)元素47插入到已排序中，為 尋找插入的合適位置需要進(jìn)行（）次元素間的比較。選擇一項(xiàng)：A.

6、 3B. 4C. 6D. 5題目15排序方法中，從未排序序列中挑選元素，并將其依次放入已排序序列（初始為空）的一端的方法，稱為（）排序。選擇一項(xiàng)：A. 插入B. 快速C. 歸并D. 選擇題目16一組記錄的關(guān)鍵字序列為（26, 59, 36, 18, 20, 25）,利用堆排序的方法建立的初始小根堆為（）。選擇一項(xiàng)：A.26,18,59,20,36, 25B.18,20,25,59,26, 36C.18,20,36,59,26, 25D.26,59,36,18,20, 25題目17一組記錄的關(guān)鍵字序列為（25, 48, 16, 35, 79, 82, 23, 40, 36, 72）,其中，含有5

7、個(gè)長(zhǎng)度為2的有序表，按歸并排序的方法對(duì)該序列進(jìn)行一趟歸并后的結(jié)果為（）o選擇一項(xiàng)：A.16, 25,35,48,79,23,36,40,82,72B.16, 25,35,48,23,40,79,82,36,72C.16, 25,48,35,79,82,23,36,40,72D.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)過一趟冒泡排序后的序列為（）o選擇一項(xiàng)：A.16,28, 34, 54, 62,60,73,26, 43, 95B.28,16,

8、 34, 54, 62,73,60,26, 43, 95C.16,28, 34, 54, 73,62,60,26, 43, 95D.28,16, 34, 54, 62,60,73,26, 43, 95題目19一組記錄的關(guān)鍵字序列為（46, 79, 56, 38, 40, 84）,利用快速排序，以第一個(gè)關(guān)鍵字為分割元素，經(jīng)過一次劃分后結(jié)果為（）0選擇一項(xiàng)：A.40,38,46, 84,56,79B.40,38,46, 79,56,84C.38,40,46, 56,79,84D.40,38,46, 56,79,84題目20一組記錄的關(guān)鍵字序列為（80, 57, 41, 39, 46, 47）,利用

9、堆排序（堆頂元素是最小元素）的方法建立的初始堆為（）。選擇一項(xiàng)：A.39,80,46,47,41,57B.39,46,41,57,80,47C.41,39,46,47,57,80D.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 stnjct Bnode ( Int key; struct Bnodeleft; struct B

10、node *right; Bnode;-Bnode *BSearch(Bnode *bt, Int k)r btffi于按收二K排字崗的t艮結(jié)點(diǎn)的指針次用以挎收要直找的關(guān)鍵字弓； Bnode *p;lt(bt= ?NULL v ) return (bt嶄 P13成 whlle(p->keyi- k )i lf(k孕Weyj p=p->left v ；else： p=p->right lf(pNULL) break; retum( p v ;：3題目22以下程序是折半插入排序的算法 設(shè)待排序的記錄序列存放在al,an中，以a0作為輔助工作單元，程序是要把a(bǔ)i插入到已經(jīng)有序的序列

11、void binsort (NODE a JJnt n)irit x j jgkmfor (1=2 ; l<= n v ；I-H-)咐渤(rn« (stJ)/2 vif( x<amakey)j=m-1 yelses=m+1 v)for (k1;k>=j+1;k-)a|k+i| 力=ak；at|+1=aDi)三、綜合題(每小題8分，共40分)題目23(1 )設(shè)查找表為27,29,55.68)畫出對(duì)上述直詼進(jìn)行t斤半查找所對(duì)應(yīng)的判定樹，為了成功查 找到元素M,需要依次與元素 危# V進(jìn)行比較.A. 23.10.1.14日.23,29,27.14C.23JD.11.14

12、0.23.29,55,14(2)在等柢率條件F 成功查找的平均比較次數(shù)為八A.24/9B.25/9:C.3D.2.5題目24(1 )-組記錄的關(guān)鍵字序列為(47,80,57,39,41 .46),利用坷非序的方:垃立的初始堆為B / 堆晰素秘dN,禍捌曬.A. 39.41.57,80,47.460,39,47,46,80.41,57：舊,3941,4£.如,47.57D.39.4t,57,80,46.47(2)輸出堆頂元素后,調(diào)整后的堆為AS V , 一:A,41,47.46,80.57C .41.57.60.47,468.41,57.46.80.47D.41.80,46,47,57

13、題目251)對(duì)關(guān)裱字序列(56,51 71,54,46 J06),利用快速排序，以第一4關(guān)鍵字為分劇元素.經(jīng)過T欠劃分后結(jié)巢 為#泮| “ :;A, 46.51.56,54,71406. B. 56.51.54,46,71.1060.46,51,54,5671,106D 56f51t46f54t71J06(2) 一組記錄的E字序列為(60.4? . 00.57 . 39.41 . 46.30 ).利用歸井排序的方法甕過(2,2)歸并的 暗果序5U為D s V &A.(30. 57. 60. 00,47,39,41.46 )0-(47.60.57.80.30,39.41 46 )C,(4

14、1457. 60. 80. 30.39,47,46 ) D. (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)過一次劃分后的免果 序列為耳=VA.30,28,4636,69,74B2& 30 r 36 r 46.69 ; 74C.20I 30.4536.69,74D.30；t:28,36,46.69,74(2) 用冒泡法對(duì)上述序列排序，經(jīng)兩趣冒泡的蜻早序列為A # .A. 36.28.30,46.69.74B. 36,46,28.20,69,74-書C“ 383&30.46,69.74D.28,36.,30,46,