【正确答案】 C

【答案解析】[解析] 考查外部排序，如何判断添加虚段的数目。虚段产生的原因是初始归并段不足以构成严格m叉树，需添加长度为0的“虚段”。按照Huffman原则，权为0的叶子应该离树根最远，所以虚段一般都在最后一层，作为叶子结点。设度为0的结点有n ₀ 个，度为m的结点n _m 个，则对严格m叉树，有n ₀ =(m-1)n _m +1，由此得n _m =(n ₀ -1)/(m-1)。
(1)如果(n ₀ -1)%(m-1)=0。则说明这n ₀ 个叶结点(初始归并段)正好可构成严格m叉树。
(2)如果(n ₀ -1)%(m-1)=u＞0。说明这n ₀ 个叶结点中有u个多余，不能包含在m叉归并树中。
为构造包含所有n ₀ 个初始归并段的m叉归并树，应在原有n _m 个内结点的基础上再增加一个内结点。它在归并树中代替了一个叶结点位置，被代替的叶结点加上刚才多出的u个叶结点，再加上m-u-1个虚段，就可以建立严格m叉树，5-(17%4)-1=3，故选C。
举一个最简单的例子如下。