试题出自试卷《408计算机学科专业基础阶段测试卷（二）》

答：
（1）生成了三个初始段，分别为：
① 37，51，63，92，94，99；
② 14，15，23，31，48，56，60，90，166；
③ 8，17，42，100。

（2）对任意m，生成的第一个初始归并段最大可能长度为n，最小可能长度为m。

（1）假设初始待排序文件为输入文件FI，初始归并段文件为输出文件FO，内存工作区为WA，FO和WA初始为空，并设内存工作区WA的容量可容纳w个记录。则置换-选择排序的操作过程为：
① 从FI输入w个记录到缓冲区WA。
② 从WA中选出其中关键字取最小值的记录，记为MINIMAX记录。
③ 将MINIMAX记录输出到FO中去。
④ 若FI不空，则从FI输入下一个记录到WA中。
⑤ 从WA中所有比MINIMAX记录的关键字大的记录中选出最小关键字记录，作为新的MINIMAX记录。
⑥ 重复(3)~(5)，直到在WA中选不出新的MINIMAX为止，由此得到一个初始归并段，输出归并段结束标志到FO中。
⑦ 重复(2)~(6)，直到WA为空，由此得到全部初始归并段。
根据上述思想，对题干所示的记录进行排序的过程如下：

（2）对任意m，生成的第一个初始归并段最大可能长度为n。若FI中的记录为升序序列，则初始归并段的长度即为n。在最坏情况下，初始时进入WA的m个记录是一定能被输出到第一个归并段中的，因此最小可能长度为m。