第 9 章 习题
1 、 填空题
1、在对一组记录（ 54 ，38 ，96 ，23 ，15 ，72 ，60 ，45 ，83 ）进行直接插入 排序时，当把第7个记录60插入到有序表时，为寻找插入位置需比较 次。
2、大多数排序的算法都有两个基本的操作： 和 。
3 、在堆排序和快速排序中，若原始记录接近正序或反序，则选用 ，
若原始记录无序，则最好选用 。
4、每次从无序表中取出一个元素，把它插入到有序序列的适当位置，使其 仍然有序，直至把所有元素都插入到有序序列中，这种排序方法称为 。
5 、 对 关 键 字 序 列 {45 ， 23 ， 12 ， 67 ， 34} ， 对 应 的 大 根 堆 为
。
2 、 选择题
1、在待排序序列基本有序的前提下，效率最高的排序方法是（ ）。
A． 快速排序 B． 归并排序 C． 直接插入排序 D． 选择排序
2 、堆的形状是一棵（ ）。
A． 二叉排序树 B． 满二叉树 C． 完全二叉树 D． 平衡二叉树
3 、用冒泡排序对 n 个数据进行排序，第一趟共比较（ ）对元素。
A． 1 B． 2 C． n-1 D． n
4、设待排序元素关键字是{2，4， 1 ，3 ，7， 1’}，应用一种排序方法进行递 增排序的结果是{1 ’， 1，2 ，3，4 ，7}，则所选用的排序方法是（ ）。
A． 直接插入 B． 直接选择 C． 冒泡 D． 二路归并
5、快速排序每次划分的效果好坏和以下哪种因素有直接关系（ ）。
A． 关键字的排列情况 B． 数据元素的个数
C． 关键字值的最大值 D． 轴的相对大小
3 、 判断题
1 、对 于 n 个 记 录 的 集 合 进 行 冒 泡 排 序 ， 所 需 要 的 平 均 时 间 是 O(n) 。 ( )
2、快速排序是一种稳定的排序方法。 ( )
3、快速排序算法在每趟排序中都能找到一个元素放到其最终位置上。 ( )
4、快速排序是基于比较的内部排序方法中最好的。 ( ) 5 、 当待排序记录规模较小时 ， 选用直接插入排序算法比较好 。
( )
四、应用题
1、对于给定的数据（ 12 ，5 ，9，20 ，6 ，31，24 ），分别写出用直接插入排 序和冒泡排序的各趟结果。
2 、有一组关键字序列（ 41 ，34 ，53 ，38，26 ，74 ），采用快速排序方法由 大到小进行排序，请写出每趟排序的结果。
3、判断下列两序列是否为堆，如不是，将其调整为堆。
（ 1 ）（ 3， 10， 12，22 ，36， 18，28，40 ）
（ 2 ）（ 5 ，8， 11， 15，23，20 ，32 ，7 ） 五、算法设计题
1、编写一个双向冒泡排序算法，即在排序过程中交替改变扫描方向。题目要 求：数据从数组的0单元放起。
2、数组中的元素有正整数或负整数。设计一个算法，将正整数和负整数分开 使数组的前一半为负整数，后一半为正整数。不要求对这些元素排序，要求尽量 减少交换次数。
评论0