若对 29 个记录只进行三趟多路平衡归并，则选取的归并路数至少是（ ）。

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

操作系统概念 外部排序

[tag_link]

正确答案：C

在多路平衡归并中，归并趟数

$t$ 与归并路数 $k$ 、初始归并段数 $m$ 之间的关系为：经过 $t$ 趟归并，最多能处理 $k^t$ 个初始归并段，即需满足

$$k^t\ge m.$$

本题中，对 29 个记录排序，初始归并段数 $m=29$ ，要求只进行三趟归并（ $t=3$ ），因此需满足

$$k^3\ge 29.$$

计算各选项的立方：

23=8«/span>29,33=27«/span>29,43=64≥29,53=125≥29.

若 $k=3$ ，则 27«/span>29 ，需至少四趟归并，不符合“只进行三趟”的要求；

$k=4$ 时， $64\ge 29$ ，可在三趟内完成。 因此归并路数至少为 4。