算法分析与设计期末考试模拟试题三
课程名称：__ 算法分析与设计 考试形式： 闭 卷
学习中心：_________ 考试时间： 90分钟
姓 名：_____________ 学 号：
一、填空题（每小题4分，共计40分）
1. 算法是满足 、 、 和 等四个性质的指令序列。
2. 算法复杂性的高低体现在运行该算法所需的计算机资源的多少上，计算
机的资源最重要的是 和 ，因此算法的复杂性有 和 之分。
3.与分治法类似，动态规划算法的基本思想是____________________________，先求解_________________，然后从这些解得到原问题的解。与分治法不同的是，适合用动态规划算法求解的问题，经分解得到的子问题往往不是___________________的。 4. Java语言的类(class)体现了抽象数据类型(ADT)的思想，一般由4个
部分组成： 、 、 和 。
5. 抽象数据类型的英文简称是 ，它是算法的一个 ____________连同定义在该模型上并作为算法构件的一组_________ 。 6. O(f)+O(g)= __，O(f)O(g)= 。
7. 分治法的设计思想是，将一个难以直接解决的大问题，分割成一些规模_______的相同问题 , 以便各个击破，_______________。
8. 动态规划算法的第一步通常是刻画最优解的结构。当问题的最优解包含了其__________________的最优解时，称该问题具有最优子结构性质。 9. 动态规划算法与贪心算法的主要区别是___________________性质。 10.表示最优前缀码的二叉树总是一颗 ，即树中任一个结
第 1 页 （共 7 页）
点都有两个儿子结点。
二、简答题（每小题10分，共计40分）
1. 请简述为什么部分背包问题可以用贪心算法求解，而0-1背包问题却不能用贪心算法求解。
2. 请写出如图语法树所对应的矩阵链相乘的最优完全加括号方式。
3. 按照下表中的字母出现频率，请画出哈夫曼树，并设计相应的哈夫曼编码。
字母 频率(千次) 哈夫曼编码 a 45 b 13 c 12 d 16 e 9 f 5 4. 请简述动态规划算法求解最优化问题的步骤。 三、算法分析和设计题（每小题10分，共计20分） 1. 请写出阶乘函数的递归定义式及其简要递归算法。
2. 给定图G=(V,E)，其中，顶点集为V={1,2,3,4,5,6}，边集和每条边的权如图所示。
第 2 页 （共 7 页）
① 用Prim算法求该图的最小生成树(画图说明算法的求解过程)。 ② 用Kruskal算法求最小生成树(画图说明算法的求解过程)。
第 3 页 （共 7 页）
算法分析与设计模拟试题三答案
一、填空题答案（每小题4分，共计40分） 1. 输入、输出、确定性、有限性
2. 时间、空间（即存储器）、时间复杂性、空间复杂性 3. 将待求解问题分解为若干个子问题、子问题、互相独立 4. 类名、数据成员、方法、访问修饰 5. ADT、数据模型、运算 6. O(f+g)、O(fg) 7. 较小、分而治之 8. 子问题 9. 贪心选择性质 10. 完全二叉树。
二、简答题答案（每小题10分，共计40分）
1.对于部分背包问题，依照贪心选择策略，可以得到最优解。而0-1背包问题，贪心选择之所以不能得到最优解，是因为在这种情况下，它无法保证最终能将背包装满，部分闲置的背包空间使每公斤背包空间的价值降低了。因而我们选择的判断标准出现了误差。。 2. 相应的矩阵链相乘的最优完全加括号方式为 ((A1(A2A3))(A4(A5A6))) 3. 哈夫曼树
第 4 页 （共 7 页）
哈夫曼编码：
字母 频率(千次) 哈夫曼编码
4. 可以按以下步骤来设计动态规划算法： （1）找出最优解的性质，并刻画其结构特征； （2）递归地定义最优值；
（3）以自底向上的方式计算出最优值；
（4）根据计算最优值时得到的信息，构造最优解。 三、算法分析和设计题答案（每小题10分，共计20分） 1. 阶乘n!的递归定义式是：
a 45 0 b 13 101 c 12 100 d 16 111 e 9 1101 f 5 1100 ?1n！???n(n?1)!
n!可以递归计算如下:
n?0n?0
public static int factorial(int n) {
if( n==0 ) return 1; return n * factorial(n-1) ;
第 5 页 （共 7 页）
算法分析与设计期末考试模拟试题三
