1、單元測驗10一.判斷題（下列各題，正確的請在前面的括號內打，；錯誤的打 X ）（義）（1）如果某種排序算法不穩定，則該排序方法就【沒】有實用價值。（，）（2）希爾排序是不穩定的排序。（義）（3）冒泡排序是 【不】穩定的排序。（，）（4）對n個記錄的進行快速排序，所需要的平均時間是O（nlog 2n）。（義）（5）堆排序所需的時間與待排序的記錄個數【無】有關。（，）（6）當待排序的元素個數很多時，為了交換元素的位置要占用較多的時間，這是影響時間復 雜度的主要因素。（義）（7）快速排序 不是在任何 情況下 都比其 它排序方 法速度 快。（，）（8）對快速排序來說，初始序列為正序或反序都是最壞情況。

2、（，）（9）采用歸并排序可以實現外排序。（，）（10）采用希爾方法排序時，若關鍵字的排列雜亂無序，則效率最高（，）（11）快速排序算 法在每一趟排序中都能找到一個元素放在其最終位置上。（，）（12）冒泡排序的時間復雜度是 O （n2）。.填空題（1） 大多數排序算法都有兩個基本的操作：比較 和移動。（2） 評價排序算法優劣的主要標準是時間復雜度和算法所需的附加空間。（3） 根據被處理的數據在計算機中使用不同的存儲設備，排序可分為：內排序和外排序。（4） 外排序是指在排序過程中，數據的主要部分存放在計算機的外存 中。（5） 對n個關鍵字進行冒泡排序，其可能的最小比較次數為：n-1 次。（6） 在

3、最壞情況下，在第i趟直接插入排序中，要進行 i-1 次關鍵字的比較。（7） 對n個關鍵字進行冒泡排序，時間復雜度為O（n 2）（8） 快速排序在最壞情況下的時間復雜度是O（n 2）。O(log2n)O(n) 。不變的排序方法,稱為穩插入排序 較好。（9） 對于n個記錄的集合進行歸并排序，所需要的平均時間為：（10） 對于n個記錄的集合進行歸并排序，所需要的附加空間是（11） 若原始數據接近無序，則選用快速排序最好。（12）在排序前，關鍵字值相等的不同記錄，排序后相對位置保持 定排序方法。（13）在插入排序和選擇排序中，若初始數據基本正序，則選用（14）當增量為1時，該趟希爾排序與直接插入排序基

4、本一致。（15）第一趟排序后，序列中鍵值最大的記錄交換到最后的排序算法是冒泡排序。（16）依次將每個記錄插入到一個有序的子文件中的排序方法稱為直接插入排序。（17）在插入排序、選擇排序和歸并排序中，排序是不穩定的為：選擇排序。（18）在對一組記錄（54, 38, 96, 23, 15, 72, 60, 45, 83）進行直接插入排序時，當把第 7個記錄60插入到有序表時，為尋找插入位置需比較3 次。(19)兩個序列分別為：L1=25 , 57, 48, 37, 92, 86, 12, 33L2=25 , 37, 33, 12, 48, 57, 86, 92。用冒泡排序法對L1和L2進行排序，交

5、換次數較少的是序列：L2 。(20)對一組記錄(54, 35, 96, 21, 12, 72, 60, 44, 80)進行 直接選擇排序 時，第四次選擇和 交換后，未排序記錄是54 , 72, 60, 96, 80 。三.選擇題(1)排序是根據(A )的大小重新安排各元素的順序。A .關鍵字 B .數組 C .元素件 D .結點(2)評價排序算法好壞的標準主要是( D )。A.執行時間B.輔助空間C.算法本身的復雜度D.執行時間和所需的輔助空間(3)直接插入排序的方法是( B )的排序方法。A .不穩定 B .穩定 C .外部 D .選擇(4)直接插入排序的方法要求被排序的數據( B )存儲。

6、A .必須鏈表B .必須順序 C.順序或鏈表D .可以任意(5)排序方法中，從無序序列中選擇關鍵字最小的記錄，將其與無序區(初始為空)的第一個記錄交換的排序方法，稱為 (D )。A .希爾排序B .歸并排序 C.插入排序D.選擇排序(6)每次把待排序方的區間劃分為左、右兩個區間，其中左區間中元素的值不大于基準元素的值，右區間中元素的值不小于基準元素的值，此種排序方法叫做( C )。A.冒泡排序B .堆排序 C.快速排序D.歸并排序(7)快速排序在(C )情況下最易發揮其長處。A.待排序的數據中含有多個相同的關鍵字B.待排序的數據已基本有序C.待排序的數據完全無序D .待排序的數據中最大值與最小

7、值相差懸殊(8)下述幾種排序方法中，要求內存量最大的是：( D )。A .插入排序B .選擇排序 C.快速排序D.歸并排序(9)直接插入排序的方法是從第( B )個元素開始，插入到前邊適當位置的排序方法。A . 1B. 2 C. 3 D. n(10)堆的形狀是一棵(C )。A.二叉排序樹B .滿二叉樹 C .完全二叉樹D .平衡二叉樹(11)內排序是指在排序的整個過程中，全部數據都在計算機的( A )中完成的排序。A .內存 B .外存 C .內存和外存D .寄存器(12)快速排序的方法是( A )的排序方法。A .不穩定 B .穩定 C .外部 D .選擇(13)下列排序方法中，關鍵字比較次

8、數與記錄的初始排列次序無關的是(A )。A .選擇排序B .希爾排序 C.插入排序D .冒泡排序(14)下述幾種排序方法中，平均時間復雜度最小的是(A .希爾排序B.插入排序C .冒泡排序 D .選擇排序(15)對有n個記錄的表作快速排序，在最壞情況下，算法的時間復雜度是( BA. O(n) B . O(n2)C . O(nlog 2n) D . O(n3)(16)冒泡排序的方法對 n個數據進行排序，第一趟排序共需要比較( C )次。(17)對n個不同的排序碼進行冒泡(遞增)排序，在下列(A.從小到大排列好的 B.從大到小排列好的 C.元素無序)情況比較的次數最多。D .元素基本有序(18)用

9、直接插入排序法對下面的四個序列進行由小到大的排序，元素比較次數最少的是 (B )。A , 94, 32, 40, 90, 80, 46, 21, 69 B . 21, 32, 46, 40, 80, 69, 90, 94C . 32, 40, 21, 46, 69, 94, 90, 80 D , 90, 69, 80, 46, 21, 32, 94, 40(19) 一組記錄的排序碼為(25, 48, 16, 35, 79, 82, 23, 40),其中含有4個長度為2的有序表, 按歸并排序的方法對該序列進行一趟歸并后的結果為：( A )。A , 16 25 35 48 23 40 79 82

10、36 72BC . 16 25 48 35 79 82 23 36 40 72D16 25 35 48 79 82 23 36 40 7216 25 35 48 79 23 36 40 72 82(20) 一個數據序列的關鍵字為：(46,79, 56,38,40,84),采用快速排序，并以第一個數為基準得到第一次劃分的結果為：( C )A.( 38, 40, 46,56,79,84)B.( 40,38, 46,79,56,84)C .( 40, 38, 46,56,79,84)D.( 40,38, 46,79,56,84)四.排序過程分析1 .已知數據序列18, 17, 序的結果。解:18 1

11、7 60 40 07 32 73 65第一趟結束時結果：17第二趟結束時結果：17第三趟結束時結果：17第四趟結束時結果：07第五趟結束時結果：07第六趟結束時結果：07第七趟結束時結果：0718 60 40 07 32 73 6518 60 40 07 32 73 6518 40 60 07 32 73 651718406032 73651718324060 73651718324060 73651718324060 657360, 40, 07, 32, 73, 65,寫出采用直接插入算法排序時，每一趟排2 .已知數據序列17 , 18, 60, 40, 7, 32, 73, 65, 85

12、請寫出采用冒泡排序法對該序列作升序排序時每一趟的結果。解：17 18 60 40 7 32 73 65 85第一趟排序結果：17 18 40 7 32 60 65 73 85匚第二趟排序結果：17 18 7 32 40 60 65 73口第三趟排序結果：17 71832406065口第四趟排序結果：7 1718324060第五趟排序結果：7 17183240口第五趟排序過程中已無記錄交換，排序結束。3 .已知數據序列10, 18, 4, 3, 6, 12, 9, 15, 8,寫出希爾排序每一趟（設d=4、2、1）排序的結果。解：4 3 6 12 9 15 8I I I、d=46 124 3 8

13、 18 9 15 1010 186 12 8 15 9 18 10d=24 3d=13 4 6 8 9 10 12 15 184 .已知數據序列12, 02, 16, 30, 28, 10, 17, 20, 06, 18,寫出希爾排序每一趟排序的結果。（設 d=5、2、1）解： 12 02 16 30 28 10 17 20 06 18d=510 02 16 06 18 12 17 20 30 28d=21III12 02 16 06 17 12 18 20 30 28d=102 06 10 12 16 17 18 20 28 305 .已知數據序列10, 18, 4, 3, 6, 12, 9

14、, 15,寫出二路歸并排序的每一趟排序結果。10 18 4 3 6 12 9 1510 18 3 4 6 12 9 15第一趟排序結果3 4 10 18 6 9 12 15第二趟排序結果3 4 6 9 10 12 15 18第三趟排序結果6.解已知數據序列10, 1, 15,18, 7, 15,試畫出采用快速排序法，第一趟排序的結果。交換7 1 10 18 15 1510 1 15 J8 7 15lowI high第一趟排序結果:low high7 .已知數據序列10, 1, 15, 18, 7, 15,試寫出采用快速排序法，第一趟排序的結果。 解：7 1 10 18 15 158 .已知序列 50, 8, 51, 6, 90, 17, 89, 27, 65, 46,請給出采用堆排序法對該序列作降序排 列時的每一趟的結果。采用堆排序法排序的各趟結果如圖所示，排序結果為9