第 3 次作业一、填空题（本大题共 30 分，共 10 小题，每小题 3 分）1. 程序的性能一般指程序的空间复杂性和 ______ 复杂性。2. 计算机算法指的是解决问题的 ______ 和 ______。3. 最优子结构性质的含义是_____。4. 贪心算法与动态规划算法的主要区别是______。5. 有如下递归过程：void print(int w) { int i; if(w!=0) { print(w-1); for(i=1;i<=w;i++) printf(“%3d”,w);printf(“\n”); } }调用语句 print(4)的结果是______。6. Edmonds-Karp 算法规定，在剩余网络中采用 ______寻找______路径作为增广路径7. 问题能够应用分治算法思想进行求解的前提是问题的 ______ 性和解的 ______ 性。8. 在快速排序、插入排序和归并排序算法中，______算法不是分治算法9. 将矩阵链 A3A4A5A6A7在 A5处断开，则 m[3,7] =         。10. 计算一个算法时间复杂度通常可以计算_____、_____或_______。二、简答题（本大题共 30 分，共 5 小题，每小题 6 分）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. 设 G=(V,E)为流网络 f 为流。证明对于所有4. Ford-Fulkerson 算法的主要问题是什么？5. 在三数取中划分法中，第 k 小的元素要成为中心数，必须与一个比它更小的元素以及一个比它大的元素一起被取出来，其概率等于多少？三、问答题（本大题共 40 分，共 5 小题，每小题 8 分）1. 输入三个不相同的数，求出其中的最小数。用自然语言描述算法。 2. 请概述最小代价生成树的贪心选择性质，并证明。3. 简述分治法在每一层递归上的三个步骤的具体内容？4. 证明 O(f(n))+O(g(n)) = O(max{f(n), g(n)})5. 分治策略一定导致递归吗？如果是，请解释原因。如果不是，给出一个不包含递归的 分治例子，并阐述这种分治和包含递归的分治的主要不同。答案：一、填空题（30 分，共 10 题，每小题 3 分）1. 参考答案：时间解题方案：评分标准：2. 参考答案：方法 过程解题方案：评分标准：3. 参考答案： 问题的最优解包含其子问题的最优解解题方案：评分标准：4. 参考答案：贪心选择性质解题方案：评分标准：5. 参考答案：1 2 23 3 34 4 4 4解题方案：评分标准：6. 参考答案：广度优先搜索法 最短解题方案：评分标准：7. 参考答案：可分 可归并解题方案： 评分标准：8. 参考答案：插入排序解题方案：评分标准：9. 参考答案：m[3,5] + m[6,7] + p2p5p7 解题方案：评分标准：10. 参考答案：循环次数 基本操作的频率 计算步解题方案：评分标准：二、简答题（30 分，共 5 题，每小题 6 分）1. 参考答案：O(n2)解题方案：评分标准：2. 参考答案： 将无序子序列中的一个或几个记录“插入”到有序序列中，从而增加记录的有序子序列的长度。解题方案：评分标准：3. 参考答案：对所有 x,y∈X, f(x,y)+f(y,x)=0。所以 f(X,X)+f(X,X)=0解题方案：评分标准：4. 参考答案：当最大流值较大时可能发生的情况是每次寻找出来的增广路径，都只能将流网络的流量增加很小的值，这样的话，会大大增加循坏的次数。尤其是|f*|=2|E|时，算法的时间复杂度变成流网络规模 O(|V|+|E|)的指数函数 O(|E| 2|E|)。解题方案：评分标准：5. 参考答案：解题方案：评分标准：三、问答题（40 分，共 5 题，每小题 8 分）1. 参考答案： 先设置一个变量 min，用于存放最小数。当输入 a、b、c 三个不相同的数后，先将 a 与 b 进行比较，把小者送给变量 min，再把 c 与 min 进行比较，若 c＜min，则 min=c。解题方案：评分标准：2. 参考答案：贪心选择的性质指的是局部最优选择可以得到全局最优解决方案，在最小代价生成树中，其表现为每次选择的为当前可选情况下权值最小的边。证明：（1）一定有一个最优解包含了当前权值最小的边 。假设最优解不包含该边，则将 加入其中，会形成一个环，任意去掉环里比 权值大的一条边，则形成了一个更优的解，与假设矛盾。 （2）选择了 后，子问题为去掉了 关联的点的剩余的点为顶点集，剩余的边为边集的图的最小代价问题，规模变小，性质不变。通过归纳法，其可以通过贪心性质得到最优解。解题方案：评分标准：3. 参考答案：分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题；解决：若子问题规模较小而容易被解决则直接解，否则递归地解各个子问题 ；合并：将各个子问题的解合并为原问题的解 。解题方案：评分标准：4. 参考答案：       所以 O(f(n))+O(g(n)) = O(max{f(n), g(n)})解题方案：评分标准：5. 参考答案：不一定导致递归。 如非递归的二叉树中序遍历。 这种分治方法与递归的二叉树中序遍历主要区别是：应用了栈这个数据结构。解题方案：评分标准：