《习题16(排序)》由会员分享，可在线阅读，更多相关《习题16(排序)（5页珍藏版）》请在金锄头文库上搜索。
1、习题习题 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,
2、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
3、）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）散
4、列表 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、当初始序列已经按键值有序时，用直接插
5、入算法进行排序，需要比较的次数为( ) 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 个最大的元素，最好的方法是（
6、 ） 。A）起泡排序 B）快速排序 C）堆排序 D）基数排序20、在待排序的元素序列基本有序的前提下，效率最高的排序方法是（ ） 。 A）插入排序 B）选择排序 C）快速排序 D）归并排序 21、排序方法中，从未排序序列中挑选元素，并将其放入已排序序列（初始为空）的一端的方法，称为（ ） 。 A）希尔排序 B）起泡排序 C）插入排序 D）选择排序 22、对 5 个不同的数排序至少需要比较（ ）次。 A）4 B）5 C）6 D）7 23、若只想得到序列中第 I 个元素之前的部分排序，最好采用（ ）排序方法。 A）快速排序 B）堆排序 C）插入排序 D）shell 排序 24、如果待排序序列中两个
7、数据元素具有相同的值，在排序前后它们的相互位置发生颠倒，则称该排序算 法是不稳定的。 （ ）就是不稳定的排序方法。 A）起泡排序 B）归并排序 C）Shell 排序 D）直接插入排序 E）简单选择排序 25、在下列排序算法中,哪一个算法的时间复杂度与初始排序无关（ ） 。 A）直接插入排序 B）气泡排序 C）快速排序 D）直接选择排序 26、数据序列（8,9,10,4,5,6,20,1,2）只能是下列排序算法中的( )的两趟排序后的结果。 A）选择排序 B）冒泡排序 C）插入排序 D）堆排序 27、数据序列（2，1，4，9，8，10，6，20）只能是下列排序算法中的( )的两趟排序后的结果。
8、A）快速排序 B）冒泡排序 C）选择排序 D）插入排序 28、对数据（84，47，25，15，21）排序，数据的排列次序在排序的过程中的变化为（1）84 47 25 15 21 （2）15 47 25 84 21 （3）15 21 25 84 47 （4）15 21 25 47 84 。则采用的是 ( ) 排序。 A）选择 B）冒泡 C）快速 D）插入 29、对序列15,9,7,8,20,-1,4进行一趟（ ）排序后,数据的排列变为4,9,-1,8,20,7,15。 A）选择 B）快速 C）希尔 D）冒泡 30、若用某种排序(分类)方法对线性表(25,84,21,47,15,27,68,35,
9、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 84。那么，所采用的排序方法是( )。A）选择排序 B）希尔排序 C）归并排序 D）快速排序 31、下列排序算法中( )不能保证每趟排序至少能将一个元素放到其最终的位置上。 A）快速排序 B）shell 排序 C）堆排序 D）冒泡排序 32、下列排序算法中( )排序在一趟结束后不一定能选出一个元素放在其最终位置上。
10、A）选择 B） 冒泡 C）归并 D）堆 33、 （ ）排序算法，在每趟都能选出一个元素放到最终位置，并且其时间性能受数据初始特性的影响。A）直接插入排序 B）快速排序 C）直接选择排序 D）堆排序 34、 在下面的排序方法中，辅助空间为 O（n）的是( ) 。 A）希尔排序 B）堆排序 C）选择排序 D）归并排序 35、下列排序算法中，在待排序数据已有序时，花费时间反而最多的是( )排序。 A）冒泡 B）希尔 C）快速 D）堆 36、下列排序算法中，占用辅助空间最多的是( ) A）归并排序 B）快速排序 C）希尔排序 D）堆排序 37、 （ ）排序方法，每次从未排序的记录中挑出最小的记录，加入
11、到已排序记录的末尾。 A）选择 B）冒泡 C）插入 D）堆 38、直接插入排序在最好情况下的时间复杂度为（ ） A）O(logn) B）O(n) C）O(n*logn) D）O(n2) 39、用 shell 对序列15,9,7,8,20,-1,4排序，一趟后变为15,-l,4,8,20,9,7,则采用的增量是( )A）l B）4 C）3 D）2 40、归并排序中，归并的趟数是( )。 A）O（n） B）O(logn) C）O(nlogn) D）O(n*n) 41、将两个各有 N 个元素的有序表归并成一个有序表,其最少的比较次数是( ) A）N B）2N-1 C）2N D）N-1 42、关键码序
12、列（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 43、对下列关键字序列用快速排序法进行排序时，速度最快的情形是( )。 A）21,25,5,17,9,23,30 B）25,23,30,17,21,5,9 C）21,9,17,30,25,23,5 D）5,9,17,21,23,25,30 44、快速排序方法在被排序的数据( )情况下最不利于发挥其长处 A）数据量太大 B）含有多个相同值 C）已基本有序
13、D）数目为奇数 45、以下关键字序列用快排序法进行排序，速度最慢的是( ) A）23,27,7,19,11,25,32 B）23,11,19,32,27,35,7 C）7,11,19,23,25,27,32 D）27,25,32,19,23,7,11 46、在快速排序过程中，每次将表划分成左、右两个子表，考虑这两个子表，下列结论正确的是（ ） 。 A）左、右两个子表都已各自排好序 B）左边子表中的元素都不大于右边子表中的元素 C）左边子表的长度小于右边子表的长度 D）左、右两个子表中元素的平均值相等 47、设关键码序列（25,18,9,33,67,82,53,95,12,70） ，要按关键码值递增的顺序排序，采取以第一个关 键码为分界元素的快速排序法，
