下面关于置换-选择排序的叙述中不正确的是()。

设内存工作区的容量为w，则置换-选择排序所得到的初始归并段的平均长度为（)。

内存工作区可容纳的记录数。方法实现的步骤

(1)建立初始堆.

①从输入文件中输入p个记录，建立大小为p的堆。

②为第一个初始归并段选择一个适当的磁盘文件作为输出文件。

(2)置换-选择。

内存工作区存在两个堆：当前堆和新堆，新堆紧接在当前堆后存放，总大小为p。

①输出当前堆的堆顶记录到选定的输出文件。

②从输入文件中输入下一个记录。若该记录排序码的值不小于刚输出记录排序码的值，则由它取代堆顶记录，并调整当前堆。若该记录排序码的值小于刚输出记录的排序码的值，则由当前堆的堆底记录取代堆顶记录，当前堆的大小减1。新输入的记录存放在当前堆的原堆底记录的位置上，成为新堆的一个记录。

③如果新堆的记录个数大于「p/2，应着手调整新堆;如果新堆中已有p个记录，表示当前堆已输出完毕，当前的初始归并段结束、应开始创建下一个初始归并段，因此必须另为新堆选择一个磁盘文件作为输出文件。

④重复步骤②~③，直到输入文件输入完毕。

(3)输出剩余记录。

①输出当前堆中的剩余记录，并对输出边调整。

②将内存工作区中的新堆作为最后一个初始归并段输出。

设p=5，排序码序列为(54，15，62，10，77，24，29，20，59，43，69，31，47，38，12，18，51，27)，执行置换选择排序的结果如图10-19(a)~图10-19(g)所示.

生成的3个初始归并段为(10，15，24，29，54，59，62，69，77)，(20、31，38，43，47，51)，(12，18，27)。编写一个算法，实现上述利用堆的置换-选择排序.

一个经过置换-选择排序得到的输出文件再进行一次置换-选择操作，文件将产生怎样的变化？

设一个记录占用64字节，一个物理记录（即页块)大小为2048-2K字节。又设内存可用工作区大小为1MB（

不含用于I/O缓冲区、程序变量等的存储空间)。使用置换-选择排序生成初始归并段和多路平衡归并进行外排序。要求平衡归并趟数只允许2趟。那么，能够得到的有序文件最长为多少？详细说明计算过程。

A.插入

B.选择

C.冒泡

D.归并

最佳归并树在外排序中的作用是（)。

A、完成k路归并排序

B、设计k路归并排序的优化方案

C、产生初始归并段

D、与锦标赛树的作用类似

设有5个初始归并段，每个归并段有20个记录，采用5路平衡归并排序，若不采用败者树，使用传统的顺序选小（参看选择排序算法)的方法，总的比较次数是（)次。

A、20

B、258

C、396

D、500

若排序码是非负整数，快速排序、归并排序、堆排序和基数排序哪一种最快？若要求辅助空间为O（1)，则应选择哪一种？若要求排序是稳定的且排序码是浮点数，则应选择哪一种？

按排序策略分类，起泡排序属于（①)。对n个元素的序列进行排序时，如果待排序元素序列的初始排列已

经全部有序，则起泡排序过程中需进行(②)次元素值的比较，(③)次元素值的交换。如果待排序元素序列的初始排列完全逆序，则起泡排序过程中需进行(④)次元素值的比较，(⑤)次元素的交换。(1)供选择的答案：A、插入排序;B、选择排序;C、交换排序;D、分配排序;E、归并排序.

结束后关键字序列的状态。

①直接插入排序;

②折半插入排序;

③希尔排序(增量选取5，3，1);

④冒泡排序;

⑤快速排序;

⑥简单选择排序;

⑦二路归并排序。