(习题16排序.docVIP

习题16（排序） 一、选择题 1、 对n个不同的关键字由小到大进行冒泡排序，在下列（ ）情况下比较的次数最多。 A）从小到大排列好的 B）从大到小排列好的 C）元素无序 D）元素基本有序 2、 堆是一种（ ）排序。 A）插入 B）选择 C）交换 D）归并 3、 堆的形状是一棵（ ）。 A）二叉排序树 B）满二叉树 C）完全二叉树 D）平衡二叉树 4、 在含有n个关键字的小根堆（堆顶元素最小）中，关键字最大的记录有可能存储在（ ）位置上。 A）?n/2? B）?n/2? -1 C）1 D）?n/2? +2 5、 以下序列不是堆的是( )。 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) 6、 下列四个序列中，哪一个是堆（ ）。 A）75,65,30,15,25,45,20,10 B）75,65,45,10,30,25,20,15 C）75,45,65,30,15,25,20,10 D）75,45,65,10,25,30,20,15 7、 在对n个元素的序列进行排序时，堆排序所需要的附加存储空间是（ ）。 A）O(log2n) B）O(1) C）O(n) D）O(nlog2n) 8、 有一组数据（15，9，7，8，20，-1，7，4），用堆排序的筛选方法建立的初始堆为 （ ） A）-1，4，8，9，20，7，15，7 B）-1，7，15，7，4，8，20，9 C）-1，4，7，8，20，15，7，9 D）A，B，C均不对 9、 对一组记录的关键码｛46,79,56,38,40,84｝采用堆排序，则初始化堆后最后一个元素是（ ）。 A）84 B）46 C）56 D）38 10、用二分法插入排序方法进行排序，被排序的表（或序列）应采用的数据结构是（ ）。 A）单链表 B）数组 C）双向链表 D）散列表 11、在所有排序方法中，关键码比较的次数与记录的初始排序次序无关的是( ) A）希尔排序 B）冒泡排序 C）直接插入排序 D）直接选择排序 12、用归并排序方法,最坏情况下，所需时间为( ) A）O(n) B）O(n2) C）O(nlog2n) D）O(nlog2n) 13、具有12个记录的序列，采用冒泡排序最少的比较次数是( ) A）1 B）144 C）11 D）66 14、用冒泡排序对序列18,14,6,27,8,12,16,52,10,26,47,29,41,24进行排序,共进行( )次比较。 A）33 B）45 C）70 D）91 15、当初始序列已经按键值有序时，用直接插入算法进行排序，需要比较的次数为( ) A）n2 B）n logan C） log2n D）n-1 16、下面四种内排序方法中，要求内存容量最大的是( ) A）插入排序 B）选择排序 C）快速排序 D）归并排序 17、在文件局部有序或文件长度较小的情况下，最佳的排序方法是( ) A）直接插入排序 B）冒泡排序 C）简单选择排序 D）都不对 18、若待排序列已基本有序，要使它完全有序，从关键码比较次数和移动次数考虑，应当使用 ( )。 A）归并排序 B）直接插入排序 C）直接选择排序 D）快速排序 19、设有1000个无序的元素，希望用最快的速度挑选出其中10个最大的元素，最好的方法是（ ）。 A）起泡排序 B）快速排序 C）堆排序 D）基数排序 20、在待排序的元素序列基本有序的前提下，效率最高的排序方法是（ ）。 A）插入排序 B）选择排序 C）快速排序 D）归并排序 21、排序方法中，从未排序序列中挑选元素，并将其放入已排序序列（初始为空）的一端的方法，称为（ ）。 A）希尔排序 B）起泡排序