算法與數(shù)據(jù)結(jié)構(gòu)第9章排序

第9章排序

一、單選題（共20題，74.1分）

1、將5個(gè)不同的數(shù)據(jù)進(jìn)行排序，至多需要比較（）次。

A、8

B、9

C、10

D、25

正確答案：C

解析：

2、排序方法中，從未排序序列中依次取出元素與已排序序列（初始時(shí)為空）中的元素進(jìn)

行比較，將其放入已排序序列的正確位置上的方法，稱為（）。

A、希爾排序

B、冒泡排序

C、插入排序

D、選擇排序

正確答案：C

3、排序方法中，從未排序序列中挑選元素，并將其依次插入已排序序列（初

始時(shí)為空）的一端的方法，稱為。

A、希爾排序

B、歸并排序

C、插入排序

D、選擇排序

正確答案：D

4、對(duì)有n個(gè)記錄的表作快速排序，在最壞情況下，算法的時(shí)間復(fù)雜度是（）。

A、0（n）

B、0（n2）

C>0（nlog2n）

D、0（n3）

正確答案：B

5、若一組記錄的排序碼為(46,79,56,38,40,84),則利用快速排序的方法，以第

一個(gè)記錄為基準(zhǔn)得到的一次劃分結(jié)果為

()。

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,84,56,79

正確答案：C

6、下列關(guān)鍵字序列中，()是堆。

A、16,72,31,23,94,53

B、94,23,31,72,16,53

C、16,53,23,94,31,72

D、16,23,53,31,94,72

正確答案：D

7、堆是一種()排序。

A、插入

B、選擇

C、交換

D、歸并

正確答案：B

8、堆的形狀是一棵()。

A、二叉排序樹

B、滿二叉樹

C、完全二叉樹

D、平衡二叉樹

正確答案：C

9、若一組記錄的排序碼為(46,79,56,38,40,84),則利用堆排序的方法建立的初

始堆為()。

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

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

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

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

正確答案：B

10、下述幾種排序方法中，平均查找長度（ASL）最小的是（）。

A、插入排序

B、快速排序

C、歸并排序

D、選擇排序

正確答案：C

11、目前以比較為基礎(chǔ)的內(nèi)部排序方法中，其比較次數(shù)與待排序的記錄的初始排列狀態(tài)無

關(guān)的是（）。

A、插入排序

B、二分插入排序

C、快速排序

D、冒泡排序

正確答案：B

12、對(duì)n個(gè)元素進(jìn)行直接插入排序時(shí)間復(fù)雜度為（）。

A、0（1）

B、0（n）

C、0（n2）

D^0（log2n）

正確答案：C

13、在對(duì)n個(gè)元素進(jìn)行冒泡排序的過程中，第一趟排序至多需要進(jìn)行（）對(duì)相鄰元素之

間的交換。

A、n

B、n-1

C、n+1

D、n/2

正確答案：B

14、在對(duì)n個(gè)元素進(jìn)行冒泡排序的過程中，最好情況下的時(shí)間復(fù)雜度

為（）。

A、0(1)

B、O(log2n)

C、0(n2)

D、0(n)

正確答案：D

15、在對(duì)n個(gè)元素進(jìn)行冒泡排序的過程中，至少需要()越完成。

A、1

B、n

C、n-1

D^n/2

正確答案：A

16、在對(duì)n個(gè)元素進(jìn)行快速排序的過程中，平均情況下的時(shí)間復(fù)雜度為()。

A、0(1)

B^O(log2n)

C、O(n2)

D、O(nlog2n)

正確答案：D

17、在對(duì)n個(gè)元素進(jìn)行堆排序的過程中，時(shí)間復(fù)雜度為()。

A、0(1)

B、O(log2n)

C、0(n2)

D、O(nlog2n)

正確答案：D

18、若要對(duì)1000個(gè)元素排序，要求既快又穩(wěn)定，則最好采用()方法。

A、直接插入排序

B、歸并排序

C、堆排序

D、快速排序

正確答案：B

19、若要對(duì)1000個(gè)元素排序，要求既快又節(jié)省存儲(chǔ)空間，則最好采用（）方法。

A、直接插入排序

B、歸并排序

C、堆排序

D、快速排序

正確答案：C

20、在平均情況下速度最快的排序方法為（）。

A、簡單選擇排序

B、歸并排序

C、堆排序

D、快速排序

正確答案：D

二、填空題（共6題，22.2分）

1、在對(duì)一組記錄（54,38,96,23,15,72,60,45,83）進(jìn)行直接插入排

序時(shí)，當(dāng)把第7個(gè)記錄60插入到有序表時(shí)，為尋找插入位置至少需比

較次。（可約定為，從后向前比較）

正確答案：

第1空：

3

2、在插入和選擇排序中，若初始數(shù)據(jù)基本正序，則選用

若初始數(shù)據(jù)基本反序，則選用o

正確答案:

第1空：

插入排序（到尾部）

第2空:

選擇排序

3、對(duì)于n個(gè)記錄的集合進(jìn)行冒泡排序，在最壞的情況下所需要的時(shí)間

是.若對(duì)其進(jìn)行快速排序，在最壞的情況下所需要的時(shí)間

是o

正確答案：

第1空：

0(n2)

第2空：

0(n2)

4、設(shè)要將序列(Q,H,C,Y,P,A,M,S,R,D,F,X)中的關(guān)鍵碼按字母序的升序重

新排列，貝!I：

冒泡排序一趟掃描的結(jié)果

是_____________________________________________________________

________________________________?*

初始步長為4的希爾(shell)排序一趟的結(jié)果

是;

正確答案:

第1空：

H,C,Q,P,A,M,S,R,D,F,X,Y

第2空：

P,A,C,S,Q,D,F,X,R,H,M,Y

5、假定一組記錄為(46,79,56,38,40,84),在冒泡排序的過程中進(jìn)行第一趟排序后的結(jié)果

為.

正確答案：

第1空：

(46,56,38,40,79,84)

6、假定一組記錄為(46,79,56,25,76,38,40,80),對(duì)其進(jìn)行快速排序的第一次劃分后，右區(qū)間

內(nèi)元素的個(gè)數(shù)為。

正確答案：

第1空：

4

三、簡答題(共1題，3.7分)

1、以關(guān)鍵字序列(256,301,751,129,937,863,742,694,076,438)

為例，分別寫出執(zhí)行以下算法的各趟排序結(jié)束時(shí)，關(guān)鍵