1、计算机专业基础综合数据结构（排序）模拟试卷 2（无答案）一、单项选择题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，
2、79，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，
3、95（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
5、） O(nlog2k)（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）D(n 2)13 以下排序方法中，稳定的排序方法是( )。（A）直接插入排序（B）直接选择排序（C）堆排序（D）基数排序14 在对一组记录(50，40，95，20，15，70，60，45，80)进行希尔排序时，假定d0=9， d1=4， d2=2，
7、d 3=1，则第二趟排序结束后前 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 设有 15 000 个无序的元素，希望用最快的速度挑选出其中前 10 个最大的元
9、素。在快速排序、堆排序、归并排序、基数排序和希尔排序中，宜采用哪种方法并说明理由?20 对一个具有 7 个记录的文件进行快速排序，请问：(1)在最好情况下需进行多少次比较? 说明理由，并给出相应实例。(2)在最坏情况下需进行多少次比较? 为什么?请给出相应实例。21 判断下列序列是否为堆，若不是堆，则把它们调整为堆。(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，20)(4)(10，20，40，60，65，75，80，82
10、，85，95，100)22 将十进制的关键字用二进制数表示，对基数排序所需的时间和附设空间分别有什么影响?各是多少 ?23 写出快速排序的非递归算法。24 试设计一算法，使得在尽可能少的时间内重排数组，将所有取负值的关键字放在所有取非负值的关键字之前，并分析算法的时间复杂度。25 写一个 HeapInsen(R,key)算法，将关键字插入到堆 R 中，并保证插入后 R 仍是堆。请分析算法的时间复杂度。提示：将 key 先插入 R 中已有元素的尾部(即原堆的长度加 1 的位置，插入后堆的长度加 1)，然后自下往上调整，使插入的关键字满足堆性质。26 写一个建立堆的算法：从空堆开始，依次读入元素，调用上题中堆插入算法将其插入堆中。
