1、1网络学院算法试题 C 及答案一填空题：（每题 4 分，共 20 分）1. 环境栈空间用来保存函数调用返回时恢复运行所需要的信息，具体包括 。（返回地址；所有局部变量的值、递归函数的传值形式参数的值；所有引用参数以及常量引用参数的定义。 ）2估算程序运行时间的方法通常有两种，分别为 和 。（操作计数方法，统计程序的执行步数）3递归函数的两大基本要素是 和 。（递归方程和边界条件）4一个分治法将规模为 n(n1)的问题分成 k 个规模为 nm 的子问题去解。设分解阀值n0=1，且解规模为 1 的问题耗费 1 个单位时间。 再设将原问题分解为 k 个子问题以及由 k 个子问题的解合并为原问题的解需
2、用 f(n)个单位时间。用 T(n)表示该分治法解规模为|P|=n 的问题所需的计算时间，则 T(n)= 。（ kT(n/m)+f(n)）5采用回溯法求解问题时，通常采用两种策略（即两种剪枝函数）避免无效的搜索，它们分别是 和。（约束函数，限界函数）二简答题：（每小题 6 分，共 18 分）1. 简述分治法的总体思想：a) 将难以直接求解的大问题分解为 k 个相同的子问题;b) 对这 k 个子问题分别求解。如果子问题的规模仍然不够小，则再划分为 k 个子问题，如此递归的进行下去，直到问题规模足够小，很容易求出其解为止;c) 将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出
3、原来问题的解。d) 经分解得到的各个子问题相互独立。2. 假设以加法和乘法为关键操作，估算下述 n 次多项式求值函数的时间复杂度（取 T为整型）template T PolyEval(T coeff, int n, const Tfor(i=1;i32 4 长度为 8;但实际路径为 124 长度为 5；所以贪心算法不总能得到整体的最优解，但它们还是最优解的最好近似；2请用分治法设计算法：在一个整数组 A1.n 中，同时寻找最大值和最小值，并分析你的算法的时间复杂度。假设 n 为 2 的方幂解答算法：MINMAX输入：n 个整数元素的数组 A1.n, n 为 2 的方幂。输出：(x, y) ，
4、A 中的最大元素和最小元素。过程 Min_Max(low, high)if high-low=1 then if Alow1; i-) jMax=min(wi-1,c);for( int j=0; j=w1) /当 w1 0)? 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 bound += pi;i+;/ 装满背包if (i = n) bound += pi / wi * cleft;return bound;注：有些问题的答案较灵活，以上答案仅供参考。
