反任何一个期限，连续使用这种方法，??就可转换成?且不违反任何一个期限，定理得证。
29．① 已知n-1个元素已按min-堆的结构形式存放在A(1),?,A(n-1)。现要将另一存放在A(n)的元素和A(1:n-1)中元素一起构成一个具有n个元素的min-堆。对此写一个计算时间为O(logn)的算法。
② 在A(1:n)中存放着一个min-堆，写一个从堆顶A(1)删去最小元素后将其余元素调整成min-堆的算法，要求这新的堆存放在A(1:n-1)中，且算法时间为O(logn).
③ 利用②所写出的算法，写一个对n个元素按非增次序分类的堆分类算法。分析这个算法的计算复杂度。
解：① procedure INSERT(A,n) integer i, j, k
j←n ; i←?n/2? while i≥1 and A[i]>A[j] do k←A[j];
A[j]←A[i]; A[i]←k
j←i ;
i←?i/2?
repeat end INSERT
② procedure RESTORE(A,l,n) integer i, j, k x←A[n];
A[n]←A[l]
i←1 j←2*i
while j≤n-1 do
if (j< n-1) and (A[j]> A[j+1])
then j←j+1 endif
if (x>A[j])
then A[i]←A[j]; i←j;j←2*i else i←n endif repeat end RESTORE
③ procedure HEAPSORT(A,n) integer i, k
for i=?n/2? to 1 step –1 do
RESTORE(A, i, n) repeat
for i=n to 2 step –1 do
k←A[1]; A[1]←A[i]; A[i]←k RESTORE(A, 1, i-1) repeat
end HEAPSORT
30．① 证明如果一棵树的所有内部节点的度都为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，即存在符合性质的树。
综合上述结果可知,命题成立。
31．① 证明如果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)的最优归并树。
32．对n=7, ( p1,...,p7)=(35，30，25，20，15，10，5) 和( d1,...,d7)=(4，2，4，3，4，8，3)的有限期作业调度问题使用教材中作业排序的更快算法求解最优解。（要求描述时间片数组F（i）和对应集合的变化过程）
33．当作业数n＝7，
（p1，p2，??，p7）＝（7, 6, 5, 4, 3, 2, 1） （d1，d2，??，d7）＝（4, 2, 4, 3, 1, 4, 6）
时，利用算法5.5（作业排序的更快算法）求解上述作业排序问题的最优解。（要求按步骤运行并给出集合树的变化情况及当前最优解）。
34．举例说明最优性原理是什么？
最优性原理是指，过程的最优决策序列具有如下性质：无论过程的初始状态和初始决策是什么，其余的决策都必须相对于初始决策所产生的状态构成一个最优决策序列。
例如：
35．举例说明支配规则的内容。
36．由最优性原理指出的过程的最优决策序列具有的性质是什么？
答：无论过程的初始状态和初始决策是什么，其余的决策都必须相对于初始决策所产生的状态构成一个最优决策序列。
37．什么样的决策过程构成多阶段决策过程？
答：活动过程可以分为若干个阶段，而且在任一阶段后的行为都仅依赖于i 阶段的过程状态，而与i 阶段之前如何到达这种状态的方式无关，这样的过程就构成一个多阶段决策过程。
38．使用动态规划求解问题的前提条件是什么？试举出两个例子，这两个例子都可以看作是多阶段决策问题，但一个例子可以用动态规划来解，而另一个例子不能用动态规划求解。
39．修改过程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) 40.已知图的邻接矩阵
?0?2??9??8103??15027???? 2??0?（1）按照每对结点间的最短路径算法ALL-PATH，求每对结点间的最短路径长度矩阵A4
（2）求路径结点矩阵P。P(i,j)表示从i到j的最短路径的第一步结点。
相关推荐：
loading