算法设计方案与分析考试(A)

1、2006级计算机专业20062007学年第二学期算法设计与分析期末试题（A卷）一、填空题（10题X 2分=20分）1、算法运行所需要的计算机资源的量，称为算法复杂性，主要包括（）和（ ）。2、对于函数T（N）,如果存在T（N）,使得当N时有（T （N 舁 T （N ） ）T/N，就说 T（N）是 T（N）当 N：时的（）。3、 多项式A（n） =amnm印n - a0的上界为（）。4、直接或间接地调用自身的算法称为（）,用函数自身给出定义的函数称为（）。5、（）与（）是递归函数的两个要素。6、（）是问题能用动态规划算法求解的前提。7、贪心算法的两个基本要素是（）和（）o8回溯法的含义是（ ）o

2、9、 回溯法中的解空间树结构通常有两种，分别是（）、（ ）o10、 用分支限界法解布线问题时，对空间树搜索结束的标志是（）o二、判断题（10题X 2分=20分）1、如果 g（N）=O（f（N），则 O（f）+O（g）=O（f）。2、所有的递归函数都能找到对应的非递归定义。3、动态规划算法中，通常不同子问题的个数随问题规模呈指数级增长。4、备忘录方法求解时采用与递归定义一致的自上而下的方式。5、用贪心算法解找零钱问题时，总能得到整体最优解。6、满足贪心选择性质必满足最优子结构性质。7、 哈夫曼算法以自上而下的方式构造表示最优前缀码的二叉树To8回溯法中限界函数的目的是剪去得不到最优解的子树。9、

3、每个优化问题都是由目标函数和约束条件组成。10、状态空间树中，只有展开了所有子结点的结点才称为死结点。三、简答题（6题X 5分=30分）1、简述分治法和动态规划算法的联系和区别。2、简述回溯法求解问题的一般步骤。3、 简述回溯法和分支限界法的相同点和不同点。4、设序列X ,Xi,x2丄，Xm和、-爲i,y,L ,y的最长公共子序列为Z ,Zi,Z2丄,Zk（1）分析该问题的最优子结构性质。（2）若用cij记录序列Xi二咲兀丄，以和乂亠y丄，曲 的公共子序列长度，给出用动态规划法求解时子问题的递归公式。5、给出01背包问题的文字及数学描述，指出用回溯法求解时的解空间树 结构，并分析该问题的约束条

4、件和限界函数。6、简述什么是P类判定问题，什么是NP类判定问题。四、计算题（2题X 7分=14分）1、描述流水作业调度问题及其 Johnson法则，应用该法则求解以下作业的 调度次序，使得所有作业加工完成所需的时间最少，要求写出求解的方法步 骤。已知：给定6个作业讣2,3,4,5,6?,其在第一台机器上加工所需时间分别为：31 1, 2, 1 6,8, 在3第二台机器上加工所需时间分别为：12,10,7,14,18,6? o2、对给定的连通带权图，画出用Kruskal算法求最小生成树的选边过程/i423五、算法分析题（2题X 8分=16分）1、设n个不同的整数按从小到大排好序后存于T0: n-1中。若存在下标i,0乞i ”： n，使得Ti =i,请找到这个下标并输出，否则给出不存在的输出信 息。要求：设计一个有效算法求解该问题，并且算法在最坏情况下的时间复 杂度为O（log n） o （注：假定若存在这样的下标，只需找到一个即可）。2、设有n个顾客同时等待一项服务。顾客i需要的服务时间为乞n。应 如何安排n个顾客的服务次序使总的等待时间最小？总的等待时间是每个顾 客等待服务时间（每个顾客等待