[数据结构与算法]数据结构-作业10

参考教材：数据结构教程（Java语言描述)? ? ? ? 作者：李春葆

1 .?容易?（5分）整数序列（5，4，15，10，3，2，9，6，1）是某排序方法第一趟后的结果，该排序算法可能是______。

A. 冒泡排序

B. 二路归并排序

C. 堆排序

D. 简单选择排序

2 .?容易?（5分）整数序列（3，2，4，1，5，6，8，7）是第一趟递增排序后的结果，则采用的排序方法可能是______。

A. 快速排序

B. 冒泡排序

C. 堆排序

D. 简单选择排序

3 .?容易?（5分）下列排序方法中，______ 在一趟结束后不一定能选出一个元素放在其最终位置上。

A. 简单选择排序

B. 冒泡排序

C. 二路归并排序

D. 堆排序

4 .?容易?（5分）以下排序算法中，______ 在最后一趟排序结束之前可能所有元素都没有放到其最终位置上。

A. 简单选择排序

B. 希尔排序

C. 堆排序

D. 冒泡排序

5 .?容易?（5分）数据序列（8，9，10，4，5，6，20，1，2）只能是______ 算法的两趟排序后的结果。

A. 简单选择排序

B. 冒泡排序

C. 直接插入排序

D. 堆排序

6 .?容易?（5分）以下排序方法中，______ ，在初始序列已基本有序的情况下，排序效率最高。

A. 冒泡排序

B. 直接插入排序

C. 快速排序

D. 堆排序

7 .?容易?（5分）在二路归并排序中归并的趟数是______。

A. n

B. log2n

C. log2n+1

D. n2

8 .?容易?（5分）有一个整数序列为（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. 以上都不对

9 .?容易?（5分）以下序列不是堆的是______。

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）

10 .?容易?（5分）2n个不同的元素选择其中最小元素所需关键字比较次数最少是______次。

A. n

B. 2n

C. 2n-1

D. n-1

11 .?容易?（5分）对有n个元素的顺序表进行直接插入排序，在最坏情况下需比较______ 次关键字。

A. n-1

B. n+1

C. n/2

D. n(n-1)/2

12 .?容易?（5分）在一般情况下，以下排序算法中元素移动次数最少的______。

A. 直接插入排序

B. 冒泡排序

C. 简单选择排序

D. 都一样

13 .?容易?（5分）设有n（n为大于10000的整数）个无序元素，希望用最快速度从中选择前k（1≤k≤n）个关键字最小的元素，在以下排序方法中应选择______。

A. 快速排序

B. 希尔排序

C. 二路归并排序

D. 直接插入排序

14 .?容易?（5分）以下关于快速排序的叙述中正确的是______。

A. 快速排序在所有排序方法中为最快，而且所需辅助空间也最少

B. 在快速排序中，不可以用队列替代栈

C. 快速排序的空间复杂度为O(n)

D. 快速排序在待排序的数据随机分布时效率最高

15 .?容易?（5分）对关键字序列（28，16，32，12，60，2，5，72）进行快速排序，第一趟从小到大一次划分结果为______。

A. (2，5，12，16) 26 (60 32 72)

B. (5，16，2，12) 28 (60，32，72)

C. (2，16，12，5) 28 (60，32，72)

D. (5，16，2，12) 28 (32，60，72)

16 .?容易?（5分）对8个元素的顺序表进行快速排序，在最好情况下，元素之间的比较次数为______ 次。

A. 7

B. 8

C. 12

D. 13

17 .?容易?（5分）对一组数据（2，12，16，88，5，10）进行排序，若前三趟的结果如下： 第一趟：2，12，16，5，10，88 第二趟：2，12，5，10，16，88 第三趟：2，5，10，12，16，88 则采用的排序方法可能是______。

A. 冒泡排序

B. 希尔排序

C. 二路归并排序

D. 基数排序

18 .?容易?（5分）对整数序列（8，9，10，4，5，6，20，1，2）进行递增排序，采用每趟冒出一个最小元素的冒泡排序算法，需要进行的趟数是______。

A. 3

B. 4

C. 6

D. 8

19 .?容易?（5分）以下排序方法中，不稳定的排序方法是______。

A. 冒泡排序

B. 直接插入排序

C. 希尔排序

D. 二路归并排序

20 .?容易?（5分）对同一待排序序列分别进行折半插入排序和直接插入排序，两者之间可能的不同之处是______。

A. 排序的总趟数

B. 元素的移动次数

C. 使用辅助空间的数量

D. 元素之间的比较次数