西安石油大学：《数据结构》精品课程资源（章节习题）第9章 排序

基本概念题: 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举例说明直接选择排序是不稳定的排序。 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设待排序的关键字序列为{114,18,33,29,9,18*,21,5,19},画出堆排序时形成初 始堆和第一次堆顶元素第一次交换后堆的变化过程 9-9证明:当待排序数据元素的关键字序列已经为有序状态时,快速排序的时间复杂 度为Omn2)。 *9-10讨论你所知道的体育比赛的产生名次方法,并以8个竞赛者为例说明各种产生名 次方法所要进行的比赛次数。 算法设计题 9-11编写一个测试希尔排序算法函数 ShellSort(的测试主函数。测试数据为 (43,5,47,1,19,11,59,15,48,41)。 9-12设待排序数据元素的关键字为整数类型,编写函数实现在O(m)的时间复杂度内和 O(1的空间复杂度内重排数组a,使得将所有取负值的关键字排在所有取非负值的关键字之 前 9-13编写函数实现单链表类数据元素的直接插入排序。 9-14直接选择排序算法是不稳定的排序算法。这主要是由于每次从无序记录区选出最 小记录后,与无序区的第一个记录交换而引起的,因为交换可能引起关键字相同的数据元素 位置发生变化。如果在选出最小记录后,将它前面的无序记录依次后移,然后再将最小记录 放在有序区的后面,这样就能保证排序算法的稳定性。编写一个稳定的直接选择排序函数。 上机实习题 9-15排序算法比较。要求: (1)用随机数产生10000°个待排序数据元素的关键字值。 (2)测试下列各排序函数的机器实际执行时间(至少测试两个) (a)直接插入排序; (b)希尔排序(增量为4,2,1) (c)直接选择排序 (d)堆排序

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

(e)冒泡排序; (f)快速排序 (g)二路归并排序 (h)基于链式队列的基数排序 9-16基数排序算法设计。要求: (1)设计基于顺序队列的基数排序函数。 (2)设计一个测试主函数,测试所设计的基于顺序队列的基数排序函数

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