网络学院算法试题C及答案一．填空题：（每题4分，共20分）1.环境栈空间用来保存函数调用返回时恢复运行所需要的信息，具体包括。（返回地址；所有局部变量的值、递归函数的传值形式参数的值；所有引用参数以及常量引用参数的定义。）2．估算程序运行时间的方法通常有两种，分别为和。（操作计数方法，统计程序的执行步数）3．递归函数的两大基本要素是和。（递归方程和边界条件）4．一个分治法将规模为n(n>1)的问题分成k个规模为n／m的子问题去解。设分解阀值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
TPolyEval(Tcoeff[],intn,constT&x){//计算n次多项式的值，coeff[0:n]为多项式的系数Ty=1,value=coeff[0];for(i=1;i<=n;i++){y*=x;value+=y*coeff[i];}returnvalue;}解答：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分，共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；所以贪心算法不总能得到整体的最优解，但它们还是最优解的最好近似；12342．请用分治法设计算法：在一个整数组A[1..n]中，同时寻找最大值和最小值，并分析你的算法的时间复杂度。[假设n为2的方幂]解答算法：MINMAX输入：n个整数元素的数组A[1..n],n为2的方幂。输出：(x,y)，A中的最大元素和最小元素。过程Min_Max(low,high){ifhigh-low=1thenifA[low]
