數(shù)據(jù)結(jié)構(gòu)：排序單元測驗(yàn)與答案

一、單選題

1、在下面的排序方法中，輔助空間為0(n)的是_____o

A.直接插入排序

B.合并排序

C.快速排序

D.選擇排序

正確答案：B

2、對初始狀態(tài)為遞增序列的表按遞增順序排序，最省時間的是

算法，最費(fèi)時間的是_算法。

A.快速排序、合并排序

B.直接插入排序、快速排序

C.冒泡排序、堆排序

D.堆排序、簡單選擇排序

正確答案：B

3、就平均性能而言，目前最好的內(nèi)排序方法是____排序法。

A眉泡

B.希爾

C.快速

D.交換

正確答案：C

4、如果只想得到1000個元素組成的序列中第5個最小元素之前的

部分排序的序列，用排序最丸

A.希爾

B.快速

C.基數(shù)

D眉泡

正確答案：D

5、需要對5個不同的數(shù)據(jù)進(jìn)行排序，則至少需要比較次;對5

個數(shù)據(jù)進(jìn)行排序，如果5個數(shù)據(jù)已經(jīng)有序，但我們并不知道，最少

比較次可結(jié)束排序；

A.7,7

B.4,4

C.7,4

D.6,7

正確答案：C

6、若要對1000個元素進(jìn)行排序，要求又快又穩(wěn)定，則最好采用

_____方法。

A.合用非序

B.快速排序

C.堆排序

D4擊入排序

正確答案：A

7、對n個數(shù)據(jù)進(jìn)行堆排序的空間復(fù)雜度為o

A.O(nlogn)

B.O(l)

C.0(n)

D.O(nA2)

正確答案：B

8、對記錄的關(guān)鍵碼{50,26,38,80,70,90,8,30,40,20}

進(jìn)行排序，各趟排序結(jié)束時的結(jié)果為：

50,26,38,80,70,90,8,30,40,20

50,8,30,40,20,90,26,38,80,70

26,8,30,40,20,80,50,38,90,70

8,20,26,30,38,40,50,70,80,90

其使用的排序方法是_____O

A.堆排序

B.希爾排序

C.基黜脖

D.快速排序

正確答案：B

9、下面各種排序方法中，最好情況下時間復(fù)雜度為O(n)的是—

A.直接插入排序

B.合并排序

C.堆排序

D.快速排序

正確答案：A

10、在所有排序方法中_________排序方法使數(shù)據(jù)的組織采用的是

完全二叉樹的結(jié)構(gòu)。

A,快速排序

B.合用非序

C.堆排序

D.二分插入排序

正確答案：C

11、如果排序過程中，序列的變化情況依次是：

(1)25,84,21,47,15,27,68,35,20(原始排列)

(2)20,15,21,25,47,27,68,35,84

(3)15,20,21,25,35,27,47,68,84

(4)15,20,21,25,27,35,47,68,84

那么，所用的排序方法是____排序。

A.選擇

B眉泡

C插入

D,快速

正確答案：D

12、在對n個元素進(jìn)行快速排序的過程中，若每次劃分得到的兩個

數(shù)據(jù)段的長度相等或只差一個元素，則排序的時間復(fù)雜度為。

A.0(1)

B.O(nlogn)

C.0(nA2)

D.O(n)

正確答案：B

13、_____可以滿足穩(wěn)定性要求。

A直接插入排序和冒泡排序

B.直接插入排序和快速排序

C.冒泡排序和堆排序

D.快速排序和簡單選擇排序

正確答案：A

14、在對n個元素進(jìn)行改進(jìn)的冒泡排序的過程中，最好情況下的時

間復(fù)雜度為—O

A.0(l)

B.O(logn)

C.0(nA2)

D.O(n)

正確答案：D

15、一組記錄的排序碼為｛79,46,84,38,40,56),則利用堆排

序(建立小根堆)的方法建立的初始堆為—0

A.38,79,56,46,40,84

B.38,46,40,56,79,84

C.38,40,56,46,79,84

D.84,56,79,40,46,38

正確答案：C

16、下列排序算法中，在每一趟都能選出一個元素放到其最終位置

上，并且其時間性能受數(shù)據(jù)初始特性影響的是。

A.直接插入排序

B.快速排序

C.簡單選擇排序

D.堆排序

正確答案：B

17、對n個元素進(jìn)行快速排序，第一次劃分最多需要移動次元素,