l算法设计与分析CK.docVIP

网络学院算法试题C及答案 一．填空题：（每题4分，共20分） 1. 环境栈空间用来保存函数调用返回时恢复运行所需要的信息，具体包括 。 （（操作计数方法，统计程序的执行步数） （递归方程和边界条件） 0=1，且解规模为1的问题耗费1个单位时间。再设将原问题分解为k个子问题以及由k个子问题的解合并为原问题的解需用f(n)个单位时间。用T(n)表示该分治法解规模为|P|=n的问题所需的计算时间，则T(n)= 。 （） ????????????? 和?????????????。 （约束函数，限界函数） a) 将难以直接求解的大问题分解为k个相同的子问题; b) 对这k个子问题分别求解。如果子问题的规模仍然不够小，则再划分为k个子问题，如此递归的进行下去，直到问题规模足够小，很容易求出其解为止; c) 将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出原来问题的解。 d) 经分解得到的各个子问题相互独立。 2. 假设以加法和乘法为关键操作，估算下述n 次多项式求值函数的时间复杂度（取T为整型） templateclass T T PolyEval(T coeff[], int n, const T x) { // 计算 n 次多项式的值， coeff[0:n] 为多项式的系数 T y=1, value=coeff[0]; for(i=1;i=n;i++) { y*=x; value+=y*coeff[i]; } return value; } 解答： T PolyEval(T coeff[], int n, const T x) { // 计算 n 次多项式的值， coeff[0:n] 为多项式的系数 T y=1, value=coeff[0]; for(i=1;i=n;i++) //n 循环 { // 累加下一项 y*=x; //一次乘法 value+=y*coeff[i]; //一次加法和一次乘法 } return value; } // 3n 次基本操作 3. 什么是贪心选择性质? 所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。 三．计算和编程题：（前两小题每题18分，后两小题每题13分，共62分） 1. 考虑如下的贪心算法，它试图找出在有正方边长的有向图G中顶点s到顶点t的距离。从顶点s开始，到最近的顶点，称为x；从x出发到最近的顶点，称为y；继续这种做法直到到达顶点t。给出一个最少顶点的图，证明这种探索不总是产生从s到t的距离； 解： 该图 各边的长度如下： （1，2）＝3； （1，3）＝2； （3，2）＝4； （2，4）＝2； （3，4）＝5； 若求1到4的最短路径：按如上的算法得到路径为： 1－3－2－4 长度为8; 但实际路径为1―2―4长度为5； 所以贪心算法不总能得到整体的最优解，但它们还是最优解的最好近似； 2．请用分治法设计算法：在一个整数组A[1..n] 中，同时寻找最大值和最小值，并分析你的算法的时间复杂度。[假设 n 为 2 的方幂] 解答算法：MINMAX 输入：n 个整数元素的数组A[1..n], n 为 2 的方幂。 输出：(x, y)， A 中的最大元素和最小元素。 过程 Min_Max(low, high) { if high-low=1 then if A[low]A[high] then return (A[low],A[high]) else return (A[high],A[low]) 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,