9.1 选择题 1．从末排序的序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在排序序列的合适位置，该排序方法称为（ ）排序法。 A）插入 B）选择 C）希尔 D）二路归并 【答案】A 2．下面各种排序方法中，最好情况下时间复杂度为O(n)的是（ ） A）快速排序 B）直接插入排序 C）堆排序 D）归并排序 【答案】B 3．用某种排序方法对线性表（25,84,21,47,15,27,68,35,20）进行排序时，无序序列的变化情况如下： 25 84 21 47 15 27 68 35 20 20 15 21 25 47 27 68 35 84 15 20 21 25 35 27 47 68 84 15 20 21 25 27 35 47 68 84 则所采用的排序方法是（ ） Ａ）选择排序 Ｂ）希尔排序 Ｃ）归并排序 Ｄ）快速排序 【答案】Ｄ 4．下面给出的四种排序法中，（ ）排序是不稳定排序法。 A）插入 B）冒泡 C）二路归并 D）堆 【答案】D 5．快速排序方法在（ ）情况下最不利于发挥其长处。 Ａ）要排序的数据量太大 Ｂ）要排序的数据中含有多个相同值 Ｃ）要排序的数据已基本有序 Ｄ）要排序的数据个数为奇数 【答案】Ｃ 6．一组记录的关键码为（46,79,56,38,40,84），则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为（ ） Ａ）38,40,46,56,79,84 B） 40,38,46,79,56,84 C） 40,38,46,56,79,84 D） 40,38,46,84,56,79 【答案】Ｃ 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） 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，不符合大根堆特点。 9．一组记录的关键字为{45， 80， 55， 40， 42， 85}，则利用堆排序的方法建立的初始堆为（ ） A） 80,45,50,40,42,85 B）...
