课程课件作业空chapter10

1复习题1.

在下列排序方法中，时间复杂度不受数据初始状态影响，恒为O(nlog2n)的是_____。

A.堆排序 B.起泡排序

C.简单选择排序 D.快速排序2.在下列排序方法中，某一趟排序结束后未必能选出一个元素放在其最终位置上的是_____。

A.堆排序 B.起泡排序

C.直接插入排序 D.快速排序2复习题3.

下列排序方法中，在待排序的数据已经为有序时，花费时间反而最多的是_____。

A.快速排序 B.希尔(Shell)排序

C.起泡排序 D.堆排序4.若表R在排序前已按关键字正序排列，则_____方法的比较次数最少。

A.直接插入排序 B.快速排序

C.归并排序 D.简单选择排序3复习题5.

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

A.直接插入排序 B.希尔(Shell)排序

C.起泡排序 D.简单选择排序6.快速排序方法在_____情况下最不利于发挥其长处。

A.要排序的数据量很大

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

C.要排序的数据已基本有序

D.要排序的数据个数为奇数4复习题7.

内排序方法的稳定性是指_____。

A.该排序方法不允许有相同的关键字记录 B.该排序方法允许有相同的关键字记录

C.平均时间为O(nlog2n)的排序方法 D.以上均不对8.以下各排序方法中，_____是稳定的排序方法。

A.直接插入和快速排序

B.快速排序和堆排序

C.简单选择和归并排序

D.归并排序和起泡排序5复习题9.

以下各排序方法中，辅助空间为O(n)的是_____。

A.堆排序 B.归并排序

C.希尔排序 D.快速排序10.若一组记录的排序码为{46,79,56,38,40,84}，则利用堆排序的方法建立的初始堆为_____。

A.79,46,56,38,40,80 B.84,79,56,38,40,46C.84,79,56,46,40,38 D.84,56,79,40,46,386复习题11.

若一组记录的关键字为{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，797复习题12.

一组记录的关键字为{25,48,16,35,79,82,23,40,36,72},其中，含有5个长度为2的有序表，按归并排序的方法对该序列再进行一趟归并后的结果为

_____。

A.16，25，35，48，23，40，79，82，36，72B.16，25，35，48，79，82，23，36，40，72 C.16，25，48，35，79，82，23，36，40，72D.16，25，35，48，79，23，36，40，72，828复习题13.

以下排序方法中，最好情况下时间复杂度为O(n)的依次是

、

。

A.直接插入排序

B.简单选择排序

C.起泡排序

D.快速排序9复习题14.判断以下叙述的正确性。

1)对一个堆，按二叉树层次进行遍历应该得到一个有序序列。

2)任何情况下，归并排序都比直接插入排序快。

3)折半插入排序所需关键字比较次数与待排序记录的初始排列状态有关。

4)对n个元素进行直接选择排序，关键字的比较次数总是n(n-1)/2次。()()()()如果是2-路插入排序呢？10复习题

5)只有在线性表的初始状态为反序的情况下，直接插入排序过程中，元素的移动次数才会达到最大值。

6)