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

第10章 排序

一、填空题

1. 大多数排序算法都有两个基本的操作： 和 。

2. 在对一组记录（54，38，96，23，15，72，60，45，83）进行直接插入排序时，当把第7

个记录60插入到有序表时，为寻找插入位置至少需比较 次。

3. 在插入和选择排序中，若初始数据基本正序，则应选用 排序算法；若初始数据基本反

序，则应选用 排序算法。

4. 在堆排序和快速排序中，若初始记录接近正序或反序，则选用 ；若初始记录基本无序，

则最好选用 。

5. 对于n个记录的集合进行冒泡排序，在最坏的情况下所需要的时间是 。若对其进行快

速排序，在最坏的情况下所需要的时间是 。

6. 对于n个记录的集合进行归并排序，所需要的平均时间是

，所需要的附加空间

是 。

7． 对于n个记录的表进行2路归并排序，整个归并排序需进行 趟（遍）。

8. 设要将序列（Q, H, C, Y, P, A, M, S, R, D, F, X）中的关键码按字母序的升序重新排列，则：冒

泡排序一趟扫描的结果是 ；初始步长为4的希尔（shell）排序一趟的结果

是 ；归并排序一趟扫描的结果是 ；快速排序一趟扫描的结果

是 ；堆排序初始建堆的结果是 。

9. 分别采用堆排序，快速排序，冒泡排序和归并排序，对初态为有序的表进行排序，则最省时间

的是 算法，最费时间的是 算法。

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

二、单项选择题

1、下列四个序列中，（ ）是堆。

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

2． 排序方法中，从未排序序列中依次取出元素与已排序序列（初始时为空）中的元素进行比较，

将其放入已排序序列的正确位置上的方法，称为（ ）

Ａ. 希尔排序 Ｂ. 冒泡排序 Ｃ. 插入排序 Ｄ. 选择排序

3．从未排序序列中挑选元素，并将其依次插入已排序序列（初始时为空）的一端的方法，称为（ ）

Ａ. 希尔排序 Ｂ. 归并排序 Ｃ. 插入排序 Ｄ. 选择排序