第八章排序练习答案

1、第八章排序(答案)一、 选择题1. 一组记录的排序码为47,78,57,39,41,85.,则利用堆排序的方法建立的初始推为 。A).78,47,57,39,41,85B).85,78,57,39,41,47C).85,78,57,47,41,39D).85,57,78,41,47,392. 一组记录的关键码为48,79,52,38,40,84.,则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为 。A).38,40, 48, 52,79,84B).40,38, 48,79, 52,84C).40,38, 48, 52,79,84D).40,38, 48,84, 52,793. 一组

2、记录的排序码为26,48,16,35,78,82,22,40,37,72., 其中含有5个长度为2的有序表，按归并排序的方法对该序列进行一趟归并后的结果为 。A).16, 26,35,48, 22,40, 78,82, 37,72B) .16, 26,35,48, 78,82, 22, 37,40,72C) .16, 26,48,35, 78,82, 22, 37,40,72D) .16, 26,35,48, 78, 22, 37,40,72,824.以下序列不是堆的是 A.105,85,98,77,80,61,82,40,22,13,66B.105,98,85,82,80,77,66,61,

3、40,22,13C.13,22,40,61,66,77,80,82,85,98,105D.105 , 85,40,77,80,61,66,98,82,13,225、下列四种排序方法中，不稳定的方法是A.直接插入排序B.冒泡排序C.归并排序 D.简单选择排序6、对下列4个序列用快速排序方法进行排序，以序列的第1个元素为基准进行划分。在第1趟划分过程中，元素移动次数最多的是序列_A.71,75,82,90, 24,18,10,68B.71,75,68,23,10,18,90,82C.82,75,71,18,10,90,68,24D.24,10,18,71,82,75,68,907 .下列排序算法中

4、，算法可能在初始数据有序时，花费的时间反而最多。A堆排序 B冒泡排序C快速排序D插入排序8 .对包含N个元素的散列表进行检索，平均查找长度为 .A .O(log 2N)B. O(N)C.不直接依赖于N D. 上述说法都不对9 .在各种排序方法中，从未排序序列中挑选元素，并将其依次放入已排序序列(初始时为空)的一端的方法是A.插入排序B.希尔排序C.选择排序D.归并排序10 . 一组记录的关键字为(46,79,56,38,40,84), 则利用堆排序的方法建立的初始堆为A 79,46,56,38,40,80B 84,79,56,38,40,46C 84,79,56,46,40,38D 84,56

5、,79,40,46,3811 .对具有8个元素白W列(49,38,65,97,76,13,27,50),按升序排序，采用快速排序法第一趟的结果为 答案：27, 38, 13, 49, 76, 97, 65, 50A) 13,65,38,97,76,49,27,50B) 13,27,38,49,50,65,76,97C) 97,76,65,50,49,38,27,13D) 13,38,65,97,76,49,27,5012 .下列哪个排序属于稳定排序 A希尔排序B 2路排序 C 堆排序D快速排序二、填空题1、在插入排序、选择排序、快速排序和归并排序中，平均查找时间最少的是快速排序,要求存储量最大

6、的是归并排序.2、用冒泡法对n个关键字排序，在最好的情况下，只需做-J 次比较和 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.)进行一趟

7、快速排序之后得到的结果为(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,9

8、9) ,7, 9第 6 趟：(7, 10, 36, 65, 72, 83, 99) , 9第 7 趟：(7, 9, 10, 36, 65, 72, 83, 99)8),请给出采用shell排序法对该序列作升序2 .已知序列(10, 16, 4, 3, 6, 12, 1, 9, 15 排序时的每一趟的结果。初始：10, 16, 4, 3, 6, 12, 1, 9, 15, 8d=5第 1 趟：10, 1, 4, 3, 6, 12, 16, 9, 15, 8d=2第 2 趟：4,1,6, 3,10, 8, 15, 9,16,12d=1 第 3 趟：1,3,4, 6,8, 9, 10, 12,15,

9、163 .已知序列 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，894 .已知序列 501 , 87, 512, 61, 908, 170,

10、 897, 275, 653, 462,请给出采用快速排序法对 该序列作升序排列时的每一趟的结果。初始：501, 89, 512, 61, 908, 170, 897, 276, 653, 462第11埴：462, 89, 276, 61, 170, 501, 897,908, 653, 512第2 1埴：170, 89, 276, 61, 462, 501, 897,908, 653, 512第3 1埴：61, 89, 170, 276, 462, 501, 897,908, 653, 512第4 1埴：61, 89, 170, 276, 462, 501, 897,908, 653, 51

11、2第5 1埴：61, 89, 170, 276, 462, 501, 897,908, 653, 512第6 1埴：61, 89, 170, 276, 462, 501, 897,908, 653, 512第7 1埴：61, 89, 170, 276, 462, 501, 512,653, 897, 908第8 1埴：61, 89, 170, 276, 462, 501, 512,653, 897, 908第9 1埴：61, 89, 170, 276, 462, 501, 512,653, 897, 908第10趟:61, 89, 170, 276, 462, 501, 512,653, 89

12、7, 9085 .已知序列 50, 8, 51, 6, 90, 17, 89, 27, 65, 46,请给出采用堆排序法对该序列作降序 排列时的每一趟的结果。采用堆排序法排序的各趟结果如图所示，排序结果为 90, 89, 65, 51, 50, 46, 27, 17, 8, 6a.初始a(d)筛选调整6(e)交换89和6,输出89(f)筛选调整g.交换65和6,输出65h. 筛选调整i.交换51和8,输出51(j )筛选调整(k)交换50和8,输出50(m)交换46和8,输出46(l )筛选调整(n)筛选调整(o).交换27和6,输出27(p)筛选调整(q.)交换17和6,输出17(r)筛选调

13、整(s)交换8和6,输出8 (t)输出66 .已知序列 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,9087 .已知序列(11, 16, 6, 5, 6, 14, 1, 9),请给出采用归并排序法对该序列