数据结构第10章作业

1、第10章排序作业作业一：1） 对人意的7个关键字进行排序，至少要进行_次关键字之间的两两比较。A. 13 B.11 C.15 D.16 E.19【参考答案】C【解题思路】任何一个借助“比较”进行排序的算法，在最坏的情况下所需进行得比较次数至少为。=15。2） 排序方法中，从未排序序列中依次取出元素与已排序序列（初始时为空）中的元素进行比较，将其放入已排序序列的正确位置上的方法，称为_。A.希尔排序 B.冒泡排序C.插入排序D.选择排序【参考答案】C【解题思路】插入排序的思想是：每一趟将一个待排序的记录，按其关键字的大小插入到已经排序的序列中的适当位置。直到全部的记录插入完成为止。3） 对记录的

2、关键字为50，26，38，80，70，90，8，30，40，20进行排序，各趟排序结束时的结果为：50 26 38 80 70 90 8 30 40 20 50 8 30 40 20 90 26 38 80 70 26 8 30 40 20 80 50 38 90 708 20 26 30 38 40 50 70 80 90 其使用的排序方法是_。A. 快速排序B. 希尔排序C.基数排序D.归并排序【参考答案】B【解题思路】由排序的结果直接可以确知（即使不知道其他几中排序方法）该排序是增量序列为5,3,1的希尔排序。4） 已知序列70，83，100，65，10，32，7，9,请给出采用插入排序

3、法对该序列作升序排序时的每一趟的结果。【参考答案】采用插入排序方法排序的各趟的结果如下：初始：（70），83，100，65，10，32，7，9第一趟：（70，83）， 100，65，10，32，7，9第二趟：（70，83，100），65，10，32，7，9第三趟：（65，70，83，100），10，32，7，9第四趟：（10，65，70，83，100），32，7，9第五趟：（10，32，65，70，83，100），7，9第六趟：（7，10，32，65，70， 83，100），9第七趟：（7，9，10，32，65，70，83，100）作业二：1） 快速排序方法在_情况下最不利于发挥其长处。A.

4、要排序的数据量太大B.要排序的数据中含有多个相同值C.要排序的数据已基本有序D.要排序的数据个数为奇数【参考答案】C【解题思路】要排序的数据（个数为n）已基本有序，采用快速排序则需要n-1趟，其时间复杂度升至O(n2)。2） 用快速排序方法对线性表(24,84,20,47,15,26,68,35,19)进行排序时，写出元素序列的变化情况：【参考答案】（1）24,84,20,47,15,26,68,35,19（2）19,15, 20,24, 47, 26,68, 35 , 84 （3）15, 19, 20,24, 35 , 26,47, 68, 84（4）15, 19, 20,24, 26, 3

5、5 , 47, 68, 84【解题思路】每一次将一个子序列以第一个元素为基准分为两段。作业三：1） 采用简单选择排序，比较的次数与移动次数分别是_.A.B. C. D. 【参考答案】C【解题思路】简单选择排序过程是：每趟从n-i+1个记录中选取关键字最小的记录（每趟比较的时间复杂度为O(n)）,并和第i个记录交换（每趟移动的时间复杂度为O(1)），因此，总的比较次数与移动次数分别是。2） 对n个元素的序列进行排序时，堆排序所需要的附加存储空间是_.A.B. C. D. 【参考答案】B【解题思路】堆排序本质上是就地排序。3） 已知序列503，87，512，61，908，170，897，275，6

6、53，462，给出采用堆排序法对该序列做降序排序时的每一趟的结果。【参考答案】排序结果为908,897,653,512,503, 462,275,170,87,61。503875121708979086127565334621初始堆90865389717051246250327561872建堆3交换908和87,输出90889765351217087462503275614筛选调整87653897170512462503275615交换897和61,输出89765350351217087462275616筛选调整61653512170874625032757交换653和61,输出6535125

7、0317061874622758筛选调整61503512170874622759交换512和87,输出512503462170618727510筛选调整875031706146227511交换503和61,输出503462275170876112筛选调整462170872756113交换462和87,输出462275871706114筛选调整275170618715交换275和61,输出275170-876116筛选调整871706117交换170和61,输出17087-6118筛选调整876119交换87和61,输出8720输出6161作业四：1） 一组纪录的排序码为25，48，16，35，

8、79，82，23，40，36，72，其中含有5个长度为2的有序表，按归并排序的方法对该序列进行一趟归并后的结果为_.A.16 25 35 48 23 40 79 82 36 72 B.16 25 35 48 79 82 23 36 40 72 C.16 23 48 35 79 82 23 36 40 72 D.16 25 35 48 79 23 36 40 72 82 【参考答案】A【解题思路】一趟归并过程如下：25， 48 ，16 ，35， 79 ，82，23，40，36，7216 ，25，35， 48 ，23，40，79 ，82， 36，722） 就排序的算法所用的辅助空间而言，堆排序、快速排序、归并排序的关系是_。A. 堆排序快速排序归并排序B. 堆排序归并排序归并排序快速排序归并排序【参考答案】A【解题思路】堆排序、快速排序、归并排序所用的辅助空间依次是:O(1)、O(n)。3)已知序列10,18,4,3,6,12,1,9,15,8,请给出采用归并排序法对该序列作升序排序的每一趟结果。【参考答案】初始: 10, 18, 4, 3, 6, 12, 1, 9, 15,