18 个初始归并段进行 5 路平衡归并，需要增加（ ）个虚拟归并段。

A. 1 B. 2 C. 3 D. 4

外部排序 操作系统概念

[tag_link]

正确答案：C

在5路平衡归并中，每次归并操作都需要恰好5个归并段作为输入，以确保归并过程平衡。

初始归并段数为18个，但归并过程中，每次归并会减少归并段的数量。 具体来说，每归并一次，5个归并段合并为1个新段，因此段数减少4个（即k-1，其中k=5）。

设归并次数为m，最终剩下1个归并段，则有关系式：18 - 4m = 1。 计算得m = (18-1)/4 = 17/4 = 4.25，不是整数。 这意味着如果不添加虚拟归并段，无法通过整数次归并完成，且最后一次归并可能不足5路，破坏平衡性。

为了使得归并次数为整数且每次归并都是5路，需要添加d个虚拟归并段，使总段数S’ = 18 + d，并满足(S’ - 1)能被4整除（即归并次数为整数）。 计算(18 + d - 1) = 17 + d，需使17 + d是4的倍数。 17除以4余1，因此d最小为3（因1+3=4可被4整除）。 此时S’ = 21，归并次数m = (21-1)/4 = 5，均为整数。

验证归并过程：添加3个虚拟段后，总段数21，进行5次归并，每次归并5个段（虚拟段视为空段，不影响结果），最终得到1个有序文件，符合5路平衡归并要求。 因此，需要增加3个虚拟归并段。