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

admin2019-07-12 39

问题求解两个长度为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://jikaoti.com/ti/e6G7FFFM

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

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

相关试题推荐

随机试题

最新回复(0)

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

软考中级

【说明】设有关于银行借贷管理系统的E-R图。图中矩形表示实体，圆表示属性，双圆表示关键字属性，菱形表示实体间的联系。为了答题的方便，图中的实体和属性同时给出了中英文说明，回答问题时只需写出英文名即可。

阅读下列函数说明和C代码，应填入(n)处。[说明]假设设A和B均为顺序表，A’和B’分别为A和B中除去最大共同前缀后的子表(例如，A=(x，y，y，z，x，z)，B=(x，y，y，z，y，x，x，z)，则两者中最大的共同前缀为(x，y，y

阅读以下说明和VisualBasic码，将应填入(n)处的字名写在对应栏内[说明]设计一个计时程序。该程序用户界面由一个文本框(text1)，两个按钮——命令按钮1(Command1)按钮、命令按钮(Command2)组成。程序运行后，用

依据说明，完成下面的类图，要求第1层和第2层填写标识、主要属性和操作，第3层填写标识即可。UML规定类图中类之间的关系有关联、聚集、继承，请说明它们的含义和之间的区别。

利用存在的依赖关系构造一个图书馆的对象模型。画出上一问中使用的图书馆程序的层次结构图。

气体干式过滤器接头处漏气的原因是接头松动或损坏，其处理方法是更换导压管。()

全身麻醉根据药物进入机体的途径分为麻醉和麻醉。

提倡“顿悟顿修”的是【】

在迪尔和肯尼迪的组织文化因素理论中，形成企业文化唯一的而且是最大的影响因素是()

净资产收益率的高低，取决于()

A．宫颈糜烂B．宫颈息肉C．宫颈肥大D．宫颈腺体囊肿E．慢性宫颈管炎宫颈糜烂愈合过程中，腺管的开口被阻塞，分泌物滞留于腺腔内，在宫颈表面形成小囊肿

DIC首选抗凝疗法是

根据《中华人民共和国城乡规划法》，县级以上地方人民政府城乡规划主管部门法定行政管理范畴是()。

课堂教学结构包括()

以下属于宋朝与西夏签订的和议是()。