数据结构-作业 1/1页
8 内排序
班级 姓名 学号 成绩 批改时间 选择填空题
1、用冒泡排序方法对n个记录按排序码值从小到大排序时，当初始序列是按排序码值从大到小排列时，与码值总比较次数是 。
（A）n-1 （B）n （C）n+1 （D）n(n-1)／2
2、下列排序方法中，与排序码值总比较次数与待排序记录的初始序列排列状态无关的是 。 （A）直接插入排序 （B）冒泡排序 （C）快速排序 （D）直接选择排序 3、将7个不同的整数进行排序，至少需要比较 次，至多需要比较 次。
4、若需要时间复杂度在O(nlog2n)内，对整数数组进行排序，且要求排序方法是稳定的，则可选择的排序方法是 。
（A）快速排序 （B）归并排序 C．堆排序 D．直接插入排序
5、当待排序的整数是有序序列时，采用 方法比较好，其时间复杂度为O(n)，而采用 方法却正
2
好相反，达到最坏情况下时间复杂度为O(n)；无论待排序序列排列是否有序，采用 方法的时间复杂
2
度都是O(n)。
（A）快速排序 （B）冒泡排序 （C）归并排序 （D）直接选择排序
6、已知A[m]中每个数组元素距其最终位置不远，采用下列 排序方法最节省时间。 A．直接插入 B．堆 C．快速 D．直接选择 7、希尔排序的增量序列一定是（ ）
（A）递增的 （B）递减的 （C）随机的 （D）不变的
简答题
1、设待排序的关键字序列为：12、2、16、30、28，10，18，20。
（1）请写出使用希尔排序时的增量序列。列出希尔排序的每一趟过程。
（2）若使用直接插入排序共需要多少趟？列出每一趟的过程。
2、对长度为n的记录序列进行快速排序时，所需要的比较次数依赖于这n个元素的初始序列。 （1）n=8时，在最好情况下需要进行多少次比较？试说明理由。 （2）给出n=8时的一个最好情况的初始排列实例。