算法设计及分析CK.doc

网络学院算法试题C及答案一填空题：（每题4分，共20分）1. 环境栈空间用来保存函数调用返回时恢复运行所需要的信息，具体包括 。（返回地址；所有局部变量的值、递归函数的传值形式参数的值；所有引用参数以及常量引用参数的定义。）2估算程序运行时间的方法通常有两种，分别为 和 。（操作计数方法，统计程序的执行步数）3递归函数的两大基本要素是 和 。（递归方程和边界条件）4一个分治法将规模为n(n1)的问题分成k个规模为nm的子问题去解。设分解阀值n0=1，且解规模为1的问题耗费1个单位时间。再设将原问题分解为k个子问题以及由k个子问题的解合并为原问题的解需用f(n)个单位时间。用T(n)表示该分治法解规模为|P|=n的问题所需的计算时间，则T(n)= 。（ kT(n/m)+f(n)）5采用回溯法求解问题时，通常采用两种策略（即两种剪枝函数）避免无效的搜索，它们分别是_ 和_。（约束函数，限界函数）二简答题：（每小题6分，共18分）1. 简述分治法的总体思想：a) 将难以直接求解的大问题分解为k个相同的子问题;b) 对这k个子问题分别求解。如果子问题的规模仍然不够小，则再划分为k个子问题，如此递归的进行下去，直到问题规模足够小，很容易求出其解为止;c) 将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出原来问题的解。d) 经分解得到的各个子问题相互独立。2. 假设以加法和乘法为关键操作，估算下述n 次多项式求值函数的时间复杂度（取T为整型） template T PolyEval(T coeff, int n, const T& x) / 计算 n 次多项式的值， coeff0:n 为多项式的系数 T y=1, value=coeff0; for(i=1;i=n;i+) y*=x; value+=y*coeffi; return value; 解答： T PolyEval(T coeff, int n, const T& x) / 计算 n 次多项式的值， coeff0:n 为多项式的系数 T y=1, value=coeff0; for(i=1;i324 长度为8;但实际路径为124长度为5；所以贪心算法不总能得到整体的最优解，但它们还是最优解的最好近似；2请用分治法设计算法：在一个整数组A1.n 中，同时寻找最大值和最小值，并分析你的算法的时间复杂度。假设 n 为 2 的方幂解答算法：MINMAX输入：n 个整数元素的数组A1.n, n 为 2 的方幂。输出：(x, y)， A 中的最大元素和最小元素。 过程 Min_Max(low, high) if high-low=1 then if AlowAhigh then return (Alow,Ahigh) else return (Ahigh,Alow) end if. else mid=(low+high)/2 (x1, y1)=Min_Max(low, mid) (x2,y2)=Min_Max(mid+1, high) x=min(x1,x2) y=max(y1,y2) return (x, y) end if该算法的复杂度分析： 设 C(n) 表示算法在由n 个元素组成的数组上执行的元素比较次数，则可得到算法所作的元素比较次数的递推关系式如下： 按以下方式展开求解这个递推式 （令 k=log n）3给定n种物品和一背包。物品i的重量是wi，其价值为vi，背包的容量为C。问应如何选择装入背包的物品，使得装入背包中物品的总价值最大?解答：1）定义最优值设m(i, j)是背包容量为j，可选择物品为i，i+1，n时0-1背包问题的最优解的值。由0-1背包问题的最优子结构性质，可以建立计算m(i，j)的递归式如下： 2) 计算最优值 void knapsack(int v , int w , int c, int m ) int n=v.length-1; int jMax=min(wn-1,c); /进行(1)式赋值 for( int j=0; j=jMax; j+) mnj=0; /当0=jwn for( int j=wn; j=c; j+) / j为背包容量 mnj=vn; /当wn 1; i-) jMax=min(wi-1,c); for( int j=0; j=jMax; j+) mij=mi+1j; /当0=jwi for(int j=wi; j=c; j+) /当wi = j = c mij=max(mi+1j, mi+1j-wi+vi); m1c=m2c; /当0=j=w1) /当w1 = j m1c=max(m1c, m2c-w1+v1);3) 根据最优值计算最优解void traceback( int m , int w , int c, int x ) int n=w.length-1; for(int i=1; i0)? 1:0;4在用回溯法求解0/1背包问题时，1） 画出该问题的解空间树；2） 用伪代码描述用于剪枝的限界函数。解答：1）这个问题的解可以表示成0/1 数组(x1, x2, . . . , xn )，依据wi 是否属于S，xi 分别取值1 或0。故解空间中共有2n 个元素。它的树结构是一棵完全二叉树。解空间树 2) 限界函数： double bound(int i) / 计算上界 double cleft = c - cw; / 剩余容量 double bound = cp; / 以物品单位重量价值递减序装入物品 while (i = n & wi