算法复习题(6)

goto end stop print

45.设n=4, 且( a1,a2,a3,a4)=(do,if,read,while)，已知P(1:4)=(3,3,1,1)和Q(0:4)=(2,3,1,1,1)，使用动态规划方法构造一棵最佳二叉排序树（计算出C、W、R阵的结果）。 解:

?08192532??28121416??01122??071219??37911??0222??????? C=?038? W= ?135? R=?033?

??????031304?????????0?1?0???????

最佳二叉排序树为:

IF DO READ WHILE

46．①证明算法OBST的计算时间是O(n2)。

②在已知根R(i, j)，0≤i < j≤4的情况下写一个构造最优二分检索树T的算法。证明这样的树能在O(n)时间内构造出来。

解：① 将C中元素的加法看做基本运算，则算法OBST的时间复杂性为：

m?2i?0n??(R(i?1,j)?R(i,j?1)?1)???(R(i?1,i?m)?R(i,i?m?1)?1)?m?2i?0nn?mnn?mm?2?(R(n?m?1,n)?R(0,m?1)?n?m?1)?O(n)

2

② 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)。

47.设计一个由设备D1,D2,D3组成的三级系统。每台设备的成本分别为30元、15元和20元，可靠性分别为0.9,0.8和0.5，计划建立该系统的投资不得超过105元。假定级有mi台设备Di并联，则该级的可靠性?i(mi)?1?(1?ri)mi。使

用序偶集合的方法求解该问题（要求给出求解过程中产生的所有序偶集合）。

1解：s1 ={(0.9,30)} s12={(0.99,60)}

S1={(0.9,30) , (0.99,60)}

22={(0.864,60)} s3={(0.8928,75)} s12={(0.72,45),(0.792,75)} s2S2={(0.72,45), (0.864,60),(0.8928,75)}

s13={(0.36,65),(0.432,80),(0.4464,95)}

33s2={(0.54,85),(0.648,100)} s3={(0.63,105)}

S3={(0.36,65),(0.432,80),(0.54,85),(0.648,100)}

最优设计有0.648的可靠性,需用资金100元。 m1=1, m2=2, m3=2。

48.对于有a，b两台设备的流水线调度问题，设数组A(n)，B(n)分别存储a，b的任务完成时间。A=(1,5,3,9,7), B=(4,2,8,6,10)，给出这四个作业的调度序列,并给出调度图和调度时间.

答: 对A,B分类后的序列是{a1,b2,a3,b1,a2,b4,a5,b3,a4,b5}

得调度序列为{1,3,5,4,2}

49.修改算法6.1和6.2，使它们只求出问题的一个解而不是问题的全部解

算法6.1

procedure BACKTRACK(n) integer k,n; local X(1: n) k ← 1 while k>0 do

if还剩有没检验过的X(k)使得

X(k) ∈ T ( X(1), ? ,X(k-1)) and Bk ( X(1), ? ,X(k)) = true then if ( X(1), ? ,X(k) ) 是一条抵达一答案节点的路径 then print ( X(1), ? ,X(k))

return endif

k ←k ＋ 1

else k ←k － 1 endif repeat end BACKTRACK

算法6.2

procedure RBACKTRACK(k) global n, X(1:n) for 满足下式的每个X(k)

X(k) ∈ T ( X(1), ? ,X(k-1)) and Bk ( X(1), ? ,X(k)) = true do if ( X(1), ? ,X(k))是一条抵达一答案结点的路径 then print ( X(1), ? ,X(k))

return

endif

call RBACKTRACK(k+1) repeat end RBACKTRACK

50．在关于解空间树结构的术语中，什么是活结点？什么是E-结点？什么叫答案状态？什么是死结点？

51．什么是状态空间树？回溯法求解问题的过程中，状态空间树所有结点没有完全遍历到，但为什么能够得到所有的解？

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库算法复习题(6)在线全文阅读。