算法设计及分析(A)评分标准及参考答案.doc

算法设计与分析试题参考答案及评分标准( A卷)适用专业年级： 计本04级 考试时间: 100分钟命题人：尹普辉一、判断题（下列各题，你认为正确的，请在题目的括号内打“”，错的打“X”，每题2分，共18分） 1.x 2.x 3. 4.x 5. 6. 7. 8. 9. 二、填空题 （每小题2分，共30分） 1.O(N2) 2.大致相同 3.T(n)= 3T(n/2)+O(n) 4.(4k-1)/3 5.舍伍德 6.重叠子问题 7.n-2 8.tij=mini=k1时, T(n)=3T(n/2)+O(n) (占2分) 2. 证明：设F(N)=O(f), 根据O的定义，存在正常数C1和N1,使得对所有N= N1有F(N)= n2有G(N)=N3,有：(占2分)F(N)= C1f(N)= C1h(N)= C3h (N); 类似地有: G(N)= C2f(N)= C2h(N)= C3h (N); 则： (占2分) O(f)+O(g)=F(N)+G(N)= C3h (N)+ C3h (N)=2 C3h (N)=O(h)=O(max(f,g)五、綜合题（每小题12分，共24分） 1.（每小问为2分）:i=n:0:i=n-r+1:i+r-1:tik+ tk+1j+w(i-1,k,j): tij2. .这三个作业的可能的调度方案总数是：P31P21P11=3*2*1=6; (占2分)具体的调度方案是1,2,3; 1,3,2; 2,1,3; 2,3,1; 3,1,2; 3,2,1; (占2分).当调度方案是1,2,3时： 机器1 机器2作业1 2 2+1=3作业2 2+3=5 5+1=6作业3 5+2=7 7+3=10 完成时间和=3+6+10=19 (占1分). 当调度方案是1,3,2时： 机器1 机器2作业1 2 2+1=3作业3 2+2=4 4+3=7作业2 4+3=7 7+1=8 完成时间和=3+7+8=18 (占1分)当调度方案是2,1,3时： 机器1 机器2作业2 3 3+1=4作业1 3+2=5 5+1=6作业3 5+2=7 7+3=10 完成时间和=4+6+10=20 (占1分) 当调度方案是2,3,1时： 机器1 机器2作业2 3 3+1=4作业3 3+2=5 5+3=8作业1 5+2=7 8+1=9 完成时间和=4+8+9=21 (占1分) 第 1 页 共 2 页 当调度方案是3,1,2时： 机器1 机器2作业3 2 2+3=5作业2 2+3=5 5+1=6作业1 5+2=7 7+1=8 完成时间和=5+6+8=19 (占1分)它们所对应的完成时间和分别是19,18,20,21,19,19;因此最佳调度方案是1,3,2; (占2分).其完成时间为18。 第 2 页 共 2 页