2009-2010学年第二学期《计算机算法设计与分析》试卷A(软07级).doc

装 订 线 2009—2010 学年第二学期《计算机算法设计与分析》试卷（A） （院系：软件学院 专业：软件工程 　 年级：07级 考核形式： 开卷 ） 题 号 一 二 三 四 卷面分 折合分 （占80%） 平时分 （占 20％） 总分 评卷人 复查人 分 数 10 15 45 30 100 80 20 100 得 分 得分 评卷人 简答题（共3小题，第1，2小题3分，第3小题4分， 总计10分） 1.(3分) 请用英文写出三种以上能求解0-1背包问题的设计算法策略。 2.(3分) 请说明动态规划方法为什么需要最优子结构性质。 4. (4分) 请说明：(1)优先队列可用什么数据结构实现？(2)优先队列插入算法基本思想？(3)优先队列插入算法时间复杂度？ 得分 评卷人 二、填空题 （共15个空，每空1分，总计15分） 1．递归的二分查找算法在divide阶段所花的时间是 ，conquer阶段所花的时间是 ，算法的时间复杂度是 。 2．Prim算法利用 策略求解 问题，其时间复杂度是 。 3．背包问题可用 ， 等策略求解。 4．用动态规划算法计算矩阵连乘问题的最优值所花的时间是 ， 子问题空间大小是 。 5．图的m着色问题可用 法求解，其解空间树中叶子结点个数是 ，解空间树中每个内结点的孩子数是 。 6．单源最短路径问题可用 、 等策略求解。 得分 评卷人 三、计算题（共4小题，第1,2,3小题10分，第4小题15分， 总计45分） 1．用动态规划策略求解最长公共子序列问题： （1）给出计算最优值的递归方程。 （3分） （2）给定两个序列X={B,C,D,A}，Y={A,B,C,B}，请采用动态规划策略求出其最长公共子序列，要求给出过程。(7分) 院 系 年 级 专 业 姓 名 学 号 考试课程 装 订 线 装 订 线 2．（10分）对下列各组函数f (n) 和g (n)，确定f (n) = O (g (n)) 或f (n) =Ω(g (n))或f(n) =θ(g(n))，并简要说明理由。 (1) f(n)=2n； g(n)=n! (2) f(n)=； g (n)=log n2 (3) f(n)=100； g(n)=log100 (4) f(n)=n3； g(n)= 3n (5) f(n)=3n； g(n)=2n 3．（10分）对下图所示的连通网络G，用克鲁斯卡尔(Kruskal)算法求G的最小生成树T,请写出在算法执行过程中，依次加入T的边集TE中的边。说明该算法的贪心策略和算法的基本思想，并简要分析算法的时间复杂度。 4．（15分）考虑n=3的批处理作业调度实例： tji 机器1 机器2 作业1 1 10 作业2 3 1 作业3 2 1 其中tji是作业Ji需要在机器j上处理的时间。对于给定的3个作业，制定一个最佳作业调度方案，使其完成时间和达到最小。 要求： （1）画出该问题的解空间树； （5分） （2）写出该问题的剪枝策略(即限界条件)，要求只保留第一个最优解；（2分） （3）按优先队列式分支限界法有哪些信誉好的足球投注网站解空间树，并用剪枝策略对解空间树中该剪枝的位置打(； （5分） （4）给出最优解及最优值。 （3分） 院 系 年 级 专 业 姓 名 学 号 考试课程 装 订 线 装 订 线 得分