算法设计与分析答案(2006)

程 工 件 软□ 生 读 跟域 领 程□工考 缓 □ 考 补 级 年 点 地 试 考号 学 点 地 课 上 名 姓 院 学 件 软 位 单院作学工 ------重庆大学工程硕士研究生《算法设计与分析》(考试时间：2 小时 闭卷 )课程试题参考答案 ---- -- 考试时间：2006-6-8 - -- - - - - --题号 一 二 三 四 五 平时成绩 总分 四、 描述算法题（15分） - -- -在下图所给的有向图G中，每一边都有一个非负边权。请画出优先队列式分支限界法解 -得分 - - -- 有向图G的单源最短路径问题产生的解空间树。其中，每一个结点旁边的数字表示该结点所 - - 说明：考试卷面成绩占80%，平时成绩占20%。答题时，请标明题号，答案写在答题纸上。 对应的当前路长。 密- - -- - -- -一、 选择题（10分） -- - --1. 问题所分解出的各子问题是相互独立的，即子问题之间不包含公共的子问题，一般 - -- -采用 C 算法较好。 -- - --(A）动态规划 (B) 贪心算法 (C) 分治算法 (D) 分支限界法 - -- - -- - --2. 下列哪个不属于动态规划算法的基本要素 D 。 - -- -(A）最优子结构 (B) 重叠子问题 (C) 备忘录方法 (D) 剪枝函数 五、 描述算法题（20分） -。-- 负-- 货物装箱问题：设有一艘货船装物品。共有n=6件物品，它们的重量为[w1,..., -自---3. 针对贪心算法以下哪个描述是不恰当 B 。 w6]=[100,200,50,90,50,20]，物品的价值为[p1,..., p6]=[20,50,25,15,20,10]，船的限任---责-(A）并不从整体最优考虑，只是在某种意义上的局部最优选择 载重量是c=300。试用贪婪算法装船，要求物品装得最多。贪婪准则：从剩下的货箱中选择--，---(B) 针对所给问题，定义问题的解空间 重量最小的货箱。试设计一个装船的贪婪算法，要求装船的物品价值最大。请用伪代码描述的---(C) 做出在当前看来最好的选择 你的算法。 绩---成---(D) 不能对所有问题都得到整体最优解 -记--- 登---法--4. 下列哪个不属于回溯法的基本思想 A 。 2．动态规划算法与贪心算法的主要区别是什么？ -无---(A）以广度优先方式搜索解空间 所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心 成--造封(B) 针对所给问题，定义问题的解空间 选择来达到。这是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主-而---(C) 确定易于搜索的解空间结构 要区别。 写---填--(D) 以深度优先方式搜索解空间 -求--- 3．什么是完全子图？什么是最大团？ 要---按-5. 下列哪个术语不用于分支限界法 B 。 给定无向图G=(V，E)。如果U?V，且对任意u，v?U有(u，v)?E，则称U是G的完全子--未---(A）广度优先 (B) 限界函数 (C) 扩展结点 (D) 以最小耗费搜索 图。G的完全子图U是G的团当且仅当U不包含在G的更大的完全子图中。 或- -清-- -不---二、 填空题（10分） 4．最大独立集的定义是什么？ 迹---字 -1. 如果各子问题是不独立的，一般用 动态规划 较好。 如果U?V且对任意u，v?U有(u，v)?E，则称U是G的空子图。G的空子图U是G的独-因---2. 分治法所能解决的问题一般具有特征为 最优子结构性质 、 子问题的解可以合并为该问立集当且仅当U不包含在G的更大的空子图中。G的最大独立集是G中所含顶点数最多如---。--题的解 、 子问题是相互独立 。 的独立集。 -写---3. 动态规划基本步骤有 找出最优解的性质 、 递归地定义最优值 、 以自底向上的方式计算 填---真-出最优值 -、 根据计算最优值时得到的信息，构造最优解 。 5．分支限界法与回溯法的区别是什么？ -认---4. 贪心算法求解的问题应具有的性质 贪心选择性质 和 最优子结构性质 。 （1）求解目标：回溯法的求解目标是找出解空间树中满足约束条件的所有解，而分支限体---字--5. 用回溯法解题的一个显著特征是 在搜索过程中动态产生问题的解空间 。 界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出-楷--- 在某种意义下的最优解。 正-用线三、 问答题（25分） （2）搜索方式的不同：回溯法以深度优先的方式搜索解空间树，而分支限界法则以广度--学---1. 分治法的设计思想是什么？ 优先或以最小耗费优先的方式搜索解空间树。 同---请-分治法的设计思想是，将一个难以直接解决的大问题，分割成一些规模较小的相同问题，--项---以便各个击破，分而治之。 各--- 上---以--- ：----注---