网络学院算法试题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)经分解得到的各个子问题相互独立
假设以加法和乘法为关键操作，估算下述n次多项式求值函数的时间复杂度（取T为整型）templateTPolyEval(Tcoeff[],intn,constT&x){//计算n次多项式的值，coeff[0:n]为多项式的系数Ty=1,value=coeff[0];for(i=1;i2－>4长度为8;但实际路径为1―>2―>4长度为5；所以贪心算法不总能得到整体的最优解，但它们
