发布时间 : 星期一 文章《计算机算法基础》第三版 - 课后习题答案更新完毕开始阅读
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
repeat
for k←1 to n do
for i←1 to n do
for j←1 to n do
if A(i,j)>A(i,k)+A(k,j)
then A(i,j)←A(i,k)+A(k,j) Path(i,j)←Path(i,k) endif
repeat repeat
repeat
for i←1 to n do
for j←1 to n do
print(“the path of i to j is ” i ) k←path(i, j) while k≠0 do print( ,k) k←path(k, j) repeat repeat repeat
end ShortestPath
时间复杂度O(n3)，空间复杂度O(n2)
6.4．①证明算法OBST的计算时间是O(n2)。
②在已知根R(i, j)，0≤i < j≤4的情况下写一个构造最优二分检索树T的算法。证明这样的树能在O(n)时间内构造出来。
解：① 将C中元素的加法看做基本运算，则算法OBST的时间复杂性为：
nn?mnn?m??(R(i?1,j)?R(i,j?1)?1)???(R(i?1,i?m)?R(i,i?m?1)?1)?m?2i?0m?2i?0n?m?2(R(n?m?1,n)?R(0,m?1)?n?m?1)?O(n2)
② Procedure BuildTree(m, n, R, Root)
integer R(n,n), k
TreeNode Root, LR, RR k←R(m,n)
if k≠0 then data(Root)←k,
BuileTree(m, k-1, R, LR), BuileTree(k, n, R, RR)
left(Root)←LR, right(Root)←RR
else data(Root)←m, left(Root)←null, right(Root)←null, endif
end BuildTree
时间复杂性分析：T(n)=c+T(k)+T(n-k-1)，此递推式保证算法的时间复杂性为O(n)，也可从递归的角度出发，递归的次数正是结点的个数，而每次递归时间复杂性为常数，所以算法的时间复杂度也为O(n)。
6.8．给出一个使得DKNAP(算法6.7)出现最坏情况的例子，它使得|Si|=2i, 0≤i 解：取(P1,P2,?,Pi,?)=(W1,W2,?,Wi,?)=(20,21,?,2i-1,?) P和W取值相同，使支配原则成立，也就是说不会因为支配原则而删除元素；只要说明不会出现相同元素被删除一个的情形，即可知是最坏的情况。可用归纳法证明此结论。