中南大学2014算法试卷和答案分析报告.pdf

word 格式文档 中南大学考试试卷 2013 -- 2014 学年 下 学期 时间 100 分钟 2014 年 6 月 6 日 算法分析与设计 课程 48 学时 3 学分 考试形式： 闭 卷 专业年级： 12 级计算机、信安、物联本科生，总分 100 分，占总评成绩 70 % 注：此页不作答题纸，请将答案写在答题纸上 一、简答题（本题 30 分，每小题 5 分） 1、 陈述算法在最坏情况下的时间复杂度和平均时间复杂度；这两种评估算法复杂性的方 法各自有什么实际意义？ 1 最坏情况下的时间复杂度称最坏时间复杂度。一般不特别说明，讨论的时间复杂度 均是最坏情况下的时间复杂度。 意义：最坏情况下的时间复杂度是算法在任何输 入实例上运行时间的上界，这就保证了算法的运行时间不会比任何更长 2 平均时间复杂度是指所有可能的输入实例均以等概率出现的情况下，算法的期望运 行时间。 意义：在输入不同的情况下算法的运行时间复杂度可能会发生变化。平 均时间复杂度给出了算法的期望运行时间，有助于算法好坏的评价以及在不同算法 之间比较时有一个统一标准 2、 简单描述分治法的基本思想。 分治法的基本思想是将一个规模为 n 的问题分解为 k 个规模较小的子问题， 这些子问题 互相独立且与原问题相同。递归地解这些子问题，然后将各个子问题的解合并得到原问 题的解 。 3、 何谓最优子结构性质？ 如果问题的最优解所包含的子问题的解也是最优的， 我们就称该问题具有最优子结构性 质（即满足最优化原理） 。最优子结构性质为动态规划算法解决问题提供了重要线索。 4、 何谓 P、 NP、NPC问题 P(Polynomial 问题 ) ：也即是多项式复杂程度的问题。 NP就是 Non-deterministic Polynomial 的问题，也即是多项式复杂程度的非确定性 问题。 NPC(NP Complete) 问题，这种问题只有把解域里面的所有可能都穷举了之后才能得出 答案，这样的问题是 NP里面最难的问题，这种问题就是 NPC问题。 5、 试比较回溯法与分支限界法。 1、引言 1.1 回溯法 回溯法在问题的解空间树中，按深度优先策略，从根结点出发搜索解空间树。算法 搜索至解空间树的任意一点时，先判断该结点是否包含问题的解。如果肯定不包含，则 跳过对该结点为根的子树的搜索，逐层向其祖先结点回溯；否则，进入该子树，继续按 深度优先策略搜索。这种以深度优先方式系统搜索问题解的算法称为回溯法。 专业整理 word 格式文档 1.2 分支限界法 分支限界法是以广度优先或以最小耗费优先的方式搜索解空间树， 在每一个活结点 处，计算一个函数值，并根据函数值，从当前活结点表中选择一个最有利的结点作为扩 展结点，使搜索朝着解空间上有最优解的分支推进，以便尽快地找出一个最优解，这种 方法称为分支限界法。 2、回溯法的基本思想 用回溯法解问题时，应明确定义问题的解空间。问题的解空间至少应包含问题的一 个解。之后还应将解空间很好的组织起来，使得能用回溯法方便的搜索整个解空间。在 组织解空间时常用到两种典型的解空间树，即子集树和排列树。确定了解空间的组织结 构后，回溯法从开始结点出发，以深度优先方式搜索整个解空间。这个开始结点成为活 结点，同时也成为当前的扩展结点。在当前的扩展结点处，搜索向纵深方向移至一个新 结点。这个新结点就成为新的活结点，并成为当前扩展结点。如果在当前的扩展结点处 不能再向纵深方向移动，则当前扩展