2006级计算机专业2006—2007学年第二学期《算法设计与分析》期末试题(A卷)一、填空题(10题×2分=20分)1、算法运行所需要的计算机资源的量，称为算法复杂性，主要包括（）和（）。2、对于函数，如果存在，使得当时有，就说是当时的（）。3、多项式的上界为（）。4、直接或间接地调用自身的算法称为（），用函数自身给出定义的函数称为（）。5、（）与（）是递归函数的两个要素。6、（）是问题能用动态规划算法求解的前提。7、贪心算法的两个基本要素是（）和（）。8、回溯法的含义是（）。9、回溯法中的解空间树结构通常有两种，分别是（）、（）。10、用分支限界法解布线问题时，对空间树搜索结束的标志是（）。二、判断题(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、状态空间树中，只有展开了所有子结点的结点才称为死结点。三、简答题(6题×5分=30分)1、简述分治法和动态规划算法的联系和区别。2、简述回溯法求解问题的一般步骤。3、简述回溯法和分支限界法的相同点和不同点。4、设序列和的最长公共子序列为。（1）分析该问题的最优子结构性质。（2）若用记录序列和的公共子序列长度，给出用动态规划法求解时子问题的递归公式。5、给出0－1背包问题的文字及数学描述，指出用回溯法求解时的解空间树结构，并分析该问题的约束条件和限界函数。6、简述什么是P类判定问题，什么是NP类判定问题。四、计算题(2题×7分=14分)1、描述流水作业调度问题及其Johnson法则，应用该法则求解以下作业的调度次序，使得所有作业加工完成所需的时间最少，要求写出求解的方法步骤。已知：给定6个作业，其在第一台机器上加工所需时间分别为：，在第二台机器上加工所需时间分别为：。2、对给定的连通带权图，画出用Kruskal算法求最小生成树的选边过程。五、算法分析题(2题×8分=16分)1、设个不同的整数按从小到大排好序后存于中。若存在下标，使得,请找到这个下标并输出，否则给出不存在的输出信息。要求：设计一个有效算法求解该问题，并且算法在最坏情况下的时间复杂度为。（注：假定若存在这样的下标，只需找到一个即可）。16234562455166432、设有个顾客同时等待一项服务。顾客需要的服务时间为。应如何安排个顾客的服务次序使总的等待时间最小？总的等待时间是每个顾客等待服务时间（每个顾客等待服务时间是指：从到达目的地到服务完毕的时间）的总和。（1）用贪心算法求解该问题，写出求解该问题的贪心选择策略。（2）编写求出总的等待时间的算法。