第八章 排序(答案) 一、 选择题1.一组记录的排序码为 47,78,57,39,41,85.,则利用堆排序的方法建立的初始推为 。A).78,47,57,39,41,85 B).85,78,57,39,41,47C).85,78,57,47,41,39 D).85,57,78,41,47,392.一组记录的关键码为 48,79,52,38,40,84.,则利用快速排序的方法,以第一个记录为基准得到的一次划分结果为 。A).38,40, 48, 52,79,84 B).40,38, 48,79, 52,84C).40,38, 48, 52,79,84 D).40,38, 48,84, 52,793.一组记录的排序码为 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,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,68 B.71,75,68,23,10,18,90,82C.82,75,71,18,10,90,68,24 D.24,10,18,71,82,75,68,907.下列排序算法中,___________算法可能在初始数据有序时,花费的时间反而最多。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,46C 84,79,56,46,40,38 D 84,56,79,40,46,3811.对具有 8 个元素的序列(49,38,65,97,76,13,27,50),按升序排序 ,采用快速排序法第一趟的结果为_________ 答案:27,38,13,49,76,97,65,50A) 13,65,38,97,76,49,27,50 B) 13,27,38,49,50,65,76,97C) 97,76,65,50,49,38,27,13 D) 13,38,65,97,76,49,27,5012.下列哪个排序属于稳定排序_________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,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,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,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,9085.已知序列{50,8,51,6,90,17,89,27,65,46},请给出采用堆排序法对该序列作降序排列时的每一趟的结果。采用堆排序法排序的各趟结果如图所示,排序结果为 90,89,65,51,50,46,27,17,8,6a.初始 ab.建堆(c)交换 90 和 8,输出 90(d)筛选调整(e)交换 89 和 6,输出 89(f)筛选调整g.交换 65 和 6,输出 65h. 筛选调整i.交换 51 和 8,输出 51(j)筛选调整 (k)交换 50 和 8,输出 50(l)筛选调整 (m )交换 46 和 8,输出 46(n)筛选调整 (o).交换 27 和 6,输出 2717(p)筛选调整 (q.)交换 17 和 6,输出 17(r)筛选调整 (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),请给出采用归并排序法对该序列作升序排序时的每一趟的结果。初始: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 趟归并完毕,则排序结束