一、选择题
1.在待排序的元素序列基本有序的前提下,效率最高的排序方法是(A)。
A.插入排序
B.选择排序
C.快速排序
D.归并排序
2.设有1000个无序的元素,希望用最快的速度挑选出其中煎10个最大的元素,最好选用(C)法。
A.冒泡排序
B.快速排序
C.堆排序
D.基数排序
3.具有12个记录的序列,采用冒泡排序最少的比较次数是(C)。
A. 1
B. 144
C. 11
D. 66
4.下列4种排序方法中,要求内存容量最大的是(D)。
A.插入排序
B.选择排序
C.快速排序
D.归并排序
5.初始序列已经按键值有序时,用直接插人算法进行排序,需要比较的次数为(D).
A. n2
B. nlog2n
C. log2n
D. n-1
6.下列4种排序方法,在排序过程中,关键码比较的次数与记录的初始排列顺序无关的是(C)。
A.直接插人排序和快速排序
B.快速排序和归并排序
C.直接选择排序和归并排序
D.直接插人排序和归并排序
7.一组记录的排序码为(46,79,56,38,40,84),则利用堆排序的方法建立的初始堆为(B)。
A. 79,46,56,38,40,84
B. 84,79,56,38,40,46
C. 84,79,56,46,40,38
D. 84,56,79,40,46,38
8.一组记录的排序码为(46,79,56,38,40,84),则利用快速排序的方法,以第1个记录为基准得到的一次划分的结果为(C)。
A. 38,40,46,56,79,84
B. 40,38,46,79,56,84
C. 40,38,46,56,79,84
D. 40,38,46,84,56,79
9.用某种排序方法对线性表(25,84,21,47,15,27,68,35,20)进行排序时,元素序列的变化情况如下:
25,84,21,47,15,27,68,35,20
20,15,21,25,47,27,68,35,84
15,20,21,25,35,27,47,68,84
15,20,21,25,27,35,47,68,84
则采用的排序方法是(D)。
A.选择排序
B.希尔排序
C.归并排序
D.快速排序
10.快速排序方法在(C)情况下最不利于发挥其长处。
A.要排序的数据量太大
B.要排序的数据中含有多个相同值
C.要排序的数据已基本有序
D.要排序的数据个数为奇数
二、判断题
1.插人排序是稳定的,选择排序是不稳定的。(√)
2.不稳定的排序算法是没有实用价值的。(×)
3.当待排序的元素很多时,为了交换元素的位置,移动元素要占较多的时间,这是影响时间复杂度的主要原因。(√)
4.对有n个记录的集合进行归并排序,所需要的辅助空间数与初始记录的排列状况有关。(x)
5.对n个记录的集合进行快速排序,所需要的附加空间数是O(n)。(x)
6.堆排序所需要的附加空间数与待排序的记录个数无关。(√)
7.对有n个记录的集合进行冒泡排序,所需时间决定于初始记录的排列情况,在初始
记录无序的情况下最好。(x)
8.对有n个记录的集合进行快速排序,所需时间决定于初始记录的排列情况,在初始
记录无序的情况下最好。(√)
9.对不稳定的排序算法,不论采用何种描述方式,总能举出一个说明它不稳定的实例
来。(√)
10.选择排序的比较次数不会随待排序记录的关键字的分布情况而改变。(√)
三、筒答题
1.以关键字序列(tim,kay,eva,roy,dot,jon,kim,ann,tom,jim,guy,amy)为例,手工执行以下排序算法(按字典序比较关键字的大小),写出每一趟排序结束时的关键字状态:
(1)直接插人排序;
(2)冒泡排序;
(3)直接选择排序;
(4)快速排序;
(5)归并排序;
(6)基数排序。
【解答】略。
2.已知序列{50,18,12,61,8,17,87,25},请给出采用堆排序对该序列做升序排序时的每一趟结果。
【解答】堆排序过程如图所示:
3.有n 个不同的英文单词,它们的长度相等,均为m ,若n>>50,m <5。试问:采用什么排序方法时间复杂度最小?为什么?
【提示】采用基数排序。基数排序是一种借助多关键码排序思想对单关键码进行排序的方法,它适合n 很大,而关键码较小的序列。本题中英文单词数目n >>50,而单词长度m<5,因此采用基数排序方法最佳。
4.如果只想得到一个含有n 个元素的序列中第k(k< 好采用什么排序方法?为什么?如有序列{57,11,25,36,18,80,22},得到其第三个最小元素之前的部分序列{11,18,22}使用所选择的算法实现时,要执行多少次比较? 【解答】采用堆排序。简单选择排序和冒泡排序可以在一趟排序后选出一个最大(或最小)元素,要比较n-1次,选次大元素要再比较n-2次……其时间复杂度是0(n2)。当k< 得到序列(57,11,25,36,18,80,22}的第3个最小元素之前的部分序列{11,18,22}共需14次比较。其中,建堆输出11比较8次,调堆输出17和25各需要比较4次和2次。 5.阅读下列排序算法,并与已学过的算法比较,讨论算法中基本操作的执行次数。 void sort(SortList r) {int i=1,j,w;