《计算机算法设计与分析》试题 (B)
软件学院 04级 软件工程专业
参考答案
一、填空题 （共8小题，15个空，每空1分，共15分。）
解：
二、计算题（共8小题，每小题4-12分，共53分） 1．（5分）给出合并排序算法时间复杂度T(n)的递归方程。 解：
??(1)?T(n) = ?n2T()??(n)??(1)??2??(1)?或 T(n) = ?n2T()??(n)??2当n?1当n?1
当n?1当n?1
2．（5分）用套用公式法计算下列递归方程解的渐进阶。
??(1)T(n) = ??2T(n/2)??(1)解： 因为a=2, b=2，
所以nlog ba当n?1当n?1
＝nlog 22＝n，
可套用第一类情况得T(n)??(n)。
3．（4分）给定两个序列X=
其最长公共子序列。
解:
4．（6分）对于下列各组函数f (n) 和g (n)，确定f (n) = O (g (n)) 或f (n) =Ω
1
(g (n))或f(n) =θ(g(n))。
（1） f(n)=2n; g(n)=n! （2） （3） 解：
（1）f (n) = O (g (n)) （2分） （2）f (n) =Ω(g (n)) （2分） (3) f(n) =θ(g(n)) （2分）
5. (7分) 采用动态规划策略，计算{3,-2,-1,8,-3,8,-1,9,-8，6，-2，7，-3，8}的最大子段和，并给出这个最大子段和的起始下标索引和终止下标索引。 解：b[1]=3
b[2]=max{b[1]+a[2],a[2]}=max{1,-2}=1 b[3]=max{b[2]+a[3],a[3]}=max{0,-1}=0 b[4]=max{b[3]+a[a],a[4]}=max{8, 8}=8 b[5]=max{b[4]+a[2],a[5]}=max{5,-3}=5 b[6]=max{b[5]+a[2],a[6]}=max{13,8}=13 b[7]=max{b[6]+a[7],a[7]}=max{12,-1}=12 b[8]=max{b[7]+a[8],a[8]}=max{21,9}=21 b[9]=max{b[8]+a[9],a[9]}=max{13,-8}=13 b[10]=max{b[9]+a[10],a[10]}=max{19,6}=19 b[11]=max{b[10]+a[11],a[11]}=max{17,-2}=17 b[12]=max{b[11]+a[12],a[12]}=max{24,7}=24 b[13]=max{b[12]+a[13],a[13]}=max{21,-3}=21 b[14]=max{b[13]+a[14],a[14]}=max{29,8}=29 （以上每2行1分，共7分）
f(n)=
n; g (n)=log n2;
f(n)= log 100; g(n)=100;
6．（6分）给出下图所示的四个顶点图所有3-着色法，要求画出可行解空间树。
1 2 4 3 解： 1 2 3
2
2 3 1 3 1 2
1 1 2 2 3 3
3 2 3 1 2 1 四个顶点的图及其所有3-着色法
7. (8分)已知一个有向图的距离矩阵如下：
?0???2??1???10?3???2??50??2?3???6??04??4 ??7??0??5????51??0?6?? 1 2 3 4 5 6用贪心策略计算出节点1到其它各个节点的最短路径长度。 解： 迭代 S u Dist[2] Dist[3] ? ? ? ? Dist[4] ? ? 12 12 Dist[5] 2 2 2 2 Dist[6] ? ? ? ? 初始 {1} - ? 1 {1,5} 5 9 2 {1,5,2} 2 9 3 {1,5,2,4} 4 9 （以上每行2分，共8分）
8. (12分) 考虑n=3的批处理作业调度实例：
tji 机器1 机器2 作业1 3 5 作业2 4 6 作业3 2 3 要求（1）画出该问题的解空间树。（2）写出该问题的剪枝策略（3）搜索解空间树，并利用剪枝策略对应该剪掉的子树打?，最终给出该问题的解。
解：(1)解空间树是一棵排列树。(2分)
用f表示当前完成作业的时间和。bestf表示完成作业的时间和的最优值。
3