第六章_排序练习

1、 第10章 排序一、选择题1某内排序方法的稳定性是指( )。 A该排序算法不允许有相同的关键字记录 B该排序算法允许有相同的关键字记录C平均时间为0（n log n）的排序方法 D以上都不对 2下面给出的四种排序法中( )排序法是不稳定性排序法。 A. 插入 B. 冒泡 C. 二路归并 D. 堆积3下列排序算法中，其中（ ）是稳定的。 A. 堆排序，冒泡排序 B. 快速排序，堆排序 C. 直接选择排序，归并排序 D. 归并排序，冒泡排序6若要求尽可能快地对序列进行稳定的排序，则应选（ A快速排序 B归并排序 C冒泡排序）。8若要求排序是稳定的，且关键字为实数，则在下列排序方法中应选（ ）排序为

2、宜。A直接插入 B直接选择 C堆 D快速 E基数 9若需在O(nlog2n)的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是（ ）。 A. 快速排序 B. 堆排序 C. 归并排序 D. 直接插入排序11下列内部排序算法中： A快速排序 B.直接插入排序 C. 二路归并排序 D. 简单选择排序 E. 起泡排序 F. 堆排序（1） 其比较次数与序列初态无关的算法是（ ） （2）不稳定的排序算法是（ ）（3）在初始序列已基本有序（除去n个元素中的某k个元素后即呈有序，k 快速排序 归并排序 E以上答案都不对 59排序方法有许多种，（1） 法从未排序的序列中依次取出元素，与已排序序列

3、（初始时为空）中的元素作比较，将其放入已排序序列的正确位置上；（2） 法从未排序的序列中挑选元素，并将其依次放入已排序序列（初始时为空）的一端； 交换排序方法是对序列中的元素进行一系列比较，当被比较的两元素逆序时，进行交换；（3） 和（4） 是基于这类方法的两种排序方法， 而（4） 是比（3） 效率更高的方法；（5） 法是基于选择排序的一种排序方法，是完全二叉树结构的一个重要应用。 （1）-（5）: A选择排序 B快速排序 C插入排序 D起泡排序 E归并排序 Fshell排序 G堆排序 H基数排序三、填空题1若不考虑基数排序，则在排序过程中，主要进行的两种基本操作是关键字的_ _和记录的_ 。

4、4分别采用堆排序，快速排序，冒泡排序和归并排序，对初态为有序的表，则最省时间的是_ _算法，最费时间的是_ _算法。5. 不受待排序初始序列的影响，时间复杂度为O(N2)的排序算法是_ _，在排序算法的最后一趟开始之前，所有元素都可能不在其最终位置上的排序算法是_ _。22堆是一种有用的数据结构. 堆排序是一种_(1) _排序，堆实质上是一棵_(2) _结点的层次序列。对含有N个元素的序列进行排序时，堆排序的时间复杂度是_(3) _，所需的附加存储结点是_(4) _。关键码序列05，23，16，68，94，72，71，73是否满足堆的性质_(5) _。 四、应用题2. 在各种排序方法中，哪些是

5、稳定的？哪些是不稳定的？并为每一种不稳定的排序方法举出一个不稳定的实例。 第10章 排序（参考答案）一、选择题 1.D2.D3.D4.B5.B 6.B7.C,E8.A9.C10.C,D,F11.1D,C 11.2A,D,F11.3B 11.4(A,C,F)(B,D,E)12.C,D13.A14.B,D15.D16.D17.C18.A19.A20.C21.C22.B23.C24.C25.A26.C27.D28.C29.B30.C,B31.D32.D33.A34.D35.A36.A37.A38.C39.B40.C41.C42.B43.A44.B45.A46.C47.B,D48.D49.D50.D5

6、1.C52.E,G53.B54.C55.C56.B57.B58.A59.1C 59.2A 59.3D 59.4B 59.5G60.1B 60.2C 60.3A61.1B 61.2D 61.3B 61.4C 61.5F62.A63.A64.B65.A66.A部分答案解释如下：18. 对于后三种排序方法两趟排序后，序列的首部或尾部的两个元素应是有序的两个极值，而给定的序列并不满足。 20. 本题为步长为3的一趟希尔排序。 24.枢轴是73。 49. 小根堆中，关键字最大的记录只能在叶结点上，故不可能在小于等于n/2的结点上。64. 因组与组之间已有序，故将n/k个组分别排序即可，基于比较的排序方法

7、每组的时间下界为O(klog2k),全部时间下界为O(nlog2k)。二、填空题1. 比较,移动 2.生成有序归并段（顺串）,归并 3.希尔排序、简单选择排序、快速排序、堆排序等4. 冒泡,快速 5. (1)简单选择排序 (2)直接插入排序（最小的元素在最后时） 22. (1) 选择 (2)完全二叉树 (3)O(Nlog2N) (4)O(1) (5)满足堆的性质三、应用题2.排序方法平均时间最坏情况辅助空间稳定性不稳定排序举例直接插入排序O（n2）O（n2）O（1）稳定折半插入排序O（n2）O（n2）O（1）稳定二路插入排序O（n2）O（n2）O（n）稳定表插入排序O（n2）O（n2）O（1）稳定起泡排序O（n2）O（n2）O（1）稳定直接选择排序O（n2）O（n2）O（1）不稳定2,2,1希尔排序O（n1.3）O（n1.3）O（1）不稳定3,2,2,1(d=2,d=1)快速排序O（nlog2n）O（n2）O（log2n）不稳