算法设计技巧与分析习题答案
【篇一:算法设计与分析考试题及答案?/p>
一特殊类型问题的一系列运算,此外,算法还应具有以下五个重要
特?/p>
:_________,________,________,__________,__________
?/p>
2.
算法的复杂性有
_____________
?/p>
___________
之分,衡量一?/p>
算法好坏的标准是
______________________
?/p>
3.
某一问题可用动态规划算法求解的显著特征?/p>
____________________________________
?/p>
4.
若序?/p>
x={b,c,a,d,b,c,d}
?/p>
y={a,c,b,a,b,d,c,d}
,请给出序列
x
?/p>
y
的一个最长公共子序列
_____________________________
?/p>
5.
?/p>
回溯法解问题时,应明确定义问题的解空间,问题的解空间至少?/p>
包含
___________
?/p>
6.
动态规划算法的基本思想是将待求解问题分解成若干
____________
,先求解
___________
,然后从这些
____________
的解得到原问题的解?/p>
7.
以深度优先方式系统搜索问题解的算法称?/p>
_____________
?/p>
8.0-1
背包问题的回溯算法所需的计算时间为
_____________,
用动
态规划算法所需的计算时间为
____________
?/p>
9.
动态规划算法的两个基本要素?/p>
___________
?/p>
___________
?/p>
10.
二分搜索算法是利?/p>
_______________
实现的算法?/p>
二、综?/p>
题(
50
分)
1.
写出设计动态规划算法的主要步骤?/p>
2.
流水作业调度问题?/p>
johnson
算法的思想?/p>
3.
?/p>
n=4
,在机器
m1
?/p>
m2
上加工作?/p>
i
所需的时间分别为
ai
?/p>
bi
?/p>
?/p>
(a1,a2,a3,a4)=(4,5,12,10)
?/p>
(b1,b2,b3,b4)=(8,2,15,9)
?/p>
4
个作?/p>
的最优调度方案,并计算最优值?/p>
4.
使用回溯法解
0/1
背包问题?/p>
n=3
?/p>
c=9
?/p>
v={6,10,3}
?/p>
w={3,4,4},
其解空间有长度为
3
?/p>
0-1
向量组成,要求用一棵完全二叉树表示
其解空间(从根出发,?/p>
1
?/p>
0
),并画出其解空间树,计算其最?/p>
值及最优解?/p>
6.
描述
0-1
背包问题?/p>
三、简答题?/p>
30
分)
1.
流水作业调度中,已知?/p>
n
个作业,机器
m1
?/p>
m2
上加工作?/p>
i
所需的时间分别为
ai
?/p>
bi
,请写出流水作业调度问题?/p>
johnson
?/p>
则中?/p>
ai
?/p>
bi
的排序算法。(函数名可写为
sort(s,n)
?/p>