1、排序模拟试卷 4 及答案与解析一、单项选择题1 一次快速排序算法中，空白处应该填入的内容是( )。int Partition(Elem R，int low，int high)*交换记录子序列 R1owhigh中的记录，使枢轴记录到位，并返回其所在位置，此时，在它之前(后) 的记录均不大(小) 于它*pivotkey=R10wkey； 用子表的第一个记录作枢轴记录while(1owhigh) 从表的两端交替地向中间扫描while(1owhigh&Rhigh key =pivotkey)_(1)_；R1owHRhigh； 将比枢轴记录小的记录交换到低端while(1owhigh&R1owkey=p
2、ivotkey)_(2)_；R1owHRhigh；将比枢轴记录大的记录交换到高端return low； 返回枢轴所在位置（A）+high，一一 low（B） +low，一一 high（C）一一 high，+low（D）一一 low，+high2 快速排序算法采用了( )算法。（A）动态规划（B）递归（C）二分法（D）优先级3 在理想的情况下，快速排序算法的时间复杂度为( )。（A）O(1)（B） O(n)（C） O(nlog2n)（D）O(1og 2n)4 最坏情况下，快速排序算法的空间复杂度为( )。（A）O(1)（B） O(n)（C） O(nlog2n)（D）O(1og 2n)5 快速排序
3、的时间效率为( )。（A）O(n)（B） O(n2)（C） O(nlog2n)（D）O(10g 2n)6 一次快速排序的时间复杂度为( )。（A）O(n)（B） O(n2)（C） O(n1og2n)（D）O(1og 2n)7 最坏情况下，快速排序算法的时间复杂度为( )。（A）O(n)（B） O(n2)（C） O(n1og2n)（D）O(1og 2n)8 对下列 4 个序列用快速排序方法进行排序，以序列的第 1 个元素为基准进行划分。在第 1 趟划分过程中，元素移动次数最多的是( )。（A）70，75，82，90，23，16，10，68（B） 70，75，68，23，10，16，90，82（C
4、） 82，75，70，16，10，90，68，23（D）23，10，16，70，82，75，68，909 快速排序最不利于发挥其长处的情况是( )。（A）待排序的数据中含有多个相同值（B）待排序的数据已基本有序（C）待排序的数据量太大（D）被排序的数据数量为奇数10 下列关于堆排序特点的说法不正确的是( )。（A）堆顶元素是整个序列中最大(或最小)的元素（B）堆排序按关键码建成堆（C）对应的这棵完全二叉树所有分支结点的值均不小于(或不大于)其子女的值（D）每棵子树内部没有顺序11 堆排序的空间复杂度为( )。（A）O(1)（B） O(n)（C） O(nlogzn)（D）O(1og 2n)12
5、堆排序的平均时间复杂度为( )。（A）O(n)（B） O(n2)（C） O(nlog2n)（D）O(1og 2n)13 下列( ) 是一个堆。（A）1975，34，26，97，56（B） 97，26，34，75，19，56（C） 19，56，26，97，34，75（D）19，34，26，97，56，7514 下列序列中，满足堆定义的是( )。（A）100，86，48，73，35，39，42，57，66，21（B） 12，70，33，65，24，56，48，92，86，33（C） 103，97，56，38，66，23，42，12，30，52，6，26（D）5，56，20，23，40，38，29，
6、61，36，76， 28，10015 在含有 n 个关键字的大顶堆中，关键字最小的记录有可能存储在( )位置上。（A）n2（B） n21（C） 1（D）n2+216 待排序列中有 n 个元素，利用二路归并排序算法，需要两两合并的次数为( )。（A）L1og 2n（B） Lnlog2n（C） log2n（D）nlog 2n17 二路归并排序的空间复杂度为( )。（A）O(1)（B） O(n)（C） O(nlog2n)（D）O(1og 2n)18 二路归并排序的时间复杂度为( )。（A）O(1)（B） O(n)（C） O(nlog2n)（D）O(1og 2n)19 一组记录的关键字为25，50，1
7、5，35，80，85，20，40，36，70 ，其中含有5 个长度为 2 的有序表，用归并排序方法对该序列进行一趟归并后的结果是( )。（A）15，25，35，50，20，40，80，85，36，70（B） 15，25，35，50，80，20，85，40，70，36（C） 15，25，50，35，80，85，20，36，40，70（D）15，25，35，50，80，20，36，40，70，8520 以下排序方法中，不需要进行关键字的比较的是( )。（A）快速排序（B）归并排序（C）基数排序（D）堆排序21 基数排序一趟排序使用的辅助空间为 r，那么完成整个基数排序的时间复杂度为( )。（A）O
8、(rlogr)（B） O(10gr)（C） O(r)（D）O(r+)22 基数排序是一种( ) 的排序算法。（A）稳定（B）不稳定（C）跳跃（D）不能确定23 外部排序是指( ) 。（A）在 CPU 外部的排序（B）只在外存上的排序（C）只在内存上的排序（D）外部排序在内、外存进行交换的排序24 多路平衡归并排序包括的阶段是( )。（A）生成初始归并段（B）多趟归并排序（C）一趟归并排序（D）A 和 B25 如果某个文件经内排序得到 80 个初始归并段，若使用多路平衡归并执行 3 趟完成排序，那么应取得归并路数至少应为( )。（A）3（B） 4（C） 5（D）626 在所有排序算法中，最快的算
9、法平均时间复杂度为( )。（A）O(n)（B） O(n2)（C） O(nlog2n)（D）O(1og 2n)27 时间复杂度为 D(nlogn)的排序方法有( ) 。（A）快速排序、堆排序、简单选择排序（B）快速排序、归并排序、简单选择排序（C）快速排序、归并排序、堆排序（D）快速排序、堆排序、冒泡排序28 时间复杂度为 O(n2)的排序算法中，最好的是 ( )。（A）直接插入排序（B）冒泡排序（C）简单选择排序（D）堆排序29 在待排序列基本有序的情况下，直接插入排序的时间复杂度为( )。（A）O(n)（B） O(n2)（C） O(nlog2n)（D）D(1og 2n)30 在待排序列基本有
10、序的情况下，快速排序的时间复杂度为( )。（A）O(n)（B） O(n2)（C） O(nlog2n)（D）D(1og 2n)31 下列几种排序算法中，空间复杂度最大的是( )。（A）直接插入排序（B）冒泡排序（C）归并排序（D）快速排序32 下列几种排序算法中，耗费辅助空间最多的是( )。（A）直接插入排序（B）冒泡排序（C）简单选择（D）快速排序33 下面属于稳定算法的是( )。（A）快速排序（B）简单选择排序（C）冒泡排序（D）希尔排序二、综合题34 某个待排序的序列是一个可变长度的正整数序列，存储于正整数数组中。请改写快速排序算法，对这个正整数序列进行排序。34 关于堆的一些问题：35
11、堆的存储表示是顺序的，还是链接的?36 设有一个最小堆，即堆中任意结点的关键字均大于它的左孩子和右孩子的关键字。其具有最大值的元素可能在什么地方?37 对 n 个元素进行初始建堆的过程中，最多做多少次数据比较(不用大 O 表示法)?排序模拟试卷 4 答案与解析一、单项选择题1 【正确答案】 C【试题解析】 在快速排序算法中，如果高端比枢纽值小，那么就将高端和低端交换；如果低端值比枢纽值大，那么就将高端和低端交换。【知识模块】 排序2 【正确答案】 B【试题解析】 快速排序是递归的，每层递归调用时的指针和参数均要用栈来存放。【知识模块】 排序3 【正确答案】 D【试题解析】 存储开销在理想情况下
12、为 D(1og2n)，即树的高度。【知识模块】 排序4 【正确答案】 B【试题解析】 在最坏情况下，快速排序的存储开销为 O(n)。【知识模块】 排序5 【正确答案】 C【试题解析】 在 n 个记录的待排序列中，一次划分需要约 n 次关键码比较，时效为 O(n)。设 t(n)为对 n 个记录的待排序列进行快速排序所需时间。理想情况下：每次划分，正好将分成两个等长的子序列，则 O(n1og2n)。【知识模块】 排序6 【正确答案】 A【试题解析】 在 n 个记录的待排序列中，一次划分需要约 n 次关键码比较，时效为 O(n)，设 T(n)为对 n 个记录的待排序列进行快速排序所需时间。【知识模块
13、】 排序7 【正确答案】 B【试题解析】 最坏情况下：即每次划分，只得到一个子序列，时效为 O(n2)。【知识模块】 排序8 【正确答案】 A【试题解析】 快速排序第一趟划分的方法：将第 1 个元素放在最终排好序列的最终位置上，则在这个位置右边小于该元素值的元素都移到其左边，则在这个位置左边小于该元素值的元素都移到其右边。故选 A。【知识模块】 排序9 【正确答案】 B【试题解析】 快速排序等改进的排序方法均适用于待排序数据量较大的情况，各种排序方法对待排序的数据中是否含有多个相同值、被排序的数据数量为奇数或偶数都没有影响。【知识模块】 排序10 【正确答案】 D【试题解析】 若将排序表按关键
14、码建成堆，堆顶元素就是选择出的最大元素(或最小)，这样就得到 n 个元素中的第一个的元素。然后，再对剩下的 n 一 1 个元素建成堆，得到 n 个元素中关键码次大 (或次小)的元素。以此类推，如此反复，直到进行 n 一 1 次后，排序结束，便得到一个按关键码有序的序列，称这个过程为堆排序。如果该序列是一个堆，则对应的这棵完全二叉树的特点是：所有分支结点的值均不小于(或不大于) 其子女的值，即每棵子树根结点的值是最大(或最小)的。堆的特点：堆顶元素是整个序列中最大(或最小)的元素。【知识模块】 排序11 【正确答案】 A【试题解析】 堆排序仅用了一个辅助单元，空间复杂度为 O(1)。【知识模块】
15、 排序12 【正确答案】 C【试题解析】 堆排序的平均和最坏时间复杂度均为 O(nlogn)。【知识模块】 排序13 【正确答案】 D【试题解析】 完全二叉树中所有非终端结点的值均不大于(或不小于)其左、右孩子结点的值，则此序列可称为堆。据此，可画出二叉树，如下图所示： 得出答案为 D。【知识模块】 排序14 【正确答案】 A【试题解析】 依据堆的定义，将选项中的每个数列分别看成是一棵完全二叉树，则堆或是空树或是满足下列特性的完全二叉树：其左、右子树分别是堆，并且当左右子树不空时，根结点的值小于(或大于)左右子树根结点的值。【知识模块】 排序15 【正确答案】 D【试题解析】 大顶堆中关键字最
16、小的记录只能在叶子结点上，不可能在小于或等于 n2 的结点上。【知识模块】 排序16 【正确答案】 A【试题解析】 只有 1 个元素的表总是有序的，所以将排序表 R1，n看作是n 个长度为 len=1 的有序子表，对相邻的两个有序子表两两合并到1，n ，使之生成表长 len=2 的有序表；再进行两两合并到 R1，n 中，直到最后生成表长 len=n 的有序表。这个过程需要 L1og2n趟。【知识模块】 排序17 【正确答案】 B【试题解析】 二路归并排序需要一个与表等长的辅助元素数组空间，所以空间复杂度为 O(n)。【知识模块】 排序18 【正确答案】 C【试题解析】 对 n 个元素的表，将这
17、 n 个元素看作叶结点，若将两两归并生成的子表看作它们的父结点，则归并过程对应由叶向根生成一棵二叉树的过程。所以归并趟数约等于二叉树的高度一 1，即 log2n，每趟归并需移动记录 n 次，故时间复杂度为 O(nlog2n)。【知识模块】 排序19 【正确答案】 A【试题解析】 对 5 个长度为 2 的有序表一趟归并后得到两个长度为 4 的有序表和一个长度为 2 的有序表。故选 A。【知识模块】 排序20 【正确答案】 C【试题解析】 基数排序是通过分配和收集实现的，不需要进行关键字的比较，而其他几种排序方法都是通过关键字的比较实现的。【知识模块】 排序21 【正确答案】 C【试题解析】 每次
18、基数排序重复使用这个辅助空间，所以空间复杂度为 O(r)。【知识模块】 排序22 【正确答案】 A【试题解析】 基数排序是稳定的算法。【知识模块】 排序23 【正确答案】 D【试题解析】 在排序过程中，由于信息量巨大，无法一次调入内存，只能驻留在辅存上。特点为内存运行时间短，内、外存进行交换需要时间长，减少 IO 时间成为主要矛盾。【知识模块】 排序24 【正确答案】 D【试题解析】 多路平衡归并排序由两个相对独立的阶段组成：生成初始归并段和多趟归并排序。生成初始归并段阶段根据内存工作区的大小，将有 n 个记录的磁盘文件分批输入内存，采用有效的内排序方法分别进行排序，生成若干个有序的子文件，即
19、初始归并段。多趟归并排序阶段采用多路归并方法将这些归并段逐趟归并，最后归并成一个有序文件。【知识模块】 排序25 【正确答案】 C【试题解析】 设归并路数为 m，初始归并段个数 r=80，归并的趟数为 3，那么m380 ，m5。【知识模块】 排序26 【正确答案】 C【试题解析】 在所有排序算法中，最快的算法平均时间复杂度也要达到 O(nlog2n)。【知识模块】 排序27 【正确答案】 C【试题解析】 时间复杂度为 D(nlogn)的方法有：快速排序、堆排序和归并排序，其中以快速排序为最好。【知识模块】 排序28 【正确答案】 A【试题解析】 时间复杂度为 D(n2)的方法有：直接插入排序、
20、冒泡排序和简单选择排序，其中以直接插入为最好，特别是那些对关键字近似有序的记录序列尤为如此。【知识模块】 排序29 【正确答案】 A【试题解析】 当待排记录序列按关键字顺序有序时，直接插入排序和冒泡排序能达到 O(n)的时间复杂度。【知识模块】 排序30 【正确答案】 B【试题解析】 对于快速排序而言，这是最不好的情况，此时的时间性能变为 O(n2)，因此是应该尽量避免的情况。【知识模块】 排序31 【正确答案】 C【试题解析】 归并排序所需辅助空间最多，其空间复杂度为 O(n)。【知识模块】 排序32 【正确答案】 D【试题解析】 快速排序为 O(1ogn)，为栈所需的辅助空间，其余都为 O
21、(1)。【知识模块】 排序33 【正确答案】 C【试题解析】 属于稳定的排序算法有：直接插入排序、冒泡排序、归并排序、基数排序。属于不稳定的排序算法有：简单选择排序、希尔排序、快速排序、堆排序。【知识模块】 排序二、综合题34 【正确答案】 Partition(RecType R，int 1，int h)一趟快速排序算法，枢轴记录到位，并返回其所在位置int i=1；j=h ；RO=Ri；x=Ri key ；while(ij)while(ij&Rjkey=x)j 一一；if(ij)Ri=Rj；while(ij&Ri key=x)i+ ；if(ij)Rj=Ri； while Ri =RO；return i； Partition【知识模块】 排序【知识模块】 排序35 【正确答案】 堆的存储是顺序的。【知识模块】 排序36 【正确答案】 最大值元素一定是叶子结点，在最下两层上。【知识模块】 排序37 【正确答案】 在建含有 n 个元素、深度为 h 的堆时，其比较次数不超过 4n，推导如下：由于第 i 层上的结点数至多是 2i 一 1，以它为根的二叉树的深度为 h 一 i+1，则调用 n2 次筛选算法时总共进行的关键字比较次数不超过下式之值。【知识模块】 排序
