【正确答案】 D

【答案解析】解析：判断是否需要补充空归并段。如何判断?设度为0的结点有n ₀ 个，度为m的结点有n _m 个，则对严格m叉树有n ₀ =(m-1)n _m +1，由此可以得出n _m =(n ₀ -1)／m-1。 (1)如果(n ₀ -1)mod(m-1)=0，则说明这n ₀ 个叶子结点(初始归并段)正好可以构造m叉归并树。此时，内结点有n _m 个。 (2)如果(n ₀ -1)mod(m-1)=u≠0，则说明这n ₀ 个叶子结点，其中有u个结点多余，不能被包含在m叉归并树内。为了构造包含所有n ₀ 个初始归并段的m叉归并树，应在原有的n _m 个内结点中再增加一个内结点。它在归并树中代替了一个叶子结点的位置，被代替的叶子结点加上刚才多出的u个叶子结点，再加上m-u-1个空归并段，就可以建立归并树。 按照以上步骤：因为(31-1)mod(5-1)≠0，所以需要增设空归并段。需要增设5-2-1=2个空归并段。接下来就比较简单了，仿造赫夫曼树的构造方法，来构造5-路最佳归并树，如图3-11所示。