第八章 排序练习答案

1、.第八章 排序（答案） 一、 选择题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,84 c).40,38, 48, 52,79,84 d).40,38, 48,84, 52,79

2、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,824.以下序列不是堆的是 a.105,85,98,77,80,61,82,40,22,13,66b.105,98,85,82,80,77,66,

3、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,82 c.82,75,71,18,10,90,68,24 d.24,10,18,71,82,75,68,907.下

4、列排序算法中，_算法可能在初始数据有序时，花费的时间反而最多。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,

5、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、在插入排序、选择排序、快速排序和归并排序中，平均查找

6、时间最少的是 快速排序 ,要求存储量最大的是 归并排序 .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、对关键字序列(

7、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，

8、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趟：

9、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趟

10、：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，27

11、6，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.初始a精品.b.建堆（c）交换90和8，输出90（d）筛选调整精品.（e）交换89和6，输出89（f）筛选调整g.交换65和6，输出65h. 筛选调整精品.17i.交换51和8，输出51（j）筛选调整 （k）交换50和8，输出50（l）筛选调

12、整 （m）交换46和8，输出46（n）筛选调整 （o）.交换27和6，输出27精品.（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，51