1、2014年 9月份考试算法设计分析第三次作业 一、填空题（本大题共 20 分，共 5 小题，每小题 4 分） 1. 如果一棵二叉树的任何结点或者是树叶，或者有两棵非空子树，则此二叉树称作 _ 。 2. 按照渐近阶比较大小 n2/3 _ 4n2? 3. 二进制大整数乘法应用于十进制大整数的乘法的优点是： _ 4. 如果存在两个正常数 c 和 n0,对于所有的 nn0, 有 _ ,则称 g(n)是f(n)的一个上界函数 5. O 的定义为 _ 二、改错题（本大题共 40 分，共 4 小题，每小题 10 分） 1. 与分治法不同的是，适合于用动态规划求解的问题经分解得到子问题往往是互相独立的 ( )
2、 2. 拉斯维加斯算法的一个显著特征是它所作的随机性决策有可能导致算法找不到所需的解。 ( ) 3. 适宜于用贪心策略来解的大多数问题都有两个特点 :贪心选择性质和最优子结 构。 ( ) 4. 贪心算法所做的选择都是目前最佳的 ( ) 三、简答题（本大题共 20 分，共 2 小题，每小题 10 分） 1. 5 输入两个正整数 a 和 b（ ab），求它们的最大公约数。 2. 描述 Dijkstra 算法的基本 思想。 四、问答题（本大题共 20 分，共 2 小题，每小题 10 分） 1. 分治法的适用条件？ 2. 描述分支限界法基本思想。 答案： 一、填空题（ 20 分，共 5 题，每小题 4
3、 分） 1. 参考答案： 满二叉树 解题方案： 知识点记忆 评分标准： 3分 2. 参考答案： 解题方案： 评分标准： 3. 参考答案： 减少乘法次数，提高算法效率 解题方案： 知识点记忆 评分标准： 3分 4. 参考答案： |f（ n） | c|g （ n） | 解题方案： 评分标准： 5. 参考答案 ： 我们称函数 f(N)当 N充分大时的阶比 g(N)低，记为 f(N)=o(g(N) 对于任意给定的 0 ，都存在正整数 N0，使得当 N N0 时有 f(N)/g(N)b）； 求 a/b 的余数 r； 如果 r0 ，则将ba ， rb ，再次求 a/b的余数 r，转至 ； 输出最大公约数
4、b。 int gcd( int a, int b ) int tmp; if ( a b tmp = a; a=b; b=tmp; while ( b 1 ) tmp = a%b; if ( tmp = 0 ) break; a=b; b=tmp; return b; 解题方案： 评分标准： 15 2. 参考答案： 按路径长度递增次序产生算法： 把顶点集合 V分成两组： （ 1） S：已求出的顶点的集合（初始时只含有源点 V0） （ 2） V-S=T：尚未确定的顶点集合 将 T中顶点按递增的次序加入到 S 中，保证： （ 1）从源点 V0到 S中其他各顶点的长度都不大于从 V0到 T中任何顶点
5、的最短路径长度 （ 2）每个顶点对应一个距离值 S中顶点：从 V0到此顶点的长度 T中顶点：从 V0到此顶点的只包括 S中顶点作中间顶点 的最短路径长度 解题方案： 评分标准： 15 四、问答题（ 20 分，共 2 题，每小题 10 分） 1. 参考答案： 1）该问题的规模缩小到一定的程度就可以容易地解决； 2）该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质； 3）利用该问题分解出的子问题的解可以合并为该问题的解 4）该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子子问题。 解题方案： 知道分治法应用 评分标准： 答对一句 4 分 2. 参考答案： 分支限界法常以广度优先或以最小耗费（最大效益）优先的方式 搜索问题的解空间树。 在分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止。 解题方案： 记忆知识点 评分标准： 10 分
