吉林省专升本考试数据结构分章习题及参考答案———选择题
（第八章）
1、若数据元素序列{11,12,13,78,9,23,4,5}是采用下列排序方法之一得到的第二趟排序后的结果，则该排序算法只能是( )
A、冒泡排序
B、插入排序
C、选择排序
D、归并排序
2、若将两个各有n个元素的有序表归并成一个有序表，则最少比较次数是()。
A、 n
B、 2*n-1
C、 2n
D、 n-1
3、已知数据表中每个元素距其最终位置不远，则采用（）方法最节省时间
A、堆排序
B、插入排序
C、快速排序
D、直接选择排序
4、下列排序算法中，（）算法可能会出现下面情况：在后一趟开始之前，所有元素都不在其终的位置上。
A、堆排序
B、冒泡排序
C、快速排序
D、插入排序
5、下述几种排序方法中，要求内存量最大的是()。
A、插入排序
B、快速排序
C、归并排序
D、选择排序
6、就排序算法所用的辅助空间而言，堆排序，快速排序，归并排序的关系是（）
A、堆排序<快速排序<归并排序
B、堆排序<归并排序<快速排序
C、堆排序>归并排序>快速排序
D、堆排序>快速排序>归并排序
7、快速排序方法在( )情况下最不利于发挥其长处。
A、要排序的数据量太大
B、要排序的数据中含有多个相同值
C、要排序的数据已基本有序
D、要排序的数据个数为奇数
8、对关键字由大到小进行冒泡排序，在下列（）情况下比较的次数最多。
A、从小到大排序
B、从大到小排序
C、元素无序
D、元素基本有序
9、对5个不同的数据元素进行直接插入排序，最多需要进行()次比较。
A、 8
B、 10
C、 15
D、 25
10、如果只想得到1000个元素组成的序列中第5个小元素之前的部分排序的序列，用（）方法快。
A、起泡排序
B、快速排列
C、堆排序
D、简单选择排序
11、设有1000个无序的元素，希望用最快的速度挑选出其中前十个最大的元素，在以下的排序方法中采用哪一种最好？()
A、快速排序
B、归并排序
C、堆排序
D、基数排序
12、下列排序算法中，（）可能会出现下面情况：在最后一趟开始之前，所有元素都不在最终位置上。
A、起泡排序
B、插入排序
C、快速排序
D、堆排序
13、对以下数据序列利用快速排序进行排序，速度最快的是（）
A、21，25，5，17，9，23，30
B、25，23，30，17，21，5，9
C、21，9，17，30，25，23，5
D、5，9，17，21，23，25，30
14、快速排序在下列( )情况下最易发挥其长处。
A、被排序的数据中含有多个相同排序码
B、被排序的数据已基本有序
C、被排序的数据完全无序
D、被排序的数据中的最大值和最小值相差悬殊
15、在含有n个关键字的小根堆（堆顶元素小）中，关键字最大的记录有可能存储在（）位置上。
A、⎣n/2⎦
B、⎣n/2⎦-1
C、1
D、⎣n/2⎦+2
16、堆排序是（）类排序.
A、插入
B、交换
C、归并
D、选择
17、下面给出的四种排序法中()排序法是不稳定性排序法。
A、插入
B、冒泡
C、二路归并
D、堆
18、若需在O(nlog2n)的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是（）。
A、快速排序
B、堆排序
C、归并排序
D、直接插入排序
19、对序列{15，9，7，8，20，-1，4}进行排序，经一趟排序后的排列为{9，15，7，8，20，-1，4}，则采用的是（）排序。
A、选择
B、堆
C、直接插入
D、冒泡
20、在所有排序方法中，关键字比较的次数与记录的初始排列次序无关的是( )。
A、希尔排序
B、起泡排序
C、插入排序
D、选择排序
21、对关键码序列{23，17，72，60，25，8，68，71，52}进行堆排序，输出两个最小关键码后的剩余堆是（）
A、{23，72，60，25，68，71，52}
B、{23，25，52，60，71，72，68}
C、{71，25，23，52，60，72，68}
D、{23，25，68，52，60，72，71}
22、对于关键字序列{46，58，15，45，90，18，10，62}，其快速排序第一趟的结果是()
A、 15 45 18 46 10 62 58 90
B、 10 15 18 45 46 58 62 90
C、 10 18 15 45 46 90 58 62
D、 15 10 18 45 46 62 58 90
23、冒泡排序是一种（）的排序。
A、插入
B、选择
C、交换
D、归并
24、当待排序序列基本有序或个数较小的情况下，最佳的内部排序方法是（）
A、直接插入排序
B、冒泡排序
C、简单选择排序
D、快速排序
25、有一组数据（15，9，7，8，20，-1，7，4）用快速排序的划分方法进行一趟划分后数据的排序为()（按递增序）。
A、下面的B，C，D都不对。
B、9，7，8，4，-1，7，15，20
C、20，15，8，9，7，-1，4，7
D、9，4，7，8，7，-1，15，20
26、对序列{15，9，7，8，20，-1，4，}用希尔排序方法排序，经一趟后序列变为{15，-l，4，8，20，9，7}则该次采用的增量是()
A、l
B、4
C、3
D、2
27、对长度为10的表作选择(简单选择)排序,共需比较()次关键字。
A、 45
B、 90
C、 55
D、 110
28、对初始状态为递增有序的序列进行排序，最费时间的是（）
A、堆排序
B、插入排序
C、快速排序
D、直接选择排序
29、下述排序方法中，时间性能与待排序记录的初始状态无关的有（）
A、插入排序和快速排序
B、归并排序和快速排序
C、选择排序和归并排序
D、插入排序和归并排序
30、分别以下列序列构造二叉排序树，与用其它三个序列所构造的结果不同的是()
A、（100，80，90，60，120，110，130）
B、（100，120，110，130，80，60，90）
C、（100，60，80，90，120，110，130）
D、(100，80，60，90，120，130，110)
31、就平均时间而言，（）最佳。
A、直接插入排序
B、冒泡排序
C、简单选择排序
D、快速排序
32、排序趟数与序列的原始状态(原始排列)有关的排序方法是()排序方法。
A、直接插入排序
B、简单选择排序
C、冒泡排序
D、快速排序
33、目前以比较为基础的内部排序方法中，其比较次数与待排序的记录的初始排列状态无关的是()。
A、插入排序
B、直接选择排序
C、快速排序
D、冒泡排序
34、在下列算法中，()算法可能出现下列情况：在最后一趟开始之前，所有的元素都不在其最终的位置上。
A、堆排序
B、冒泡排序
C、插入排序
D、快速排序
35、下列排序方法中，哪一个是稳定的排序方法？（）
A、直接选择排序
B、插入排序
C、希尔排序
D、快速排序
36、归并排序中，归并的趟数是()。
A、O（n）
B、O(logn)
C、O(nlogn)
D、O(n*n)
37、快速排序方法在（）情况下不利于发挥其长处。
A、要排序的数据量太大
B、要排序的数据中含有多个相同值
C、要排序的数据个数为奇数
D、要排序的数据已基本有序
38、下述几种排序方法中，要求内存最大的是( )
A、希尔排序
B、快速排序
C、归并排序
D、堆排序
39、对于下列关键字序列，不可能构成某二叉排序树中一条查找路径的序列是（）。
A、95, 22, 91, 24, 94, 71
B、92, 20, 91, 34, 88, 35
C、21, 89, 77, 29, 36, 38
D、12, 25, 71, 68, 33, 34
40、若用冒泡排序方法对序列{10,14,26,29,41,52}从大到小排序，需进行（）次比较。
A、3
B、10
C、15
D、25
41、下面给出的四种排序方法中，排序过程中的比较次数与序列的初始状态无关
的是。()
A、选择排序法
B、插入排序法
C、快速排序法
D、堆排序法
42、改进的冒泡排序在最好情况下时间复杂度为()
A、 O(1)
B、 O(nlog2n)
C、 O(n)
D、 O(n2)
43、希尔排序法属于哪一种类型的排序法()。
A、交换类排序
B、插入类排序
C、选择类排序
D、建堆排序法
44、下列排序算法中，( )不能保证每趟排序至少能将一个元素放到其最终的位置上。
A、希尔排序
B、快速排序
C、冒泡排序
D、堆排序
45、如果待排序序列中两个数据元素具有相同的值，在排序前后它们的相互位置发生颠倒，则称该排序算法是不稳定的。（）就是不稳定的排序方法。
A、起泡排序
B、归并排序
C、Shell排序
D、直接插入排序
46、设有5000个元素，希望用最快的速度挑选出前10个最大的元素，采用（）方法最好。
A、快速排序
B、堆排序
C、希尔排序
D、归并排序
47、为实现快速排序算法，待排序序列宜采用的存储方式是( )。
A、顺序存储
B、散列存储
C、链式存储
D、索引存储
48、数据序列（8，9，10，4，5，6，20，1，2）只能是下列排序算法中的()的两趟排序后的结果。
A、选择排序
B、冒泡排序
C、插入排序
D、堆排序
49、（）方法是从未排序序列中挑选元素，并将其放入已排序序列的一端。
A、归并排序
B、插入排序
C、快速排序
D、选择排序
50、下列排序算法中()不能保证每趟排序至少能将一个元素放到其终的位置上。
A、快速排序
B、shell排序
C、堆排序
D、冒泡排序
参考答案：
1.B
2.A
3.B
4.D
5.C
6.A
7.C
8.A
9.B10.C
11.C12.B13.A14.C15.D16.D17.D18.C19.C20.D
21.D22.C23.C24.A25.A26.B27.A28.C29.C30.C
31.D32.D33.B34.C35.B36.B37.D38.C39.A40.C
41.A42.C43.B44.A45.C46.B47.A48.C49.D50.B
