第九章 排序
一、选择题
1．对n个记录的文件进行快速排序，所需要的辅助存储空间大致为
A. O（1） B. O（n） C. O（1og2n） D. O（n2）
2.对于线性表（7，34，55，25，64，46，20，10）进行散列存储时，若选用H（K）=K %9作为散列函数，则散列地址为1的元素有（ ）个， A．1 B．2 C．3 D．4
3. 设一组初始记录关键字序列(5，2，6，3，8)，以第一个记录关键字5为基准进行一趟快速排序的结果为（ ）。 A．2，3，5，8，6 B． 3，2，5，8，6 C． 3，2，5，6，8 D． 2，3，6，5，8
4．设有n个待排序的记录关键字，则在堆排序中需要（ ）个辅助记录单元。 A． 1 B． n C． nlog2n D． n2
5．设一组初始关键字记录关键字为(20，15，14，18，21，36，40，10)，则以20为基准记录的一趟快速排序结束后的结果为( )。 A. 10，15，14，18，20，36，40，21 B.10，15，14，18，20，40，36，21 C． 10，15，14，20，18，40，36，2l D． 15，10，14，18，20，36，40，21
6．设有5000个待排序的记录关键字，如果需要用最快的方法选出其中最小的10个记录关键字，则用下列（ ）方法可以达到此目的。
A． 快速排序 B． 堆排序 C． 归并排序 D． 插入排序
7．下列四种排序中（ ）的空间复杂度最大。 A.插入排序 B.冒泡排序 C. 堆排序 D. 归并排序
8．设一组初始记录关键字序列为(345，253，674，924，627)，则用基数排序需要进行（ ）趟的分配和回收才能使得初始关键字序列变成有序序列。 A. 3 B. 4 C. 5 D. 8 9．下列四种排序中（ ）的空间复杂度最大。
A. 快速排序 B. 冒泡排序 C. 希尔排序 D. 堆
10．设一组初始记录关键字序列为(50，40，95，20，15，70，60，45)，则以增量d=4的一趟希尔排序结束后前4条记录关键字为（ ）。 A. 40，50，20，95 B. 15，40，60，20 C. 15，20，40，45 D. 45，40，15，20
11．设一组初始记录关键字序列为(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，35，50，80，85，20，36，40，70 D. 15，25，35，50，80，20，36，40，70，85
1
12．设一组初始记录关键字序列为(45，80，55，40，42，85)，则以第一个记录
关键字45为基准而得到一趟快速排序的结果是（ ）。 A.40，42，45，55，80，83 B. 42，40，45，80，85，88 C. 42，40，45，55，80，85 D. 42，40，45，85，55，80 13．执行一趟快速排序能够得到的序列是（ ）。 A. [41，12，34，45，27] 55 [72，63] B. [45，34，12，41] 55 [72，63，27] C. [63，12，34，45，27] 55 [41，72] D. [12，27，45，41] 55 [34，63，72]
14．时间复杂度不受数据初始状态影响而恒为O(nlog2n)的是（ ）。
A. 堆排序 B. 冒泡排序 C. 希尔排序 D. 快速排序 15．一趟排序结束后不一定能够选出一个元素放在其最终位置上的是（ ）。 A. 堆排序 B. 冒泡排序 C. 快速排序 D. 希尔排序 16．二路归并排序的时间复杂度为（ ）。
A. O(n) B. O(n2) C. O(nlog2n) D. O(1og2n) 17．设一组初始记录关键字序列为(60，80，55，40，42，85)，则以第一个关键字45为基准而得到的一趟快速排序结果是（ ）。 A .40，42，60，55，80，85 B. 42，45，55，60，85，80 C. 42，40，55，60，80，85 D. 42，40，60，85，55，80
18．利用直接插入排序法的思想建立一个有序线性表的时间复杂度为（ ）。 A. O(n) B. O(nlog2n) C. O(n2) D. O(1og2n) 19．下列各种排序算法中平均时间复杂度为O(n2)是（ ）。 A. 快速排序 B. 堆排序 C. 归并排序 D. 冒泡排序 20．向堆中插入一个元素的时间复杂度为（ ）。 A．O(log2n) B．O(n) C．O(1) D．16 O(nlog2n) 21．每次从无序表中取出一个元素，把它插入到有序表中的适当位置，此种排序方法叫做（ ）排序
A．插入 B．交换 C．选择 D．归并 22．如果只想得到1024个元素组成的序列中第5个最小元素之前的部分排序的序列，用（）方法最快。
A．起泡排序 B．快速排序 C．简单选择排序 D．堆排序 23．如果待排序序列中两个数据元素具有相同的值，在排序后它们的位置发生颠倒，则称该排序是不稳定的。（）就是不稳定的排序方法。
A．起泡排序 B．归并排序 C．直接插入法排序 D．简单选择排序
24．下列排序算法中, 只有____排序算法是不稳定的。
A. 快速排序 B. 冒泡排序 C. 二路归并排序 D. 直接插入排序
25．快速排序算法的平均时间复杂度是（ ）
A．O（n2） B. O (nlog2n) C. O(n) D. O(logn) 26．一组记录的关键字为{45，80，55，40，42，85}，则利用堆排序的方法建立
的初始堆为（ ） A.80，45，55，40，42，85 B.85，80，55，40，42，45 C.85，80，55，45，42，40 D.85，55，80，42，45，40
2
27．一个序列中有10000个元素，若只想得到其中前10个最小元素，最好采用的排序方法是( )
A. 快速排序 B. 堆排序 C. 插入排序 D. 二路归并排序
28．在排序方法中，从未排序序列中依次取出元素与已排序序列（初始时为空）中的元素进行比较，将其放入已排序序列的正确位置上的方法，称为( ) A.希尔排序 B.插入排序 C.冒泡排序 D.快速排序
29．设一组初始记录关键字的长度为8，则最多经过（ ）趟插入排序可以得到有序序列。
A. 6 B. 7 C. 8 D. 9
30．设一组初始记录关键字序列为(Q，H，C，Y，P，A，M，S，R，D，F，X)，则按字母升序的第一趟冒泡排序结束后的结果是（ ）。 A. F，H，C，D，P，A，M，Q，R，S，Y，X B. P，A，C，S，Q，D，F，X，R，H，M，Y C. A，D，C，R，F，Q，M，S，Y，P，H，X D. H，C，Q，P，A，M，S，R，D，F，X，Y
31．排序算法中，第一趟排序后，任一元素都不能确定其最终位置的算法是．．．( )
A.选择排序 B.插入排序 C.冒泡排序 D.快速排序
32．在排序方法中，从未排序序列中挑选元素，并将其依次放入已排序序列（初始时为空）的一端的方法，称为( )
A.希尔排序 B.归并排序 C.插入排序 D.选择排序 33．设有一组初始关键字值序列为（49，81，55，36，44，88），则利用快速排序的方法，以第一个关键字值为基准得到的一次划分为（ ） A．36，44，49，55，81，88 B.44，36，49，55，81，88 C.44，36，49，81，55，88 D.44，36，49，55，88，81 34．排序算法中，第一趟排序后，任一元素都不能确定其最终位置的算法是（ ） A.选择排序 B.快速排序 C.冒泡排序 D.插入排序 35．排序算法中，不稳定的排序是（ ）
A.直接插入排序 B.冒泡排序 C.堆排序 D.归并排序 36．当待排序序列中记录数较多时，速度最快的排序方法是（ ）
A.冒泡排序法 B.快速排序法 C.堆排序法 D.归并排序法 37．若对序列（15，30，26，22，69，50，53，87）采用二路归并法排序，则进行一趟归并后产生的序列为（ ） A.15，22，26，30，50，53，69，87 B.15，30，22，26，50，69，53，87 C.15，26，30，22，50，69，53，87 D.15，26，22，30，50，53，69，87 38．一组记录的键值为（46，74，18，53，14，20，40，38，86，65），利用堆排序的方法建立的初始堆为（ ） A．（14，18，38，46，65，40，20，53，86，74） B．（14，38，18，46，65，20，40， 53，86，74） C．（14，18，20，38，40，46，53，65，74，86） D．（14，86，20，38，40，46，53，65，74，18）
39．对序列（22，86，19，49，12，30，65，35，18）进行一趟排序后得到的结果如下：（18，12，19，22，49，30，65，35，86），则可以认为使用的排序方法是（ ）
3
A．选择排序 B．冒泡排序 C．快速排序 D．插入排序 40．若给定的关键字集合为{20,15,14,18,21,36,40,10}，一趟快速排序结束后，键值的排序为（ ）。
A．10,15,14,18,20,36,40,21 B．10,15,14,18,20,40,36,21 C．10,15,14,20,18,40,36,21 D．15,10,14,18,20,36,40,21
41．在所有排序方法中，关键字的比较次数与记录的初始排列无关的是（ ）。 A．快速排序 B．冒泡排序 C．直接插入排序 D．简单选择排序 42．当待排序序列的关键码是随机分布时，下列哪种排序算法的平均时间复杂度最优（ ）。
A．直接插入排序 B．直接选择排序 C．快速排序 D．冒泡排序
43．快速排序在（ ）情况下最不利于发挥其长处。 A．被排序的数据量很大 B．被排序的数据完全无序
C．被排序的数据已基本有序 D．被排序的数据中最大的值与最小值相差不大 44．在所有排序方法中，关键字比较次数与记录的初始排列次序无关的是 。
A、直接插入排序 B、起泡排序 C、快速排序 D、直接选择排序
45．一个对象序列的排序码为{46，79，56，38，40，84}，采用快速排序以位于最左位置的对象为基准而得到的第一次划分结果为（ ）。
A．{38，46，79，56，40，84} B．{38，79，56，46，40，84} C．{40，38，46，56，79，84} D．{38，46，56，79，40，84} 46．若待排序对象序列在排序前已按其排序码递增顺序排序，则采用（ ）方法比较次数最少。
A．直接插入排序 B．快速排序 C．归并排序 D．直接选择排序 47．排序算法的稳定性是指( A )。
A．经过排序之后，能使值相同的数据保持原顺序中的相对位置不变 B．经过排序之后，能使值相同的数据保持原顺序中的绝对位置不变 C．算法的排序性能与被排序元素的数量关系不大 D．算法的排序性能与被排序元素的数量关系密切 48．稳定的排序方法是( B )
A．直接插入排序和快速排序 B．折半插入排序和起泡排序 C．简单选择排序和四路归并排序 D．树形选择排序和shell排序 49．若要求尽可能快地对序列进行稳定的排序，则应选( B ) A．快速排序 B．归并排序 C．冒泡排序
50．若要求排序是稳定的，且关键字为实数，则在下列排序方法中应选( A )排序为宜。
A．直接插入 B．直接选择 C．堆 D．快速 E．基数
51．在下列排序算法中,哪一个算法的时间复杂度与初始排序无关( D)。
A． 直接插入排序 B. 气泡排序 C. 快速排序 D. 直接选择排序 52．设被排序的结点序列共有N个结点，在该序列中的结点已十分接近排序的情
4
况下，用直接插入法、归并法和一般的快速排序法对其排序，这些算法的时间复杂性应为( C )。
A. O(N)，O(N)，O(N) B. O(N)，O(N*log2N),O(N*log2N) C. O(N)，O(N*log2N),O(N2) D. O(N2)，O(N*log2N)，O(N2) 53．一个排序算法的时间复杂度与( B)有关。
A．排序算法的稳定性 B. 所需比较关键字的次数 C. 所采用的存诸结构 D. 所需辅助存诸空间的大小 54．( A)占用的额外空间的空间复杂性为O(1)。
A. 堆排序算法 B. 归并排序算法 C. 快速排序算法 D. 以上答案都不对 55．下列排序算法中( C )排序在一趟结束后不一定能选出一个元素放在其最终位置上。
A. 选择 B. 冒泡 C. 归并 D. 堆 56．适合并行处理的排序算法是(B )。
A、选择排序 B、快速排序 C、希尔排序 D、基数排序
57．一组记录的关键码为(46，79，56，38，40，84)，则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为( C )。 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) 58．下列排序算法中，( A )算法可能会出现下面的情况：初始数据有序时，花费的时间反而最多。
A. 快速排序 B. 堆排序 C. 希尔排序 D. 冒泡排序 59．有些排序算法在每趟排序过程中，都会有一个元素被放置在其最终的位置上，下列算法不会出现此情况的是(A )。
A. SHELL排序 B. 堆排序 C. 冒泡排序 D. 快速排序
60．在文件\局部有序\或文件长度较小的情况下，最佳内部排序的方法是( A )。
A. 直接插入排序 B. 冒泡排序 C. 简单选择排序 D. 快速排序
61．在下列排序方法中，(D )方法可能出现这种情况：在最后一趟开始之前，所有的元素都不在其最终应在的正确位置上。
A、快速排序 B、冒泡排序 C、堆排序 D、插入排序 62．下列排序算法中，占用辅助空间最多的是：( A )
A. 归并排序 B. 快速排序 C. 希尔排序 D. 堆排序 63．用直接插入排序方法对下面四个序列进行排序(由小到大)，元素比较次数最少的是(C )。
A． 94,32,40,90,80,46,21,69 B． 32,40,21,46,69,94,90,80 C． 21,32,46,40,80,69,90,94 D． 90,69,80,46,21,32,94,40
64．对下列关键字序列用快速排序法进行排序时，速度最快的情形是( A )。 A． {21,25,5,17,9,23,30} B．{25,23,30,17,21,5,9} C． {21,9,17,30,25,23,5} Ｄ． {5,9,17,21,23,25,30} 65．快速排序方法在( D )情况下最不利于发挥其长处。
A. 要排序的数据量太大 B. 要排序的数据中含有多个相同值 C. 要排序的数据个数为奇数 D. 要排序的数据已基本有序 66．在含有n个关键字的小根堆(堆顶元素最小)中，关键字最大的记录有可能存储在( D )位置上。
5