第八章排序練習(xí)答案

1、第八章排序(答案)一、 選擇題1. 一組記錄的排序碼為47,78,57,39,41,85.,則利用堆排序的方法建立的初始推為 。A).78,47,57,39,41,85B).85,78,57,39,41,47C).85,78,57,47,41,39D).85,57,78,41,47,392. 一組記錄的關(guān)鍵碼為48,79,52,38,40,84.,則利用快速排序的方法，以第一個記錄為基準(zhǔn)得到的一次劃分結(jié)果為 。A).38,40, 48, 52,79,84B).40,38, 48,79, 52,84C).40,38, 48, 52,79,84D).40,38, 48,84, 52,793. 一組

2、記錄的排序碼為26,48,16,35,78,82,22,40,37,72., 其中含有5個長度為2的有序表，按歸并排序的方法對該序列進行一趟歸并后的結(jié)果為 。A).16, 26,35,48, 22,40, 78,82, 37,72B) .16, 26,35,48, 78,82, 22, 37,40,72C) .16, 26,48,35, 78,82, 22, 37,40,72D) .16, 26,35,48, 78, 22, 37,40,72,824.以下序列不是堆的是 A.105,85,98,77,80,61,82,40,22,13,66B.105,98,85,82,80,77,66,61,

3、40,22,13C.13,22,40,61,66,77,80,82,85,98,105D.105 , 85,40,77,80,61,66,98,82,13,225、下列四種排序方法中，不穩(wěn)定的方法是A.直接插入排序B.冒泡排序C.歸并排序 D.簡單選擇排序6、對下列4個序列用快速排序方法進行排序，以序列的第1個元素為基準(zhǔn)進行劃分。在第1趟劃分過程中，元素移動次數(shù)最多的是序列_A.71,75,82,90, 24,18,10,68B.71,75,68,23,10,18,90,82C.82,75,71,18,10,90,68,24D.24,10,18,71,82,75,68,907 .下列排序算法中

4、，算法可能在初始數(shù)據(jù)有序時，花費的時間反而最多。A堆排序 B冒泡排序C快速排序D插入排序8 .對包含N個元素的散列表進行檢索，平均查找長度為 .A .O(log 2N)B. O(N)C.不直接依賴于N D. 上述說法都不對9 .在各種排序方法中，從未排序序列中挑選元素，并將其依次放入已排序序列(初始時為空)的一端的方法是A.插入排序B.希爾排序C.選擇排序D.歸并排序10 . 一組記錄的關(guān)鍵字為(46,79,56,38,40,84), 則利用堆排序的方法建立的初始堆為A 79,46,56,38,40,80B 84,79,56,38,40,46C 84,79,56,46,40,38D 84,56

5、,79,40,46,3811 .對具有8個元素白W列(49,38,65,97,76,13,27,50),按升序排序，采用快速排序法第一趟的結(jié)果為 答案：27, 38, 13, 49, 76, 97, 65, 50A) 13,65,38,97,76,49,27,50B) 13,27,38,49,50,65,76,97C) 97,76,65,50,49,38,27,13D) 13,38,65,97,76,49,27,5012 .下列哪個排序?qū)儆诜€(wěn)定排序 A希爾排序B 2路排序 C 堆排序D快速排序二、填空題1、在插入排序、選擇排序、快速排序和歸并排序中，平均查找時間最少的是快速排序,要求存儲量最大

6、的是歸并排序.2、用冒泡法對n個關(guān)鍵字排序，在最好的情況下，只需做-J 次比較和 0 次移動；在最壞的情況下，要做 n(n-1)/2 次比較3、在快速排序和堆排序中，若待排序記錄序列接近正序或逆序，則應(yīng)該選用堆排序，若待排序記錄序列無序，則應(yīng)該選用快速排序.4、設(shè)順序表中有1000個元素，用折半查找時，最大比較次數(shù)為10 ,最小比較次數(shù)為1.5、已知關(guān)鍵字序列為(20, 15, 14, 18, 21, 36, 40, 10),采用快速排序法對其排序，第一趟排序后的關(guān)鍵字序列為(10,15,14,18,20,36,40,21)6、對關(guān)鍵字序列(52 , 80, 63, 46 , 90.)進行一趟

7、快速排序之后得到的結(jié)果為(46,52,63,80,90)三、簡答題1 .已知序列 72, 83, 99, 65, 10, 36, 7, 9,請給出采用插入排序法對該序列作升序排序時的每一趟的結(jié)果。初始： (72) , 83, 99, 65, 10, 36, 7, 9第 1 趟：( 72, 83 ) , 99, 65, 10, 36, 7, 9第 2 趟：( 72,83 ,99 ), 65,10,36,7, 9第 3 趟：( 65,72 ,83 ,99) ,10,36,7, 9第 4 趟：( 10, 65, 72,83,99), 36,7, 9第 5 趟：( 10, 36, 65,72,83,9

8、9) ,7, 9第 6 趟：(7, 10, 36, 65, 72, 83, 99) , 9第 7 趟：(7, 9, 10, 36, 65, 72, 83, 99)8),請給出采用shell排序法對該序列作升序2 .已知序列(10, 16, 4, 3, 6, 12, 1, 9, 15 排序時的每一趟的結(jié)果。初始：10, 16, 4, 3, 6, 12, 1, 9, 15, 8d=5第 1 趟：10, 1, 4, 3, 6, 12, 16, 9, 15, 8d=2第 2 趟：4,1,6, 3,10, 8, 15, 9,16,12d=1 第 3 趟：1,3,4, 6,8, 9, 10, 12,15,

9、163 .已知序列 17, 18, 55, 40, 7, 32, 73, 65, 89,請給出采用冒泡排序法對該序列作升序 排序的每一趟的結(jié)果。初始:17, 18, 55, 40, 7, 32, 73, 65, 89第 1趟：17,18, 40, 7,32,55,65,73,89第 2趟：17,18, 7, 32,40,55,65,73,89第 3趟：17,7, 18, 32,40,55,65,73,89第4 趟：7，17，18，32，40，55，65，73，89第5 趟：7，17，18，32，40，55，65，73，894 .已知序列 501 , 87, 512, 61, 908, 170,

10、 897, 275, 653, 462,請給出采用快速排序法對 該序列作升序排列時的每一趟的結(jié)果。初始：501, 89, 512, 61, 908, 170, 897, 276, 653, 462第11埴：462, 89, 276, 61, 170, 501, 897,908, 653, 512第2 1埴：170, 89, 276, 61, 462, 501, 897,908, 653, 512第3 1埴：61, 89, 170, 276, 462, 501, 897,908, 653, 512第4 1埴：61, 89, 170, 276, 462, 501, 897,908, 653, 51

11、2第5 1埴：61, 89, 170, 276, 462, 501, 897,908, 653, 512第6 1埴：61, 89, 170, 276, 462, 501, 897,908, 653, 512第7 1埴：61, 89, 170, 276, 462, 501, 512,653, 897, 908第8 1埴：61, 89, 170, 276, 462, 501, 512,653, 897, 908第9 1埴：61, 89, 170, 276, 462, 501, 512,653, 897, 908第10趟:61, 89, 170, 276, 462, 501, 512,653, 89

12、7, 9085 .已知序列 50, 8, 51, 6, 90, 17, 89, 27, 65, 46,請給出采用堆排序法對該序列作降序 排列時的每一趟的結(jié)果。采用堆排序法排序的各趟結(jié)果如圖所示，排序結(jié)果為 90, 89, 65, 51, 50, 46, 27, 17, 8, 6a.初始a(d)篩選調(diào)整6(e)交換89和6,輸出89(f)篩選調(diào)整g.交換65和6,輸出65h. 篩選調(diào)整i.交換51和8,輸出51(j )篩選調(diào)整(k)交換50和8,輸出50(m)交換46和8,輸出46(l )篩選調(diào)整(n)篩選調(diào)整(o).交換27和6,輸出27(p)篩選調(diào)整(q.)交換17和6,輸出17(r)篩選調(diào)

13、整(s)交換8和6,輸出8 (t)輸出66 .已知序列 513, 87, 612, 61, 908, 180, 898, 265, 673, 412,請給出，采用基數(shù)排序法 對該序列作升序排序時的每一趟的結(jié)果。初始序列：513 , 87, 612, 61, 908, 180, 899, 265, 673, 412第 1趟（按個位排序）：180, 61, 612, 412, 513, 673, 265,87,908,899第 2趟（按十位排序）：908,612 , 412, 513, 61, 265, 673,180,87 ,899第 3趟（按百位排序）：61, 87, 180, 265, 412, 513, 612,673,899,9087 .已知序列(11, 16, 6, 5, 6, 14, 1, 9),請給出采用歸并排序法對該序列