排序自测题答案.doc

第9章 排序 自测卷 姓名 班级

题号
一
二
三
四
五
总分
题分
24
18
36
8
14
100
得分

一、填空题（每空1分，共24分）
1. 大多数排序算法都有两个基本的操作： 比较 和 移动 。
2. 在对一组记录（54，38，96，23，15，72，60，45，83）进行直接插入排序时，当把第7个记录60插入到有序表时，为寻找插入位置至少需比较 6 次。
3. 设要将序列（Q, H, C, Y, P, A, M, S, R, D, F, X）中的关键码按字母序的升序重新排列，则：
冒泡排序一趟扫描的结果是 H C Q P A M S R D F X Y ；
初始步长为4的希尔（shell）排序一趟的结果是 P A C S Q H F X R D M Y ；
二路归并排序一趟扫描的结果是 H Q C Y A P M S D R F X；
快速排序一趟扫描的结果是 F H C D P A M Q R S Y X ；
堆排序初始建堆的结果是 A D C R F Q M S Y P H X 。

二、单项选择题（每小题1分，共18分）
（ C ）1． 排序方法中，从未排序序列中依次取出元素与已排序序列（初始时为空）中的元素进行比较，将其放入已排序序列的正确位置上的方法，称为
Ａ. 希尔排序 Ｂ. 冒泡排序 Ｃ. 插入排序 Ｄ. 选择排序
（ D ）2．从未排序序列中挑选元素，并将其依次插入已排序序列（初始时为空）的一端的方法，称为
（ C ）3．快速排序在下列哪种情况下最易发挥其长处。
Ａ. 被排序的数据中含有多个相同排序码 Ｂ. 被排序的数据已基本有序
Ｃ. 被排序的数据完全无序 Ｄ. 被排序的数据中的最大值和最小值相差悬殊
（ C ）4．若一组记录的排序码为（46, 79, 56, 38, 40, 84），则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为
Ａ. 38, 40, 46, 56, 79, 84 Ｂ. 40, 38, 46 , 79, 56, 84
Ｃ. 40, 38，46, 56, 79, 84 Ｄ. 40, 38, 46, 84, 56, 79
（ D ）5．下列关键字序列中， 是堆。
Ａ. 16, 72, 31, 23, 94, 53 Ｂ. 94, 23, 31, 72, 16, 53
Ｃ. 16, 53, 23, 94，31, 72 Ｄ. 16, 23, 53, 31, 94, 72
（ B ）6．堆是一种 排序。
Ａ. 插入 Ｂ.选择 Ｃ. 交换 Ｄ. 归并
（ C ）7．堆的形状是一棵
Ａ. 二叉排序树 Ｂ.满二叉树 Ｃ. 完全二叉树 Ｄ. 平衡二叉树
（ C ）8． 下述几种排序方法中，要求内存最大的是
Ａ. 插入排序 Ｂ.快速排序 Ｃ. 归并排序 Ｄ. 选择排序
1