(中国铁道出版社数据结构第二版单元10练习参考答案.docVIP

单元测验10 一．判断题（下列各题，正确的请在前面的括号内打√；错误的打╳ ） （ㄨ）（1）如果某种排序算法不稳定，则该排序方法就没有实用价值。 （√）（2）希尔排序是不稳定的排序。 （ㄨ）（3）冒泡排序是不稳定的排序。 （√）（4）对n个记录的进行快速排序，所需要的平均时间是O(nlog2n)。 （ㄨ）（5）堆排序所需的时间与待排序的记录个数无关。 （√）（6）当待排序的元素个数很多时，为了交换元素的位置要占用较多的时间，这是影响时间复杂度的主要因素。 （ㄨ）（7）快速排序在任何情况下都比其它排序方法速度快。 （√）（8）对快速排序来说，初始序列为正序或反序都是最坏情况。 （√）（9）采用归并排序可以实现外排序。 （√）（10）采用希尔方法排序时，若关键字的排列杂乱无序，则效率最高。 （√）（11）快速排序算法在每一趟排序中都能找到一个元素放在其最终位置上。 （√）（12）冒泡排序的时间复杂度是O（n2）。 二．填空题 大多数排序算法都有两个基本的操作： 比较 和移动。 评价排序算法优劣的主要标准是 时间复杂度 和算法所需的附加空间。 根据被处理的数据在计算机中使用不同的存储设备，排序可分为： 内排序 和外排序。 外排序是指在排序过程中，数据的主要部分存放在计算机的 外存 中。 对n个关键字进行冒泡排序，其可能的最小比较次数为： n-1 次。 在最坏情况下，在第i趟直接插入排序中，要进行 i-1 次关键字的比较。 对n个关键字进行冒泡排序，时间复杂度为 O(n2) 。 快速排序在最坏情况下的时间复杂度是 O(n2) 。 对于n个记录的集合进行归并排序，所需要的平均时间为： O(log2n) 。 对于n个记录的集合进行归并排序，所需要的附加空间是 O(n) 。 若原始数据接近无序，则选用 快速排序 最好。 在排序前，关键字值相等的不同记录，排序后相对位置保持 不变 的排序方法，称为稳定排序方法。 在插入排序和选择排序中，若初始数据基本正序，则选用 插入排序 较好。 当增量为1时，该趟希尔排序与 直接插入 排序基本一致。 第一趟排序后，序列中键值最大的记录交换到最后的排序算法是 冒泡排序 。 依次将每个记录插入到一个有序的子文件中的排序方法称为 直接插入 排序。 在插入排序、选择排序和归并排序中，排序是不稳定的为： 选择排序 。 在对一组记录（54，38，96，23，15，72，60，45，83）进行直接插入排序时，当把第7个记录60插入到有序表时，为寻找插入位置需比较 3 次。 两个序列分别为： L1={25，57，48，37，92，86，12，33} L2={25，37，33，12，48，57，86，92}。 用冒泡排序法对L1和L2进行排序，交换次数较少的是序列： L2 。 （20）对一组记录（54，35，96，21，12，72，60，44，80）进行直接选择排序时，第四次选择和交换后，未排序记录是 54，72，60，96，80 。 三．选择题 （1）排序是根据（ A ）的大小重新安排各元素的顺序。 A．关键字 B．数组 C．元素件 D．结点 （2）评价排序算法好坏的标准主要是（ D ）。 A．执行时间 B．辅助空间 C．算法本身的复杂度 D．执行时间和所需的辅助空间 （3）直接插入排序的方法是（ B ）的排序方法。 A．不稳定 B．稳定 C．外部 D．选择 （4）直接插入排序的方法要求被排序的数据（ B ）存储。 A．必须链表 B．必须顺序 C．顺序或链表 D．可以任意 （5）排序方法中，从无序序列中选择关键字最小的记录，将其与无序区（初始为空）的第一个记录交换的排序方法，称为 ( D )。 A．希尔排序 B．归并排序 C．插入排序 D. 选择排序 （6）每次把待排序方的区间划分为左、右两个区间，其中左区间中元素的值不大于基准元素的值，右区间中元素的值不小于基准元素的值，此种排序方法叫做（ C ）。 A．冒泡排序 B．堆排序 C．快速排序 D. 归并排序 （7）快速排序在（ C ）情况下最易发挥其长处。 A．待排序的