第5章排序测试卷(2)

【3】已知序列{503，87，512，61，908，170，897，275，653，462}，请给出采用堆序法对该序列作降序排序时的每一趟的结果。

6

【4】已知序列{503，87，512，61，908，170，897，275，653，462}，请给出采用基数排序法对该序列作升序排序时的每一趟的结果。

【5】已知序列{503，17，512，908，170，897，275，653，426，154，509，612，677，765，703，94}，请给出采用希尔排序法(d1=8)对该序列作升序排序时的每一趟的结果。

7

【6】已知序列{70，83，100，65，10，32，7，9}，请给出采用直接插入排序法对该序列作升序排序时的每一趟的结果。

【7】已知序列{10，18，4，3，6，12，1，9，18，8}，请给出采用2路归并排序法对该序列作升序排序时的每一趟的结果。

【8】在冒泡排序过程中，有的关键字在某趟排序中可能朝着与最终排序相反的方向移动。试举例说明之。快速排序过程中有没有这种现象?

8

【9】假设我们把n个元素的序列{a1，a2，?，an}中满足条件ak?max?at?的元素ak称为

1?t?k逆序元素。若在一个无序序列中有一对元素ai>aj(i

【10】请回答下列关于堆的一些问题：

（1）堆的存储表示是顺序的，还是链式的? （2）设有一个最小堆(小根堆)，即堆中任意结点的关键字均小于它的左孩子和右孩子的关键字。其具有最大关键字的元素可能在什么地方?

【11】 有n个不同的英文单词，它们的长度相等，均为m，若n>>50，m<5，试问采用什么排序方法时间复杂度最佳?为什么?

9

【12】针对以下情况确定非递归的归并排序的运行时间(数据比较次数与移动次数)： (1)输入的n个数据全部有序； (2)输入的n个数据全部逆向有序； (3)随机地输入n个数据。