求解两个长度为n的序列X和Y的一个最长公共序列(如序列ABCBDAB和BDCABA的一个最长公共子序列为BCBA)可以采用多种计算方法。如可以采用蛮力法，对X的每一个子序列，判断其是否也是Y的子序列，最后求出最长的即可，该方法的时间复杂度为(62)。经分析

admin2019-07-12 52

问题求解两个长度为n的序列X和Y的一个最长公共序列(如序列ABCBDAB和BDCABA的一个最长公共子序列为BCBA)可以采用多种计算方法。如可以采用蛮力法，对X的每一个子序列，判断其是否也是Y的子序列，最后求出最长的即可，该方法的时间复杂度为(62)。经分析发现该问题具有最优子序列，可以定义序列成都分别为i和j的两个序列X和Y的最长公共子序列的成都为C[i，j]如下式所示。该方法的时间复杂度为(63)。

(63)

选项 A、O(n²)
B、O(n²lgn)
C、O(n³)
D、O(n2ⁿ)

答案A

解析第62题一个给定的序列的子序列，就是将给定序列中零个或多个元素去掉之后得到的结果。序列ABCBDAB去掉划线的字符ABCBDAB得到的BCBA就是它的一个子序列。一个序列的子序列有2ⁿ个，将X、Y的所有子序列都检查过后即可求出X、Y的最长公共子序列。这种方式的时间复杂度为O(n2ⁿ)。
第63题引进一个二维数组c[j]表示X的i位和Y的j位之前的最长公共子序列的长度，按照公式将数值填入下表。

此时，c[j]中最大的数就是X和Y的最长公共子序列的长度，等于4。该算法的时间复杂度为O(n²)。

转载请注明原文地址:https://kaotiyun.com/show/zQCZ777K

本试题收录于：软件设计师上午基础知识考试题库软考中级分类

软件设计师上午基础知识考试
软考中级

相关试题推荐

随机试题

最新回复(0)

软件设计师上午基础知识考试

软考中级

阅读以下说明和c++码，将应填入(n)处的字名写在的对应栏内。[说明]以下函数完成求表达式的值，请填空使之完成此功能。floatsum(floatx){floats=0.0;ints

阅读以下说明，回答问题，将解答填入对应的解答栏内。[说明]计算下列源代码的McCabe环数，画出控制流程图并用罗马数字标出区域。readx，y，z；type=“scalene”；if(x==yorx==zo

该程序的控制流图中A～E分别是什么?为各测试路径设计测试用例。

阅读以下说明和JAVA2代码，填入(n)处的。[说明]以下JAVA程序实现了在接口interfaceiShape2D的定义和应用，仔细阅读代码和相关注释，将程序补充完整。[代码6-1]interfaceiShape2D

根据题意，指出数据流图中缺失的数据流(a)的名称，并指出该数据流的起点。根据题意，补充数据字典中(d)、(e)、(f)处的空缺。

根据题意，指出数据流图中缺失的数据流(a)的名称，并指出该数据流的起点。将下述文件正确填充在数据流图(b)、(c)处：读者文件、借书文件。

企业信息整合、共享需要一个代表企业身份的信息，该信息应该具有唯一性和易管理性，上述表格中信息项(1)代表企业身份最合适。请将以下叙述中(2)～(5)空缺处的内容填写完整。随着WebService的成熟，现在的(2)(SOA)已经有所发

A．桃红饮加味B．炙甘草汤加味C．独活寄生汤D．蠲痹汤E．犀角散加味(2001年第97，98题)痹证日久，除见关节肿痛外，兼见气血不足及肝肾亏虚症状，治疗宜选用()

在适用第一审程序审理案件的过程中，被告人当庭表示愿意认罪认罚，此时法官的哪种做法是错误的?()

“酶胆分离”通常是哪种疾病的征兆

【2010年第100题】大悬挑体育场屋盖设计中，哪种结构用钢量最少?

光纤通信、卫星通信和数字通信是现代通信的重要方式和发展方向。()

你是限价房的负责人，房屋出现问题，业主网上曝光，媒体来采访，你怎么办？

宪法的本质在于，它是各种（）对比关系的集中体现

Onecenturyago,intheyearbeforeFreudandJung’sfamousvisithere,Americanpsychiatrywasincrisis.Therehadbeenhopet

AncienttreeswithrichtalescanbefoundacrosstheUK.Theyarethesilentwitnessestothestoryoftheseislesthatwelive

PopulationViabilityAnalysisPartATomakepoliticaldecisionsabouttheextentandtypeofforestryinaregionitisimp