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

2009—2010 学年第二学期《计算机算法设计与分析》试卷(A)

(院系:软件学院 专业:软件工程 年级:07级 考核形式: 开卷 )

参考答案

一、简答题(共3小题,第1,2小题3分,第3小题4分,总计10分) 1.(3分) 请用英文写出三种以上能求解0-1背包问题的设计算法策略。 答:

Dynamic Programming Backtrack

Branch-and-Bound (每答对一条给一分)

2.(3分) 请说明动态规划方法为什么需要最优子结构性质。 答:

最优子结构性质是指大问题的最优解包含子问题的最优解。

动态规划方法是自底向上计算各个子问题的最优解,即先计算子问题的最优解,然后再利用子问题的最优解构造大问题的最优解,因此需要最优子结构 3. (4分) 请说明:(1)优先队列可用什么数据结构实现?(2)优先队列插入算法基本思想?(3)优先队列插入算法时间复杂度? 答:(1)堆。(1分)

(2)在小根堆中,将元素x插入到堆的末尾,

然后将元素x的关键字与其双亲的关键字比较, 若元素x的关键字小于其双亲的关键字, 则将元素x与其双亲交换,然后再将元素x与其新双亲的关键字相比,直到元素x的关键字大于双亲的关键字,或元素x到根为止。 (3)O( log n)(1分) 二、填空题 (共15个空,每空1分,总计15分)

1.递归的二分查找算法在divide阶段所花的时间是conquer

阶段所花的时间是 T(n/2) ,算法的时间复杂度是 O( log n) 。 2.Prim算法利用问题,其时间复杂度是 O(n2

3.背包问题可用,等策略求解。

4.用动态规划算法计算矩阵连乘问题的最优值所花的时间是3, 子问题空间大小是 O(n2。

5.图的m着色问题可用法求解,其解空间树中叶子结点个数是 mn,解空间树中每个内结点的孩子数是。

6.单源最短路径问题可用 、等策略求解。

你可能喜欢

  • 算法设计与分析期末考试题
  • 算法设计与分析第三版王晓东
  • 计算机操作系统期末考试及答案
  • 计算机算法分析
  • 分支限界法
  • 计算机算法设计与分析

2009 2010学年第二学期《计算机算法设计与分析》试卷A 参考答案(软07级)相关文档

最新文档

返回顶部