【正确答案】 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。 举一个最简单的例子如下。