上传第10章排序习题

本文格式为Word版，下载可任意编辑——上传第10章排序习题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,2050,8,30,40,20,90,26,38,80,7026,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(nlog2n)；直接插入排序在待排序列基本有序时，每趟的比较次数大为降低，也即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,66B）100,98,85,82,80,77,66,60,40,20,10C）10,20,40,60,66,77,80,82,85,98,100D）100,85,40,77,80,60,66,98,82,10,20D

根据堆采用完全二叉树的顺序存储形式及堆的特点，因第一个结点即根结点关键字值最大，则应建立一个大根堆，但依据此数据序列建立起堆后关键字值为40的左右孩子结点分别为60、66，不符合大根堆特点。

13．下面排序方法中，关键字比较次数与记录的初始排列无关的是（）A）希尔排序B）冒泡排序C）直接插入排序D）直接选择排序D

假使初始排列基本有序，则对希尔排序来说，前几趟的插入工作大为减少。冒泡排序和直接插入排序都与初始排序序列有关，只有直接选择排序与初始序列无关．应选D。

14．一组记录的关键字为{45，80，55，40，42，85}，则利用堆排序的方法建立的初始堆为（）

A）80,45,50,40,42,85B）85,80,55,40,42,45C）85,80,55,45,42,40D）85,55,80,42,45,40B

16．n个元素进行冒泡排序的过程中，最好状况下的时间繁杂度为（）A）O(1)B）O(log2n)C）O(n2)D）O(n)D

最好状况下至少需要一趟排序，即比较n-1次，应选D。

17．n个元素进行快速排序的过程中，第一次划分最多需要移动（）次元素(包括开始将基准元素移到临时变量的那一次)。A）n／2B）n-1C）nD）n+lD

移动次数最多的状况是对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(nlog2n)，应选B。

20．对以下4个序列用快速排序方法进行排序，以序列的第1个元素为基准进行划分。在第1趟划分过程中，元素移动次数最多的是序列（）A）70,75,82,90,23,16,10,68B）70,75,68,23,10,16,90,82C）82,75,70,16,10,90,68,23D）23,10,16,70,82,75,68,90A

快速排序第一趟划分的方法是：将第1个元素放入最终排好序序列中的正确位置上，则在这个位置右边小于该元素值的元素都将移到其左边，在这个位置左边大于该元素值的元素都将其移到其右边。由此得到A需移动的元素最多，应选A。9.2填空题

2．在堆排序、快速排序和归并排序中，若从节省存储空间考虑，则应首先选取_____________方法，其次选取_____________方法；若只从排序结果的稳定性考虑，则应先择_____________方法；若只从平均状况下排序的速度来考虑，则选择_____________方法；若只从最坏状况下排序最快并且要节省内存考虑，则应选取_____________方法。