算法设计及分析(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.t[i][j]=mini<=k<j{ t[i][k]+ t[k+1][j]+w(vi-1vkvj)}
9.整体最优 10.约束条件
11.直接或间接地 12.贪心选择性质
13.相容活动 14.优先队列式
15.完全二叉树

三、单项选择题（在每小题的四个备选答案中选出一个正确的答案，并将其号码填在括号内，每小题2分，共12分）
1.B， 2. C， 3.C， 4.A 5.A 6.B

四、证明题（每小题8分，共16分）
1. 证明：我们将n 位的二进制整数X和Y都分为2段，每段的长为n/2位，如下图所示：
n/2位 n/2位 n/2位 n/2位 (占2分)
X= A B Y=CD
由此X=A2n/2+B, Y=C2n/2+D,这样X和Y的乘积为：
XY=( A2n/2+B)*( C2n/2+D)=AC2n+(AD+BC) 2n/2+BD,则我们必须进行 (占2分)
4次n/2位整数的乘法(AC,AD,BC,BD),以及3次整数加法，2次移位；
要想算法的计算复杂性，必须减少乘法次数，把XY写成另一种形式：
XY= AC2n+((A-B)(D-C)+AC+BD) 2n/2+BD,它仅需做3次n/2位整数的 (占2分)
乘法（AC，BD，（A-B）（D-C）），6次加、减法和2次移位，由此可得：
大整数的乘法的运算总数
T(n),当n=1时,T(n)=O(1);当n>1时, T(n)=3T(n/2)+O(n) (占2分)

2. 证明：设F(N)=O(f)), 根据O的定义，存在正常数C1和N1,
使得对所有N>= N1有F(N)<=C1f(N); (占2分)
再设G(N)= O(g), 根据O的定义，存在正常数C2和N2,
使得对所有N>= n2有G(N)<= C2f(n); (占2分)
令C3=max{C1,C2},N3=max{N1,N2},h(N)=max{f,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
⑤:t[i][k]+ t[k+1][j]+w(i-1,k,j)
⑥: t[i][j]
2.
.这三个作业的可能的调度方案总数是：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 页