内容发布更新时间 : 2024/10/1 7:34:40星期一 下面是文章的全部内容请认真阅读。
第九章 排序
一、选择题
1.在所有排序方法中，关键字比较的次数与记录得初始排列次序无关的是（ ） （A）希尔排序 （B）起泡排序 （C）插入排序 （D）选择排序
2.设有1000个无序的元素,希望用最快的速度挑选出其中前10个最大的元素,最好（ ）排序法。
（A）起泡排序（B）快速排序（C）堆排序（D）基数排序
3.在待排序的元素序列基本有序的前提下,效率最高的排序方法是（ ） （A）插入排序（B）选择排序（C）快速排序（D）归并排序
4.一组记录的排序码为(46,79,56,38,40,84),则利用堆排序的方法建立的初始推为（ ）。 （A）79,46,56,38,40,80 （B）84,79,56,38,40,46 （C）84,79,56,46,40,38 （D）84,56,79,40,46,38
5.一组记录的关键码为(46,79,56,38,40,84),则利用快速排序的方法,以第一个记录为基准得到的一次划分结果为（ ）。
（A）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
6.一组记录的排序码为(25,48,16,35,79,82,23,40,36,72),其中含有5个长度为2的有序表,按归并排序的方法对该序列进行一趟归并后的结果为（ ）。
（A）16,25,35,48,23,40,79,82,36,72（B）16,25,35,48,79,82,23,36,40,72 （C）16,25,48,35,79,82,23,36,40,72（D）16,25,35,48,79,23,36,40,72,82
7.排序方法中,从未排序序列中依次取出元素与己排序序列(初始时为空)中的元素进行比较,将其放入己排序序列的正确位置上的方法,称为（ ） （A）希尔排序（B）起泡排序（C）插入排序（D）选择排序
8.排序方法中,从未排序序列中挑选元素并将其依次放入己排序序列(初始为空)的一端的方法,称为（ ）
（A）希尔排序（B）归并排序（C）插入排序（D）选择排序
9.用某种排序方法对线性表(25,84,21,47,15,27,68,35,20)进行排序时,元素序列的变化情况如下:
(1)25,84,21,47,15,27,68,35,20 ??(2)20,15,21,25,47,27,68,35,84 (3)15,20,21,25,35,27,47,68,84 ??(4)15,20,21,25,27,35,47,68,845 则所采用的排序方法是（ ）。
（A）选择排序（B）希尔排序（C）归并排序（D）快速排序 10.下述几种排序方法中,平均查找长度最小的是（ ） （A）插入排序（B）选择排序（C）快速排序（D）归并排序 11.下述几种排序方法中,要求内存量最大的是（ ）。 （A）插入排序（B）选择排序（C）快速排序（D）归并排序 12.快速排序方法在情况下最不利于发挥其长处。( )
（A）要排序的数据量太大??? （B）要排序的数据中含有多个相同值 （C）要排序的数据已基本有序（D）要排序的数据个数为奇数
13.设有10000个元素组成的无序序列,希望尽快挑选出其中前10个最大值元素,在不改变已有算法结构的前提下,以下几种内排序算法中(?? ?)最合适。 (A)选择排序法(B)快速排序法(C)堆排序法(D)冒泡排序法。 14.下列四种排序方法中，不稳定的方法是（ ）
(A)直接插入排序 (B)冒泡排序 (C)归并排序 (D)直接选择排序
二、判断题
1.用直接选择排序方法分别对序列S1＝（1，2，3，4，5，6，7）和序列S2＝（7，5，3，2，4，1， 6）进行排序，两者的比较次数不相同。（ ） 2.快速排序是所有排序中速度最快的一种。（ ）
3.堆排序是直到最后一趟排序结束之前所有元素才能在其最终的位置上。（ ）
三、填空题
1.试五种排序方法与对应的操作联系起来: (A)归并排序 ________ (B)选择排序 ________ (C)冒泡排序 _________ (D)插入排序 _________ (E)快速排序__________
(1)从待排序序列中依次取出元素与己排序序列中的元素作比较将其放入己排序序列中的正确的位置上。
(2)从待排序序列中挑选元素,并将其放入己排序序列的一端。 (3)依次将相邻的有序表合并成一个有序表。
(4)每次把待排序的区间划分为左、右两个子区间,其中左区间中元素的键值均小于等于基准元素的键值,右区间中元素的键值均大于等于基准元素的键值。 (5)当两个元素比较出现反序(即逆序)时就相互交换位置。
2.在对一组记录（4,38,96,23,15,72,60,45,83）进行直接插入排序时,当把第7个记录60插入到有序表时,为寻找插入位置需比较_______次。
3.在利用快速排序方法对一组记录(54,38,96,23,15,72,60,45,83)进行快速排序时,递归调用而使用的栈的所能达到的最大深度为_________,共需递归调用的次数为_______,其中第二次递归调用是对_________一组记录进行快速排序。
4.在堆排序,快速排序和归并排序中,若只从存储空间考虑,则应首先选取________方法,其次选取________方法,最后选取__________方法:若只从排序结果的稳定性考虑,则应选取________方法:若只从平均情况下排序最快考虑,则应选取________方法:若只从最坏情况下排序最快并且要节省内存考虑,则应选取___________方法。
5.在插入排序、希尔排序、选择排序、快速排序、堆排序、归并排序和基数排序中,排序是不稳定的有___________。
6.在插入排序、希尔排序、选择排序、快速排序、堆排序、归并排序和基数排序中,平均比较次数最少的排序是___________需要内存容量最多的是______________。
7.在堆排序和快速排序中,若原始记录接近正序或反序,则选用___________若原始记录无序则最好选用_____________。
8.在插入和选择排序中,若初始数据基本正序,则选用___________若初始数据基本反序,则选用___________。
9.对n个元素的序列进行起泡排序时,最少的比较次数是_________ 10.两个序列如下： L1＝{25，57，48，37，92，86，12，33} L2＝{25，37，33，12，48，57，86，92}
用冒泡排序方法分别对序列L1和L2进行排序，交换次序较少的是序列__________。