设外存上有 120 个初始归并段，进行 12 路归并时，为实现最佳归并，需要补充的虚段个数是（ ）。

外部排序

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

[tag_link]

正确答案：B

在 12 路归并树中只存在度为 0 和度为 12 的结点，设度为 0 的结点数、度为 12 的结点数和要补充的结点数分别为n0，n12，n补，则有n0 =120+n补，n0 =(12−1)n12 +1，可得n12 =(120−1+n补 )/(12−1)。由于结点数n12为整数，所以 n 补是使上式整除的最小整数，求得n补 =2，所以答案选 B。