9.1 选择题
1．从末排序的序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在排序序列的合适位置，该排序方法称为（ ）排序法。 A）插入 B）选择 C）希尔 D）二路归并 【答案】A
2．下面各种排序方法中，最好情况下时间复杂度为O(n)的是（ ） A）快速排序 B）直接插入排序 C）堆排序 D）归并排序 【答案】B
4．下面给出的四种排序法中，（ ）排序是不稳定排序法。 A）插入 B）冒泡 C）二路归并 D）堆 【答案】D
5．快速排序方法在（ ）情况下最不利于发挥其长处。 Ａ）要排序的数据量太大
Ｂ）要排序的数据中含有多个相同值 Ｃ）要排序的数据已基本有序 Ｄ）要排序的数据个数为奇数 【答案】Ｃ
7．对记录的关键码{50，26，38，80，70，90，8，30，40，20}进行排序，各趟排序结束时的结果为： 50,26,38,80,70,90 ,8,30,40,20 50,8,30,40,20,90,26,38,80,70 26,8,30,40,20,80,50,38,90,70
8,20,26,30,38,40,50,70,80,90 其使用的排序方法是（ ）
A）快速排序 B）基数排序 C）希尔排序 D）归并排序 【答案】C
8．在文件“局部有序”或文件长度较小的情况下，最佳内部排序方法是（ ） A）直接插入排序 B）冒泡排序 C）简单选择排序 D）归并排序 【答案】A
【解析】当待排序列基本有序时，对冒泡排序来说，若最大关键字位于序列首部，则每趟排序仅能使其“下沉”一个位置，要使其下沉到底部仍需n-1趟排序，也即时间复杂度仍为O(n2)。而对简单选择排序来说，其比较次数与待排序列的初始状态无关；归并排序要求待排序列已经部分有序，而部分有序的含义是待排序列由若干有序的子序列组成，即每个子序列必须有序，并且其时间复杂度为O(n log2n)；直接插入排序在待排序列基本有序时，每趟的比较次数大为降低，也即n-1趟比较的时间复杂度由O(n)降至O(n)。
9．在下列算法中，（ ）算法可能出现下列情况：在最后一趟开始之前，所有的元素都不在其最终的位置上。
A）堆排序 B）冒泡排序 C）插入排序 D）快速排序 【答案】C
【解析】在插入排序中，如果待排序列中的最后一个元素其关键字值为最小，则在最后一趟开始之前，前n-1个排好序的元素都不在其最终位置上，与排好序后的位置相差一个位置。因此，选C。
10．设有5000个无序的元素，希望用最快速度挑选出其中前10个最大的元素，在以下的排序方法中，采用（ ）方法最好 A）快速排序 B）堆排序 C）基数排序 【答案】B
2
【解析】用堆排序最好，因为堆排序不需要等整个排序结束就可挑出前10个最大元素，而快速排序和基数排序都需等待整个排序结束才能知道前10个最大元素。
11．对给出的一组关键字{14，5，19，20，11，19}。若按关键字非递减排序，第一趟排序结果为{14，5，19，20，11，19}，问采用的排序算法是（ ） A）简单选择排序 B）快速排序 C）希尔排序 D）二路归并排序 【答案】C
12．以下序列不是堆的是（ ） A）100,85,98,77,80,60,82,40,20,10,66 B）100,98,85,82,80,77,66,60,40,20,10 C）10,20,40,60,66,77,80,82,85,98,100 D）100,85,40,77,80,60,66,98,82,10,20 【答案】D
【解析】根据堆采用完全二叉树的顺序存储形式及堆的特点，因第一个结点即根结点关键字值最大，则应建立一个大根堆，但依据此数据序列建立起堆后关键字值为40的左右孩子结点分别为60、66，不符合大根堆特点。
13．下面排序方法中，关键字比较次数与记录的初始排列无关的是（ ） A）希尔排序 B）冒泡排序 C）直接插入排序 D）直接选择排序 【答案】D
【解析】如果初始排列基本有序，则对希尔排序来说，前几趟的插入工作大为减少。冒泡排序和直接插入排序都与初始排序序列有关，只有直接选择排序与初始序列无关．故选D。
14．一组记录的关键字为{45，80，55，40，42，85}，则利用堆排序的方法建立的初始堆为（ ）
A）80,45,50,40,42,85 B）85,80,55,40,42, 45 C）85,80,55,45,42,40 D）85,55,80,42,45,40 【答案】B
16．n个元素进行冒泡排序的过程中，最好情况下的时间复杂度为（ ） A）O(1) B）O(log2n) C）O(n2) D）O(n) 【答案】D
【解析】最好情况下至少需要一趟排序，即比较n-1次，故选D。
17．n个元素进行快速排序的过程中，第一次划分最多需要移动（ ）次元素(包括开始将基准元素移到临时变量的那一次)。 A）n／2 B）n-1 C）n D）n+l 【答案】D
【解析】移动次数最多的情况是对n-1个元素比较时都需移动，加上开始将基准元素移到临时变量以及由临时变量移至正确位置的二次，即共需n+1次，故选D。 18．下述几种排序方法中，要求内存量最大的是（ ） A）插入排序 B）选择排序 C）快速排序 D）归并排序 【答案】D
【解析】插入排序和选择排序需要的辅助空间为O(1)，快速排序需要的辅助空间为O(log2n )，归并排序需要的辅助空间为O(n)，因此选D。 19．下面排序方法中，时间复杂度不是O(n2)的是（ ）
A）直接插入排序 B）二路归并排序 C）冒泡排序 D）直接选择排序 【答案】B
【解析】直接插入排序、冒泡排序和直接选择排序的时间复杂度为O(n2)，而二路归并排序的时间复杂度为O(n log2n)，故选B。
20．对下列4个序列用快速排序方法进行排序，以序列的第1个元素为基准进行划分。在第1趟划分过程中，元素移动次数最多的是序列（ ） A）70,75,82,90, 23,16,10,68 B）70,75,68,23,10,16,90,82 C）82,75,70,16,10,90,68,23 D）23,10,16,70,82,75,68,90 【答案】A
【解析】快速排序第一趟划分的方法是：将第1个元素放入最终排好序序列中的正确位置上，则在这个位置右边小于该元素值的元素都将移到其左边，在这个位置左边大于该元素值的元素都将其移到其右边。由此得到A需移动的元素最多，故选A。 9.2 填空题
2．在堆排序、快速排序和归并排序中，若从节省存储空间考虑，则应首先选取_____________方法，其次选取_____________方法；若只从排序结果的稳定性考虑，则应先择_____________方法；若只从平均情况下排序的速度来考虑，则选择_____________方法；若只从最坏情况下排序最快并且要节省内存考虑，则应选取_____________方法。
【答案】（1）堆排序 （2）快速排序 （3）归并排序 （4）快速 （5）堆
3．对n个元素的序列进行冒泡排序，最少的比较次数是_____________，此时元素的排列情况为_____________，在_____________情况下比较次数最多，其比较次数为_____（4）_ ____。 【答案】