【正确答案】 C

【答案解析】解析：A:影响外部排序时间的主要因素就是内存与外设交换信息的总次数，所以A错误。 B:外部排序也是在内存上进行排序，只不过需要分为多步而已，所以B错误。 C:从败者树的构建方式可知，败者树是一棵完全二叉树，所以C正确。 补充知识点：败者树和堆有什么区别？ 解析：外部排序中败者树和堆排序的区别在于： (1)败者树是在双亲结点中记下刚进行完的这场比赛的败者，而让胜者去参加更加高一层的比赛，便可得到一棵败者树。而堆排序可看作一种胜者树，即双亲结点表示其左右孩子中的胜者。 (2)在败者树中，参加比较的n个关键字全部为叶子结点，双亲即为其左、右子女的败者，败者树中结点总数为2n—1，加上冠军结点恰好为2n。而堆是由n个关键字组成的完全二叉树，每个关键字作为树中一个结点，根是n个关键字中的胜者，树中结点总数为n。 D:使用置换一选择排序得到的初始归并段长度不一定相等，从最佳归并树构造赫夫曼树的过程也可以得到答案，所以D错误。 外部排序的基本过程： 基于磁盘进行的排序多使用归并排序方法。其排序过程主要分为两个阶段： (1)建立用于外部排序的内存缓冲区。根据它们的大小将输入文件划分为若干段，用某种内排序方法对各段进行排序。经过排序的段叫作初始归并段。当它们生成后就被写到外存中。 (2)按归并树模式，把(1)生成的初始归并段加以归并，一趟趟扩大归并段和减少归并段数，直到最后归并成一个大归并段为止。 例如：设有一个包含4500个记录的输入文件，现用一台其内存至多可容纳750个记录的计算机对该文件进行排序。输入文件放在磁盘上，磁盘每个页块可容纳250个记录，这样全部记录可存储在4500/250=18个块中。输出文件也放在磁盘上，用以存放归并结果。由于内存中可用于排序的存储区域能容纳750个记录，所以内存中恰好能存3个块的记录。在外排序一开始，把1 8块记录每3块一组读入内存。利用某种内排序方法进行内排序，形成初始归并段，再写回外存。总共可得到6个初始归并段。然后一趟一趟进行归并排序，如图1—10所示。