算法设计分析(第3次)

1、第3次作业一、填空题（本大题共30 分，共 10小题，每小题3分）1.程序的性能一般指程序的空间复杂性和_ 复杂性。2.计算机算法指的是解决问题的_ 和 _ 。最优子结构性质的含义是 _。贪心算法与动态规划算法的主要区别是_。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.问题能够应用分治算法思想进行求解的前提是问题的_ 性

2、和解的 _性。8.在快速排序、插入排序和归并排序算法中，_算法不是分治算法9.将矩阵链 A3A4A5A6A7 在 A5 处断开，则 m3,7 =。10.计算一个算法时间复杂度通常可以计算_、_或 _。二、简答题（本大题共30 分，共 5小题，每小题6分）下面程序段的所需要的计算时间为 _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;jsum) sum=thissum;besti=i;bestj=j;return sum;请简单描

3、述一下插入排序算法思想。3.设 G=(V,E) 为流网络 f 为流。证明对于所有Ford-Fulkerson 算法的主要问题是什么？在三数取中划分法中，第 k 小的元素要成为中心数，必须与一个比它更小的元素以及一个比它大的元素一起被取出来，其概率等于多少？三、问答题（本大题共40 分，共 5小题，每小题8分）1.输入三个不相同的数，求出其中的最小数。用自然语言描述算法。请概述最小代价生成树的贪心选择性质，并证明。3.简述分治法在每一层递归上的三个步骤的具体内容？4.证明 O(f(n)+O(g(n) = O(maxf(n), g(n)5.分治策略一定导致递归吗？如果是，请解释原因。如果不是，给出

4、一个不包含递归的 分治例子，并阐述这种分治和包含递归的分治的主要不同。答案：一、填空题（ 30 分，共 10 题，每小题 3分）1.参考答案：时间解题方案：评分标准：2.参考答案：方法 过程解题方案：评分标准：3.参考答案：问题的最优解包含其子问题的最优解解题方案：评分标准：4.参考答案：贪心选择性质解题方案：评分标准：5.参考答案：123 34 4 4解题方案：评分标准：6.参考答案：广度优先搜索法最短解题方案：评分标准：7.参考答案：可分 可归并解题方案：评分标准：8.参考答案：插入排序解题方案：评分标准：9.参考答案：m3,5 + m6,7 + p2p5p7解题方案：评分标准：10.参考

5、答案：循环次数基本操作的频率计算步解题方案：评分标准：二、简答题（ 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时，算法的时间复杂度变成流网络规模O(|V|+|E|)的指数函数

6、O(|E| 2*|=2 |E|E|)。解题方案：评分标准：5.参考答案：解题方案：评分标准：三、问答题（ 40 分，共 5题，每小题 8分）1.参考答案：先设置一个变量min，用于存放最小数。当输入a、b、 c 三个不相同的数后，先将 a 与 b 进行比较，把小者送给变量 min，再把 c 与 min 进行比较，若 cmin，则 min=c。解题方案：评分标准：2.参考答案：贪心选择的性质指的是局部最优选择可以得到全局最优解决方案，在最小代价生成树中，其表现为每次选择的为当前可选情况下权值最小的边。证明：（ 1）一定有一个最优解包含了当前权值最小的边包含该边，则将加入其中，会形成一个环，任意去掉环里比一条边，则形成了一个更优的解，与假设矛盾。假设最优解不权值大的（2）选择了后，子问题为去掉了关联的点的剩余的点为顶点集，剩余的边为边集的图的最小代价问题，规模变小，性质不变。通过归纳法，其可以通过贪心性质得到最优解。解题方案：评分标准：3.参考答案：分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题；解决：若子问题规模较小而容易被解决则直接解，否则递归地解各个子问题 ；合并：将各个子问题的解合并为原问题的解。解题方案：评分标准：4.参考答案：所以 O(f(n)+O