算法设计与分析c&k

《算法设计与分析c&k》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、网络学院算法试题C及答案一．填空题：（每题4分，共20分）1.环境栈空间用来保存函数调用返回时恢复运行所需要的信息，具体包括。（返回地址；所有局部变量的值、递归函数的传值形式参数的值；所有引用参数以及常量引用参数的定义。）2．估算程序运行时间的方法通常有两种，分别为和。（操作计数方法，统计程序的执行步数）3．递归函数的两大基本要素是和。（递归方程和边界条件）4．一个分治法将规模为n(n>1)的问题分成k个规模为n／m的子问题去解。设分解阀值n0=1，且解规模为1的问题耗费1个单位时间。再设将原问题分解为k个子问题以及由k个子问题的

2、解合并为原问题的解需用f(n)个单位时间。用T(n)表示该分治法解规模为

3、P

4、=n的问题所需的计算时间，则T(n)=。（kT(n/m)+f(n)）5．采用回溯法求解问题时，通常采用两种策略（即两种剪枝函数）避免无效的搜索，它们分别是_____________和_____________。（约束函数，限界函数）二．简答题：（每小题6分，共18分）1.简述分治法的总体思想：a)将难以直接求解的大问题分解为k个相同的子问题;b)对这k个子问题分别求解。如果子问题的规模仍然不够小，则再划分为k个子问题，如此递归的进行下去，直到问题规模足够

5、小，很容易求出其解为止;c)将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出原来问题的解。d)经分解得到的各个子问题相互独立。2.假设以加法和乘法为关键操作，估算下述n次多项式求值函数的时间复杂度（取T为整型）templateTPolyEval(Tcoeff[],intn,constT&x){//计算n次多项式的值，coeff[0:n]为多项式的系数Ty=1,value=coeff[0];for(i=1;i<=n;i++)6{y*=x;value+=y*coeff[i];}returnvalu

6、e;}解答：TPolyEval(Tcoeff[],intn,constT&x){//计算n次多项式的值，coeff[0:n]为多项式的系数Ty=1,value=coeff[0];for(i=1;i<=n;i++)//n循环{//累加下一项y*=x;//一次乘法value+=y*coeff[i];//一次加法和一次乘法}returnvalue;}//3n次基本操作3.什么是贪心选择性质?所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。三．计算和编程题：（前两小题每题18分，后两小题每题13分，

7、共62分）1.考虑如下的贪心算法，它试图找出在有正方边长的有向图G中顶点s到顶点t的距离。从顶点s开始，到最近的顶点，称为x；从x出发到最近的顶点，称为y；继续这种做法直到到达顶点t。给出一个最少顶点的图，证明这种探索不总是产生从s到t的距离；解：1234该图各边的长度如下：（1，2）＝3；（1，3）＝2；6（3，2）＝4；（2，4）＝2；（3，4）＝5；若求1到4的最短路径：按如上的算法得到路径为：1－>3－>2－>4长度为8;但实际路径为1―>2―>4长度为5；所以贪心算法不总能得到整体的最优解，但它们还是最优解的最好近似；2

8、．请用分治法设计算法：在一个整数组A[1..n]中，同时寻找最大值和最小值，并分析你的算法的时间复杂度。[假设n为2的方幂]解答算法：MINMAX输入：n个整数元素的数组A[1..n],n为2的方幂。输出：(x,y)，A中的最大元素和最小元素。过程Min_Max(low,high){ifhigh-low=1thenifA[low]

9、x(low,mid)(x2,y2)=Min_Max(mid+1,high)x=min(x1,x2)y=max(y1,y2)return(x,y)endif}该算法的复杂度分析：设C(n)表示算法在由n个元素组成的数组上执行的元素比较次数，则可得到算法所作的元素比较次数的递推关系式如下：按以下方式展开求解这个递推式（令k=logn）63．给定n种物品和一背包。物品i的重量是wi，其价值为vi，背包的容量为C。问应如何选择装入背包的物品，使得装入背包中物品的总价值最大?解答：1）定义最优值设m(i,j)是背包容量为j，可选择物品为i，

10、i+1，…，n时0-1背包问题的最优解的值。由0-1背包问题的最优子结构性质，可以建立计算m(i，j)的递归式如下：2)计算最优值voidknapsack(intv[],intw[],intc,intm[][]){intn=v.length-1;i