1、 第 3次作业 一、填空题（本大题共 40 分，共 10 小题，每小题 4 分） 1. 程序的性能一般指程序的空间复杂性和 _ 复杂性。 2. 矩阵连乘问题的算法可由（ ）设计实现。 3. 贪心算法通过 _达成全局最优。 4. 对于有 n种可选择物品的 0-1背包问题，其解空间由长度为 n的 0-1向量组成。该解空间包含对变量的所有 0-1赋值。当 n=2时，其解空间是： _ 。 5. 穷举一个矩阵链的全部完全加括号形式将会导致 _级的计算复杂性。 6. 数据的定义形式按递归定义，如裴波那契数列的定义： f(n)=f(n-1)+f(n-2),f(0)=1,f(1)=2. 这类递归问题可转化为递
2、推算法， _ 作为递推的边界条件。 7. 最长公共子序列问题中， ci,j被定义为序列 _与 序列 _ 的最长公共子序列的长度。 8. 如果存在两个正常数 c和 n0,对于所有的 nn 0,有 _ ,则称 g(n)是 f(n)的一个下界函数。 9. 将递归算法转换成对应的非递归算法时，通常需要使用 _ 10. Edmonds 所以， r1=1. (2)当 j=2时， 当 i=1时， 所以， r2=5. 同理 j=3,4,5时，可计算出 r3=8;r4=10;r5=13. i 1 2 3 4 5 1 4 8 10 13 解题方案： 评 分标准： 5. 参考答案： 证明：举例如： p=7,4,4,
3、w=3,2,2,c=4 时，由于 7/3最大，若按题目要求的方法，只能取第一个，收益是 7。而此实例的最大的收益应该是 8，取第 2，3 个。 解题方案： 评分标准： 三、问答题（ 40 分，共 5 题，每小题 8 分） 1. 参考答案： 先设置一个变量 min，用于存放最小数。当输入 a、 b、 c三个不相同的数后，先将 a与 b进行比较，把小者送给变量 min，再把 c与 min 进行比较，若 cmin，则 min=c。 解题方案： 评分标准： 2. 参考答案： 分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题；解决：若子问题规模较小而容易被解决则直接解，否则递归地解
4、各个子问题 ；合并：将各个子问题的解合并为原问题的解 。 解题方案： 评分标准： 3. 参考答案： （ 1）成立。题中由于两个函数的最高次项都是 n3,因此当 n 时，两个函数的比值是一个常数，所以这个关系式是成立的。 （ 2）成立。与上同理。 （ 3）成立。与上同理。 （ 4）不成立。由于当 n 时 n1.5比 nlgn 递增的快，所以 h(n)与 nlgn的比值不是常数 ，故不成立。 解题方案： 评分标准： 4. 参考答案： 动态规划法与分治法和贪心法类似，它们都是将问题实例归纳为更小的、相似的子问题，并通过求解子问题产生一个全局最优解。 其中贪心法的当前选择可能要依赖已经作出的所有选择，但不依赖于有待于做出的选择和子问题。 因此贪心法自顶向下，一步一步地作出贪心选择，而分治法中的各个子问题是独立的（即不包含公共的子子问题）。因此一旦递归地求出各子问题的解后，便可自下而上地将子问题的解合并成问题的解。但不足的是，如果当前选择可能要依赖子问题的解时，则难以通过局部的贪 心策略达到全局最优解 如果各子问题是不独立的，则分治法要做许多不必要的工作，重复地解公共的子问题。 解题方案： 评分标准： 5. 参考答案： 剩余网络 流网络 没有增广路径，最大流 =12+11=23 解题方案： 评分标准：
