算法设计与分析C&K.doc

网络学院算法试题C及答案
:(每题4分,共20分)
1. 环境栈空间用来保存函数调用返回时恢复运行所需要的信息,具体包括

。
(返回地址;所有局部变量的值、递归函数的传值形式参数的值;所有引用参数以及常量引用参数的定义。)
,分别为和
。
(操作计数方法,统计程序的执行步数)

。
(递归方程和边界条件)
(n>1)的问题分成k个规模为n/m的子问题去解。设分解阀值n0=1,且解规模为1的问题耗费1个单位时间。再设将原问题分解为k个子问题以及由k个子问题的解合并为原问题的解需用f(n)个单位时间。用T(n)表示该分治法解规模为|P|=n的问题所需的计算时间,则T(n)=
。
( kT(n/m)+f(n))
,通常采用两种策略(即两种剪枝函数)避免无效的搜索,它们分别是_____________ 和_____________。
(约束函数,限界函数)
:(每小题6分,共18分)
简述分治法的总体思想:
a) 将难以直接求解的大问题分解为k个相同的子问题;
b) 对这k个子问题分别求解。如果子问题的规模仍然不够小,则再划分为k个子问题,如此递归的进行下去,直到问题规模足够小,很容易求出其解为止;
c) 将求出的小规模的问题的解合并为一个更大规模的问题的解,自底向上逐步求出原来问题的解。
d) 经分解得到的各个子问题相互独立。
2. 假设以加法和乘法为关键操作,估算下述n 次多项式求值函数的时间复杂度(取T为整型)
template<class 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
4
该图
各边的长度如下