题目

在外排序中，利用败者树对初始为升序的归并段进行多路归并，败者树中记录"冠军"的结点保存的是（ ）。

错因

A

把多路归并的"取出方向"搞反了。所有归并段都是升序的，归并要从 m 个段当前的头部里挑最小元素输出（这样才能维持输出序列的升序），不是挑最大。冠军 = 当前轮次的最小元素所在段。

B

方向对了——确实围绕"最小"——但败者树的所有内部结点（包括存放冠军的 top 结点）保存的都是"归并段号"，不是关键字本身。关键字只存在外部结点（叶子）里。这样设计的好处是：冠军段输出一个元素后，要从同段补一个新元素再调整树，按段号能直接定位回叶子继续操作。

C

意识到结点里存的是"段号"是对的，但方向选错——多路归并取最小不取最大。把"败者"留下、"胜者"向上的图景与"最大"绑在一起，没有把"升序段 → 取最小 → 维持输出升序"这条线串起来。

总解析

为什么用败者树？

m 路归并中每输出一个元素就要从 m 个段头里重新挑最小。朴素做法每轮要做 m−1 次比较；败者树把这一步压到 次：每次只需沿着"刚输出元素的那一片叶子 → 根"这条路径，与沿途已记录的"败者"对比一次，就能决定新的冠军。

结构约定（这道题的关键）：

• 外部结点（叶子）：每段当前的头部关键字（或指向段头部的引用）。
• 内部结点：每次两两比较中的"败者"对应的归并段号——记败者，让胜者继续向上比。
• 树顶（top）结点：最终胜出的"冠军"对应的归并段号。

注意全树内部结点（含 top）存的都是"段号"，关键字本身只在叶子里。

为什么记败者而不记胜者？

冠军段输出一个元素后，需要从该段补充下一个元素，再重新决出新冠军。补元素后只有"该叶子 → 根"这一条路径上的胜负关系会变，路径外的败者全部不动。如果记的是胜者，路径外的胜者也会跟着翻转，反而要更新更多结点；记败者刚好让"沿路再比一遍"就能更新正确，达成 。

逐项判断：

选项	取最小	存段号	对错
A. 最大关键字	✗	✗	✗
B. 最小关键字	✓	✗（存的是段号，不是关键字）	✗
C. 最大关键字所在的归并段号	✗	✓	✗
D. 最小关键字所在的归并段号	✓	✓	✓

最终答案是 D（最小关键字所在的归并段号）。