文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > 高等教育 > 工学 > 东南大学算法设计与分析复习题
侵权投诉

东南大学算法设计与分析复习题

东南大学算法设计与分析复习题 2012年

C[I,j]=max{C[i-1,j],C[i,j-1]} 若i,j>0且xi!=yi

二维数组C,用C[i,j]记录Xi与Yj的LCS的长度 如果我们是自底向上进行递推计算,那么在计算C[i,j]之前, C[i-1,j-1], C[i-1,j]与C[i,j-1]均已计算出来。此时我们 根据X[i]=Y[j]还是X[i]≠Y[j],就可以计算出C[i,j]。

计算的理由:求LCS(Xm-1,Y)的长度与LCS(X,Yn-1)的长度 这两个问题不是相互独立的: ∵两者都要求LCS(Xm-1,Yn-1)的长度, 因而具有重叠性。 另外两个序列的LCS中包含了两个序列的前缀的LCS, 故问题具有最优子结构性质 考虑用动态规划法。

用200~300字概述求最优二分搜索树算法的主要步骤。算法中有哪几点最为关键? 答:记cij是最优子树Tij的耗费, 则ci,k-1是最优子树Ti,k-1的耗费,ck,j是最优子树Tk,j的耗费。 考察以ak (i+1 k j)为根、由结点bi,ai+1,bi+1, ,aj,bj构成的、 耗费最小的树的总耗费:该树的左子树必然是Ti,k-1,右子树必然是Tk,j。 这棵树的总耗费可分为三部分:左子树、右子树和根。 由于Ti,k-1作为左子树接到结点ak之下时,其耗费增加wi,k-1, 故左子树的耗费为:ci,k-1+ wi,k-1, 同理,右子树的耗费为:ck,j+wk,j, 由于根ak的深度为0,按定义,根的耗费为pk。 因此,以ak 为根、耗费最小的树的总耗费为:ci,k-1+ wi,k-1+ckj+wk,j+pk。 注意到,wi,k-1=qi+pi+1+qi+1+ +pk-1+qk-1, wk,j=qk+pk+1+qk+1+ +pj+qj, 从而有wi,k-1+wkj+pk = qi+pi+1+qi+1+ +pk-1+qk-1+ pk +qk+pk+1+qk+1+ +pj+qj = wij。 由此得到以ak 为根、耗费最小的树的总耗费为:ci,k-1+ckj+wi,j

由于pi(i=1,2, ,n), qj(j=0,1,2, ,n)在初始时已经知道, 若wi,j-1已知,则根据wi,j= wi,j-1+pj + qj可以计算出wij。 故当ci,k-1与ckj已知时,以ak 为根的树的最小总耗费 在O(1)时间就可以计算出来。 分别计算以ai+1,ai+2, ,aj为根、 含有结点bi,ai+1,bi+1, ,aj,bj的树的最小总耗费, 从中选出耗费最小的树,此即最优子树Tij。 因此,最优子树Tij的耗费cij={cminj k i <j k i <i,k-1+ckj+wij}。 递推求cij及记录Tij的根的算法

本算法的关键点:分析出最优二分搜索树具有最优子结构;在计算中规模较小的最优子树在计算中要被多次用到。Cij和Wij都是可以通过前面的计算递推得出的。

有了Tij的根的序号后,如何构造出最优二分搜索树?

答:设Tij的根为ak (rij记录到的值是k),则从根开始建结点。

Build-tree(i,j,r,A) /*建立最优子树Tij*/

{If i j return "nill";

pointer←newnode(nodetype);

k←rij; /*必有i < m j*/

pointer→value←A[k]; /*A[k]即ak*/

上一页第4页

你可能喜欢

  • 程序设计基础复习题
  • 系统分析设计复习题
  • 平法复习题
  • 道路勘测设计复习题
  • 算法分析设计复习题
  • 算法设计分析复习题
  • 电路分析基础复习题

热门文档

相关文档

  • 东南大学算法设计与分析复习题

    东南大学算法设计与分析复习题_理学_高等教育_教育专区。算法设计与分析期末考试提纲的参考资料。什么是基本运算? 什么是基本运算? 答:基本运算是解决问题时占支配...

  • 算法设计与分析复习题

    算法设计与分析复习题_IT/计算机_专业资料。算法设计与分析复习题算法设计与分析复习题 1、 一个算法应有哪些主要特征? 又穷性,确定性,可行性,0 个或多个输入...

  • 算法设计与分析复习题

    算法设计与分析复习题_工学_高等教育_教育专区。算法设计与分析复习题 1 一个... 算法设计与分析期末试题... 3页 免费 东南大学算法设计与分析... 22页 ...

  • 算法设计与分析复习题

    算法设计与分析复习题_计算机软件及应用_IT/计算机_专业资料。西南交大 算法 ... 东南大学算法设计与分析... 22页 免费 算法设计与分析期末试题... 3页 ...

  • 算法设计与分析复习题

    算法设计与分析复习题 1、 一个算法应有哪些主要特征? 又穷性,确定性,可行性... 东南大学算法设计与分析... 22页 免费 算法设计与分析试题(A) 3页 免费 ...

  • 算法设计与分析复习题目及答案(物联班)

    算法设计与分析复习题目及答案(物联班)_IT认证_资格考试/认证_教育专区。一。选择题 1、二分搜索算法是利用( A、分治策略 B、动态规划法 )实现的算法。 C...

  • 算法设计与分析复习题

    算法设计与分析复习题 1、分治法的基本思想:是将一个规模为 N 的问题分解为 K 个规模较小的子问题,这些子问题互相独立且与原问 、分治法的基本思想: 题相同...

  • 算法设计与分析考试复习题

    算法设计与分析考试复习题_工学_高等教育_教育专区。该文档用于算法设计与分析考试的复习,文档中有选择填空和知识点总结,涵盖了大量的考点信息,适合大学本科生复习...

  • 算法分析与设计—部分复习题答案

    算法分析与设计—部分复习题答案_计算机软件及应用_IT/计算机_专业资料。西南交大 算法考试题目算法设计与分析复习题 1、 一个算法应有哪些主要特征? 有限性、确定...

  • 计算机算法设计与分析复习题

    计算机算法设计与分析复习题_工学_高等教育_教育专区。选填,简要介绍文档的主要内容,方便文档被更多人浏览和下载。《算法分析与设计》期末复习题一、 选择题 1....

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email