武大06级《算法设计与分析》.doc

武汉大学计算机学院 2006级《算法设计与分析》考试试卷1. （10分）对下表中的每一对(n)，(n)，问(n)是否(g(n)),(g(n)),(g(n))，(g(n))，若是，则在相应空格打√P19 复杂性类比较层次、P17-18举例】(n)(n)√√√√ √2. （10分）求解下列递归关系 （n=1） ()其中为一个非负整数解： f(n)=2(n^3)-n^2…………………………… P57 3. （15分）回答下列问题a） 依次将13，4，25，26，10，3，30，11，13插入一个非空的极大堆，画出所得到的极大堆的表示；（5分）（b） 高度为的堆最少有几个元素？最多有几个元素？（二叉树的高度定义如下：根结点的层次为0，若一个结点的层次为，则其儿子结点的层次为，树中结点的最大层次为树的高度）；（5分）（c） 证明具有n个元素的堆的高度为5分）解：(a). 30 25 26 13 10 3 13 4 11(b). 高度为的堆最少有2^h 个元素（不是2^(h-1)，因为高度从0开始不是从1开始）； 最多有2^（h+1）个元素(c). 证明：运用数学归纳法: 4. （10分）给定数组A=（10,12,17,26,33,75,81,96），使用二分搜索依次搜索4,12,11,35,87，请统计一共进行了多少次比较？解： 4→26/12/10 【3】12→26/12 【2】11→26/12/10 【3】35→26/75/33 【3】87→26/75/81/96 【4】一共比较次数： 3+2+3+3+4=15（次）5. 设含有3个结点的有向图G的成本矩阵如下图所示，试用FLOYD算法求解出该有向图的所有结点对间的最短距离。

123104112602330 解：p136 12310411260233012310411260233701231046260233701231046250233706.(10分)KRUSKAL是找无向图的最小生成树的算法，证明在含权无向图中，算法KRUSKAL能正确找出最小生成树解：p1537.（15分）利用回溯法求4皇后问题，设解的形式为（），其中表示第i个皇后放在第i行，第列，画出求解过程中生成的部分状态树（搜索树），（10分）给出最终解的形式（2分），并统计算法总共生成了多少个结点3分）(p222)解： 最终解：（2，4，1，3）或者（3，1，4，2）总共产生结点27个8.（10分）已知可满足性问题是NP完全问题，证明团集问题也是NP完全问题解： 定义10.4+推论10.1+ p180（可满足性“多项式时间规约到”团集）9.（10分）编辑距离问题：设A和B是2个字符串，要用最少的字符操作将字符串A换为字符串B，这里所说的字符操作包括（1）删除一个字符；（2）插入一个字符；（3）将一个字符该为另一个字符将字符串A变换为字符串B所用的最少字符操作数称为字符串A到B的编辑距离，记为。

设计一个动态规划算法，给定任意两个字符串A和B，算法能输出该实例的编辑距离要求写出算法的思想和算法的代码或者伪码）解：//完整程序代码//#include #include #include int _Min(int a,int b,int c) { int min=a; if (b

第二个性质: 由于我们定义的三个操作来作为编辑距离的一种衡量方法 于是对ch1,ch2可能的操作只有1. 把ch1变成ch22. s1+ch1后删除ch1 d = (1+d(s1,s2+ch2))3. s1+ch1后插入ch2 d = (1 + d(s1+ch1,s2)) 对于2和3的操作可以等价于: _2. s2+ch2后添加ch1 d=(1+d(s1,s2+ch2)) _3. s2+ch2后删除ch2 d=(1+d(s1+ch1,s2)) 因此可以得到计算编辑距离的性质2。

复杂度分析从上面性质2可以看出计算过程呈现这样的一种结构(假设各个层用当前计算的串长度标记，并假设两个串长度都为 n )可以看到，该问题的复杂度为指数级别 3 的 n 次方，对于较长的串，时间上是无法让人忍受的 分析: 在上面的结构中，我们发现多次出现了 (n-1,n-1), (n-1,n-2)……换句话说该结构具有重叠子问题再加上前面性质2所具有的最优子结构符合动态规划算法基本要素因此可以使用动态规划算法把复杂度降低到多项式级别动态规划求解 首先为了避免重复计算子问题，添加两个辅助数组一. 保存子问题结果M[ |s1| ,|s2| ] , 其中M[ i , j ] 表示子串 s1(0->i) 与 s2(0->j) 的编辑距离二. 保存字符之间的编辑距离.E[ |s1|, |s2| ] , 其中 E[ i, j ] = s[i] = s[j] ? 0 : 1三. 新的计算表达式根据性质1得到M[ 0,0] = 0;M[ s1i, 0 ] = |s1i|;M[ 0, s2j ] = |s2j|;根据性质2得到M[ i, j ] = min( m[i-1,j-1] + E[ i, j ] , m[i, j-1] , m[i-1, j] ); 复杂度 从新的计算式看出，计算过程为 i=1 -> |s1| j=1 -> |s2| M[i][j] = …… 因此复杂度为 O( |s1| * |s2| ) ，如果假设他们的长度都为n，则复杂度为 O(n^2)。