单元测验10 一．判断题（下列各题，正确的请在前面的括号内打√；错误的打╳ ） （ㄨ）（1）如果某种排序算法不稳定，则该排序方法就没有实用价值。 （√）（2）希尔排序是不稳定的排序。 （ㄨ）（3）冒泡排序是不稳定的排序。 （√）（4）对 n 个记录的进行快速排序，所需要的平均时间是 O(nlog2n)。 （ㄨ）（5）堆排序所需的时间与待排序的记录个数无关。 （√）（6）当待排序的元素个数很多时，为了交换元素的位置要占用较多的时间，这是影响时间复杂度的主要因素。 （ㄨ）（7）快速排序在任何情况下都比其它排序方法速度快。 （√）（8）对快速排序来说，初始序列为正序或反序都是最坏情况。 （√）（9）采用归并排序可以实现外排序。 （√）（10）采用希尔方法排序时，若关键字的排列杂乱无序，则效率最高。 （√）（11）快速排序算法在每一趟排序中都能找到一个元素放在其最终位置上。 （√）（12）冒泡排序的时间复杂度是 O（n2）。 二．填空题 （1） 大多数排序算法都有两个基本的操作： 比较 和移动。 （2） 评价排序算法优劣的主要标准是 时间复杂度 和算法所需的附加空间。 （3） 根据 被 处 理 的数据 在计 算机 中使 用不同 的存 储 设 备 ，排序可分 为： 内排序 和外排序。 （4） 外排序是指 在排序过 程 中，数据 的主要部 分 存 放在计 算机 的 外存 中。 （5） 对 n 个关键字进行冒泡排序，其可能的最小 比较次 数为： n-1 次 。 （6） 在最坏情况下，在第 i 趟直 接 插 入 排序中，要进行 i-1 次 关键字的比较。 （7） 对 n 个关键字进行冒泡排序，时间复杂度为 O(n2) 。 （8） 快速排序在最坏情况下的时间复杂度是 O(n2) 。 （9） 对于 n 个记录的集 合 进行归并排序，所需要的平均时间为： O(log2n) 。 （10） 对于 n 个记录的集 合 进行归并排序，所需要的附加空间是 O(n) 。 （11） 若原 始数据 接 近 无序，则选 用 快速排序 最好 。 （12） 在排序前，关键字值相 等 的不同 记录，排序后 相 对位置保 持 不变 的排序方法，称 为稳定排序方法。 （13） 在插 入 排序和选 择 排序中，若初始数据 基本正序，则选 用 插 入 排序 较好 。 （14） 当增 量 为 1 时，该趟希尔排序与 直 接 插 入 排序基本一致 。 （15） 第 一趟排序后 ，序列中键值最大的记录交换...
