《计算机算法设计与分析》试卷99

《算法分析与设计》试卷(A)（时间90分钟满分100分）一、填空题（30分,每题2分）。

1．最长公共子序列算法利用的算法是（ B ）。

A、分支界限法B、动态规划法C、贪心法D、回溯法2．在对问题的解空间树进行搜索的方法中,一个活结点最多有一次机会成为活结点的是( B ).A.回溯法B.分支限界法C.回溯法和分支限界法D.回溯法求解子集树问题3．实现最大子段和利用的算法是（ B ）。

A、分治策略B、动态规划法C、贪心法D、回溯法4．.广度优先是（ A ）的一搜索方式。

A、分支界限法B、动态规划法C、贪心法D、回溯法5．衡量一个算法好坏的标准是（ C ）。

A 运行速度快B 占用空间少C 时间复杂度低D 代码短6．Strassen矩阵乘法是利用（ A）实现的算法。

A、分治策略B、动态规划法C、贪心法D、回溯法7. 使用分治法求解不需要满足的条件是（ A ）。

A 子问题必须是一样的B 子问题不能够重复C 子问题的解可以合并D 原问题和子问题使用相同的方法解8．用动态规划算法解决最大字段和问题，其时间复杂性为( B ).A.lognB.nC.n2D.nlogn9.解决活动安排问题，最好用（ B ）算法A.分治B.贪心C.动态规划D.穷举10.下面哪种函数是回溯法中为避免无效搜索采取的策略（ B ）A．递归函数 B.剪枝函数C。

随机数函数 D.搜索函数11. 从活结点表中选择下一个扩展结点的不同方式将导致不同的分支限界法,以下除( C )之外都是最常见的方式.A.队列式分支限界法B.优先队列式分支限界法C.栈式分支限界法D.FIFO分支限界法12. .回溯算法和分支限界法的问题的解空间树不会是( D ).A.有序树B.子集树C.排列树D.无序树13.优先队列式分支限界法选取扩展结点的原则是（ C ）。

A、先进先出B、后进先出C、结点的优先级D、随机14．下面是贪心算法的基本要素的是（ C ）。

A、重叠子问题B、构造最优解C、贪心选择性质D、定义最优解15．回溯法在解空间树T上的搜索方式是( A ).A.深度优先B.广度优先C.最小耗费优先D.活结点优先二、填空题（20分,每空1分）。

算法设计与分析试题 一、 对于下图使用Dijkstra算法求由顶点a到顶点h的最短路径。

ahgfedcb12122823223

解：用V1表示已经找到最短路径的顶点，V2表示与V1中某个顶点相邻接且不在

V1中的顶点；E1表示加入到最短路径中的边，E2为与V1中的顶点相邻接且距离最短的路径。【1分】 步骤 V1 V2 E1 E2 1. {a} {b} {} {ab} 2. {a,b} {d} {ab} {bd} 3. {a,b,d} {c,f} {ab,bd} {dc,df} 4. {a,b,d,c} {f} {ab,bd} {df} 5. {a,b,c,d,f} {e} {ab,bd,dc,df} {fe} 6. {a,b,c,d,e,f} {g} {ab,bd,dc,df,fe} {eg} 7. {a,b,c,d,e,f,g} {h} {ab,bd,dc,df,fe,eg} {gh} 8. {a,b,c,d,e,f,g,h} {} {ab,bd,de,df,fe,eg,gh} {} 【以上每步2分】

结果：从a到h的最短路径为abdfegh，权值为18。【1分】

求所有顶点对之间的最短路径可以使用Dijkstra算法，使其起始节点从a循环到h，每次求起始节点到其他节点的最短路径，最终可以求得所有顶点对之间的最短路径。【2分】

二、 假设有7个物品，它们的重量和价值如下表所示。若这些物品均不能被分割，且背包容量M＝150，使用回溯方法求解此背包问题。请写出状态空间搜索树。 物品 A B C D E F G

重量 35 30 60 50 40 10 25 价值 10 40 30 50 35 40 30

解：按照单位效益从大到小依次排列这7个物品为：FBGDECA。将它们的序号分

别记为1～7。则可生产如下的状态空间搜索树。其中各个节点处的限界函数值通过如下方式求得：【排序1分】

a

aabaacQ111x21x31x41x50x60x70xdee40x30x41xe51xf60xg50xh40xi20xj10x

(占 1 分) 当调度方案是 2,3,1 时：
(占 1 分)
第
1 页 共
2 页
当调度方案是 3,1,2 时： 机器 1 机器 2 作业 3 2 作业 2 2+3=5 作业 1 5+2=7 完成时间和=5+6+8=19
2+3=5 5+1=6 7+1=8 (占 1 分)
它们所对应的完成时间和分别是 19,18,20,21,19,19; 因此最佳调度方案是 1,3,2; .其完成时间为 18。 (占 2 分)
2. 证明：设 F(N)=O(f)), 根据 O 的定义，存在正常数 C1 和 N1, 使得对所有 N>= N1 有 F(N)<=C1f(N); (占 2 分) 再设 G(N)= O(g), 根据 O 的定义，存在正常数 C2 和 N2, 使得对所有 N>= n2 有 G(N)<= C2f(n); (占 2 分) 令 C3=max{C1,C2},N3=max{N1,N2},h(N)=max{f,g},则对所有的 N>=N3,有：(占 2 分) F(N)<= C1f(N)<= C1h(N)<= C3h (N); 类似地有: G(N)<= C2f(N)<= C2h(N)<= C3h (N); 则： (占 2 分) O(f)+O(g)=F(N)+G(N)<= C3h (N)+ C3h (N) =2 C3h (N)=O(h)=O(max(f,g))
五、綜合题（每小题 12 分，共 24 分）
1.（每小问为 2 分） ①:i<=n ②:0 ③:i<=n-r+1 ④:i+r-1 ⑤:t[i][k]+ t[k+1][j]+w(i-1,k,j) ⑥: t[i][j] 2. 1 1 1 .这三个作业的可能的调度方案总数是：P3 P2 P1 =3*2*1=6; 具体的调度方案是 1,2,3; 1,3,2; 2,1,3; 2,3,1; 3,1,2; 3,2,1; .当调度方案是 1,2,3 时： 机器 1 机器 2 作业 1 2 2+1=3 作业 2 2+3=5 5+1=6 作业 3 5+2=7 7+3=10 完成时间和=3+6+10=19 . 当调度方案是 1,3,2 时： 机器 1 机器 2 作业 1 2 2+1=3 作业 3 2+2=4 4+3=7 作业 2 4+3=7 7+1=8 完成时间和=3+7+8=18 (占 1 分) 当调度方案是 2,1,3 时： 机器 1 机器 2 作业 2 3 3+1=4 作业 1 3+2=5 5+1=6 作业 3 5+2=7 7+3=10 完成时间和=4+6+10=20 机器 1 机器 2 作业 2 3 3+1=4 作业 3 3+2=5 5+3=8 作业 1 5+2=7 8+1=9 完成时间和=4+8+9=21

武汉大学计算机学院2007---2008学年第一学期2005级《算法设计与分析》考试试卷（A）1、（10分）证明：若f₁(n)=O(g₁(n)), f₂(n)=O(g₂(n)),则有：f₁(n)* f₂(n)= O(g₁(n))* O(g₂(n))2、（10分）设f(n)为单调递减函数，利用不等式证明：= O(log n)。

3、（10分）用归纳法证明递归关系：T（n的解为T(n)=,n=0,1,2….4、（10分）试用RadixSort算法对下面数组进行排序，写出排序的详细过程：1455，5677，5323，8122，4901，6647，1123，87625、（10分）给定数组含25个元素的数组如下，利用SELECT算法求数组中第13小的元素，在应用SELECT算法时，要求每组含有的元素个数为7而不是5，另外，当元素个数是6时，直接求解：8,33,17,51,57,49,35,11,25,37,14,2,3, 13,52,12,6,29,32,54,5,16,22,23,76、（12分）给定两个字符串X=（A,B,C,B,D,A,B）和Y=(B,D,C,A,B,A)，考虑利用动态规划方法求解这两个字符串的最长公共子序列问题：（1）利用动态规划算法求出上述两个字符串的最长公共子序列，要求写出动态规划方程和详细的求解过程，不需要写出具体的算法；（2）请给出一个最长公共子序列的表达式，并说明你的依据。

7、（12分）假设有一个包含100，000个字符的数据文件要压缩存储，各字符的出现频度如下：(1)试构造出这些字符的哈弗曼编码方案，要求写出详细过程，不需要写出具体算法；(2)计算采用哈弗曼编码方案与定长编码的压缩比。

8、（16分）设有向图的成本矩阵如下，写出利用TSP问题的分析限界法（搜索树限为二叉树）求经过该图每个节点刚好一次的闭合最短路径的过程：（1）写出原始成本矩阵的归约矩阵，并计算其矩阵约数；（2）写出用来划分节点的边的选择方法；（3）给出具体的搜索树；（4）根据搜索树，列出最优的周游路线和其对应的成本值。