1、计算机专业基础综合（排序）模拟试卷 4 及答案与解析一、单项选择题1-40 小题，每小题 2 分，共 80 分。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。1 采用简单选择排序，比较次数与移动次数分别为( )。（A）O(n)， O(log2n)（B） O(log2n)，O(n 2)（C） O(n2)，O(n)（D）O(nlog 2n)，O(n)2 就排序算法所用的辅助空间而言，堆排序、快速排序、归并排序的关系是( )。（A）堆排序快速排序归并排序（B）堆排序归并排序快速排序（C）堆排序归并排序快速排序（D）堆排序快速排序归并排序3 一组记录的关键码为(25，48，16，35，79
2、，82，23，40，36，72)，其中，含有5 个长度为 2 的有序表，按归并排序的方法对该序列进行一趟归并后的结果为( )。（A）16，25，35，48，23，40，79，82，36，72（B） 16，25，35，48，79，82，23，36，40，72（C） 16，25，48，35，79，82，23，36，40，72（D）16，25，35，48，79，23，36，40，72，824 已知 10 个数据元素为(54，28，16，34，73，62，95，60，26，43)，对该序列按从小到大排序，经过一趟冒泡排序后的序列为( )。（A）16，28，34，54，73，62，60，26，43，95
3、（B） 28，16，34，54，62，73，60，26，43，95（C） 28，16，34，54，62，60，73，26，43，95（D）16，28，34，54，62，60，73，26，43，955 用某种排序方法对线性表(25，84，21，47，15，27，68，35，20)进行排序时，元素序列的变化情况如下：(1)25，84， 21，47，15，27，68，35，20(2)20，15， 21，25，47，27，68，35，84(3)15，20， 21，25，35，27，47，68，84(4)15，20， 21，25，27，35，47，68，84其所采用的排序方法是( )。（A）直接选择排序
4、（B）希尔排序（C）归并排序（D）快速排序6 在对一组记录(50，40，95，20，15，70，60，45，80)进行直接插入排序时，当把第 7 个记录 60 插入到有序表时，为寻找插入位置需比较( )次。（A）1（B） 2（C） 3（D）47 将两个各有 N 个元素的有序表归并成一个有序表，其最少的比较次数是 ( )。（A）N（B） 2N-1（C） 2N（D）N-18 已知待排序的 n 个元素可分为 nk 个组，每个组包含 k 个元素，且任一组内的各元素均分别大于前一组内的所有元素和小于后一组内的所有元素，若采用基于比较的排序，其时间下界应为( )。（A）O(nlog 2n)（B） O(nl
5、og2k)（C） O(klog2n)（D）O(klog 2k)9 已知关键序列 5，8，12，19，28，20，15，22 是小根堆(最小堆)，插入关键字3，调整后得到的小根堆是( )。（A）3，5，12，8，28，20，15，22，19（B） 3，5，12，19，20，15，22，8，28（C） 3，8，12，5，20，15，22，28，19（D）3，12，5，8，28，20，15，22，1910 归并排序中，归并的趟数是( )。（A）O(n)（B） O(log2n)（C） O(nlog2n)（D）O(n 2)11 有一组数据(15，9，7，8，20，一 1，7，4)，用堆排序的筛选方法建立
6、的初始堆为( )。（A）一 1，4，8，9，20，7，15，7（B）一 1，7，15，7，4，8，20，9（C）一 1，4，7，8，20，15，7，9（D）A、B、C 均不对12 基于比较方法的 n 个数据的内部排序，最坏情况下的时间复杂度能达到的最好下界是( ) 。（A）O(nlog 2n)（B） O(log2n)（C） O(n)（D）O(n 2)13 以下排序方法中，稳定的排序方法是( )。（A）直接插入排序（B）直接选择排序（C）堆排序（D）基数排序14 在对一组记录(50，40，95，20，15，70，60，45，80)进行希尔排序时，假定d0=9， d1=4， d2=2，d 3=1，
7、则第二趟排序结束后前 4 条记录为( )。（A）(50 ，20，15，70)（B） (60，45，80，50)（C） (15，20，50，40)（D）(15 ，20，80，70)15 在归并排序中，若待排序记录的个数为 20，则共需要进行( )趟归并，在第三趟归并中，是把长度为( )的有序表归并为长度为( )的有序表。（A）5，4，8（B） 6，3，9（C） 7，4，3（D）3，8，2二、综合应用题41-47 小题，共 70 分。16 已知关键字序列(K 1，K 2，K 3，K n-1)是大根堆。试写出一算法将(K1，K 2，K 3，K n+1，K n)调整为大根堆，并利用调整算法写一个建大根
8、堆的算法。17 最小最大堆(min max Heap)是一种特定的堆，其最小层和最大层交替出现，根总是处于最小层。最小最大堆中的任一结点的关键字值总是在以它为根的子树中的所有元素中最小(或最大) 。如图所示为一最小最大堆。 (1)画出在图中插入关键字为 5的结点后的最小最大堆。 (2)画出在图中插入关键字为 80 的结点后的最小最大堆。 (3)编写一算法实现最小最大堆的插入功能。假定最小最大堆存放在数组中，关键字为整数。18 输入 N 个只含一位数字的整数，试用基数排序的方法，对这 N 个数排序。19 试构造对 5 个元素进行排序，最多只用 7 次比较的算法。20 设有 15 000 个无序的
9、元素，希望用最快的速度挑选出其中前 10 个最大的元素。在快速排序、堆排序、归并排序、基数排序和希尔排序中，宜采用哪种方法并说明理由?21 对一个具有 7 个记录的文件进行快速排序，请问：(1)在最好情况下需进行多少次比较? 说明理由，并给出相应实例。(2)在最坏情况下需进行多少次比较? 为什么?请给出相应实例。22 判断下列序列是否为堆，若不是堆，则把它们调整为堆。(1) (100，85，95，75，80，60，82，40，20，10，65)(2) (100，95，85，82，80，75，65，60，40，20，10)(3) (100，85，40，75，80，60，65，95，82，10，2
10、0)(4) (10，20，40，60，65，75，80，82，85，95，100)23 将十进制的关键字用二进制数表示，对基数排序所需的时间和附设空间分别有什么影响?各是多少 ?24 写出快速排序的非递归算法。25 试设计一算法，使得在尽可能少的时间内重排数组，将所有取负值的关键字放在所有取非负值的关键字之前，并分析算法的时间复杂度。26 写一个 Heaplnsert(R，key) 算法，将关键字插入到堆 R 中，并保证插入后 R 仍是堆。请分析算法的时间复杂度。提示：将 key 先插入 R 中已有元素的尾部(即原堆的长度加 1 的位置，插入后堆的长度加 1)，然后自下往上调整，使插入的关键字
11、满足堆性质。27 写一个建立堆的算法：从空堆开始，依次读入元素，调用上题中堆插入算法将其插入堆中。计算机专业基础综合（排序）模拟试卷 4 答案与解析一、单项选择题1-40 小题，每小题 2 分，共 80 分。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。1 【正确答案】 C【试题解析】 简单选择排序的关键字比较次数 KCN 与对象的初始排列无关。第 i趟选择具有最小关键字对象所需的比较次数总是 n 一 i 一 1 次(此处假定整个待排序对象序列有 n 个对象) 。因此，总的关键字比较次数为： 最坏情况是每一趟都要进行交换，总的对象移动次数为 RMN=3(n1)。【知识模块】 排序2
12、 【正确答案】 A【试题解析】 此题考查的知识点为排序的空间复杂性。堆排序辅助空间为 O(1)，快速排序为 O(log2n)，归并排序为 O(n)。应选 A。【知识模块】 排序3 【正确答案】 A【试题解析】 对于(25，48，16，35，79，82，23，40，36，72)，(25，48)和(16，35)归并的结果为 (16，25，35，48) 。(79，82) 和(23 ，40)归并后的结果为(23，40 ，79，82) ，余下的两个记录不归并，所以一趟归并后的结果为(16，25 ，35，48，23，40，79，82，36，72)，本题答案为 A。【知识模块】 排序4 【正确答案】 B【试
13、题解析】 冒泡排序每趟经过比较、交换，从无序区中产生一个最大的元素，所以选 B。【知识模块】 排序5 【正确答案】 A【试题解析】 可以看到，每趟从无序区中找出一个最大的元素定位，所以答案为A。【知识模块】 排序6 【正确答案】 C【试题解析】 第 6 趟的结果为(15，20，40，50，70，95，60，45，80)，此时插入 60，要与 95、70 和 50 进行比较，共比较 3 次，本题答案为 C。【知识模块】 排序7 【正确答案】 A【试题解析】 此题考查的知识点是归并排序思想。当第一个有序表中所有的元素都小于第二个表中元素，或者都大于第二个表中元素时，比较次数最少为 N。【知识模块】
14、 排序8 【正确答案】 B【试题解析】 此题考查的知识点是分块排序的思想。因组与组之间已有序，故将nk 个组分别排序即可，基于比较的排序方法每组的时间下界为 O(klog2k)。可以用二叉树分治形式描述，最好的情况是树的高度为 log2k。全部时间下界为O(nlog2k)。应选 B。【知识模块】 排序9 【正确答案】 A【试题解析】 根据题目中给出的序列建立一个堆，并将其调整为小根堆，其过程如下： 可以得出调整后的小根堆为 3，5，12，8，28，20，15，22，19。【知识模块】 排序10 【正确答案】 B【试题解析】 此题考查的知识点是归并排序。第 1 遍归并的子序列长度为 20，第2
15、遍为 21，第 i 遍为 2i-1，所以由 2i-1n 知，对 n 个记录的数据集合，总共需要归并 log2n 次。应选 B。【知识模块】 排序11 【正确答案】 C【试题解析】 此题考查的知识点是堆排序。应选 C。【知识模块】 排序12 【正确答案】 A【试题解析】 此题考查的知识点是各类排序的效率。理论上可以证明，对于基于关键字之间比较的分类，无论用什么方法都至少需要进行 log2(n!)次比较。 由Stirling 公式可知，log 2(n!)nlog2n 一 144n+O(log 2n)。所以基于关键字比较的分类时间的下界是 O(nlog2n)。因此不存在时间复杂性低于此下界的基于关键
16、字比较的分类。应选 A。【知识模块】 排序13 【正确答案】 A【试题解析】 下表为各种排序方法的性能比较。由表可知，本题答案为 A。 【知识模块】 排序14 【正确答案】 C【试题解析】 t=3，d 0=9， d1=4，d 2=2，d 3=1，第 1 趟(d 1=4)后的结果为(15，40 ，60，20，50，70，95，45，80)，第 2 趟(以=2) 后的结果为(15，20 ，50，40，60，45，80，70，95)，本题答案为(15，20，50，40)。【知识模块】 排序15 【正确答案】 A【试题解析】 n=20，共需进行log 2n=5 趟归并，第 1 趟归并后成为 10 个有
17、序表，第 2 趟归并后成为 5 个有序表(每个长度为 4)，第 3 趟归并将长度为 4 个的有序表归并为长度为 8 的有序表，本题答案为：5，4，8。【知识模块】 排序二、综合应用题41-47 小题，共 70 分。16 【正确答案】 void sift(RecType R，int n) 把 Rn调成大堆int j=n； R0=Rj；for(i=n2；i=1；i=i2)if(R0keyRikey)Rj=Ri ；j=i；else break：Rj=R0；void HeapBuilder(RecType R，int n)for(i=2；iRi) Ri=Rj；i=j；j=i4； 调小堆 Ri=R0；
18、else 插入元素大于双亲，调大堆 i=n；j=i 4； while(j0&RJRi key) 插入元素大于双亲，先与双亲交换，然后调大堆 Rj=Ri ； j=i4； while(j0&Rj0&RjRi) Ri=Rj；i=j；j=i 4； Ri=R0 ； 【知识模块】 排序18 【正确答案】 typedef structint key；int next；SLRecType；SLRecType RN+1；typedef structint f，e；SLQueue；SLQueue B10；int Radixsort(SLReeType R，int n) 设备关键字已输入到 R 数组中for(i=1
19、；i0) 栈非空，则取出一个子文件进行划分low=stacktoplow；high=stacktophigh；top 一一； 出栈i=low；j=high ；temp=Ri；dowhile(itempkey)j 一一；if(i=0)j 一一； 从右向左找负数while(i0) 调整为堆 if(RRecikey 2Rlen，调整是自底向上查找，最多查找到树根，所以时间复杂度为 O(10g2R1en)。【知识模块】 排序27 【正确答案】 建立堆的算法如下：void BuildHeap(SeqList R，KeyType An) 类型定义int i；R1en=0： 初始化for(i=0；in ；i+)HeapInsert(R，Ai)；【知识模块】 排序
