1. 从未排序序列中挑选元素，并将其依次放入已排序序列(初始时为空)的一端的方法，称为（ ）。

    A．归并排序         B．冒泡排序            C．插入排序             D．选择排序

   【答案】D。

2. 快速排序在下列（ ）情况下最易发挥其长处。

    A．被排序的数据中含有多个相同排序码        B．被排序的数据已基本有序

    C．被排序的数据完全无序                            D．被排序的数据中的最大值和最小值相差悬殊

   【答案】C 。B 选项是快速排序的最坏情况。

 3. 堆是一种（ ）排序。

    A．插入            B．选择                C．交换                 D．归并

    【答案】B。 

4. 下述几种排序方法中，要求内存最大的是（ ）。

    A．希尔排序            B．快速排序             C．归并排序            D．堆排序

   【答案】C 。堆排序、希尔排序的空间复杂度为 O(1) ，快速排序的空间复杂度为 O(log 2n)，归并排序的空间复杂度为 O(n) 。

5. 数据表中有 10000 个元素，如果仅要求求出其中最大的 10 个元素，则采用 ( )算法最节省时间。

    A．冒泡排序            B．快速排序            C．简单选择排序             D．堆排序

   【答案】D。

6. 下列排序算法中，（ ）不能保证每趟排序至少能将一个元素放到其最终的位置上。

    A．希尔排序             B．快速排序            C．冒泡排序               D．堆排序

  【答案】A。快速排序的每趟排序能将作为枢轴的元素放到最终位置；冒泡排序的每趟排序能将最大或最小的元素放到最终位置；堆排序的每趟排序能将最大或最小的元素放到最终位置。

7. 对任意7个关键字进行基于比较的排序，至少要进行(  )次关键字之间的两两比较。

    A.13                B. 14               C.15                D. 6

  【答案】A。对于任意序列进行基于比较的排序，求最少的比较次数应考虑最坏情况。对任意n个关键字排序的比较次数至少为「log2(n!)]。将n=7代入公式，答案为13。

8. 在下列算法中，( ) 算法可能出现下列情况:在最后一趟开始之前，所有元素都不在最终位置上。

    A.堆排序             B.冒泡排序            C.直接插入排序            D. 快速排序

  【答案】C。在直接插入排序中，若待排序列中的最后一个元素应插入表中的第一个位置， 则前面的有序子序列中的所有元素都不在最终位置上。

9.用希尔排序方法对一个数据序列进行排序时，若第1趟排序结果为9, 1,4,13, 7,8, 20,23, 15，则该趟排序采用的增量(间隔)可能是( )。

    A.2                B.3                C.4                D. 5

【答案】B。首先，第二个元素为1,是整个序列中的最小元素，因此可知该希尔排序为从小到大排序。然后考虑增量问题，若增量为2,则第1 +2个元素4明显比第1个元素9要小，A排除;若增量为3，则第,i+3,i+6 (i=1, 2, 3)个元素都为有序序列，符合希尔排序的定义:若增量为4,则第1个元素9比第1+4个元素7要大，C排除:若增量为S,则第1个元素9比第1+5个元素8要大，D排除，选B.

10. 折半插入排序算法的时间复杂度为(  )。

    A. O (n)               B. O(nlog2n)                C. O (n2)                D. O(n3)

【答案】C。虽然折半插入排序是对直接插入排序的改进，但它改进的只是比较的次数，而移动次数未发生变化，时间复杂度仍为O(n2)。

11. 用某种排序方法对线性表{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, 84，则所采用的排序方法是( )。

    A.选择排序                B.插入排序                C.2路归并排序                D.快速排序

【答案】D。选择排序在每趟结束后可以确定一个元素的最终位置， 不对。插入排序，第i趟后前i+ 1个元素应该是有序的，不对。第2趟{20, 15}和{21, 25}是反序的，因此不是归并排序。快速排序每趟都将基准元素放在其最终位置，然后以它为基准将序列划分为两个子序列。观察题中的排序过程，可知是快速排序。

12. 快速排序算法在(   )情况下最不利于发挥其长处。

    A.要排序的数据量太大                   B.要排序的数据中含有多个相同值

    C.要排序的数据个数为奇数            D.要排序的数据已基本有序

【答案】D。当待排序数据为基本有序时，每次选取第n个元素为基准，会导致划分区间分配不均匀，不利于发挥快速排序算法的优势。相反，当待排序数据分布较为随机时，基准元素能将序列划分为两个长度大致相等的序列，这时才能发挥快速排序的优势。

13. 数据序列F= {2,1,4,9, 8, 10, 6, 20}只能是下列排序算法中的( ) 两趟排序后的结果。

    A.快速排序            B.冒泡排序            C.选择排序            D.插入排序.

【答案】A。若为插入排序，则前三个元素应该是有序的，显然不对。而冒泡排序和选择排序经过两趟排序后应该有两个元素处于最终位置(最左/右端)，无论是按从小到大还是从大到小排序，数据序列中都没有两个满足这样的条件的元素，因此只可能选A。

14. 对下列关键字序列用快排进行排序时，速度最快的情形是( ), 速度最慢的情形是( ).

    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}

【答案】A、D。由考点精析可知，当每次的枢轴都把表等分为长度相近的两个子表时，速度是最快的；当表本身已经有序或逆序时，速度最慢。选项D中的序列已按关键字排好序，因此它是最慢的，而A中第一趟枢轴值21将表划分为两个子表{9, 17, 5}和{25, 23, 30},而后对两个子表划分时，枢轴值再次将它们等分，所以该序列是快速排序最优的情况，速度最快。其他选项可以类似分析。

15. 下列序列中，( )可能是执行第一趟快速排序后所得到的序列。

    I. {68, 11,18, 69, 23, 93, 73}                    II. {68, 11, 69, 23, 18, 93, 73}

    II，{93, 73, 68, 11, 69, 23, 18}                IV. {68, 11, 69, 23, 18, 73, 93}

    A.I、IV                    B.Il、III                       C.III、IV                    D.只有IV

【答案】C。显然，若按从小到大排序，则最终有序的序列是{11, 18, 23, 68, 69, 73, 93};若按从大到小排序，则最终有序的序列是{93, 73, 69, 68, 23, 18, 11}。对比可知1、I中没有处于最终位置的元素,故I、II都不可能。III 中73和93处于从大到小排序后的最终位置，而且73将序列分割成大于73和小于73的两部分，故m是有可能的。IV中73和93处于从小到大排列后的最终位置，73也将序列分割成大于73和小于73的两部分。

16.下列选项中，不可能是快速排序第2趟排序结果的是(  )。

    A.2,3,5,4,6,7,9                          B. 2,7,5,6,4,3,9

    C. 3,2,5,4, 7,6,9                        D.4,2,3,5, 7, 6,9

【答案】C。快排的阶段性排序结果的特点是，第i趟完成时，会有i个以上的数出现在它最终将要出现的位置，即它左边的数都比它小，它右边的数都比它大。题目问第二趟排序的结果，即要找不存在两个这样的数的选项。A选项中2,3, 6, 7, 9均符合，所以A排除; B选项中，2,9 均符合，所以B排除; D选项中5, 9均符合，所以D排除;最后看C选项，只有9一个数符合，所以C不可能是快速排序第二趟的结果。

17. 对n个关键字进行快速排序，最大递归深度为( )， 最小递归深度为( )。

    A. 1                        B. n                    C. log2n                    D. nlog2n

【答案】B、C。快速排序过程构成一个递归树，递归深度即递归树的高度。枢轴值每次都将子表等分时，递归树的高为log2n;枢轴值每次都是子表的最大值或最小值时，递归树退化为单链表,树高为n。

18. 排序过程中，对尚未确定最终位置的所有元素进行一遍处理称为一“趟”。下列序列中，不可能是快速排序第二趟结果的是( )。

    A.5,2, 16, 12, 28, 60, 32, 72                B.2, 16.5, 28, 12, 60, 32, 72

    C.2, 12, 16, 5, 28,32, 72, 60                D.5,2, 12, 28, 16, 32, 72, 60

【答案】D。要理解清楚排序过程中一“趟”的含义，题干也进行了解释_--对 尚未确定最终位置的所有元素都处理一遍才是一趟，所以此时要对前后两块子表各做一次快速排序才是一 “趟”快速排序，如果只对一块子表进行了 排序，而未处理另-块子表，就不能算是完整的一趟。选项A，第一趟匹配72,只余一块无序序列，第二趟匹配28，A可能。选项B，第一趟匹配2,第二趟匹配72, B可能。选项C，第一趟匹配2,第二趟匹配28或32, C可能。选项D,无论是先匹配12还是先匹配32,都会将序列分成两块，那么第二趟必须有两个元素匹配，所以D不可能，故选D.

19. 简单选择排序算法的比较次数和移动次数分别为( )。

    A. O (n), O(log2n)                    B. O(log2n), O (n2)

    C. O (n2), O(n)                        D. O(nlog2n), O(n)

【答案】C。

20.设线性表中每个元素有两个数据项k和k2，现对线性表按以下规则进行排序:先看数据项k, k值小的元素在前，大的元素在后;在k值相同的情况下，再看k，kz值小的在前，大的元案在后，满足这种要求的排序方法是()。

    A.先按k1进行直接插入排序，再按k2进行简单选择排序 

    B.先按k2进行直接插入排序，再按k1进行简单选择排序

    C.先按k1进行简单选择排序，再按k2进行直接插入排序

    D.先按k2进行简单选择排序，再按k1进行直接插入排序

  【答案】D。首先应确定k1、k2的排序顺序，若先排k1再排k2,则排序结果不符合题意，排除选项A、C。再考虑算法的稳定性，当k2排好序后，再对k1排序，若对k1排序采用的算法是不稳定的，则对于k1相同而k2不同的元素可能会改变相对次序，从而不一定能满足题干中的条件“在k1值相同的情况下，k2值小的元素在前，大的元素在后”。直接插入排序算法是稳定的，而简单选择排序算法是不稳定的，故只能选D。

21. 向具有n个结点的堆中插入一个新元素的时间复杂度为( ), 删除一个元素的时间复杂度为( )。

    A. O (1)               B. O(n)                C. O (log2n)                D. O(nlog2n)

  【答案】C、C。在向有n个元案的堆中插入一个新元素时，需要调用一个向上调整的算法，比较次数最多等于树的高度减1,由于树的高度为Llog2nJ+ 1,所以堆的向.上调整算法的比较次数最多等于Llog2nJ。此处需要注意，调整堆和建初始堆的时间复杂度是不一样的。

22. 构建n个记录的初始堆，其时间复杂度为( ); 对n个记录进行堆排序，最坏情况下其时间复杂度为( )。

    A. O(n)                B. O (n2)                C. O(log2n)                D. O(nlog2n)

  【答案】A、D。建堆过程中，向下调整的时间与树高h有关，为O(h).每次向下调整时，大部分结点的高度都较小。因此，可以证明在元素个数为n的序列上建堆，其时间复杂度为0(n)。无论是在最好情况下还是在最坏情况下，堆排序的时间复杂度均为o(nlog2n)o。

23.巳知小根堆为8, 15, 10, 21,34, 16, 12,删除关键字8之后需重建堆，在此过程中，关键字之间的比较次数是( )。

    A.1                    B.2                        C.3                   D.4

  【答案】C。删除8后，将12移动到堆项，第一次是15和10比较，第二次是10和12比较并交换，第三次还需比较12和16，故比较次数为3。

24. 以下排序算法中，( )不需要进行关键字的比较。

    A.快速排序            B.归并排序            C.基数排序            D.堆排序

  【答案】C。基数排序是基于关键字各位的大小进行排序的，而不是基于关键字的比较进行的。

25. 在下列排序算法中，平均情况下空间复杂度为O(n)的是(    ); 最坏情况下空间复杂度为O(n)的是(    )。

    I.希尔排序        I.堆排序        II.冒泡排序        IV.归并排序        V.快速排序        VI.基数排序

    A. I、IV、VI             B. II、V            C. IV、V                D. IV

  【答案】D、C。归并排序算法在平均情况下和最坏情况下的空间复杂度都会达到O(n),快速排序只在最坏情况下才会达到O(n),平均情况下为O(log2n)。所以归并排序算法可视为本章所有算法中占用辅助空间最多的排序算法。

26. 2路归并排序中，归并趟数的数量级是( ).

    A. O(n)             B. O (log2n)            C. O(nlogzn)            D. O (n2)

  【答案】B。对N个元素进行k路归并排序时，排序的趟数m满足k"=N,所以m = ⌈ logN ⌉,本题中即为⌈ log2n ⌉.

27. 将两个各有N个元素的有序表合并成一个有序表，最少的比较次数是(      )， 最多的比较次数是(      )。

    A. N                B.2N-1                C.2N                D.N-1

  【答案】A、B。注意到当一个表中的最小元素比另一个表中的最大元素还大时，比较的次数是最少的，仅比较N次;而当两个表中的元素依次间隔地比较时，即a1