数据结构第七章复习题.pdfVIP

数据结构第七章复习题

第7章排序

一、选择题

1．某内排序方法的稳定性是指(D)。

A．该排序算法不允许有相同的关键字记录B．该排序算法允许有

相同的关键字记录

C．平均时间为0（nlogn）的排序方法D．以上都不对

2．下面给出的四种排序法中(D)排序法是不稳定性排序法。

A.插入

B.冒泡

C.二路归并

D.堆

3．下列排序算法中，其中（D）是稳定的。

A.堆排序，冒泡排序

B.快速排序，堆排序

C.直接选择排序，归并排序

D.归并排序，冒泡排序

6．若要求尽可能快地对序列进行稳定的排序，则应选（B）。

A．快速排序B．归并排序C．冒泡排序

13．下面给出的四种排序方法中，排序过程中的比较次数与排序

方法无关的是。(A)A．选择排序法B.插入排序法C.快速排序法D.

堆积排序法15．在下列排序算法中,哪一个算法的时间复杂度与初始排

序无关（D）。

A．直接插入排序B.气泡排序C.快速排序D.直接选择排序

22．下列排序算法中(B)不能保证每趟排序至少能将一个元素放

到其最终的位置上。

A.快速排序

B.shell排序

C.堆排序

D.冒泡排序

23．下列排序算法中(C)排序在一趟结束后不一定能选出一个元

素放在其最终位置上。

A.选择

B.冒泡

C.归并

D.堆

27.在下面的排序方法中，辅助空间为O（n）的是(D)。

A．希尔排序B.堆排序C.选择排序D.归并排序

31.就平均性能而言，目前最好的内排序方法是(D)排序法。

A.冒泡

B.希尔插入

C.交换

D.快速

35.下列排序算法中，占用辅助空间最多的是：(A)

A.归并排序

B.快速排序

C.希尔排序

D.堆排序

36．从未排序序列中依次取出一个元素与已排序序列中的元素依

次进行比较，然后将其放在已排序序列的合适位置，该排序方法称为

(A)排序法。

A.插入

B.选择

C.希尔

D.二路归并

37.在排序算法中，每次从未排序的记录中挑出最小（或最大）关

键码字的记录，加入到已排序记录的末尾，该排序方法是（A）。

A.选择

B.冒泡

C.插入

D.堆

38．用直接插入排序方法对下面四个序列进行排序（由小到大），

元素比较次数最少的是（C）。

A．94,32,40,90,80,46,21,69B．32,40,21,46,69,94,90,80

C．21,32,46,40,80,69,90,94D．90,69,80,46,21,32,94,40

39．直接插入排序在最好情况下的时间复杂度为（B）

A．O(logn)B．O(n)C．O(n*logn)D．O(n2)

42.对序列{15，9，7，8，20，-1，4，}用希尔排序方法排序，

经一趟后序列变为{15，-l，4，8，20，9，7}则该次采用的增量是(B)

A.l

B.4

C.3

D.2

56.归并排序中，归并的趟数是(B)。

A．O（n）B．O(logn)C．O(nlogn)D．O(n*n)58．就排序算

法所用的辅助空间而言，堆排序，快速排序，归并排序的关系是（A