《数据结构》第九章 排序 习题.doc

《《数据结构》第九章 排序 习题.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、《数据结构》第九章排序习题基本概念题：9-1什么是关键字？什么是主关键字？什么是次关键字？9-2什么是稳定的排序算法？什么是不稳定的排序算法？对同一个问题，若有一个算法是稳定的，另一个算法是不稳定的，哪一种算法更好？9-3什么是内部排序？什么是外部排序？9-4设数据元素关键字序列为{475,137,481,219,382,674,350,326,815,506}，分别写出执行下列排序算法时，各趟排序后的关键字序列：（1）希尔排序（增量d=5,3,1）（2）快速排序（3）堆排序（4）归并排序（5）基数排序复杂概念题：9-5举例说明直接选择排序是不

2、稳定的排序。9-6举例说明希尔排序、快速排序和堆排序是不稳定的排序。9-7判断下列序列是否为堆，若是堆则进一步指出是最大堆还是最小堆。（1）(50,36,41,19,23,4,20,18,12,22)（2）(43,5,47,1,19,11,59,15,48,41)（3）(50,36,41,19,23,20,18,12,22)（4）(9,13,17,21,22,31,33,24,27,23)9-8设待排序的关键字序列为{11,4,18,33,29,9,18*,21,5,19}，画出堆排序时形成初始堆和第一次堆顶元素第一次交换后堆的变化过程。*9-

3、9证明：当待排序数据元素的关键字序列已经为有序状态时，快速排序的时间复杂度为O(n2)。*9-10讨论你所知道的体育比赛的产生名次方法，并以8个竞赛者为例说明各种产生名次方法所要进行的比赛次数。算法设计题：9-11编写一个测试希尔排序算法函数ShellSort()的测试主函数。测试数据为(43,5,47,1,19,11,59,15,48,41)。9-12设待排序数据元素的关键字为整数类型，编写函数实现在O(n)的时间复杂度内和O(1)的空间复杂度内重排数组a，使得将所有取负值的关键字排在所有取非负值的关键字之前。9-13编写函数实现单链表类数据

4、元素的直接插入排序。9-14直接选择排序算法是不稳定的排序算法。这主要是由于每次从无序记录区选出最小记录后，与无序区的第一个记录交换而引起的，因为交换可能引起关键字相同的数据元素位置发生变化。如果在选出最小记录后，将它前面的无序记录依次后移，然后再将最小记录放在有序区的后面，这样就能保证排序算法的稳定性。编写一个稳定的直接选择排序函数。上机实习题：9-15排序算法比较。要求：（1）用随机数产生100000个待排序数据元素的关键字值。（2）测试下列各排序函数的机器实际执行时间（至少测试两个）：（a）直接插入排序；（b）希尔排序（增量为4,2,1）

5、；（c）直接选择排序；（d）堆排序；（e）冒泡排序；（f）快速排序；（g）二路归并排序；（h）基于链式队列的基数排序9-16基数排序算法设计。要求：（1）设计基于顺序队列的基数排序函数。（2）设计一个测试主函数，测试所设计的基于顺序队列的基数排序函数。