第九章自測題答案

1、_第9章排序自測卷答案姓名班級題號一二三四五總分題分241836814100得分一、填空題（每空1 分，共 24 分）1. 大多數(shù)排序算法都有兩個基本的操作：比較（兩個關鍵字的大?。┖鸵苿樱ㄓ涗浕蚋淖冎赶蛴涗浀闹羔槪?。2. 在對一組記錄（54 ，38，96 ，23 ，15， 72，60 ，45 ， 83）進行直接插入排序時，當把第7 個記錄 60 插入到有序表時，為尋找插入位置至少需比較3次。 (可約定為，從后向前比較)3. 在插入和選擇排序中，若初始數(shù)據(jù)基本正序，則選用插入排序（到尾部）；若初始數(shù)據(jù)基本反序，則選用選擇排序。4. 在堆排序和快速排序中，若初始記錄接近正序或反序，則選用堆排序；

2、若初始記錄基本無序，則最好選用快速排序。5. 對于 n 個記錄的集合進行冒泡排序，在最壞的情況下所需要的時間是O(n 2)。若對其進行快速排序，在最壞的情況下所需要的時間是O(n 2)。6. 對于 n 個記錄的集合進行歸并排序，所需要的平均時間是O(nlog 2n) ，所需要的附加空間是O(n)。精品資料_8. 設要將序列（ Q, H, C, Y, P, A, M, S, R, D, F, X）中的關鍵碼按字母序的升序重新排列，則：冒泡排序一趟掃描的結(jié)果是H,C,Q,P,A,M,S,R,D,F,X,Y；初始步長為4 的希爾（ shell ）排序一趟的結(jié)果是P, A, C, S, Q, D, F

3、, X , R, H,M, Y；二路歸并排序一趟掃描的結(jié)果是H,Q,C,Y ，A,P,M,S,D,R,F,X；快速排序一趟掃描的結(jié)果是F,H,C,D,P,A,M,Q,R,S,Y，X；堆排序初始建堆的結(jié)果是A,D,C,R,F,Q,M,S,Y，P,H,X。9. 在堆排序、快速排序和歸并排序中，若只從存儲空間考慮，則應首先選取堆排序方法，其次選取快速排序方法，最后選取歸并排序方法；若只從排序結(jié)果的穩(wěn)定性考慮，則應選取歸并排序方法；若只從平均情況下最快考慮，則應選取快速排序方法；若只從最壞情況下最快并且要節(jié)省內(nèi)存考慮，則應選取堆排序方法。二、單項選擇題（每小題1 分，共 18分）（C ） 1將 5 個

4、不同的數(shù)據(jù)進行排序，至多需要比較次。 . 8 . 9. 10.25（ C ）2 排序方法中，從未排序序列中依次取出元素與已排序序列（初始時為空）中的元素進行比較，將其放入已排序序列的正確位置上的方法，稱為 . 希爾排序 . 冒泡排序 . 插入排序 . 選擇排序（D）3 排序方法中，從未排序序列中挑選元素，并將其依次插入已排序序列（初始時為空）的一端的方精品資料_法，稱為 . 希爾排序 . 歸并排序 . 插入排序 . 選擇排序（ C ） 4對個不同的排序碼進行冒泡排序，在下列哪種情況下比較的次數(shù)最多。 . 從小到大排列好的 . 從大到小排列好的 . 元素無序 . 元素基本有序（ D ） 5 對個

5、不同的排序碼進行冒泡排序，在元素無序的情況下比較的次數(shù)為 . n+1. n . n-1 . n(n-1)/2( 前 3 個答案都太小了)（ C ） 6快速排序在下列哪種情況下最易發(fā)揮其長處。 .被排序的數(shù)據(jù)中含有多個相同排序碼 . 被排序的數(shù)據(jù)已基本有序 .被排序的數(shù)據(jù)完全無序 . 被排序的數(shù)據(jù)中的最大值和最小值相差懸殊（B） 7 【計研題2001 】對有 n 個記錄的表作快速排序，在最壞情況下，算法的時間復雜度是A O(n)B O(n 2 )C O(nlog 2 n)D O(n 3)（C ） 8若一組記錄的排序碼為（46, 79, 56, 38, 40, 84 ），則利用快速排序的方法，以第

6、一個記錄為基準得到的一次劃分結(jié)果為 . 38, 40, 46, 56, 79, 84 . 40,38, 46 , 79, 56, 84 . 40, 38 ， 46, 56, 79, 84 . 40, 38,46, 84, 56, 79（A&D） 9 【計研題2001 】在最好情況下，下列排序算法中排序算法所需比較關鍵字次數(shù)最少。A 冒泡B 歸并C 快速D直接插入精品資料_(僅 n 1 次！ )（A） 11 將 5 個不同的數(shù)據(jù)進行排序，至少需要比較次。.4.5.6.7（D ） 12下列關鍵字序列中，是堆。 . 16,72,31,23,94,53 . 94,23, 31, 72, 16,

7、 53 . 16, 53, 23,94,31, 72 . 16, 23, 53,31, 94, 72（B） 13 堆是一種排序。. 插入.選擇. 交換 . 歸并（ C ） 14堆的形狀是一棵 . 二叉排序樹 . 滿二叉樹. 完全二叉樹 . 平衡二叉樹（B ） 15 若一組記錄的排序碼為（46, 79, 56, 38, 40, 84），則利用堆排序的方法建立的初始堆為 . 79, 46, 56, 38, 40, 84 . 84, 79, 56, 38, 40, 46 . 84, 79, 56, 46, 40, 38 . 84, 56, 79, 40, 46, 38（ C ） 17 下述幾種排序方

8、法中，要求內(nèi)存最大的是 . 插入排序 .快速排序 . 歸并排序 . 選擇排序（ B ） 18 目前以比較為基礎的內(nèi)部排序方法中，其比較次數(shù)與待排序的記錄的初始排列狀態(tài)無關的是 . 插入排序 . 二分插入排序. 快速排序 . 冒泡排序精品資料_四、【全國專升本類似題】 【類嚴題集10.1 】以關鍵字序列（ 256 ，301 ，751 ，129 ，937 ，863 ，742 ，694 ，076 ，438 ）為例，分別寫出執(zhí)行以下算法的各趟排序結(jié)束時，關鍵字序列的狀態(tài)，并說明這些排序方法中，哪些易于在鏈表（包括各種單、雙、循環(huán)鏈表）上實現(xiàn)？ 直接插入排序 希爾排序冒泡排序 快速排序直接選擇排序 堆排序 歸并排序 基數(shù)排序（ 8 分）解：先回答第2 問： 皆易于在鏈表上實現(xiàn)。 直接插入排序的中間過程如下：希爾排序的中間過程如下：