数据结构2025试题-第10章 排序 - 答案 .pdfVIP

博学之，审问之，慎思之，明辨之，笃行之。——《礼记》

我下vip免费资源网

第10章排序（参考答案）

一、选择题

1.D2.D3.D4.B5.B7.C,6.B8.A9.C10.C,D,F11.1D,C

E11.2A,D,F

11.3B12.C13.14.B15.16.D17.18.19.A20.21.

11.4(A,C,F)(B,D,E),DA,DDCACC

22.23.24.C25.26.C27.28.C29.30.C31.32.33.A34.35.

BCADB,BDDDA

36.37.38.C39.40.C41.42.B43.44.B45.46.47.B48.49.

AABCAAC,DDD

50.51.52.E53.54.C55.56.B57.58.A59.1C59.2A59.3D59.4B

DC,GBCB59.5G

60.1B60.2C61.1B61.2D61.3B61.4C61.5F62.A63.64.65.A66.

60.3AABA

部分答案解释如下：

18.对于后三种排序方法两趟排序后，序列的首部或尾部的两个元素应是有序的两个极值，

而给定的序列并不满足。

20.本题为步长为3的一趟希尔排序。枢轴是73。24.

49.小根堆中，关键字最大的记录只能在叶结点上，故不可能在小于等于n/2的结点上。

64.因组与组之间已有序，故将n/k个组分别排序即可，基于比较的排序方法每组的时间下

界为O(klogk),全部时间下界为O(nlogk)。

22

二、判断题

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.免去查找过程中每一步都要检测整个表是否查找完毕，提高了查找效率。