C. 84，79，56，46，40，38 D. 84，56，79，40，46，38
12、用某种排序方法对线性表（ 25，84，21，47，15，27，68，35，20）进行排序时，元素序列的变化情况如下：
⑴ 25，84，21，47，15，27，68，35，20 ⑵ 20，15，21，25，47，27，68，35，84 ⑶ 15，20，21，25，35，27，47，68，84 ⑷ 15，20，21，25，27，35，47，68，84 则所采用的排序方法是（ D ）。
A. 选择排序 B. 希尔排序 C. 归并排序 D. 快速排序 13、设有1024个无序的元素，希望用最快的速度挑选出其中前5个最大的元素，最好选用（ D ）。
A. 冒泡排序 B. 选择排序 C. 快速排序 D. 堆排序
14、下列排序方法中，平均时间性能为O(nlogn)且空间性能最好的是（ B ）。
A. 快速排序 B. 堆排序 C. 归并排序 D. 基数排序 15、希尔排序的增量序列必须是（ D ）。
A. 递增的 B. 递减的 C. 随机的 D. 非递减的
二、填空题
1、在插入和选择排序中，若初始数据基本正序，则选用 递减排序 ，若初始数据基本反序，则选用 递减排序 。
2、在插入排序、希尔排序、选择排序、快速排序、堆排序、归并排序和基数排序中，排序是不稳定的有 希尔排序，快速排序，堆排序 。
三、判断题
1、直接选择排序是一种稳定的排序方法。对
2、快速排序在所有排序方法中最快，而且所需附加空间也最少。错 3、直接插入排序是不稳定的排序方法。错 4、选择排序是一种不稳定的排序方法。 对
四、程序分析题
五、综合题
1、写出用直接插入排序将关键字序列{54,23,89,48,64,50,25,90,34}排序过程的每一趟结果。
46
答案：初始： 54，23，89，48，64，50，25，90，34
1：（23，54），89，48，64，50，25，90，34 2：（23，54，89），48，64，50，25，90，34 3：（23，48，54，89），64，50，25，90，34 4：（23，48，54，64，89），50，25，90，34 5：（23，48，50，54，64，89），25，90，34 6：（23，25，48，50，54，64，89），90，34 7：（23，25，48，50，54，64，89，90），34 8：（23，25，48，50，54，64，89，90，34）
2、设待排序序列为{10,18,4,3,6,12,1,9,15,8}请写出希尔排序每一趟的结果。增量序列为5，3，2，1。
答案：初始： 10，18，4，3，6，12，1，9，15，8
d=5： 10，1，4，3，6，12，18，9，15，8 d=3： 3，1，4，8，6，12，10，9，15，18 d=2： 3，1，4，8，6，9，10，12，15，18 d=1： 1，3，4，6，8，9，10，12，15，18
3、已知关键字序列{418，347，289，110，505，333，984，693，177}，按递增排序，求初始堆（画出初始堆的状态）。
答案：418，347，289，110，505，333，984，693，177
418984347289693418110505333984347505333289693177110177
4、有一关键字序列（265，301，751，129，937，863，742，694，076，438），写出希尔排序的每趟排序结果。（取增量为5，3，1） 答案：
初始： 265，301，751，129，937，863，742，694，076，438 d=5： 265，301，694，076，438，863，742，751，129，937 d=3： 076，301，129，265，438，694，742，751，863，937 d=1： 076，129，265，301，438，694，742，751，863，937
5、对于直接插入排序，希尔排序，冒泡排序，快速排序，直接选择排序，堆排序和归并排序等排序方法，分别写出：
（1）平均时间复杂度低于O（n2）的排序方法； （2）所需辅助空间最多的排序方法；
答案：(1) 希尔、快速、堆、归并 (2) 归并
6、对关键子序列（72，87，61，23，94，16，05，58）进行堆排序，使之按关键字递减次序排列（最小堆），请写出排序过程中得到的初始堆和前三趟的序列状态。
47
答案：
初始堆7287235994166105875923947205166105592394728716610559239472第1趟166187第2趟872359059472611605875994722361160587599423726116第3趟5972870594236116
附：
48
数据结构试题集（含答案）
