國家開放大學(xué)電大《數(shù)據(jù)結(jié)構(gòu)》網(wǎng)絡(luò)課形考任務(wù)4作業(yè)及答案 檔任務(wù)4 一、單項選擇題（每小題2分，共40分） 題目1 對線性表進行二分查找時，要求線性表必須（）= 選擇一項： A. 以鏈接存儲方式 B. 以鏈接存儲方式，且數(shù)據(jù)元素有序 C. 以順序存儲方式 D. 以順序存儲方式，且數(shù)據(jù)元素有序 題目2 采用順序查找方法查找長度為n的線性表時，每個元素的平均查找長度為（）。 選擇一項： A. n B. （n-l）/2 C. n/2 D. （n+l）/2 題目3 有一個長度為10的有序表，按折半查找對該表進行查找，在等概率情況下查找成功的平均比較次數(shù)為（）. 選擇一項： 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. 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)的是（） 選擇一項： A. 希爾捧序 B. 直涯序 C. 冒泡排序 D. 直接插入捶序 題目8 從未排序序列中依次取出元素與已經(jīng)排好序的序列中的元素作比較。將其放入已排序序列的正確的位置上，此方法稱 為（）。 選擇一項： A. 插入拌序 B. 選擇排序 C. 歸并排序 D. 交換排序 題目9 依次將每兩個相鄰的有序表合并成一個有序表的排序方法稱為（）<> 選擇一項： A. 交換排序 B. 歸并排序 C. 插入排序 D. 選擇捶序 題目10 當(dāng)兩個元素出現(xiàn)逆序的時候就交換位置，這種排序方法稱為（） 選擇一項： A. 選擇捶序 B. 插入擂序 C. 歸并捶序 D. 交換排序 題目11 每次把待排序的區(qū)間劃分為左、右兩個子區(qū)間，其中左區(qū)間中記錄的關(guān)鍵字均小于等于基準(zhǔn)記錄的關(guān)鍵字，右區(qū)間中 記錄的關(guān)鍵字均大于等于基準(zhǔn)記錄的關(guān)鍵字，這種排序稱為（）。 選擇一項： A. 插入排序 B. 快鞘序 C. 堆排序 D. 歸并排序 題目12 一組記錄的關(guān)鍵字序列為（46,20,30,79, 56.38, 40, 84,90,110）,利用快速排序，以第一個關(guān)鍵字為分割元素， 經(jīng)過一次劃分后結(jié)果為（） 選擇一項： 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, 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 排序方法中，從未捶序序列中挑選元素，并將其依次放入已排序序列（初始為空）的一端的方法，稱為（）排序。 選擇一項： 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的有序表，按歸 并排序的方法對該序列進行一趟歸并后的結(jié)果為（） 選擇一項： 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)過一趟冒泡排序后 的序列為（）- 選擇一項: 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)過一次劃分 后結(jié)果為（）. 選擇一項： 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. 41, 39, 46, 47, 57, 80 D. 39, 47, 46, 80, 41, 57 二、程序填空J(rèn)S 10分，2題，共20分.請點擊正確選項，然后拖拽至相應(yīng)的方框上） 題目21 以下函數(shù)是二叉排序樹的查找算法，若二叉樹為空，則返回根結(jié)點的指針，否則，返回值是指向樹結(jié)點的結(jié)構(gòu)指 針P （查找成功P指向查到的樹結(jié)點，不成功P指向為NULL）完成程序中的空格 typedef struct Bnode ( int key; struct Bnode *left; struct Bnode *right; ) Bnode; Bnode *BSearch(Bnode *bt, int k) r bt用于接收二叉排序倒的根結(jié)點的指針，k用以接收要直找的關(guān)鍵字〃 ( Bnode *p; if(bt== NULL 寸) return (bt); P=bt; while(p->key!= k 寸) { if(k<p->key) p=p->left 寸； else p=p->right y ; if(p==NULL) break; } return( p v \ } 題目22 以下程序是折半插入排序的算法 設(shè)待排序的記錄序列存放在a[l],…a[n]中，以a[0]作為輔助工作單元，程序是要把a[i]插入到已經(jīng)有序的序 void binsort (NODE a[ ]jnt n) { intxjj.sKm; for (i=2 ; i<= n 寸;i++ ) { a(0]=ali]; x= a[i].key; S=1； j=i-1； while (s<=j) { m=| (s+jy2 I ? for (k=k1;k>=j+1;k--) a[k+l] v =a[k]; a[j+1]=a[Oj; } } 三、綜合題(每小題8分，共40分) 題目23 (1)設(shè)查找表為(1,10,11,14,23,27,29,55,68)，畫出對上述直找表進行折半直找所對應(yīng)的判定樹，為了成功查 找到元素14,需要依次與元素C = V進行比較。 A. 23.10.1.14 B.23.29.27.14 C. 23.10,11.14 D.23.29.55,14 (2 )在等概率條件下，成功查找的平均比較次數(shù)為B # V。 A.24/9 B. 25/9 C.3 D.2.5 題目24 2 - (47、80、57、3gkr46 )、^sisiiMU^ B " < 《磊島沖洲池婀、M沖洲-米曲食3*斗厚)。 >? 39-4L57.847.46 B.3g.4BCDp47.57 0- 3g.47.46.84L57 D.39.4L5700P46.47 Q 淳任A " < - A4M7.46.8P57 B.4L5746.8P47 C.4L57.8P47.46 D.4L8P4647.57 s 25 (1)咨冰電囤倒(56公.7言4含.占6).絲魚港廁贛>? 、潛白—>竺少on爵油 翌c ” < ; >? 46.5L56.54m 二。6 B. 56.5L54.46.7二06 0-46.5L54.56.7L106 0. 56.5L46.54.71M6 -e —Baucis ( 6.470?57、39kr46 .3。)、座理1JJ%4 藻3,卅成K(2.2s*s 籍&*一 0 A?(3p57. 6P8P47.39.4L46 ) B.(47. 6P57?000. 3P39BM6 ) C.(4L 57. 6P8P30.3g.47.46 ) 0. (47. 573 8P30.3941 .46 ) 筒IE26 (1) 涔冰漏40囤涅(36念.46.28.3。?74)湘丑>5廖贛>、H普府*葉慰弟、的心—壽竺冷5B3器油 畫浸D " < A3T 28 ~ 46 ~ 36 ~ 69 ~74 B.2S03?36 ~ 46 ~ 69 ~ 74 92W 3CL46L6 ~ 69 ~ 74 0- 3T 28 ~ 36k6 ~ 69 L4 (2) ? >? 36.28.3。46念.74 w 3646.28.2P69-74 ?0- 38.36.3。.46 念.74 D.2B.36..3P46.6W74 S 27 (--、4。、65\3 ? 35 ? 951任迷前一港圓巖教圳研? 座3&性d)曹醐涉00 < - A 35 40 65 45 35 95 B 35 4。65 43 45 95 935 4043 45 65 95 D? 35 40 45 43 65 95 （2 ）對上述序511利用直接插入排序，逐次插入過程中，共進行了 D W /次元素間的比較? A. 8 B. 11 C.9 D 10