第10章排序(参考答案) 选择题 D2.D3.D 15.B 6.B7.CE8A9C 10.C,D, F11.ID,C11.2A,D,F 11:3B14(ACF)(BDE)12CD13A14BD15.D16D17C18.A[19A20.c21.C 22.B23.c24.C25.A26.C27.D28.C|29.B30.C,B31.D32.D33.A34.D|35.A 36.A37.A38.C39.B40.C41.C42.B43.A44.B45.A46.C47.B,D48.D49.D 0.D51.C52.E,G53.B54.C5.C56.B57.B58.A59.1c59.2A59.3D59.4B59.5G 60.1B60.2C60.3A61.1B61.2D61.3B61.4C61.5F 62.A63.A64.B65.A6.A 部分答案解释如下 18.对于后三种排序方法两趟排序后,序列的首部或尾部的两个元素应是有序的两个极值, 而给定的序列并不满足。 20.本题为步长为3的一趟希尔排序。 24.枢轴是73 49.小根堆中,关键字最大的记录只能在叶结点上,故不可能在小于等于n/2」的结点上。 64.因组与组之间已有序,故将n/k个组分别排序即可,基于比较的排序方法每组的时间下 界为0(klog2k),全部时间下界为0( logik) 判断题 1.√|2.×|3.×4.×5.×6.×|7.×8.×9.×|10.11.12.|13 14.15.|16.17.1 部分答案解释如下: 5.错误。例如冒泡排序是稳定排序,将4,3,2,1按冒泡排序排成升序序列,第一趟变成 3,2,1,4,此时3就朝向最终位置的相反方向移动。 12.错误。堆是n个元素的序列, 可以看作是完全二叉树,但相对于根并无左小右大的要求,故其既不是二叉排序树,更不会 是平衡二叉树。 错误。待排序序列为正序时,简单插入排序比归并排序快 三、填空题 1.比较,移动2.生成有序归并段(顺串),归并3.希尔排序、简单选择排序、快速 排序、堆排序等 4.冒泡,快速5.(1)简单选择排序(2)直接插入排序(最小的元素在最后时) 免去查找过程中每一步都要检测整个表是否查找完毕,提高了查找效率 8.题中p指向无序区第一个记录,q指向最小值结点,一趟排序结束,p和q所指结点值交 换,同时向后移p指针。(1)!=null (2)p->next (3r!=null (4)r->data<g->data (5)r->next(6)p->next 9.题中为操作方便,先增加头结点(最后删除),p指向无序区的前一记录,r指向最小值 结点的前驱,一趟排序结束,无序区第一个记录与r所指结点的后继交换指针 (1)g->link!=NULL(2)r!=p (3)p->link (4)p->link=s (5)p=p->link第 10 章 排序（参考答案） 一、选择题 1.D 2.D 3.D 4.B 5.B 6.B 7.C,E 8.A 9.C 10.C,D,F 11.1D,C 11.2A,D,F 11.3B 11.4(A,C,F)(B,D,E) 12.C,D 13.A 14.B,D 15.D 16.D 17.C 18.A 19.A 20.C 21.C 22.B 23.C 24.C 25.A 26.C 27.D 28.C 29.B 30.C,B 31.D 32.D 33.A 34.D 35.A 36.A 37.A 38.C 39.B 40.C 41.C 42.B 43.A 44.B 45.A 46.C 47.B,D 48.D 49.D 50.D 51.C 52.E,G 53.B 54.C 55.C 56.B 57.B 58.A 59.1C 59.2A 59.3D 59.4B 59.5G 60.1B 60.2C 60.3A 61.1B 61.2D 61.3B 61.4C 61.5F 62.A 63.A 64.B 65.A 66.A 部分答案解释如下： 18. 对于后三种排序方法两趟排序后，序列的首部或尾部的两个元素应是有序的两个极值， 而给定的序列并不满足。 20. 本题为步长为 3 的一趟希尔排序。 24.枢轴是 73。 49. 小根堆中，关键字最大的记录只能在叶结点上，故不可能在小于等于 n/2 的结点上。 64. 因组与组之间已有序，故将 n/k 个组分别排序即可，基于比较的排序方法每组的时间下 界为 O(klog2k),全部时间下界为 O(nlog2k)。 二、判断题 1.√ 2.× 3.× 4.× 5.× 6.× 7.× 8.× 9.× 10. × 11. × 12. × 13. × 14. √ 15. √ 16. × 17. × 18. × 19. × 20. × 21. × 22. × 23. × 24. × 25. √ 26. × 27. √ 28. × 29. × 30. × 31. √ 部分答案解释如下： 5. 错误。例如冒泡排序是稳定排序，将 4,3,2,1 按冒泡排序排成升序序列，第一趟变成 3,2,1,4，此时 3 就朝向最终位置的相反方向移动。 12. 错误。堆是 n 个元素的序列， 可以看作是完全二叉树，但相对于根并无左小右大的要求，故其既不是二叉排序树，更不会 是平衡二叉树。 22. 错误。待排序序列为正序时，简单插入排序比归并排序快。 三、填空题 1. 比较,移动 2.生成有序归并段（顺串）,归并 3.希尔排序、简单选择排序、快速 排序、堆排序等 4. 冒泡,快速 5. (1)简单选择排序 (2)直接插入排序（最小的元素在最后时） 6. 免去查找过程中每一步都要检测整个表是否查找完毕，提高了查找效率。 7. n(n-1)/2 8.题中 p 指向无序区第一个记录，q 指向最小值结点，一趟排序结束，p 和 q 所指结点值交 换，同时向后移 p 指针。(1)!=null (2)p->next (3)r!=null (4)r->data<q->data (5)r->next (6)p->next 9. 题中为操作方便，先增加头结点（最后删除），p 指向无序区的前一记录，r 指向最小值 结点的前驱，一趟排序结束，无序区第一个记录与 r 所指结点的后继交换指针。 (1)q->link!=NULL (2)r!=p (3)p->link (4)p->link=s (5)p=p->link