计算机专业基础综合数据结构（排序）模拟试卷2
单选题
1.采用简单选择排序，比较次数与移动次数分别为( )。(C)
A. O(n)，O(log2n)
B. O(log2n)，O(n2)
C. O(n2)，O(n)
D. O(nlog2n)，O(n)
解析：简单选择排序的关键字比较次数KCN与对象的初始排列无关。第i趟选择具有最小关键字对象所需的比较次数总是n—i—1次(此处假定整个待排序对象序列有n个对象)。因此，总的关键字比较次数为：
2.就排序算法所用的辅助空间而言，堆排序、快速排序、归并排序的关系是( )。(A)
A. 堆排序＜快速排序＜归并排序
B. 堆排序＜归并排序＜快速排序
C. 堆排序＞归并排序＞快速排序
D. 堆排序＞快速排序＞归并排序
解析：此题考查的知识点为排序的空间复杂性。堆排序辅助空间为O(1)，快速排序为O(log2n)，归并排序为O(n)。应选A。
3.一组记录的关键码为(25，48，16，35，79，82，23，40，36，72)，其中，含有5个长度为2的有序表，按归并排序的方法对该序列进行一趟归并后的结果为( )。(A)
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，82
解析：对于(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.已知10个数据元素为(54，28，16，34，73，62，95，60，26，43)，对该序列按从小到大排序，经过一趟冒泡排序后的序列为( )。(B)
A. 16，28，34，54，73，62，60，26，43，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，95
解析：冒泡排序每趟经过比较、交换，从无序区中产生一个最大的元素，所以选B。
5.用某种排序方法对线性表(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)
A. 直接选择排序
B. 希尔排序
C. 归并排序
D. 快速排序
解析：可以看到，每趟从无序区中找出一个最大的元素定位，所以答案为A。
6.在对一组记录(50，40，95，20，15，70，60，45，80)进行直接插入排序时，当把第7个记录60插入到有序表时，为寻找插入位置需比较( )次。(C)
A. 1
B. 2
C. 3
D. 4
解析：第6趟的结果为(15，20，40，50，70，95，60，45，80)，此时插入60，要与95、70和50进行比较，共比较3次，本题答案为C。
7.将两个各有N个元素的有序表归并成一个有序表，其最少的比较次数是( )。(A)
A. N
B. 2N一1
C. 2N
D. N一1
解析：此题考查的知识点是归并排序思想。当第一个有序表中所有的元素都小于第二个表中元素，或者都大于第二个表中元素时，比较次数最少为N。
8.已知待排序的n个元素可分为n／k个组，每个组包含k个元素，且任一组内的各元素均分别大于前一组内的所有元素和小于后一组内的所有元素，若采用基于比较的排序，其时间下界应为( )。(B)
A. O(nlog2n)
B. O(nlog2k)
C. O(klog2n)
D. O(klog2k)
解析：此题考查的知识点是分块排序的思想。因组与组之间已有序，故将n／k个组分别排序即可，基于比较的排序方法每组的时间下界为O(klog2k)。可以用二叉树分治形式描述，最好的情况是树的高度为log2k。全部时间下界为O(nlog2k)。应选B。
9.已知关键序列5，8，12，19，28，20，15，22是小根堆(最小堆)，插入关键字3，调整后得到的小根堆是( )。(A)
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，19
解析：根据题目中给出的序列建立一个堆，并将其调整为小根堆，其过程如下：
10.归并排序中，归并的趟数是( )。(B)
A. O(n)
B. O(l
本文档预览：3000字符，共12796字符，源文件无水印，下载后包含无答案版和有答案版，查看完整word版点下载
