第10章排序练习题答案.doc

these precious and worth cherishing. Second, scientific research situation, grasp the opportunities and challenges of transformation and upgrading of full completion of the "Thirteen-Five" development tasks, start is crucial. Focused grand blueprint, must to history of thinking views trend, put associate times forward of pulse, stepped on associate economic law of drums, find associate transformation upgrade of path, in grasp macro trend in the advance science development; to strategy of vision conspiracy to global, always tight buckle national macro policy oriented, accurate grasp County love actual, based overall caught opportunities, and PCT thought, ensure County economic social development always along right track continued forward; to precision of measures seeking breakthrough, tightly pegged focus task and bottleneck restricted, Science and identify practical and effective measures, advance breakthrough, ensuring all tasks carry out to the letter; based on scientific assessment and strict implementation, persist in combining routine supervision and centralized supervision, accurate assessment Township departments, strictly cash rewards, prompted the departments own implementation at all levels. In working to advance, to truly grasp the Guide, seize the opportunity, finding a position and play to our strengths and take the initiative, ensure that the start of the new year tree, new performance. Grasp the Guide, is to dock in policy measures to seize the initiative. Accurate grasp of the Central Government, provinces and cities to speed up the development of new policies and new initiatives with a high degree of policy acumen to capture opportunities to accelerate development. Follow-up to promote the transformation and upgrading of the five great ideas offer a great chance. Five large development philosophy is the Party Central Committee with a view to promote economic transformation and upgrading, complete the building of a well-off society in major decisions and arrangements, is the development of a profound change. County-wide at all levels should conscientiously study and implement, implement the five ideas, green development, open development, on which to share advantages, and actively explore new path of innovative and coordinated development, changing the concept of leading the transformation of development mode of development, promote the development of quality improvement. Floor supply side structural reform implementation provides an effective strategy for improving the quality of development. Supply side structural reform is future full deepening reform of plays, to according to "macro policy to stability, and industry policy to associate, and micro policy to live, and reform policy to real, and social policy to backing" of requirements, keen grasp Central, and provinces release out of new signal, combined County love actual accurate docking, full grasp "to capacity, and to inventory, and to lever, and drop cost, and fill short Board" five big focus task implementation, prompted County economic transformation upgrade, and continued upgrade. Poverty
第10章排序练习题答案
一、填空题
1. 大多数排序算法都有两个基本的操作： 比较 和 移动 。
2. 在对一组记录（54，38，96，23，15，72，60，45，83）进行直接插入排序时，当把第7个记录60插入到有序表时，为寻找插入位置至少需比较 3 次。
3. 在插入和选择排序中，若初始数据基本正序，则选用 插入 ；若初始数据基本反序，则选用 选择 。
正序时两种方法移动次数均为0，但比较次数量级不同，插入法：n-1即O(n)，选择法：O(n2)
反序时两种方法比较次数量级相同，均为O(n2)，但移动次数不同，插入法：O(n2)，选择法：3(n-1)即O(n)
4. 在堆排序和快速排序中，若初始记录接近正序或反序，则选用 堆排序 ；若初始记录基本无序，则最好选用 快速排序 。
5. 对于n个记录的集合进行冒泡排序，在最坏的情况下所需要的时间是 O(n2) 。若对其进行快速排序，在最坏的情况下所需要的时间是 O(n2) 。
6. 对于n个记录的集合进行归并排序，所需要的平均时间是 O(nlog2n)
，所需要的附加空间是 O(n) 。
7． 对于n个记录的表进行2路归并排序，整个归并排序需进行 ┌log2n┐ 趟（遍）。
8. 设要将序列（Q, H, C, Y, P, A, M, S, R, D, F, X）中的关键码按字母序的升序重新排列，则：
冒泡排序一趟扫描的结果是 H C Q P A M S R D F X Y ；
二路归并排序一趟扫描的结果是 H Q C Y A P M S D R F X；
快速排序一趟扫描的结果是 F H C D P A M Q R S Y X ；
堆排序初始建堆的结果是 Y S X R P C M H Q D F A 。（大根堆）
9. 在堆排序、快速排序和归并排序中，
若只从存储空间考虑，则应首先选取 堆排序 方法，其次选取 快速排序方法，最后选取归并排序方法；
若只从排序结果的稳定性考虑，则应 选取归并排序方法；
若只从平均情况下最快考虑，则应选取快速排序方法；
若只从最坏情况下最快并且要节省内存考虑，则应选取堆排序方法。

二、单项选择题
（ C ）1． 排序方法中，从未排序序列中依次取出元素与已排序序列（初始时为空）中的元素进行比较，将其放入已排序序列的正确位置上的方法，称为
Ａ. 归并排序 Ｂ. 冒泡排序 Ｃ. 插入排序 Ｄ. 选择排序
（ D ）2．从未排序序列中挑选元素，并将其依次插入已排序序列（初始时为空）的一端的方法，称为
Ａ. 冒泡排序 Ｂ. 归并排序 Ｃ. 插入排序 Ｄ. 选择排序
（ B ）3．对ｎ个不同的排序码进行冒泡排序，在下列哪种情况下比较的次数最多。
Ａ. 从小到大排列好的 Ｂ. 从大到小排列好的 Ｃ. 元素无序 Ｄ. 元素基本有序
（ D ）4．对ｎ个不同的排序码进行冒泡排序，在元素无序的情况下比较的次数为
Ａ. n+1 Ｂ. n Ｃ. n-1 Ｄ. n(n-1)/2
（ C ）5．快速排序在下列哪种情况下最易发挥其长处。
Ａ. 被排序的数据中含有多个相同排序码 Ｂ. 被排序的数据已基本有序
Ｃ. 被排序的数据完全无序 Ｄ. 被排序的数据中的最大值和最小值相差悬殊
（ B ）6． 对有n个记录的表作快速排序，在最坏情况下，算法的时间复杂度是
A．O(n) B．O(n2) C．O(nlog2n) D．O(n3)
（ C ）7．若一组记录的排序码为（46, 79, 56, 38, 40, 84），则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为
Ａ. 38, 40, 46, 56, 79, 84 Ｂ. 40, 38, 46 , 79, 56, 84
Ｃ. 40, 38，46, 56, 79, 84 Ｄ. 40, 38, 46, 84, 56, 79
（ D ）8．下列关键字序列中， 是堆。
Ａ. 16, 72, 31, 23, 94, 53 Ｂ. 94, 23, 31, 72, 16, 53
Ｃ. 16, 53, 23, 94，31, 72 Ｄ. 16, 23, 53, 31, 94, 72
（ B ）9．堆是一种 排序。
Ａ. 插入 Ｂ.选择 Ｃ. 交换 Ｄ. 归并
（ C ）10．堆的形状是一棵
Ａ. 二叉排序树 Ｂ.满二叉树 Ｃ. 完全二叉树 Ｄ. 平衡二叉树
（ B ）11．若一组记录的排序码为（46, 79, 56, 38, 40, 84），则利用堆排序的方法建立的初始堆为
Ａ. 79, 46, 56, 38, 40, 84 Ｂ. 84, 79, 56, 38, 40, 46
Ｃ. 84, 79, 56, 46, 40, 38 Ｄ. 84, 56, 79, 40, 46, 38
（ C ）12． 下述几种排序方法中，要求内存最大的是
Ａ. 插入排序 Ｂ.快速排序 Ｃ. 归并排序 Ｄ. 选择排序
三、简答题
设待排序的关键码序列为{12, 2, 16, 30, 28, 10, 16*, 20, 6, 18}, 试分别写出使用以下排序方法每趟排序后的结果。
(1) 直接插入排序 (2)起泡排序 (3) 直接选择排序 (4) 快速排序 (5) 二路归并排序 (6)堆排序

（1）直接插入排序
[12] 2 16 30 28 10 16* 20 6 18
[2 12] 16 30 28 10 16* 20 6 18
[2 12 16] 30 28 10 16* 20 6 18
[2 12 16 30] 28 10 16* 20 6 18
[2 12 16 28 30] 10 16* 20 6 18
[2 10 12 16 28 30] 16* 20 6 18
[2 10 12 16 16* 28 30] 20 6 18
[2 10 12 16 16* 20 28 30] 6 18
[2 6 10 12 16 16* 20 28 30] 18
[2 6 10 12 16 16* 18 20 28 30]

（2）起泡排序
2 12 16 28 10 16* 20 6 18 [30]
2 12 16 10 16* 20 6 18 [28 30]
2 12 10 16 16* 6 18 [20 28 30]
2 10 12 16 6 16* [18 20 28 30]
2 10 12 6 16 [16* 18 20 28 30]
2 10 6 12 [16 16* 18 20 28 30]
2 6 10 [12 16 16* 18 20 28 30]
2 6 10 12 16 16* 18 20 28 30]

（3）直接选择排序
2 [12 16 30 28 10 16* 20 6 18]
2 6 [16 30 28 10 16* 20 12 18]
2 6 10 [30 28 16 16* 20 12 18]
2 6 10 12 [28 16 16* 20 30 18]
2 6 10 12 16 [28 16* 20 30 18]
2 6 10 12 16 16* [28 20 30 28]
2 6 10 12 16 16* 18 [20 30 28]
2 6 10 12 16 16* 18 20 [28 30]
2 6 10 12 16 16* 18 20 28 [30]

（4）快速排序
12 [12 2 16 30 28 10 16* 20 6 18]
6 [6 2 10] 12 [28 30 16* 20 16 18]
28 [2] 6 [10] 12 [28 30 16* 20 16 18 ]
18 2 6 10 12 [18 16 16* 20 ] 28 [30 ]
16* 2 6 10 12 [16* 16] 18 [20] 28 30
2 6 10 12 16* [16] 18 20 28 30
左子序列递归深度为1，右子序列递归深度为3。

（5）二路归并排序

12 2 16 30 28 10 16* 20 6 18
2 12 16 30 10 28 16 * 20 6 18
2 12 16 30 10 16 * 20 28 6 18
2 10 12 16 16* 20 28 30 6 18
2 6 10 12 16 16* 18 20 28 30

（6）堆排序
第一步,形成初始大根堆（详细过程略），第二步做堆排序。
12
2
16
20
10
30
16*
28
6
18
30
28
16
10
20
16*
18
2
12
6

初始排序 不是大根堆 形成初始大根堆12
28
16
2
10
20
16*
18
6
30
28
20
16
10
12
16*
18
2
30
6

交换1与10对象 从1到9重新形成堆
6
20
16
2
10
12
16*
18
28
30
20
18
16
10
12
16*
6
2
30
28

交换1与9对象 从1到8重新形成堆
2
18
16
20
10
12
16*
6
28
30
18
12
16
10
2
16*
12
20
30
28

交换1与8对象 从1到7重新形成堆
16*
12
16
20
10
2
18
6
28
30
16*
12
16
10
2
18
6
20
30
28

交换1与7对象 从1到6重新形成堆
10
12
16
20
16*
2
18
6
28
30
16
12
10
16*
2
18
6
20
30
28

交换1与6对象 从1到5重新形成堆
6
12
10
20
16*
2
18
16
28
30
12
6
10
16*
2
18
16
20
30
28

交换1与5对象 从1到4重新形成堆
12
6
10
20
16*
12
18
16
28
30
10
6
2
16*
12
18
16
20
30
28

交换1与4对象 从1到3重新形成堆
2
6
10
20
16*
12
18
16
28
30
6
2
10
16*
12
18
16
20
30
28

交换1与3对象 从1到2重新形成堆

2
6
10
20
16*
12
18
16
28
30
2
6
10
16*
12
18
16
20
30
28

交换1与2对象 得到结果

母亲通情达理，也鼓励他儿子奋勇杀敌，岳飞参军时，岳飞母亲在他背上刺上了“精忠报国”四个醒目大字，后来，英勇奋战的岳飞建立起了属于自己的部落岳家军，他们不屈不挠，喊着愤慨激昂慷慨的口号奋勇杀5