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

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

A、20

B、250

C、300

D、500

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

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

试问：

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

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

多路平衡归并排序是外排序的主要方法，试问：（1)多路平衡归并排序包括哪两个相对独立的阶段？每

多路平衡归并排序是外排序的主要方法，试问：

(1)多路平衡归并排序包括哪两个相对独立的阶段？每个阶段完成何种工作？

(2)完成下列操作：

①补充完整如图10-18所示的败者树.

②输出全局优胜者，并重构败者树。

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

A、完成k路归并排序

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

C、产生初始归并段

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

对包含64个初始归并段执行4路平衡归并排序，需将待排序的文件中的每个记录从磁盘读写（)次（读和写各计1次)。

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

号，败者树的内结点存放子女结点两两比较的败者的归并段编号，内结点编号也是0，1，…，k-1.编号为i的外结点的父结点的编号为()。

A、i/2」

B、(i-1)/2」

C、(i+k)/2」

D、(i+k-1)/2」

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

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

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

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

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

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