算法分析与设计期末考试模拟试题三

1、PAGE 第7页 （共7页）算法分析与设计期末考试模拟试题三课程名称：_ 算法分析与设计 考试形式： 闭 卷 学习中心：_ 考试时间： 90分钟 姓 名：_ 学 号： 填空题（每小题4分，共计40分）1. 算法是满足 、 、 和 等四个性质的指令序列。2. 算法复杂性的高低体现在运行该算法所需的计算机资源的多少上，计算机的资源最重要的是 和 ，因此算法的复杂性有 和 之分。3.与分治法类似，动态规划算法的基本思想是_，先求解_，然后从这些解得到原问题的解。与分治法不同的是，适合用动态规划算法求解的问题，经分解得到的子问题往往不是_的。4. Java语言的类(class)体现了抽象数据类型(AD

2、T)的思想，一般由4个部分组成： 、 、 和 。5. 抽象数据类型的英文简称是 ，它是算法的一个 _连同定义在该模型上并作为算法构件的一组_ 。6. O(f)+O(g)= _，O(f)O(g)= 。7. 分治法的设计思想是，将一个难以直接解决的大问题，分割成一些规模_的相同问题 , 以便各个击破，_。8. 动态规划算法的第一步通常是刻画最优解的结构。当问题的最优解包含了其_的最优解时，称该问题具有最优子结构性质。9. 动态规划算法与贪心算法的主要区别是_性质。10.表示最优前缀码的二叉树总是一颗 ，即树中任一个结点都有两个儿子结点。二、简答题（每小题10分，共计40分）1. 请简述为什么部分背

3、包问题可以用贪心算法求解，而0-1背包问题却不能用贪心算法求解。2. 请写出如图语法树所对应的矩阵链相乘的最优完全加括号方式。3. 按照下表中的字母出现频率，请画出哈夫曼树，并设计相应的哈夫曼编码。 字母abcdef频率(千次)4513121695哈夫曼编码4. 请简述动态规划算法求解最优化问题的步骤。三、算法分析和设计题（每小题10分，共计20分）1. 请写出阶乘函数的递归定义式及其简要递归算法。2. 给定图G=(V,E)，其中，顶点集为V=1,2,3,4,5,6，边集和每条边的权如图所示。用Prim算法求该图的最小生成树(画图说明算法的求解过程)。用Kruskal算法求最小生成树(画图说明

4、算法的求解过程)。算法分析与设计模拟试题三答案一、填空题答案（每小题4分，共计40分）1. 输入、输出、确定性、有限性2. 时间、空间（即存储器）、时间复杂性、空间复杂性3. 将待求解问题分解为若干个子问题、子问题、互相独立4. 类名、数据成员、方法、访问修饰5. ADT、数据模型、运算6. O(f+g)、O(fg)7. 较小、分而治之8. 子问题9. 贪心选择性质10. 完全二叉树。二、简答题答案（每小题10分，共计40分）1.对于部分背包问题，依照贪心选择策略，可以得到最优解。而0-1背包问题，贪心选择之所以不能得到最优解，是因为在这种情况下，它无法保证最终能将背包装满，部分闲置的背包空间

5、使每公斤背包空间的价值降低了。因而我们选择的判断标准出现了误差。2. 相应的矩阵链相乘的最优完全加括号方式为(A1(A2A3)(A4(A5A6)3. 哈夫曼树哈夫曼编码：字母abcdef频率(千次)4513121695哈夫曼编码0101100111110111004. 可以按以下步骤来设计动态规划算法： （1）找出最优解的性质，并刻画其结构特征； （2）递归地定义最优值； （3）以自底向上的方式计算出最优值； （4）根据计算最优值时得到的信息，构造最优解。三、算法分析和设计题答案（每小题10分，共计20分）1. 阶乘n!的递归定义式是： n!可以递归计算如下:public static int factorial(int n)if( n