(C) 84，79，56，46，40，38 (D)A,B,C都不对 21. 下面四个序列中， 是一个堆。

(A)16，72，31，23，94，53 (B)94，53，31，72，16，23 (C) 16，53，23，94，31，72 (D) 16，31，23，94，53，72

22. 一组记录的关键码为(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

23. 用某种排序方法对线性表(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)快速排序

24. 对序列（15，9，7，8，20，-1，4）进行排序，进行一趟后数据的排列变为（4，9，-1，8，20，7，15）则采用的是 排序。

(A) 选择 (B) 快速 (C) 希尔 (D) 起泡

25. 对（05，46，13，55，94，17，42）进行基数排序，一趟排序的结果是 。

(A)（05，46，13，55，94，17，42） (B)（05，13，17，42，46，55，94） (C)（42，13，94，05，55，46，17） (D)（05，13，46，55，17，42，94） 二、填空题

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

2、按照排序过程涉及的存储设备的不同，排序可分为________排序和________排序。 3、按排序过程中依据的不同原则对内部排序方法进行分类，主要有：________、________、________、________等四类。

4、简单选择排序算法在最好情况下和最坏情况下的时间复杂度分别为_________和

- 41 -

_________。

5、高度为h的堆中，最多有_______ 个元素，最少有_______个元素。

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

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

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

10、在对一组记录(54，38，96，23，15，72，60，45，83)进行直接插入排序时，当把第7个记录60插入到有序表时，为寻找插入位置需比较________次。

11、利用快速排序方法对记录（50，40，95，20，15，70，60，45，80）进行快速排序，其需递归调用的次数为________，其中第二次递归调用是对________组记录进行快速排序。 12、在堆排序，快速排序和归并排序中，若只从存储空间考虑，则首先选取________方法，其次选取________方法；若只从排序结果的稳定性考虑，则应选取________方法；若只 从平均情况下排序最快考虑，则应选取________方法；若只从最坏情况下排序最快并且要节省内存考虑，则应选取________方法。

13、对于关键字序列（12，13，11，18，60，15，7，20，25，100），用筛选法建堆，必须从键值为 的关键字开始

三、判断题

1、 直接选择排序在最好情况下的时间复杂度是O(n）。

2、 在初始数据表已经有序时，快速排序算法的时间复杂度为O（nlogn）。 3、 在用堆排序算法排序时，如果要进行增序，则需要采用“大顶堆”。 4、 在待排数据基本有序的情况下，快速排序的效果最好。 5、 两分法插入排序所需比较次数与待排序记录的初始状态相关。 6、 希尔排序的最后一趟与直接插入排序过程相同。 7、 在任何情况下，归并排序都比简单排序速度快。 8、 堆是满二叉树。

9、堆肯定是一棵平衡二叉树。

- 42 -

10、内排序要求数据一定要以顺序方式存储。

11、快速排序和归并排序在最坏情况下的比较次数都是O（nlogn）。 12、用希尔排序法时，若关键字的初始排序杂乱无序，则排序效率就低。 13、基数分类只适用于以数字为关键字的情况，不适用以字符串为关键字的情况。 14、若中序遍历平衡的二叉排序树，可得到排好序的关键字序列。

15、在执行某个排序算法过程中，出现了排序码朝着最终排序序列位置相反方向移动，则该算法是不稳定的。

四、解答题

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

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

（1）（100,90,80,60,85,75,20,25,10,70,65,50）； （2）（100,70,50,20,90,75,60,25,10,85,65,80）。

3．对于下列一组关键字(12，2，16，30，8，28，4，10，20，6，18），试写出用下列算法从小到大排序时第一趟结束时的序列。 （1)希尔排序（第一趟排序的增量为5） （2）快速排序（选第一个记录为枢纽） （3)基数排序。

4.有n个不同的英文单词，它们的长度相等，均为m，若n＞＞50,m＜5，试问采用什么排序方法时间复杂性最佳?为什么?

5. 已知序列（54，21，52，14，98，47，41，75，5，62），请给出采用堆排序法对该序列作升序排序时的每一趟结果。

6.已知序列（53，82，62，71，93，70，34，25，47，29），请给出采用二路归并排序法对该序列作升序排序时的每一趟结果。

五、算法设计题

1．以下是直接选择排序的算法，请补充完整。

- 43 -

void selectSort(list r,int n)

{//对于包含n个元素的待排序列r进行直接选择排序

for(i=1;i<=________;i++) {k=i;

for(j=i+1;j<=n;j++)if(r[j].key

2．以下对进行一趟快速排序，请补充完整。 int quickpass(list r,int h,int p)

{//对子序列r[h],r[h+1],……r[p]进行一趟快速排序，以第一个记录的键值为枢纽

i=h;j=p;x=r[i];

while(i

{while((r[j].key>=x.key)&&(i

{________;i++;

while((r[i].key<=x.key)&&(i

r[i]=________;return(i); }

3．设带头结点的单链表L，结点数据值为整型。试写出对链表L按“插入方法”排序的算法：LINSORT(L).

4．冒泡排序算法是把大的元素向上移（起泡的上浮），也可把小的元素向下移（起泡的下沉），请给出上浮和下沉过程交替的起泡排序算法。

5.一个线性表中的元素为正整数或负整数。设计一个算法，将正整数和负整数分开，使线性表前一半为负整数，后一半为正整数。不要求对这些元素排序，但要求尽量减少交换次数。 6.已知排序码序列{k1,k2,...,kn}是小顶堆，试写一算法，增加排序码x到堆中{k1,k2,...,kn，x}后，将其调整为小顶堆的算法。（排序码值为ki的记录存于r[i-1]中）

7．请用快速排序思想，设计递归算法实现求n(n>1)个不同元素集合中的第i（0

- 44 -

8、有一种简单的排序算法，叫做计数排序。这种排序算法对一个待排序的表（用数组表示）进行排序，并将排序结果存放到另一个新的表中。必须注意的是，表中所有待排序的关键字互不相同，计数排序算法针对表中的每个记录，扫描待排序的表一趟，统计表中有多少个记录的关键字比该记录的关键字小。假设对某一个记录，统计出数值为c，那么这个记录在新的有序表中的合适的存放位置即为c。 （1）给出适用于计数排序的数据表定义。 （2）编写实现计数排序的算法。

（3）对于有n个记录的表，比较次数是多少？

（4）与简单选择排序相比，这种方法是否更好？为什么？

- 45 -