查找和排序(12)

习题习题习题习题习题习题习题习题习题

10、内排序要求数据一定要以顺序方式存储。

11、快速排序和归并排序在最坏情况下的比较次数都是O（nlogn）。

12、用希尔排序法时，若关键字的初始排序杂乱无序，则排序效率就低。

13、基数分类只适用于以数字为关键字的情况，不适用以字符串为关键字的情况。

14、若中序遍历平衡的二叉排序树，可得到排好序的关键字序列。

15、在执行某个排序算法过程中，出现了排序码朝着最终排序序列位置相反方向移动，则该算法是不稳定的。

四、解答题

1．已知数据序列为（12，5，9，20，6，31，24），对该数据序列进行排序，试写出插入排序和冒泡排序每趟的结果。

2．判断下列两序列是否为堆？如不是，按照建堆的思想把它调整为堆，并用图表示建堆的过程。

（1）（100,90,80,60,85,75,20,25,10,70,65,50）；

（2）（100,70,50,20,90,75,60,25,10,85,65,80）。

3．对于下列一组关键字(12，2，16，30，8，28，4，10，20，6，18），试写出用下列算法从小到大排序时第一趟结束时的序列。

（1)希尔排序（第一趟排序的增量为5）

（2）快速排序（选第一个记录为枢纽）

（3)基数排序。

4.有n个不同的英文单词，它们的长度相等，均为m，若n＞＞50,m＜5，试问采用什么排序方法时间复杂性最佳?为什么?

5. 已知序列（54，21，52，14，98，47，41，75，5，62），请给出采用堆排序法对该序列作升序排序时的每一趟结果。

6.已知序列（53，82，62，71，93，70，34，25，47，29），请给出采用二路归并排序法对该序列作升序排序时的每一趟结果。

五、算法设计题

1．以下是直接选择排序的算法，请补充完整。