练习题

一、填空题

1.若待排序的序列中存在多个记录具有相同的键值，经过排序，这些记录的相对次序仍然保持不变，则称这种排序方法是____________的，否则称为____________的。

2.按照排序过程涉及的存储设备的不同，排序可分为__________排序和__________排序。

3.按排序过程中依据的不同原则对内部排序方法进行分类，主要有________、________、_______________、四类。

4.在排序算法中，分析算法的时间复杂性时，通常以________和________为标准操作。评价排序的另一个主要标准是执行算法所需要的_________________。

5.常用的插入排序方法有________插入排序、_______插入排序、________插入排序和________插入排序。

6.直接插入排序是稳定的，它的时间复杂度为________，空间复杂度为________。

7.对于n个记录的集合进行冒泡排序，其最坏情况下所需的时间复杂度是________。

8.归并排序要求待排序列由若干个________的子序列组成。

9.设表中元素的初始状态是按键值递增的，分别用堆排序、快速排序、冒泡排序和归并排序方法对其仍按递增顺序进行排序，则_____________最省时间，___________最费时间。

10.分别采用堆排序、快速排序、插入排序和归并排序算法对初始状态为递增序列的表按递增顺序进行排序，最省时间的是____________算法，最费时间的是____________算法。

二、单项选择

1.以下说法错误的是（ ）。

A.直接插入排序的空间复杂度为O（1）

B.快速排序附加存储开销为O（log2n）

C.堆排序的空间复杂度为O（n）

D.2－路归并排序的空间复杂度为O（n），需要附加两倍的存储开销

2.以下不稳定的排序方法是（ ）。

A.直接插入排序　B.冒泡排序　C.直接选择排序　D.2－路归并排序

3.在文件局部有序或文件长度较小的情况下，最佳的排序方法是（ ）。

A.直接插入排序　B.冒泡排序　C.直接选择排序　D.归并排序

4.对于大文件的排序要研究在外设上的排序技术，即（ ）。

A.快速排序法　B.内排序法　C.外排序法　D.交叉排序法

5.排序的目的是为了以后对已排序的数据元素进行（ ）操作。

A.打印输出　B.分类　C.合并　D.查找

6.当初始序列已按键值有序时，用直接插入算法进行排序，需要比较的次数为（ ）。

A.n－1　B.log2n　C.2log2n　D.n2

7.具有24个记录的序列，采用冒泡排序至少的比较次数是（ ）。

A.1　B.23　C.24　D.529

8.在排序过程中，键值比较的次数与初始序列的排列顺序无关的是（ ）。

A.直接插入排序和快速排序　B.直接插入排序和归并排序

C.直接选择排序和归并排序　D.快速排序和归并排序

9.（ ）方法是对序列中的元素通过适当的位置交换将有关元素一次性地放置在其最终位置上。

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

10.将上万个一组无序并且互不相等的正整数序列，存放于顺序存储结构中，采用（ ）方法能够最快地找出其中最大的正整数。

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

11.一般情况下，以下四种排序方法中，平均查找长度最小的是（ ）。

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

12.以下四种排序方法中，要求附加的内存容量最大的是（ ）。

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

13.已知一个链表中有3 000个结点，每个结点存放一个整数，（ ）可用于解决这3 000个整数的排序问题且不需要对算法进行大的变动。

A.直接插入排序法　B.简单选择排序方法

C.快速排序方法　D.堆排序方法

14.若用冒泡排序法对序列（18，14，6，27，8，12，16，52，10，26，47，29，41，24）从小到大进行排序，共要进行（ ）次比较。

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

15.对一个由n个整数组成的序列，借助排序过程找出其中的最大值，希望比较次数和移动次数最少，应选用（ ）方法。

A.归并排序　B.直接插入排序

C.直接选择排序　D.快速排序

三、简答与应用

1.对于给定的一组键值：83，40，63，13，84，35，96，57，39，79，61，15，分别画出应用直接插入排序、直接选择排序、快速排序、堆排序、归并排序对上述序列进行排序中各趟的结果。

2.举例说明本章介绍的各排序方法中哪些是不稳定的？

3.判断下列两序列是否为堆？如果不是，按照建堆的思想把它调整为堆，并用图表示建堆的过程。

（1）（3，10，12，22，36，18，28，40）；

（2）（5，8，11，15，23，20，32，7）。

4.对于下列一组关键字46，58，15，45，90，18，10，62，试写出快速排序每一趟的排序结果，并标出每一趟中各元素的移动方向。

5.已知数据序列为（12，5，9，20，6，31，24），对该数据序列进行排序，试写出插入排序和冒泡排序每趟的结果。

四、算法设计

1.插入排序中找插入位置的操作可以通过二分法查找的方法来实现。试据此写一个改进后的插入排序方法。

2.一个线性表中的元素为正整数或负整数。设计一个算法，将正整数和负整数分开，使线性表前一半为负整数，后一半为正整数。不要求对这些元素排序，但要求尽量减少交换次数。

3.已知（k1，k2，…，kn）是堆，试写一个算法将（k1，k2，…，kn，kn＋1）调整为堆。按此思想写一个从空堆开始一个一个填入元素的建堆算法（提示：增加一个kn＋1后应从叶子向根的方向调整）。

4.设计一个用链表表示的直接插入排序算法。