《算法设计与分析试题(A)》由会员分享，可在线阅读，更多相关《算法设计与分析试题(A)（2页珍藏版）》请在金锄头文库上搜索。
1、2006级计算机专业20062007学年第二学期算法设计与分析期末试题 (A卷)一、 填空题(10题2分=20分)1、算法运行所需要的计算机资源的量，称为算法复杂性，主要包括（ ）和（ ）。2、对于函数，如果存在，使得当时有，就说是当时的（ ）。3、多项式的上界为（ ）。4、直接或间接地调用自身的算法称为（ ），用函数自身给出定义的函数称为（ ）。5、（ ）与（ ）是递归函数的两个要素。6、（ ）是问题能用动态规划算法求解的前提。7、贪心算法的两个基本要素是（ ）和（ ）。8、回溯法的含义是（ ）。9、回溯法中的解空间树结构通常有两种，分别是（ ）、（ ）。10、用分支限界法解布线问题时，对空
2、间树搜索结束的标志是（ ）。二、判断题(10题2分=20分)1、如果g(N)=O(f(N)，则O(f)+O(g)=O(f)。2、所有的递归函数都能找到对应的非递归定义。3、动态规划算法中，通常不同子问题的个数随问题规模呈指数级增长。4、备忘录方法求解时采用与递归定义一致的自上而下的方式。5、用贪心算法解找零钱问题时，总能得到整体最优解。6、满足贪心选择性质必满足最优子结构性质。7、哈夫曼算法以自上而下的方式构造表示最优前缀码的二叉树T。8、回溯法中限界函数的目的是剪去得不到最优解的子树。9、每个优化问题都是由目标函数和约束条件组成。10、状态空间树中，只有展开了所有子结点的结点才称为死结点。三
3、、简答题(6题5分=30分)1、简述分治法和动态规划算法的了解和区别。2、简述回溯法求解问题的一般步骤。3、简述回溯法和分支限界法的相同点和不同点。4、设序列和的最长公共子序列为。（1）分析该问题的最优子结构性质。（2）若用记录序列和的公共子序列长度，给出用动态规划法求解时子问题的递归公式。5、给出01背包问题的文字及数学描述，指出用回溯法求解时的解空间树结构，并分析该问题的约束条件和限界函数。6、简述什么是P类判定问题，什么是NP类判定问题。四、计算题(2题7分=14分)1、描述流水作业调度问题及其Johnson法则，应用该法则求解以下作业的调度次序，使得所有作业加工完成所需的时间最少，要求
4、写出求解的方法步骤。已知：给定6个作业，其在第一台机器上加工所需时间分别为：，在第二台机器上加工所需时间分别为：。2、对给定的连通带权图，画出用Kruskal算法求最小生成树的选边过程。1623456245516643五、算法分析题(2题8分=16分)1、设个不同的整数按从小到大排好序后存于中。若存在下标，使得,请找到这个下标并输出，否则给出不存在的输出信息。要求：设计一个有效算法求解该问题，并且算法在最坏情况下的时间复杂度为。（注：假定若存在这样的下标，只需找到一个即可）。2、设有个顾客同时等待一项服务。顾客需要的服务时间为。应如何安排个顾客的服务次序使总的等待时间最小？总的等待时间是每个顾客等待服务时间（每个顾客等待服务时间是指：从到达目的地到服务完毕的时间）的总和。（1）用贪心算法求解该问题，写出求解该问题的贪心选择策略。（2）编写求出总的等待时间的算法。二、简答题(5题6=30分)友情提示：部分文档来自网络整理，供您参考！文档可复制、编制，期待您的好评与关注！ /
