发布时间 : 星期一 文章算法设计与分析试卷(A)及答案更新完毕开始阅读6789d869a617866fb84ae45c3b3567ec102ddc90
______________________________________________________________________________________________________________
考试课程： 班级： 姓名： 学号：
------------------------------------------------- 密 ---------------------------------- 封 ----------------------------- 线 --------------------------------------------------------- 算法分析考试试卷（A卷） 课程名称 算法分析 编号 题号 得分 评阅人 一 二 三 四 总分 一、填空题（每小题3分，共30分） 1、一个算法的优劣可以用 空间复杂度 与 时间复杂度 来衡量。 2、这种不断回头寻找目标的方法称为 回溯法 。 3、直接或间接地调用自身的算法称为 递归算法 。 4、? 记号在算法复杂性的表示法中表示 紧致界 。 5、由分治法产生的子问题往往是 原问题较小模式 ，这就为使用 递归技术 提供了方便。 6、建立计算模型的目的是为了使 问题的计算复杂性分析有一个共同的客观尺度 。 7、下列各步骤的先后顺序是 ②③④① 。①调试程序 ②分析问题 ③设计算法 ④编写程序。 8、最优子结构性质的含义是 问题最优解包含其子问题最优解 。 9、贪心算法从初始阶段开始，每一个阶段总是作一个使 局部最优 的贪心选择。 10、拉斯维加斯算法找到的解一定是 正确的 。 二、选择题（每小题2分，共20分） 1、哈夫曼编码可利用（ C ）算法实现。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 2、下列不是基本计算模型的是（ B ）。 A、RAM B、ROM C、RASP D、TM 3、下列算法中通常以自顶向下的方式求解最优解的是（ C）。 A、分治法 B、动态规划法 C、贪心法 D、回溯法 精品资料
______________________________________________________________________________________________________________
4、在对问题的解空间树进行搜索的方法中,一个活结点有多次机会成为活结点的是( A ) A、回溯法 B、分支限界法 C、回溯法和分支限界法 D、动态规划 5、秦始皇吞并六国使用的远交近攻，逐个击破的连横策略采用了以下哪种算法思想？ B A、 递归；B、分治；C、迭代；D、模拟。 精品资料 ______________________________________________________________________________________________________________
精品资料
______________________________________________________________________________________________________________
级： 姓名： 学号： ------------- 封 ----------------------------- 线 --------------------------------------------------------- 四、算法设计题（每小题15分，共30分） 1、假设有7个物品，它们的重量和价值如下表所示。若这些物品均不能被分割，且背包容量M＝150，使用回溯方法求解此背包问题。请写出状态空间搜索树并计算各个节点处的限界函数值，最后给出装载方案及背包中物品的重量和价值。 物品 A B C D E F G 重量 35 30 60 50 40 10 25 价值 10 40 30 50 35 40 30 x1?1x2?1x3?1ax1?0ax2?0jaix4?1ax4?0x3?0ax5?0dx4?1ex4?0bx6?0x5?1ex5?0hg精品资料 cex6?0