计算机专业基础综合数据结构（排序）模拟试卷1
单选题
1.下面给出的4种排序方法中，( )排序法是不稳定性排序法。(D)
A. 插入
B. 冒泡
C. 二路归并
D. 堆
解析：此题考查的知识点是排序算法的稳定性问题。如果待排序的文件中，存在多个关键字相同的记录，经过排序后这些具有相同关键字的记录之间的相对次序保持不变，则称这种排序是稳定的排序：反之，若具有相同关键字的记录之间的相对次序发生变化，则称这种排序是不稳定的排序。是否稳定与算法有关，相邻数据比较的算法是稳定的，不相邻数据比较会出现不稳定。选项A、B、C都是相邻元素比较，是稳定的。所以选D。
2.下列内部排序算法中，其比较次数(或交换次数)与序列初态无关的算法是( )。(C)
A. 快速排序
B. 直接插入排序
C. 二路归并排序
D. 冒泡排序
解析：此题考查的知识点是各类排序算法的思想。
冒泡排序方法就是自底向上检查这个序列，若两个相邻的元素的顺序不对，则交换。直到所有元素处理完为止。与序列初态有关，D错。
直接插入排序思想是假设待排序的记录存放在数组R[n+1]中，排序过程中的某一时刻，R被分成两个子区间[R[1]，R[i一1]]和[R[i]，R[n]]，其中，前一个子区间是已排好序的有序区；后一个子区间是当前未排序的无序区。直接插入排序的基本操作是将当前无序区的第i个记录R[i]插入到有序区中的适当位置，使得R[1]到R[i]变为新的有序区。首先比较R[i]和R[i—1]，如果R[i一1]≤R[i]，则R[1．．i]已排好序，第i遍处理就结束了；否则交换R[i]与R[i一1]的位置，继续比较R[i—1]和R[i一2]，直到找到某一个位置j(1≤j≤i一1)使得R[j]≤R[j+1]时为止。与序列初态有关，B错。
快速排序是通过基准元素v把表(文件，数据集合)划分成左、右两部分，使得左边的各记录的关键字都小于v；右边的各记录的关键字都大于等于v；重复该过程直到排好序。与序列初态有关，A错。
二路归并是首先把每个记录看成是一个有序序列，共n个，将它们两两合并成[n／2]个分类序列，每个序列长度为2(当n为奇数时，最后一个序列长度为1)；对[n／2]个分类序列，再两两归并在一起；如此进行，直到归并成一个长度为n的分类序列为止。与序列初态无关，所以选C。
3.下列内部排序算法中，在初始序列已基本有序(除去n个元素中的某k个元素后即呈有序，k＜＜n)的情况下，排序效率最高的算法是( )。(C)
A. 冒泡排序
B. 堆排序
C. 直接插入排序
D. 二路归并排序
解析：此题考查的知识点是各类排序算法的效率。起泡排序比较n(n一1)／2次，没有交换次数；堆排序一次比较log2n次，共需要n轮；直接插入排序比较n—1次，没有交换；二路归并排序一次比较log2n次，共需要n轮。综上，应选C。
4.下列排序算法中，( )每一趟都能选出一个元素放在最终位置上，并且是不稳定的。(C)
A. 冒泡排序
B. 希尔排序
C. 简单选择排序
D. 直接插入排序
解析：本题考查各种内部排序算法的比较，考生一定要熟记下面这张表格。
5.下列排序方法中，时间复杂性不受数据初始状态影响，恒为O(nlog2n)的是( )。(A)
A. 堆排序
B. 冒泡排序
C. 直接选择排序
D. 快速排序
解析：由这些排序方法的特点可知本题答案为A。
6.下列排序算法中，某一趟结束后未必能选出一个元素放在其最终位置上的是( )。(C)
A. 选择排序
B. 冒泡排序
C. 归并排序
D. 堆排序
解析：此题考查的知识点是各类排序算法的思想。应选c。
7.下列排序算法中，在每一趟都能选出一个元素放到其最终位置上，并且其时间性能受数据初始特性影响的是( )。(A)
A. 直接插入排序
B. 归并排序
C. 直接选择排序
D. 堆排序
解析：此题考查的知识点是各类排序算法的思想。应选A。
对初始状态为递增序列的表按递增顺序排序，最省时间的是( (1) )算法，最费时间的是( (2) )算法。
8. (1)(C)
A. 堆排序
B. 快速排序
C. 插入排序
D. 归并排序
解析：
9. (2)(B)
A. 堆排序
B. 快速排序
C. 插入排序
D. 归并排序
解析：此题考查的知识点是各类排序算法的思想。应选C，B。
10.如果只想得到1 000个元素组成的序列中第5个最小元素之前的部分排序的序列，用( )方法最快。(D)
A. 冒泡排序
B. 快速排序
C. 简单选择排序
D. 堆排序
解析：此题考查的知识点是各类排序算法的思想。冒泡排序和简单选择排序每次要比较n一i次，快速排序结束后才能得到结果，堆排序可以在选择5次后得到结果，每次比较元素次数为log2n。所以应选D。
11.数据表A中有10 000个元素，如果仅要求求出其中最大的10个元素，则采用( )方法最节省时间。(A)
A. 堆排序
B. 希尔排序
C. 快速排序
D. 直接选择排序
解析：只有堆排序每次输出一个堆顶元素(即最大或最小值的元素)，然后对堆再进行调整，保证堆顶元素总是当前剩下元素的最大或最小的，本题答案为A。
12.若对序列(tang，deng，an，wang，shi，bai，fang，liu)采用简单选择排序法按字典顺序进行排序，下面给出的四个序列中，第三趟的结果是( )。(B)
A. an ，bai，deng，
本文档预览：3000字符，共11369字符，源文件无水印，下载后包含无答案版和有答案版，查看完整word版点下载
