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

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

A、置换-选择排序用于生成外排序的初始归并段

B、置换-选择排序是完成将一个磁盘文件排列成有序文件有效的外排序算法

C、置换-选择排序生成的初始归并段的长度平均是内存工作区的2倍

D、置换-选择排序是一些不等长的初始归并段

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

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

设有若干个初始归并段，其平均长度为2M，现进行k=8路归并排序，并最多只允许扫描两遍，则外排序能处理的文件的平均长度最多是（)。

110，21，40。现采用置换-选择方法生成初始归并段，并假设内存工作区可同时容纳5个记录，请画出选择的过程

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

(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)。编写一个算法，实现上述利用堆的置换-选择排序.

设初始归并段为（10，15，31，∞)，（9，20，∞)，（22，34，37，∞)，（6，15，42，∞)，（12，37，∞)，（84，95，∞)，试利用

败者树进行k路归并，手工给出执行选择最小的5个排序码的过程。

设计算机中用于外排序的内存工作区可容纳450个记录，在磁盘上每个物理记录可放75个记录。应采用（)路平衡归并排序。

出表示归并过程的最佳归并树，并计算该归并树的带权路径长度WPL。

试问：

(1)可以建立多少个初始归并段？每个初始归并段有多少个记录？存放于多少个块中？

(2)应采用几路归并？请写出归并过程及每趟需要读写磁盘的块数。

设在磁盘上存放有375000个记录，做5路平衡归并排序，内存工作区能够容纳600个记录，为把所有记录排好序，需要做（)趟归并排序。

A、3

B、4

C、5

D、6