2. 在利用快速排序方法对一组记录（54，38，96，23，15，72，60，45，83） 进行快速排序时，递归调用而使用的栈所能达到的最大深度为____，共需递归调用 的次数为____，其中第二次递归调用是对____一组记录进行快速排序。
3. 在堆排序，快速排序和归并排序中，若只从存储空间考虑，则应首先选取____ 方法，其次选取____方法，最后选取____方法；若只从排序结果的稳定性考虑，则 应选取____方法；若只从平均情况下排序最快考虑，则应选取____方法；若只从最 坏情况下排序最快并且要节省内存考虑，则应选取____方法。
4. 在插入排序、希尔排序、选择排序、快速排序、堆排序、归并排序和基数排 序中，排序是不稳定的有____。
5. 在在插入排序、希尔排序、选择排序、快速排序、堆排序、归并排序和基数 排序中，平均比较次数最少的排序是____，需要内存容量最多的是____。 6. 在堆排序和快速排序中，若原始记录接近正序或反序，则选用____，若原始 记录无序，则最好选用____。
7. 在插入和选择排序中，若初始数据基本正序，则选用____；若初始数据基本 反序，则选用____。
8. 对n个元素的序列进行起泡排序时，最少的比较次数是____。 329.3 综合题 综合题综合题
综合题 1. 以关键码序列（503,087,512,061,908,170,897,275,653,426），为例，手工 执行以下排序算法，写出每一趟排序结束时的关键码状态： （1） 直接插入排序；
（2） 希尔排序（增量d[1]=5）； （3） 快速排序； （4） 堆排序； （5） 归并排序； （6） 基数排序。
2. 判别以下序列是否为堆（小顶堆或大顶堆）。如果不是，则把它调整为堆（要 求记录交换次数最少）。 (1）(100,86,48,73,35,39,42,57,66,21); (2)(12,70,33,65,24,56,48,92,86,33)
(3)(103,97,56,38,66,23,42,12,30,52,06,20)
(4)(05,56,20,23,40,38,29,61,35,76,28,100). 习题答案 习题答案习题答案
习题答案 9.1 1. D 2. C 3. A 4. B 5. C 6. A 7. C 8. D 9.D
10. C 11. D 12. C 9.2 1. 5
2. 2; 4; （23，38，15）
3. 堆排序、快速排序、归并排序、归并排序、快速排序、堆排序 4. 希尔排序、选择排序、快速排序和堆排序 5. 快速排序、基数排序 6. 堆排序、快速排序 7. 插入排序、选择排序 8. n-1