1、排序模拟试卷 2 及答案与解析一、单项选择题下列各题的备选答案中，只有一个是符合题意的。1 下列（ ）是一个堆。（A）19，75，34，26，97，56（B） 97，26，34，75，19，56（C） 19，56，26，97，34，75（D）19，34，26，97，56，752 在含有 n 个关键字的小根堆中，关键字最大的记录有可能存储在（ ）。（A）n2（B） n2+2（C） 1（D）n2-13 有一组数据(15，9，7，8，20，-1，7，4)，用堆排序的筛选方法建立的初始小根堆为（ ）。（A）-1 ，4，8，9，20，7，15，7（B） -1，7，15，7，4，8，20，9（C） -1，
2、4，7，8，20，15，7，9（D）A、B、C 均不对4 构建 n 个记录的初始堆，其时间复杂度为（ ）；对 n 个记录进行堆排序，最坏情况下其时间复杂度为（ ）。（A）O(n)（B） O(n2)（C） O(log2n)（D）0(nlog 2n)5 向具有 n 个结点的堆中插入一个新元素的时间复杂度为（ ），删除一个元素的时间复杂度为（ ）。（A）O(1)（B） O(n)（C） O(nlog2n)（D）O(nlog 2n)6 已知关键字序列 5，8，12，19，28，20，15，22 是小根堆，插入关键字 3，调整好后得到的小根堆是（ ）。（A）3，5，12，8，28，20，15，22，19（
3、B） 3，5，12，19，20，15，22，8，28（C） 3,12,5，20，15，22,28（D）5,8，28,20,15,22，19,37 己知序列 25，13，10，12，9 是大根堆，在序列尾部插入新元素 18，将其再调整为大根堆，调整过程中元素之间进行的比较次数是（ ）。（A）1（B） 2（C） 4（D）58 对关键码序 Yfl23，17，72，60，25，8，68， 71，52 进行堆排序，输出两个最小关键码后的剩余堆是（ ）。（A）23 ，72 ，60，25，68，71，52（B） 23，25，52，60，71，72，68（C） 71，25，23，52，60，72，68（D）2
4、3 ，25 ，68，52，60，72，719 下面给出的四种排序方法中，排序过程中的比较次数与序列初始状态无关的是（ ）。（A）归并排序（B）插入排序（C）快速排序（D）冒泡排序10 在下列排序算法中，平均情况下空间复杂度为 O(n)的是（ ）；最坏情况下空间复杂度为 O(n)的是（ ）。I,希尔排序 II,堆排序 III,冒泡排序,归并排序 V,快速排序,基数排序（A）I、VI（B） II、V（C） 、V（D）11 2-路归并排序中，归并趟数的数量级是（ ）。（A）O(n)（B） O(log2n)（C） O(nlog2n)（D）O(n 2)12 若对 27 个元素只进行三趟多路归并排序，则选
5、取的归并路数为（ ）。（A）2（B） 3（C） 4（D）513 将两个各有 N 个元素的有序表合并成一个有序表，最少的比较次数是（ ），最多的比较次数是（ ）。（A）N（B） 2N-1（C） 2N（D）N-114 对05 ，46 ，13，55， 94，17，42 进行基数排序，一趟排序的结果是（ ）。（A）05,46,13,55,94,17,42（B） 05,13,17,42,46,55,94（C） 42，13，94，05，55，46，17（D）05，13，46，55，17，42，9415 以下排序方法中，（ ）在一趟结束后不一定能选出一个元素放在其最终位置上。（A）简单选择排序（B）冒泡排序
6、（C）归并排序（D）堆排序16 以下排序算法中，（ ）不需要进行关键字的比较。（A）快速排序（B）归并排序（C）基数排序（D）堆排序17 如果将中国人按照生日(不考虑年份，只考虑月、日)来排序，那么使用下列排序算法中最快的是（ ）。（A）归并排序（B）希尔排序（C）快速排序（D）基数排序18 一组经过第一趟 2 路归并排序后的记录的关键字为25，50 ，15 ，35，80，85 ，20，40，36，70 ，其中包含 5 个长度为 2 的有序表，用 2 路归并排序方法对该序列进行第二趟归并后的结果为（ ）。（A）15，25，35，50，80，20，85，40，70，36（B） 15，25，35，
7、50，20，40，80，85，36，70（C） 15，25，50，35，80，85，20，36，40，70（D）15，25，35,50,80,20,36,40,70,8519 设被排序的结点序列共有 N 个结点，在该序列中的结点已十分接近排序的情况下，用直接插入排序、归并排序和快速排序对其进行排序，这些算法的时间复杂度应为（ ）。（A）O(N) ， O(N)，O(N)（B） O(N)，0(N*log 2N)，O(N*log 2N)（C） O(N)，O(N*log 2N)，O(N 2)（D）O(N 2)， O(N*log2N)，O(N 2)20 以下排序方法中时间复杂度为 O(nlog2n)且稳
8、定的是（ ）。（A）堆排序（B）快速排序（C）归并排序（D）直接插入排序21 若要求排序是稳定的，且关键字为实数，则在下列排序方法中应选（ ）。（A）直接插入排序（B）选择排序（C）基数排序（D）快速排序22 一般情况下，以下查找效率最低的数据结构是（ ）。（A）有序顺序表（B）二叉排序树（C）堆（D）平衡二叉树23 就排序算法所用的辅助空间而言，堆排序、快速排序和归并排序的关系是（ ）。（A）堆排序 归并排序 快速排序（D）堆排序快速排序归并排序24 排序趟数与序列的原始状态无关的排序方法是（ ）。I,直接插入排序 II,简单选择排序 III,冒泡排序,基数排序（A）I、III（B） I、I
9、I、 （C） I、II、 III（D）I、25 若序列的原始状态为1，2，3，4，5，10，6，7，8，9 ，要想使得排序过程中元素比较次数最少，则应该采用（ ）方法。（A）插入排序（B）选择排序（C）希尔排序（D）冒泡排序二、综合题26 冒泡排序算法是把大的元素向上移(气泡的上浮)，也可以把小的元素向下移(气泡的下沉)请给出上浮和下沉过程交替的冒泡排序算法。27 有 50 个学生的记录(每个学生的记录包括学号和成绩)，组成记录数组，按成绩由高到低的次序输出(每行 10 个记录)。排序方法采用选择排序。28 设有顺序放置的 n 个桶，每个桶中装有一粒砾石，每粒砾石的颜色是红、白、蓝之一。要求重
10、新安排这些砾石，使得所有红色砾石在前，所有白色砾石居中，所有蓝色砾石居后，重新安排时对每粒砾石的颜色只能看一次，并且只允许交换操作来调整砾石的位置。排序模拟试卷 2 答案与解析一、单项选择题下列各题的备选答案中，只有一个是符合题意的。1 【正确答案】 D【知识模块】 排序2 【正确答案】 B【知识模块】 排序3 【正确答案】 C【知识模块】 排序4 【正确答案】 A【试题解析】 建堆过程中，向下调整的时间与树高 h 有关，为 O(h)，每次向下调整时，大部分结点的高度都较小。因此，可以证明在元素个数为 n 的序列上建堆，其时间复杂度为 O(n)。无论在最好情况还是在最坏情况下，堆排序的时间复杂
11、度均为 O(nlog2n)。【知识模块】 排序5 【正确答案】 C【试题解析】 在向有 n 个元素的堆中插入一个新元素时，需要调用一个向上调整的算法，比较次数最多等于树的高度减 1，由于树的高度为log 2n+1，所以堆的向上调整算法的比较次数最多等于log 2n。此处需要注意到，调整堆和建初始堆的时间复杂度是不一样的，读者可以仔细分析两个算法的具体执行过程。【知识模块】 排序6 【正确答案】 A【知识模块】 排序7 【正确答案】 B【知识模块】 排序8 【正确答案】 D【知识模块】 排序9 【正确答案】 A【试题解析】 前面已讲过选择排序的比较次数与序列初始状态无关，归并排序也与序列的初始状
12、态无关，读者还应能从算法的原理方面来考虑为什么和初始状态无关。【知识模块】 排序10 【正确答案】 D【试题解析】 归并排序算法在平均情况和最坏情况下空间复杂度都会达到 O(n)，快速排序只有在最坏情况下才会达到 O(n)，一般平均情况下为 O(log2n)。所以归并排序算法可以看作是本章中所有算法中占用辅助空间最多的排序算法。【知识模块】 排序11 【正确答案】 B【试题解析】 对于 N 个元素进行 k-路归并排序时，排序的趟数 m 满足 km=N，所以 m=log2n。【知识模块】 排序12 【正确答案】 B【试题解析】 利用上述公式，这里要求的是 k，代入可得 k=3。【知识模块】 排序
13、13 【正确答案】 A【试题解析】 ，B 注意到当一个表中最小元素比另一个表中最大元素还大的时候，比较的次数是最少的，仅比较 N 次；而当两个表中元素依次间隔地比较时，即a1b 1a 2 b2a nb n 时，比较的次数是最多的，为 2N1 次。【知识模块】 排序14 【正确答案】 C【试题解析】 比较各数的个位数，按各数的个位数进行排序，可知选 C。【知识模块】 排序15 【正确答案】 C【知识模块】 排序16 【正确答案】 C【试题解析】 基数排序是基于关键字各位的大小进行排序的，它不是基于关键字的比较进行的。【知识模块】 排序17 【正确答案】 D【试题解析】 按照所有中国人的生日排序，
14、一方面 N 是非常大的，另一方面关键字所含排序码数为 2，且一个排序码基数为 12，另一个为 31，都是较小的常数值，采用基数排序可以在 O(N)内完成排序过程。【知识模块】 排序18 【正确答案】 B【知识模块】 排序19 【正确答案】 C【知识模块】 排序20 【正确答案】 C【试题解析】 堆排序和快速排序不是稳定排序方法，而直接插入排序算法时间复杂度为 O(n2)。【知识模块】 排序21 【正确答案】 A【试题解析】 由于题目要求是稳定排序，排除 B 和 D，又由于基数排序不能对float 和 double 类型的实数排序，故排除 C。【知识模块】 排序22 【正确答案】 C【试题解析】
15、 堆是用于排序的，在查找时它是无序的，所以效率没有其他的查找结构效率高。【知识模块】 排序23 【正确答案】 A【试题解析】 由于堆排序空间复杂度为 O(1)，快速排序空间复杂度在最坏情况下为 O(n)，平均为 O(log2n、)，归并排序空间复杂度为 O(n)，所以不难得出选 A。【知识模块】 排序24 【正确答案】 B【试题解析】 交换类的排序，其趟数和原始序列状态有关，故冒泡排序与初始序列有关。直接插入排序：每一趟排序都是插入一个元素，所以排序趟数固定为 n-1；简单选择排序：每趟排序都是选出一个最小(或最大)的元素，所以排序趟数固定为 n-1；基数排序：每趟排序都要进行“分配”和 “收
16、集”，排序趟数固定为 d。【知识模块】 排序25 【正确答案】 A【试题解析】 选择排序和序列初态无关，直接排除。初始序列基本有序时，插入排序比较次数较少。本题中，插入排序仅需比较 n+4 次，而希尔排序和冒泡排序均远大于此。【知识模块】 排序二、综合题26 【正确答案】 算法的基本设计思想：冒泡排序的方法，先从上向下起泡，然后从下向上起泡，设置变量标记冒泡的上下界。算法的代码：VOid BubbleSOrt2(int a，int n)相邻两趟向相反方向起泡的冒泡排序算法int change=1；int 10W=0；int high=n-1； 冒泡的上下界while(10wai+1)int t
17、emp=ai；ai=ai+1;ai+1=temp；change=1； 有交换，修改标志 changehigh-； 修改上界for(i=high; ilow，i-) 从下向上起泡if(aiRkScore)k=j ;if(i !=k)swap(Ri，Rk) ； 与第 i 个记录交换 forfor(i=1; i=j) 左侧只有红色砾石，交换 rk和 ritemp=rk；rk=ri;ri=temp;i+；else 左侧已有红色和白色砾石，先交换白色砾石到位temp=rj；rj=ri;ri=temp;j+;temp=rk; 再交换 rk和 ri，使红色砾石入位rk=ri;ri=temp；i+；if(rkkey=2)if(ik 为止。算法片段如下：int i=1，j=1，k=n；while(j=k)if(rj=1) 当前元素是红色temp=ri；ri=rj；rj=temp；i+；j+；else if(rJ=2)j+； 当前元素是白色else if(rj=3) 当前元素是蓝色temp=rj；rj=rk；rk=temp;k-；对比两种算法，可以看出，正确选择变量(指针)的重要性。【知识模块】 排序
