第八章 排序(答案)
一、 选择题
1.一组记录的排序码为47,78,57,39,41,85.,则利用堆排序的方法建立的初始推为 。
A).78,47,57,39,41,85 B).85,78,57,39,41,47
C).85,78,57,47,41,39 D).85,57,78,41,47,39
2.一组记录的关键码为48,79,52,38,40,84.,则利用快速排序的方法,以第一个记录为基准得到的一次划分结果为 。
A).38,40, 48, 52,79,84 B).40,38, 48,79, 52,84
C).40,38, 48, 52,79,84 D).40,38, 48,84, 52,79
3.一组记录的排序码为26,48,16,35,78,82,22,40,37,72.,其中含有5个长度为2的有序表,按归并排序的方法对该序列进行一趟归并后的结果为 。
A).16, 26,35,48, 22,40, 78,82, 37,72
B).16, 26,35,48, 78,82, 22, 37,40,72
C).16, 26,48,35, 78,82, 22, 37,40,72
D).16, 26,35,48, 78, 22, 37,40,72,82
4.以下序列不是堆的是
A.105,85,98,77,80,61,82,40,22,13,66
B.105,98,85,82,80,77,66,61,40,22,13
C.13,22,40,61,66,77,80,82,85,98,105
D.105,85,40,77,80,61,66,98,82,13,22
5、下列四种排序方法中,不稳定的方法是
A.直接插入排序 B.冒泡排序 C.归并排序 D. 简单选择排序
6、对下列4个序列用快速排序方法进行排序,以序列的第1个元素为基准进行划分。在第1趟划分过程中,元素移动次数最多的是序列
A.71,75,82,90, 24,18,10,68
B.71,75,68,23,10,18,90,82
C.82,75,71,18,10,90,68,24
D.24,10,18,71,82,75,68,90
7.下列排序算法中,___________算法可能在初始数据有序时,花费的时间反而最多。
A 堆排序 B 冒泡排序 C 快速排序 D 插入排序
8.对包含N个元素的散列表进行检索,平均查找长度为_________.
A .O(log2N) B. O(N)
C.不直接依赖于N D. 上述说法都不对
9.在各种排序方法中,从未排序序列中挑选元素,并将其依次放入已排序序列(初始时为空)的一端的方法是________________
A. 插入排序 B. 希尔排序 C. 选择排序 D. 归并排序
10.一组记录的关键字为(46,79,56,38,40,84),则利用堆排序的方法建立的初始堆为_____________
A 79,46,56,38,40,80 B 84,79,56,38,40,46
C 84,79,56,46,40,38 D 84,56,79,40,46,38
11.对具有8个元素的序列(49,38,65,97,76,13,27,50),按升序排序,采用快速排序法第一趟的结果为_________ 答案:27,38,13,49,76,97,65,50
A) 13,65,38,97,76,49,27,50 B) 13,27,38,49,50,65,76,97
C) 97,76,65,50,49,38,27,13 D) 13,38,65,97,76,49,27,50
12.下列哪个排序属于稳定排序_________
A 希尔排序 B 2路排序 C 堆排序 D 快速排序
二、填空题
1、在插入排序、选择排序、快速排序和归并排序中,平均查找时间最少的是 快速排序 ,要求存储量最大的是 归并排序 .
2、用冒泡法对n个关键字排序,在最好的情况下,只需做 n-1 次比较和 0 次移动;在最坏的情况下,要做 n(n-1)/2 次比较
3、在快速排序和堆排序中,若待排序记录序列接近正序或逆序,则应该选用 堆排序 ,若待排序记录序列无序,则应该选用 快速排序 .
4、设顺序表中有1000个元素,用折半查找时,最大比较次数为 10 ,最小比较次数为
1 .
.5、已知关键字序列为(20,15,14,18,21,36,40,10),采用快速排序法对其排序,第一趟排序后的关键字序列为 (10,15,14,18,20,36,40,21)
6、对关键字序列(52,80,63, 46,90.)进行一趟快速排序之后得到的结果为 (46,52,63,80,90)
三、简答题
1.已知序列{72,83,99,65,10,36,7,9},请给出采用插入排序法对该序列作升序排序时的每一趟的结果。
初始: (72),83,99,65,10,36,7,9
第1趟:(72, 83),99,65,10,36,7,9
第2趟:(72, 83, 99),65,10,36,7,9
第3趟:(65, 72, 83,99),10,36,7,9
第4趟:(10,65,72,83,99),36,7,9
第5趟:(10,36,65,72,83,99),7,9
第6趟:(7,10,36,65,72,83,99),9
第7趟:(7,9,10,36,65,72,83,99)
2.已知序列(10,16,4,3,6,12,1,9,15,8),请给出采用shell排序法对该序列作升序排序时的每一趟的结果。
初始:10,16,4,3,6,12,1,9,15,8
d=5第1趟:10,1,4,3,6,12,16,9,15,8
d=2第2趟:4,1,6,3,10,8,15,9,16,12
d=1第3趟:1,3,4,6,8,9,10,12,15,16
3.已知序列{17,18,55,40,7,32,73,65,89},请给出采用冒泡排序法对该序列作升序排序的每一趟的结果。
初始:17,18,55,40,7,32,73,65,89
第1趟:17,18,40,7,32,55,65,73,89
第2趟:17,18,7,32,40,55,65,73,89
第3趟:17,7,18,32,40,55,65,73,89
第4趟:7,17,18,32,40,55,65,73,89
第5趟:7,17,18,32,40,55,65,73,89
4.已知序列{501,87,512,61,908,170,897,275,653,462},请给出采用快速排序法对该序列作升序排列时的每一趟的结果。
初始:501,89,512,61,908,170,897,276,653,462
第1趟:462,89,276,61,170,501,897,908,653,512
第2趟:170,89,276,61,462,501,897,908,653,512
第3趟:61,89,170,276,462,501,897,908,653,512
第4趟:61,89,170,276,462,501,897,908,653,512
第5趟:61,89,170,276,462,501,897,908,653,512
第6趟:61,89,170,276,462,501,897,908,653,512
第7趟:61,89,170,276,462,501,512,653,897,908
第8趟:61,89,170,276,462,501,512,653,897,908
第9趟:61,89,170,276,462,501,512,653,897,908
第10趟:61,89,170,276,462,501,512,653,897,908
5.已知序列{50,8,51,6,90,17,89,27,65,46},请给出采用堆排序法对该序列作降序排列时的每一趟的结果。
采用堆排序法排序的各趟结果如图所示,排序结果为90,89,65,51,50,46,27,17,8,6
a.初始a
b.建堆
(c)交换90和8,输出90
(d)筛选调整
(e)交换89和6,输出89
(f)筛选调整
g.交换65和6,输出65
h. 筛选调整
i.交换51和8,输出51
(j)筛选调整 (k)交换50和8,输出50
(l)筛选调整 (m)交换46和8,输出46
(n)筛选调整 (o).交换27和6,输出27
(p)筛选调整 (q.)交换17和6,输出17
(r)筛选调整 (s)交换8和6,输出8 (t)输出6
6.已知序列{513,87,612,61,908,180,898,265,673,412},请给出,采用基数排序法对该序列作升序排序时的每一趟的结果。
初始序列: 513,87,612,61,908,180,899,265,673,412
第1趟(按个位排序):180,61,612,412,513,673,265,87,908,899
第2趟(按十位排序):908,612,412,513,61,265,673,180, 87,899
第3趟(按百位排序):61,87,180,265,412,513,612,673,899,908
7.已知序列(11,16,6,5,6,14,1,9),请给出采用归并排序法对该序列作升序排序时的每一趟的结果。
初始:11,16,6,5,3,14,1,9,
第1趟:[11,16][5,6][3,14][1,9]
第2趟:[5,6,11,16][1,3,9,14]
第3趟:[1,3,5,6, 9,11,14,16]
第3趟归并完毕,则排序结束
本文来源:https://www.2haoxitong.net/k/doc/d2f4db838762caaedd33d487.html
文档为doc格式