16
第十章 习题 一、 单选或填空题
1. 数组中原有数据如下：15，13，20，18，12，60。下面是一组用不同排序方法进行一趟排序后的结果。则ABCD四个选项中，说法正确的是 I． 12，13，15，18，20，60 II． 13，15，18，12，20，60
III． 13，15，20，18，12，60 IV． 12，13，20，18，15，60
V． 13，15，18，20，12，60
A) I快速排序；II简单选择排序；III直接插入排序；IV冒泡排序；V归并排序
B) I冒泡排序；II快速排序；III归并排序；IV简单选择排序；V直接插入排序
C) I快速排序；II冒泡排序；III直接插入排序；IV简单选择排序；V归并排序
D) I直接插入排序；II归并排序；III快速排序；IV简单选择排
序；V冒泡排序 2. 对一组数据(2，12，16，88，5，10)进行排序，若前三趟排序结果如下：
第一趟：2，12，16，5，10，88 第二趟：2，12，5，10，16，88 第三趟：2，5，10，12，16，88 则采用的排序方法可能是( )
A.冒泡排序法 B.希尔排序法 C.归并排序法 D.基数排序法
3. 若一组记录的排序码为(45，78，56，36，40，87)，则初始小根堆的结果为
A．36，45，56，78，40，87 B．87，78，56，36，40，45 C．40，36，45，56，78，87 D．36，40，56，78，45，87 4．下列排序算法中属于不稳定的排序方法是
A)直接插入排序 B)冒泡排序 C)简单选择排序 D)归并排序
5．下列排序方法的时间复杂度不为线性对数阶的是 。 A）快速排序 B）2-路归并排序 C）希尔排序 D） 堆排序
6．最好和最坏时间复杂度均为O(nlogn)且稳定的排序方法是 。
A）快速排序 B）2-路归并排序 C）冒泡排序 D） 堆排序 7. 对于快速排序，若初始关键字有序排列，则时间复杂度
17
为 。
8．分别采用堆排、快序速排序、直接插入排序和归并排序算法对初始状态为递增序列的表按递增顺序排序，最省时间的是 算法。
二、 解答题
1. 已知待排序的序列为{37，65，56，8，76，3，89，34，21，46}，试完成下列各题（本题排序均指非递减有序排列）：
(1) 写出希尔排序每一趟排序的结果；（d1=5,d2 = 3,d3 = 1） (2) 写出第一趟快速排序过程及结果。
（3）画出初始堆，以及第一次交换后，经过堆调整重新形成的堆。
2. 已知待排序的序列为 ( 503，087，512，061，908，170，897，275，653，426}，试完成下列各题（本题排序均指非递减有序排列）：
(1) 写出直接插入排序每一趟排序的结果； (2) 写出希尔排序每一趟排序的结果；（d1=5,d2 = 3,d3 = 1） (3) 写出2路归并排序每一趟排序的结果。 三、算法题
1. 编程实现直接插入排序算法； 2. 编程实现一趟快速排序算法； 3. 编程实现简单选择排序算法。
18
19