算法设计与分析试卷B与解答
一．填空题：（每题4分，共20分）
1. 算法的特性有 _0至多个输入， 至少一个输出， 指令无歧义性，指令条数有限且每条指令执行时间有限 . 2．直接或间接地调用自身的算法称为 递归 算法。用函数自身给出定义的函数称为 递归 函数。
和 。 （约束剪枝，限界剪枝）
3．在回溯法中，为了避免无效的搜索，通常采用两种剪枝策略，分别为
4．算法的复杂性是指 算法运行所需要的 计算机资源. 算法的时间复杂性T(n) 是指算法
所需要的时间资源的量；其中n是问题的规模。
5．动态规划算法的两大基本要素分别为 和 。
（最优子结构性质和子问题的重叠性质。）
二．简答题：（每小题5分，共20分）
1. 给定2个序列X?{x1,x2,L,xm}和Y?{y1,y2,L,yn}，说明X和Y的最长公共子序列
问题具有最优子结构性质。
设序列X={x,x,…,x}和Y={y,y,…,y}的最长公共子序列为Z={z,z,…,z} ，则
m
1
2
m
n
1
2
n
k
1
2
k
(1)若x=y，那么z=x=y，且Z
m
n
k
m
n
k-1
是X
m-1
和Y
n-1
的最长公共子序列。
(2)若x≠y且z≠x，那么Z是X
m
n
k
m
k
m-1
和Y的最长公共子序列。
n
(3)若x≠y且z≠y，那么Z是X和Y
m
n
k
n
k
m
n-1
的最长公共子序列。
由此可见，2个序列的最长公共子序列包含了这2个序列的前缀的最长公共子序列。因
此，最长公共子序列问题具有最优子结构性质。
2. 简述常见的两种分支限界法。
（1）队列式(FIFO)分支限界法：按照队列先进先出（FIFO）原则选取下一个节点为扩展节点。
（2）优先队列式分支限界法：按照优先队列中规定的优先级选取优先级最高的节点成为当前扩展节点。
3. 假设以加法和乘法为关键操作，估算下述n 次多项式求值函数的时间复杂度（取T为
整型）
1
template
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 次基本操作
4. 动态规划算法的基本思想是什么？ 它和分治法有什么区别和联系？
答：动态规划算法的基本思想为：该方法的思路也是将待求解的大问题分成规模较小的子问题，但所得的各子问题之间有重复子问题，为了避免子问题的重复计算，可依自底向上的方式计算最优值，并根据子问题的最优值合并得到更大问题的最优值，进而可构造出所求问题的最优解。
分治法也是将待求解的大问题分成若干个规模较小的相同子问题，即该问题具有最优子结构性质。规模缩小到一定的程度就可以容易地解决。所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题；利用该问题分解出的子问题的解可以合并为该问题的解。
三．算法分析解答题：（每题20分，共60分）
1. 假设有n(n?N且n>1)个硬币，已知其中有一个是假币且假币较真币轻. 请设计分治算法求解该问题.并给出其复杂度分析.
Feit_money(low, high) // 假定伪币较真币轻{ float mid;
if ( high-low==1 )
if (A[low] else if (A[low]>A[high]) return A[high]; else { 2 mid=(low+high)/2; if ((high-low+1)%2)==0 { sum1=sum(low, mid); sum2=sum(mid+1, high); } else{ sum1=sum(low, mid-1); sum2=sum(mid+1, high); } if sum1==sum2 return A[mid]; else if (sum1 (high-low+1)%2==0? Feit_money(low, mid) : Feit_money(low, mid-1); else Feit_money(mid+1, high); } return 0; } //其时间复杂度为：O(log n). 2. 记矩阵连乘积 A[i,j]?%AiAi?1...Aj,i?j。 确定计算A[1:n]的最优计算次序，使得所 需数乘的次数最少。 1、说明矩阵连乘计算次序问题的最优解包含着其子问题的最优解，即最优子结构性质。 2、该问题具备子问题的重叠性质。 3、说明采用动态规划方法可以解决该问题。 4、设计该算法，分析算法的复杂性。 解：设这个计算次序在矩阵Ak和Ak+1之间将矩阵链断开，i ≤ k ?m[i,k]?m[k?1,j]?pi?1pkpji?j m[i,j]??i?j?0 Ai是:pi?1?pi阶矩阵。 1、 所以可以看到计算A[i:j]的最优次序所包含的计算矩阵子链 A[i:k]和A[k+1:j] 的次序也是最优的。该问题具有最优子结构性质； 2、 递归算法求解问题时，每次产生的子问题并不总是新问题，有些子问题被反复计 算多次。这种性质称为子问题的重叠性质。 3、 由于最优子结构性质和子问题的重叠性质，所以该问题可用动态规划算 法求解。 void MatrixChain(int *p，int n，int **m，int **s){ for (int i = 1; i <= n; i++) m[i][i] = 0; for (int r = 2; r <= n; r++) for (int i = 1; i <= n - r+1; i++) { 3
算法设计与分析b卷及答案
