数据结构第10章排序练习及答案.doc

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）85,80,55,40,42, 45 C）85,80,55,45,42,40 D）85,55,80,42,45,40 【答案】B 10．一组记录的关键字为{25，50，15，35，80，85，20，40，36，70}，其中含有5个长度为2的有序表，用归并排序方法对该序列进行一趟归并后的结果为（　　） A）15,25,35,50,20,40,80,85,36,70 B）15,25,35,50,80,20,85,40,70,36 C）15,25,50,35,80,85,20,36,40,70 D）15,25,35,50,80,20,36,40,70,85 【答案】A 【解析】对5个长度为2的有序表一趟归并后得到前两个长度为4的有序表和最后一个长度为2的有序表，故选A。 11．n个元素进行冒泡排序的过程中，最好情况下的时间复杂度为（　　） A）O(1) B）O(log2n) C）O(n2) D）O(n) 【答案】D 【解析】最好情况下至少需要一趟排序，即比较n-1次，故选D。 12．下述几种排序方法中，要求内存量最大的是（　　） A）插入排序 B）选择排序 C）快速排序 D）归并排序 【答案】D 【解析】插入排序和选择排序需要的辅助空间为O(1)，快速排序需要的辅助空间为O(log2n )，归并排序需要的辅助空间为O(n)，因此选D。 13．下面排序方法中，时间复杂度不是O(n2)的是（　　） A）直接插入排序 B）二路归并排序 C）冒泡排序 D）直接选择排序 【答案】B 【解析】直接插入排序、冒泡排序和直接选择排序的时间复杂度为