2024年4月30日发(作者：)

习题16（排序）

一、选择题

1、 对n个不同的关键字由小到大进行冒泡排序，在下列（ ）情况下比较的次数最多。

A）从小到大排列好的 B）从大到小排列好的 C）元素无序 D）元素基本有序

2、 堆是一种（ ）排序。

A）插入 B）选择 C）交换 D）归并

3、 堆的形状是一棵（ ）。

A）二叉排序树 B）满二叉树 C）完全二叉树 D）平衡二叉树

4、 在含有n个关键字的小根堆（堆顶元素最小）中，关键字最大的记录有可能存储在（ ）位

置上。

A）n/2 B）n/2 -1 C）1 D）n/2 +2

5、 以下序列不是堆的是( )。

A）(100,85,98,77,80,60,82,40,20,10,66) B）(100,98,85,82,80,77,66,60,40,20,10)

C）(10,20,40,60,66,77,80,82,85,98,100) D）(100,85,40,77,80,60,66,98,82,10,20)

6、 下列四个序列中，哪一个是堆（ ）。

A）75,65,30,15,25,45,20,10 B）75,65,45,10,30,25,20,15

C）75,45,65,30,15,25,20,10 D）75,45,65,10,25,30,20,15

7、 在对n个元素的序列进行排序时，堆排序所需要的附加存储空间是（ ）。

A）O(log2n) B）O(1) C）O(n) D）O(nlog2n)

8、 有一组数据（15，9，7，8，20，-1，7，4），用堆排序的筛选方法建立的初始堆为 （ ）

A）-1，4，8，9，20，7，15，7 B）-1，7，15，7，4，8，20，9

C）-1，4，7，8，20，15，7，9 D）A，B，C均不对

9、 对一组记录的关键码｛46,79,56,38,40,84｝采用堆排序，则初始化堆后最后一个元素是

（ ）。

A）84 B）46 C）56 D）38

10、用二分法插入排序方法进行排序，被排序的表（或序列）应采用的数据结构是（ ）。

A）单链表 B）数组 C）双向链表 D）散列表

11、在所有排序方法中，关键码比较的次数与记录的初始排序次序无关的是( )

A）希尔排序 B）冒泡排序 C）直接插入排序 D）直接选择排序

12、用归并排序方法,最坏情况下，所需时间为( )

A）O(n) B）O(n2) C）O(nlog2n) D）O(nlog2n)

13、具有12个记录的序列，采用冒泡排序最少的比较次数是( )

A）1 B）144 C）11 D）66

14、用冒泡排序对序列18,14,6,27,8,12,16,52,10,26,47,29,41,24进行排序,共进行(

较。

A）33 B）45 C）70 D）91

15、当初始序列已经按键值有序时，用直接插入算法进行排序，需要比较的次数为(

A）n2 B）n logan C） log2n D）n-1

16、下面四种内排序方法中，要求内存容量最大的是( )

A）插入排序 B）选择排序 C）快速排序 D）归并排序

17、在文件局部有序或文件长度较小的情况下，最佳的排序方法是( )

A）直接插入排序 B）冒泡排序 C）简单选择排序 D）都不对

)次比

)

18、若待排序列已基本有序，要使它完全有序，从关键码比较次数和移动次数考虑，应当使用

( )。

A）归并排序 B）直接插入排序 C）直接选择排序 D）快速排序

19、设有1000个无序的元素，希望用最快的速度挑选出其中10个最大的元素，最好的方法是

（ ）。

A）起泡排序 B）快速排序 C）堆排序 D）基数排序

20、在待排序的元素序列基本有序的前提下，效率最高的排序方法是（ ）。

A）插入排序 B）选择排序 C）快速排序 D）归并排序

21、排序方法中，从未排序序列中挑选元素，并将其放入已排序序列（初始为空）的一端的方法，

称为（ ）。

A）希尔排序 B）起泡排序 C）插入排序 D）选择排序

22、对5个不同的数排序至少需要比较（ ）次。

A）4 B）5 C）6 D）7

23、若只想得到序列中第I个元素之前的部分排序，最好采用（ ）排序方法。

A）快速排序 B）堆排序 C）插入排序 D）shell排序

24、如果待排序序列中两个数据元素具有相同的值，在排序前后它们的相互位置发生颠倒，则称

该排序算法是不稳定的。（ ）就是不稳定的排序方法。

A）起泡排序 B）归并排序 C）Shell排序 D）直接插入排序 E）简单选择排序

25、在下列排序算法中,哪一个算法的时间复杂度与初始排序无关（ ）。

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

26、数据序列（8,9,10,4,5,6,20,1,2）只能是下列排序算法中的( )的两趟排序后的结果。

A）选择排序 B）冒泡排序 C）插入排序 D）堆排序

27、数据序列（2，1，4，9，8，10，6，20）只能是下列排序算法中的( )的两趟排序后的结

果。

A）快速排序 B）冒泡排序 C）选择排序 D）插入排序

28、对数据（84，47，25，15，21）排序，数据的排列次序在排序的过程中的变化为（1）84 47

25 15 21 （2）15 47 25 84 21 （3）15 21 25 84 47 （4）15 21 25 47 84 。则采用的是 ( )

排序。

A）选择 B）冒泡 C）快速 D）插入

29、对序列{15,9,7,8,20,-1,4}进行一趟（ ）排序后,数据的排列变为{4,9,-1,8,20,7,15}。

A）选择 B）快速 C）希尔 D）冒泡

30、若用某种排序(分类)方法对线性表(25,84,21,47,15,27,68,35,20)进行排序时，结点序列的变化

情况依次为： (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）快速排序

31、下列排序算法中( )不能保证每趟排序至少能将一个元素放到其最终的位置上。

A）快速排序 B）shell排序 C）堆排序 D）冒泡排序

32、下列排序算法中( )排序在一趟结束后不一定能选出一个元素放在其最终位置上。

A）选择 B） 冒泡 C）归并 D）堆

33、（ ）排序算法，在每趟都能选出一个元素放到最终位置，并且其时间性能受数据初始特性

的影响。

A）直接插入排序 B）快速排序 C）直接选择排序 D）堆排序

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

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

35、下列排序算法中，在待排序数据已有序时，花费时间反而最多的是( )排序。

A）冒泡 B）希尔 C）快速 D）堆

36、下列排序算法中，占用辅助空间最多的是( )

A）归并排序 B）快速排序 C）希尔排序 D）堆排序

37、（ ）排序方法，每次从未排序的记录中挑出最小的记录，加入到已排序记录的末尾。

A）选择 B）冒泡 C）插入 D）堆

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

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

39、用shell对序列{15,9,7,8,20,-1,4}排序，一趟后变为{15,-l,4,8,20,9,7},则采用的增量是(

A）l B）4 C）3 D）2

40、归并排序中，归并的趟数是( )。

A）O（n） B）O(logn) C）O(nlogn) D）O(n*n)

41、将两个各有N个元素的有序表归并成一个有序表,其最少的比较次数是( )

A）N B）2N-1 C）2N D）N-1

42、关键码序列（46,79,56,38,40,84）采用快速排序得到的一次划分结果为（ ）。

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

43、对下列关键字序列用快速排序法进行排序时，速度最快的情形是( )。

A）{21,25,5,17,9,23,30} B）{25,23,30,17,21,5,9}

C）{21,9,17,30,25,23,5} D）{5,9,17,21,23,25,30}

44、快速排序方法在被排序的数据( )情况下最不利于发挥其长处

A）数据量太大 B）含有多个相同值 C）已基本有序 D）数目为奇数

45、以下关键字序列用快排序法进行排序，速度最慢的是( )

A）{23,27,7,19,11,25,32} B）{23,11,19,32,27,35,7}

C）{7,11,19,23,25,27,32} D）{27,25,32,19,23,7,11}

46、在快速排序过程中，每次将表划分成左、右两个子表，考虑这两个子表，下列结论正确的是

（ ）。

A）左、右两个子表都已各自排好序 B）左边子表中的元素都不大于右边子表中的元

素

C）左边子表的长度小于右边子表的长度 D）左、右两个子表中元素的平均值相等

47、设关键码序列（25,18,9,33,67,82,53,95,12,70），要按关键码值递增的顺序排序，采取以第一

个关键码为分界元素的快速排序法，第一趟排序完成后关键码33被放到了第几个位置（ ）。

A）3 B）5 C）7 D）9

48、快速排序在下列（ ）情况下最易发挥其长处。

A）被排序的数据中含有多个相同排序码 B）被排序的数据已基本有序

C）被排序的数据完全无序 D）被排序的数据中的最大值和最小值相差悬殊

49、对n个关键字作快速排序，在最坏情况下，算法的时间复杂度是（ ）。

A）O(n) B）O(n2) C）O(nlog2n) D）O(n3)

二、填空题

1、 对下列两个表：L1=（55,61,68,70,75,65,78,81,93,98,84），L2=

（75,70,65,84,98,78,93,55,61,81,68），使用直接选择排序和直接插入排序两种方法进行排序，（ ）

方法对两个表所花费的时间相同。

2、 若不考虑基数排序，则在排序过程中，主要进行的两种基本操作是关键字的（ ）和记录

的（ ）。

3、 内部排序将待排序的记录存放在（ ）中进行排序，按排序过程中工作量来区分，可分为

（ ）、（ ）和（ ）三类。

4、 对n个元素进行起泡排序时，最少的比较次数是（ ）。

5、 在插入排序和选择排序中，若初始数据基本正序，则选用（ ）。若数据基本反序，则选

用（ ）。

6、 关键码序列（ Q，H，C，Y，Q，A，M，S，R，D，F，X），要按照关键码值递增的次序进

行排序，若采用初始步长为4的Shell排序法，则一趟扫描的结果是（ ）；若采用以第一个元素为

分界元素的快速排序法，则扫描一趟的结果是（ ）。

7、 在插入排序、希尔排序、选择排序、快速排序、堆排序、归并排序和基数排序中，不稳定的

有（ ）。

8、 在堆排序、快速排序和归并排序中，若只从存储空间考虑，则应首先选取（ ）方法，

其次选取（ ）方法，最后选取（ ）方法；若只从排序结果的稳定性考虑，则应选取（ ）

方法；若只从平均情况下排序最快考虑，则应选取（ ）方法；若只从最坏情况下排序最快并且要节

省内存考虑，则应选取（ ）方法。

9、 快速排序、简单选择排序和直接插入排序三种排序方法中，当待排关键字序列基本有序时，

运行效率最高的是（ ），比较次数与待排记录初始状态无关的是（ ）。

10、设有9个元素的关键字序列为｛26，5，71，1，61，11，59，15，48｝，按堆排序思想选

出当前序列的最大值71和61之后，所余7个元素的关键字构成的堆是（ ）。

11、对一组记录（54,38,96,23,15,2,60,45,83）进行直接插入排序，当把第7个记录60插入到有

序表时，为寻找插入位置需比较（ ）次。

12、在利用快速排序方法对一组记录（54,38,96,23,15,2,60,45,83）进行快速排序时，递归调用

而使用的栈所能达到的最大深度为（ ），共需递归调用的次数为（ ），其中第二次递归调用是

对（ ）一组记录进行快速排序。

13、在插入排序、希尔排序、选择排序、快速排序、堆排序、归并排序和基数排序中，平均比较

次数最少的排序是（ ），需要内存容量最多的是（ ）。

14、快速排序的非递归算法实现，除了可以借助于栈结构解决外，（ ）也可以用来解决这个

问题。

15、分别采用堆排序、快速排序、插入排序和归并排序算法对初始状态为递增序列的表按递增顺

序，最省时间的是（ ），最费时间的是（ ）。如果加入冒泡排序方法，结果又如何？（ ）

16、对一个由n个整数组成的序列，借助排序过程找出其中的最大值，希望比较次数和移动次数

最少，对归并排序、直接插入排序和直接选择排序，应选用哪一种方法（ ）。

17、不受待排序初始序列的影响，时间复杂度为O(N2)的排序算法是（ ），在排序算法的最

后一趟开始之前，所有元素都可能不在其最终位置上的排序算法是（ ）。

18、直接插入排序用监视哨的作用是（ ）。

19、对n个记录的表]进行简单选择排序，所需进行的关键字间的比较次数为（ ）。

20、下面的排序算法的思想是：第一趟比较将最小的元素放在r[1]中，最大的元素放在r[n]中，第

二趟比较将次小的放在r[2]中，将次大的放在r[n-1]中，…,依次下去，直到待排序列为递增序。（注：

<-->代表两个变量的数据交换）。

void sort(SqList &r,int n)

{

i=1;

while( （1） )

{ min=max=1;

for (j=i+1; （2） ;++j)

{ if( （3） ) min=j; else if(r[j].key>r[max].key) max=j; }

if( （4） ) r[min]<--->r[j];

if(max!=n-i+1) { if ( （5） ) r[min]<--->r[n-i+1]; else （6） ; }

i++;

}

}//sort

21、设用希尔排序对数组{98，36，-9，0，47，23，1，8，10，7}进行排序，给出的步长（也

称增量序列）依次是4，2，1则排序需（ ）趟，写出第一趟结束后，数组中数据的排列次序（ ）。

22、从平均时间性能而言，（ ）排序最佳。

23、对于7个元素{1,2,3,4,5,6,7}进行快速排序，具有最小比较和交换次数的初始排列次序为

（ ）。

24、快速排序法在（ ）情况下最不利于发挥其长处，在（ ）情况下最易发挥其长处。

25、堆排序是一种（ ）类型的排序，它的一个基本问题是如何建堆，常用的建堆算法是1964

年Floyd提出的（ ），对含有n个元素的序列进行排序时,堆排序的时间复杂度是（ ），所需

要的附加结点是（ ）。关键码序列05，23，16，68，94，72，71，73是否满足堆的性质（ ）。

三、应用题

1、设待排序的关键字序列为{12，2，16，30，28，10，16*，20，6，18}，试分别写出使用以

下排序方法，每趟排序结束后关键字序列的状态。

（1）直接插入排序 （2）二路归并排序 （3）希尔排序（增量选取5，3，1）

（4）冒泡排序 （5）快速排序 （6）简单选择排序

2、给出如下关键字序列｛321，156，57，46，28，7，331，33，34，63｝，试按链式基数排序

方法，列出每一趟分配和收集的过程。

5、给定如下关键字序列：49，38，65，97，76，13，27，49，分别写出采用冒泡排序，简单选

择排序，快速排序，希尔排序（增量为3）以及2路归并排序的第一趟排序结果。

6、全国有10000人参加物理竞赛，只录取成绩优异的前10名，并将他们从高分到低分输出。而

对落选的其他考生，不需排出名次，问此种情况下，用何种排序方法速度最快？为什么？

7、我们知道，对n个元素进行快速排序时，所需进行的比较次数与这n个元素的初始排序有关。

问：

（1） 当n=7时，在最好情况下需进行多少次比较？请说明理由。

（2） 当n=7时，给出一个最好情况的初始排序的实例。

（3） 当n=7时，在最坏情况下需进行多少次比较？请说明理由。

（4） 当n=7时，给出一个最坏情况的初始排序的实例。

8、设有5个互不相同的元素a、b、c、d、e，能否通过7次比较就将其排好序？如果能，请列出

其比较过程；如果不能，则说明原因。

四、算法设计题

1、试以单链表为存储结构，实现简单选择排序算法。

2、有n个记录存储在带头结点的双向链表中，现用双向冒泡排序法对其按上升序进行排序，请写

出这种排序的算法。（注：双向冒泡排序即相邻两趟排序向相反方向冒泡）。