排序练习题

一、选择题

1、以下序列不是堆的是   D     。

     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）

2、在文件“局部有序”或文件长度较小的情况下，最佳内部排序方法是   A     。

     A、直接插入排序                 B、冒泡排序

     C、简单选择排序                 D、归并排序


3、在下列算法中， C 算法可能出现下列情况；在最后一趟开始之前，所有的元素都不在其最终的位置上。

     A、堆排序                        B、冒泡排序

     C、插入排序                      D、快速排序

4、从未排序的序列中依次取出一个元素与已排序序列中的元素依次进行比较，
然后将其放在排序序列的合适位置，该排序方法称为    A    排序法。

     A、插入          B、选择         C、希尔          D、二路归并

5、排序趟数与序列原始状态有关的排序方法是  D或C      排序法。

     A、插入         B、选择         C、冒泡           D、快速

6、下面给出的四种排序方法中，  D      排序是不稳定排序法。

    A、插入         B、冒泡         C、二路归并       D、堆

7、快速排序在最坏情况下时间复杂度是O（n2），比    A    的性能差。

    A、堆排序    B、起泡排序             C、选择排序

8、若需在O(nlog2n)的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是    C    。

    A、快速排序     B、堆排序       C、归并[排序       D、直接插入排序

9、就排序算法所用的辅助空间而言，堆排序、快速排序、归并排序的关系是    A  。

   A、堆排序<快速排序<归并排序     B、堆排序<归并排序<快速排序

   C、堆排序>归并排序>快速排序     D、堆排序>快速排序>归并排序

   E、以上答案都不对

10、下面排序方法中，关键字比较次数与记录的初始排列无关的是    D    。

     A、希尔排序      B、冒泡排序      C、直接插入排序     D、直接选择排序

11、对记录的关键字集合key={50，26，38，80，70，90，8，30，40，20}进行排序，各趟排序结束时的结果为：

         50  26  38  80  70  90  8   30  40  20

         50  8   30  40  20  90  26  38  80  70

         26  8   30  40  20  80  50  38  90  70

         8   20  26  30  38  40  50  70  80  90

     其使用的排序方法是   C     。

     A、快速排序       B、基数排序       C、希尔排序       D、归并排序

12、一组记录的关键字为{45，80，55，40，42，85}，则利用堆排序的方法建立的初始堆为   B     。

     A、80，45，50，40，42，85         B、85，80，55，40，42，45

     C、85，80，55，45，42，40         D、85，55，80，42，45，40

13、在对n个元素进行冒泡排序的过程中，最好情况下的时间复杂性为   D     。

     A、O(1)         B、O(nlog2n)       C、O(n^2)        D、O(n)

14、在对n个元素进行快速排序的过程中，第一次划分最多需要移动 D 次元素
  （包括开始将基准元素移动到临时变量的那一次）。

     A、n/2          B、n-1          C、n          D、n+1

15、下述几种排序方法中，要求内存量最大的是   D    。

     A、插入排序      B、选择排序       C、快速排序        D、归并排序

16、下面排序方法中，时间复杂性不是O(n^2)的是   B     。

     A、直接插入排序                B、二路归并排序

     C、冒泡排序                    D、直接选择排序



二、判断题

  1、快速排序的速度在所有排序方法中为最快，而且所需附加空间最少。（错  ）

  2、内排序的快速排序方法，在任何情况下均可得到最快的排序结果。（  错  ）

  3、基数排序的设计思想是按照对关键字值的比较来实施的。（错   ）

  4、在快速排序算法中，不可以用队列替代栈。（  错  ）

  5、用希尔方法排序时，若关键字初始排序杂乱无序，则排序效率较低。（  错  ）

  6、当待排序的元素很大时，为了交换元素的位置，移动元素要占用较多的时间，
      这是影响复杂度的主要因素。（  对   ）

  7、对于n个记录的集合进行归并排序，在最坏情况下所需要的时间是O(n^2)。（错   ）

  8、对于n个记录的集合进行冒泡排序，在最坏情况下所需要的时间是O(n^2)。（  对  ）

  9、使用置换选择排序的主要目的是为了增加初始归并段的长度。（  对  ）

  10、对一个堆，按二叉树层次进行遍历可以得到一个有序序列。（  错  ）

  11、有一小根堆，堆中任意结点的关键字均小于它的左、右孩子关键字。
     其具有最大值的结点一定是一个叶结点并可能在堆的最后两层中。（  对  ）