end HEAPSORT 5.11．① 证明如果一棵树的所有内部节点的度都为k，则外部节点数n满足n mod (k-1)=1.
② 证明对于满足 n mod (k-1)=1的正整数n，存在一棵具有n个外部节点的k元树T(在一棵k元树中，每个节点的度至多为k)。进而证明T中所有内部节点的度为k.
证明：① 设某棵树内部节点的个数是m，外部结点的个数是n，边的条数是e，
则有
e=m+n-1和 e=mk
mk=m+n-1 ? (k-1)m=n-1 ? n mod (k-1)=1
② 利用数学归纳法。
当n=1时，存在外部结点数目为1的k元树T，并且T中内部结点的度为
k；
假设当 n≤m，且满足n mod (k-1)=1时，存在一棵具有n个外部结点的
k元树T，且所有内部结点的度为k；
我们将外部结点数为n(n为满足n≤m，且n mod (k-1)=1的最大值)的符
合上述性质的树T中某个外部结点用内部结点a替代，且结点a生出k个外部结点，易知新生成的树T’中外部结点的数目为n+(k-1)，显然n为满足n mod (k-1)=1，且比m大的最小整数，而树T’每个内结点的度为k，即存在符合性质的树。
综合上述结果可知,命题成立。
5.12．① 证明如果n mod (k-1)=1，则在定理5.4后面所描述的贪心规则对于所有的（q1,q2,?, qn）生成一棵最优的k元归并树。
② 当（q1,q2,?, q11）=（3,7,8,9,15,16,18,20,23,25,28）时，画出使用这一规则所得到的最优3元归并树。 解：①通过数学归纳法证明：
对于n=1，返回一棵没有内部结点的树且这棵树显然是最优的。
假定该算法对于（q1,q2,?, qm），其中m =(k-1)s+1 (0 ≤ s)，都生
成一棵最优树.
则只需证明对于(q1,q2,?, qn)，其中n=(k-1)(s+1)+1，也能生成最优
树即可。
不失一般性，假定q1≤q2≤?≤qn，且q1,q2,?, qk是算法所找到的k
棵树的WEIGHT信息段的值。于是q1,q2,?, qk棵生成子树T，设T?是一棵对于（q1,q2,?, qn）的最优k元归并树。设P是距离根最远的一个内部结点。如果P的k个儿子不是q1,q2,?, qk，则可以用q1,q2,?, qk和P现在的儿子进行交换，这样不增加T?的带权外部路径长度。因此T也是一棵最优归并树中的子
树。于是在T?中如果用其权为q1+q2+?+qk的一个外部结点来代换T，则所生成的树T??是关于(q1+q2+?+qk,qk?1,?,qn)的一棵最优归并树。由归纳假设，在使用其权为q1+q2+?+qk的那个外部结点代换了T以后，过程TREE转化成去求取一棵关于(q1+q2+?+qk,qk?1,?,qn)的最优归并树。因此TREE生成一棵关于(q1,q2,?, qn)的最优归并树。
6.2．修改过程ALL_PATHS，使其输出每对结点（i,j）间的最短路径，这个新算法的时间和空间复杂度是多少？
Procedure ShortestPath(COST, n, A, Max)
integer i , j, k
real COST(n, n), A(n, n), Path(n, n), Max
for i←1 to n do
for j←1 to n do
A(i ,j)←COST(i ,j)
if i≠j and A(i, j)≠Max then Path(i, j )←j else Path(i, j)←0 endif
repeat