2010《算法设计与分析》期末试题.docVIP

  1. 1、本文档共2页,可阅读全部内容。
  2. 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
  3. 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载
  4. 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
  5. 5、该文档为VIP文档,如果想要下载,成为VIP会员后,下载免费。
  6. 6、成为VIP后,下载本文档将扣除1次下载权益。下载后,不支持退款、换文档。如有疑问请联系我们
  7. 7、成为VIP后,您将拥有八大权益,权益包括:VIP文档下载权益、阅读免打扰、文档格式转换、高级专利检索、专属身份标志、高级客服、多端互通、版权登记。
  8. 8、VIP文档为合作方或网友上传,每下载1次, 网站将根据用户上传文档的质量评分、类型等,对文档贡献者给予高额补贴、流量扶持。如果你也想贡献VIP文档。上传文档
查看更多
《算法设计与分析》期末试题A卷 一、填空题(10×2分=20分) 按照渐近阶从低到高的顺序排列下列表达式: ( ) 最优子结构性质的含义是( )。 流水作业调度问题中,作业不满足Johnson不等式时,交换它们的加工顺序后,加工时间( )(增加、不增加、减少、不减少、不变)。 动态规划算法通常以( )的方式解各子问题,而贪心算法通常以( )的方式进行迭代。 优化问题主要由两个部分组成()和( )。 贪心算法的核心问题是( )。 n个元素的集合S中找出满足某种性质的子集时,相应的解空间树称为( ),通常有( )个叶子结点,遍历此空间树需要( )的计算时间。 按照活结点表的组织方式的不同,分支限界法包括( )和( )两种形式。 最大优先队列分支限界法中,优先值较( )的结点优先级较高,通常用( )实现,体现( )的原则。 问题Q的非确定性算法分为两个阶段( )阶段和( )阶段。 二、名词解释(×5分=分) 渐近复杂性 备忘录方法 贪心选择性质 三、算法设计、分析(×5分=2分) 对任何非零偶数,总可以找到奇数和正整数,使得。为了求出两个阶矩阵的乘积,可以把一个阶矩阵分成个子矩阵,每个子矩阵有个元素。当需要求的子矩阵的积时,使用Strassen算法(不必写出)。设计一个传统方法与Strassen算法相结合的矩阵相乘算法,对任何偶数,都可以求出两个阶矩阵的乘积,并分析算法的计算时间复杂性。 设序列和的最长公共子序列为,试说明最长公共子序列问题的最优子结构性质。 对于下图所示的有向图,用Dijkstra算法计算从源顶点1到其他顶点间的最短路径,请列表描述出Dijkstra算法的迭代过程。 表示解向量,其中,表示第i个皇后的列号,试分析其空间树的表示形式及其约束条件。 对于如下图所示的TSP问题,使用优先队列式分支限界法进行求解,试构造出描述其有哪些信誉好的足球投注网站过程的状态空间树,并说明活结点表的变化情况。 四、分析说明题(×5分=30分) 分析说明分治法与动态规法的联系与区别。 在0-1背包问题中,设是背包容量为,可选择物品为时背包问题的最优值,请给出用动态规划算法求解的递归定义。 说明贪心选择性质的证明过程。 列举NP完全问题常用的求解策略。 1 第 2 页 共 2 页 5 1 2 3 4 10 50 20 10 30 100 60 1 30 2 4 3 20 6 10 4 5

文档评论(0)

185****7617 + 关注
实名认证
文档贡献者

该用户很懒,什么也没介绍

1亿VIP精品文档

相关文档