第 3 次作业一、填空题（本大题共 40 分，共 10 小题，每小题 4 分）1. 程序的性能一般指程序的空间复杂性和 ______ 复杂性。2. 算法的时间复杂度随着问题规模 n 的增大而 ______ 。3. 最优子结构性质的含义是_____。4. 在 n 加倍的情况下，一个 O(2n)的算法计算时间增长 ______ 倍。5. 下列关于算法的说法正确的是______ . (填上正确的序号) ① 某算法可以无止境地运算下去 ②一个问题的算法步骤不能超过 1 万次 ③完成一件事情的算法有且只有一种 ④设计算法要本着简单方便可操作的原则。6. Edmonds-Karp 算法规定，在剩余网络中采用 ______寻找______路径作为增广路径7. 对于 01 背包问题，如果物品 5 的重量为 12，价值为 10，则 OPT(5,10) = _____。8. 常见的指数时间限界函数：O(2n)、O(nn)、O(n！)按从小到大排列： ______ 。9. 三数取中划分法的快速排序比基本的快速排序的实际计算效率高，是因为________________。10. Edmonds&Karp 算法相对于 Ford-Fulkerson 算法的优点是______。二、简答题（本大题共 20 分，共 5 小题，每小题 4 分）1. 下面程序段的所需要的计算时间为___________ int MaxSum(int n, int *a, int &besti, int &bestj) {  int sum=0;  for(int i=1;i<=n;i++){  int thissum=0;  for(int j=i;j<=n;j++){  thissum+=a[j];  if(thissum>sum) {  sum=thissum;  besti=i;  bestj=j;  }  }  } return sum; } 2. 为什么一般情况下，讨论的时间复杂度均是最坏情况下的时间复杂度？3. 设 n 为正整数，利用大“O”记号，将下列程序段的执行时间表示为 n 的函数。 (1) i=1; j=0; while(i<=n) { if (i>j) j++; else i++; } (2)x=n;y=0 while (x>=(y+1)*(y+1)) y++; (3) x=91; y=100; while(y>0) if(x>100) {x=x-10;y--;} else x++; 4. 设 是一个流网络，f 为 G 的流，(S,T)为 G 的一个割，证明|f|=f(S,T)。5. 举反例证明 0/1 背包问题若使用的算法是按照单位重量价值的非递减次序考虑选择的物品，即只要正在被考虑的物品装得进就装入背包，则此方法不一定能得到最优解。 三、问答题（本大题共 40 分，共 5 小题，每小题 8 分）1. 简述什么是贪心选择性质？2. 描述 Ford-Fulkerson 算法基本步骤。3. 该递推方程可用递推法[2]展开求解4. 分治法与递归法的联系与区别？5. 具体解释算法的五个特性？答案：一、填空题（40 分，共 10 题，每小题 4 分）1. 参考答案： 时间解题方案：评分标准：2. 参考答案：增大解题方案：评分标准：3. 参考答案：问题的最优解包含其子问题的最优解解题方案：评分标准：4. 参考答案：16解题方案：评分标准：5. 参考答案：④解题方案：评分标准：6. 参考答案：广度优先搜索法 最短 解题方案：评分标准：7. 参考答案：OPT(4,10)解题方案：评分标准：8. 参考答案：O(2n) < O(n！) < O(nn)解题方案：评分标准：9. 参考答案：在绝大多数情况下，划分得更均衡。解题方案：评分标准：10. 参考答案：计算时间与最大流值无关，只与流网络的结构相关。解题方案：评分标准： 二、简答题（20 分，共 5 题，每小题 4 分）1. 参考答案：O(n2)解题方案：评分标准：2. 参考答案：原因是最坏情况下的时间复杂度是算法在任何输入实例上运行时间的上界，这就保证了算法的运行时间不会比任何更长。解题方案：评分标准：3. 参考答案：(1) T(n)=O(n) (2) T(n)= O(n0.5) (3) T(n)=O(1)解题方案：评分标准：4. 参考答案：    解题方案： 评分标准：5. 参考答案：证明：举例如：p={7,4,4},w={3,2,2},c=4 时，由于 7/3 最大，若按题目要求的方法，只能取第一个，收益是 7。而此实例的最大的收益应该是 8，取第 2，3 个。解题方案：评分标准：三、问答题（40 分，共 5 题，每小题 8 分）1. 参考答案：贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到，这是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别。解题方案：评分标准：2. 参考答案：（1）开始的时候，所有的节点 u,v∈V 间的流值都为 0，即 f(u,v)=0。 （2）在每一次迭代中，我们将流网络 G 的流量进行增加，方法就是在一个关联的“剩余网络”Gf 中寻找一条“增广路径”。一旦知道 Gf 中的一条增广路径的边，就可以很容易辨别出 G 中的对应的边，我们可以对这些边上的流值进行修改，从而增加流量（3）重复第 2 的操作，直到剩余网络中不再存在增广路径为止。解题方案：评分标准： 3. 参考答案：解题方案：评分标准：4. 参考答案：有许多算法在结构是递归的：为了解决一个给定问题，算法要一次或多次地调用其 自身来解决相关的子问题。 这些算法通常采用分治策略：将原问题分成 n个规模较小而结构结原问题相似的子问题。递归地解这些子问题，然后合并其结果就得到原问题的解。解题方案：评分标准：5. 参考答案：概括起来，算法有以下几个特性： 1．确定性：算法的每一种运算（包括判断）必须要有确切的定义，即每一种运算应该执行何种动作必须是相当清楚的、无二义性的。 2．可实现性：此性质是指算法中有待实现的运算都是相当基本的，每种运算至少在原理上能由人用纸和笔在有限的时间内完成。 3．具有数据输入：一个算法有零个或多个数据输入，它们是在算法开始之前对算法最初赋予的量，这些输入取自特定的对象集合。 4．具有数据输出：一个算法产生一个或多个输出，它们是同输入有某种特定关系的量。 5．有穷性：一个算法总是在执行了有穷步之后终止。解题方案： 评分标准：