第八部分 排序 带答案

第八部分 排序

一、选择题

1．冒泡排序在最好情况下时间复杂度为 ( C )

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

2．对长度为10的表作选择(简单选择)排序,共需比较(A )次关键字。

A.45 B.90 C.55 D.110

3．对n个元素的表作快速排序,在最坏情况下,算法的时间复杂度为( C )。

A.O(log2 n) B.O(nlog2 n) C.O(n2) D.O(2n ) 4．对n个元素的表作堆排序,在最坏情况下,算法的时间复杂度为( B )。 A.O(log2 n) B.O(nlog2 n) C.O(n2) D.O(2n )

5．一个排序算法时间复杂度的大小(A )有关。

A.与所需比较关键字的次数 B.与该算法的稳定性

C.不与所需移动记录的数目 D.与所需辅助存储空间的大小

6. 排序趟数与序列的原始状态(原始排列)有关的排序方法是( D )排序方法。

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

7. 设有100个数据元素，采用折半搜索时，最大比较次数为 (B )。

A. 6 B. 7 C. 8 D. 10

8. 对待排序的元素序列进行划分，将其分为左、右两个子序列，再对两个子序列施加同样

的排序操作，直到子序列为空或只剩一个元素为止。这样的排序方法是 ( C )。

A. 选择排序

B. 直接插入排序

C. 快速排序 D. 起泡排序

9. 对5个不同的数据元素进行直接插入排序，最多需要进行 ( B ) 次比较。

A. 8 B. 10 C. 15 D. 25

10. 采用折半查找方法进行查找，数据文件应为(A )，且限于( )。

A 有序表 顺序存储结构 B 有序表 链式存储结构 C 随机表 顺序存储结构 D 随机表 链式存储结构

11. 从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其存

放在已排序序列的合适位置，该排序方法称为(A )排序法。

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

12. 就平均查找速度而言，下列几种查找速度从慢至快的关系是( B )

A 顺序 折半 哈西 分块 B 顺序 分块 折半 哈西 C 分块 折半 哈西 顺序 D 顺序 哈西 分块 折半

13. 在下列算法中，( C )算法可能出现下列情况：在最后一趟开始之前，所有的元素都不

在其最终的位置上。

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

14．堆是一个键值序列( K1, K2, …, Kn )，对 I = 1,2…[n/2], 满足(C )

A) Ki <= K2i <= K2i+1 B) Ki < K2i+1 < K2i C) Ki <= K2i 且 Ki <=K2i+1 D) Ki <= K2i 或 Ki <= K2i+1

15．对于关键字序列 {46，58，15，45，90，18，10，62}，其快速排序第一趟的结果是(C )

A) 15 45 18 46 10 62 58 90 B) 10 15 18 45 46 58 62 90 C) 10 18 15 45 46 90 58 62 D) 15 10 18 45 46 62 58 90

16．用某种排序方法对关键字序列（25，84，21，47，15，27，68，35，20）进行排序时，序列的变化情况如下：

20，15，21，25，47，27，68，35，84 15，20，21，25，35，27，47，68，84 15，20，21，25，27，35，47，68，84 则所采用的排序方法是(D )

A．选择排序 B．希尔排序 C．归并排序 D．快速排序 17．下列关键字序列中(D )是堆。

A．16，72，31，23，94，53 C．16，53，23，94，31，72

B．94，23，31，72，16，53 D．16，23，53，31，94，72

18．目前以比较为基础的内部排序方法中，其比较次数与待排序的记录的初始排列状态

无关的是( B )。

A．插入排序

B．直接选择排序

C．快速排序

D．冒泡排序

19．对n个不同的排序码进行冒泡排序，在元素无序的情况下比较的次数为(D )。

A．n+1 B．n C．n-1 D．n(n-1)/2

20.下述几种排序方法中，要求内存量最大的是( C )。

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

21．若将两个各有 n个元素的有序表归并成一个有序表，则最少比较次数是( A )。

A n B 2*n-1 C 2n D n-1

22．已知数据表A中每个元素距其最终位置不远，为节省时间，应采用的算法是( B )。

A. 堆排序

B. 直接插入排序

C. 快速排序

D. 直接选择排序

22．希尔排序法属于哪一种类型的排序法(B )。

A. 交换类排序

B. 插入类排序

C. 选择类排序

D. 建堆排序法

23．对有11个记录的表作简单选择排序，需要比较( C )次关键字。

A. 100

B. 45

C. 55

D. 110

二、填空题

1．在单链表上难以实现的排序方法有 快速排序 、 堆排序 和 希尔排序 。 2．在最坏情况下，冒泡排序的时间复杂度为___O(n2)___。 3．在最坏情况下，堆排序需要比较的次数为___nlog2n___。

4．数据文件最重要的操作除了插入、删除、修改和查找外，还有___排序______。

三、判断题

1．二路归并排序的核心操作是将两个有序序列合并成一个有序序列。( R ) 2．不稳定的排序算法有冒泡排序、快速排序、堆排序、直接排序。( W ) 3．哈希表的查找效率主要取决于所选择的哈希函数与处理冲突的方法。( R )

四、操作题

1．给出一组关键字（19，01，26，92，87，11，43，87，21）进行冒泡排序，试列

出每一趟排序后关键字的排列次序，并比较每遍排序所进行的关键字比较次数。 第1趟 01,19,26,87,11,43,87,21,92 第2趟 01,19,26,11,43,87,21,87,92 第3趟 01,19,11,26,43,21,87,87,92 第4趟 01,11,19,26,21,43, 87,87,92 8次 7次 6次 5次 第5趟 01,11,19,21,26, 43, 87,87,92 4次 第6趟 01,11,19,21,26, 43, 87,87,92 3次 第7趟 01,11,19,21,26, 43, 87,87,92 2次 第8趟 01,11,19,21,26, 43, 87,87,92 1次 2．设待排序序列为 {10, 18, 4, 3, 6, 12, 1, 9, 15, 8}，请给出用希尔排序每一趟的结果。增量序列取为5, 3, 2, 1。

10, 18, 4, 3, 6, 12, 1, 9, 15, 8 d=5 10,1,4,3,6,12,18,9,15,8 d=3 3,1,4,8,6,12,10,9,15,18 d=2 3,1,4,8,6,9,10,12,15,18 d=1 1,3,4,6,8,9,10,12,15,18

3．对于给定键值： 83 ， 40 ， 63 ， 12 ， 35 ， 90 ， 65, 画出堆排序各趟排序的结果。

4．若对序列(49，38，65，97，76，13，27，50)采用选择排序法排序，则各趟结束后序列。

第1趟 13 ,38，65，97，76，49，27，50 第2趟 13,27, 65，97，76，49，38，50 第3趟 13,27,38，97，76，49，65，50 第4趟 13,27,38，49，76，97，65，50 第5趟 13,27,38，49，50，97，65，76 第6趟 13,27,38，49，50，65,97,76 第7趟 13,27,38，49，50，65,76,97