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

admin2019-07-12 47

问题求解两个长度为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)

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

软考中级

下面是快速排序的伪代码，请填补其中的空缺；伪代码中的主要变量说明如下。A：待排序数组p，r:数组元素下标，从p到rq:划分的位置x：枢轴元素i：整型变量，用于描述数组下标。下标小于或等于i的元素的值小于或等于枢轴

(1)nv[i-1][j]≥nv[i-1][j-p[i]]+v[i](2)nv[i][j]＝nv[i-1][j](3)j＝j-p[i]现有5项食物，每项食物的营养价值和价格如下表所示。食物营养价值及价格表　　若要求总价格不超过100的营养

试分析该关系模式中的函数依赖，并指出关系模式的候地选码。如下的SQL语句是检索“每个学生及其选修的课程名和成绩”的不完整语句，请在空缺处填入正确的内容。SELEC(1)FROM(2)WHERE(3)

阅读以下关于某订单管理系统的技术说明、部分UML类图及C++代码，将C++程序中(1)～(5)空缺处的语句填写完整。[说明]某订单管理系统的部分UML类图如图5-15所示。图5-15中，Product表示产品，Produc

IP协议是TCP/IP体系结构(20)上的实用的协议。TCP协议是TCP/IP体系结构(21)上使用的协议。TCP/IP体系结构的(22)上没有专用的协议。SUP协议位于TCP/IP体系结构的(23)。

核酸分子杂交可用于

最近报道一女青年接受X线检查时，对医生让其脱掉上衣不解，甚至认为医生这样做是非常无礼的，有的甚至因此发生纠纷。此案例说明的核心伦理学问题是

关于注射法哪项叙述不正确

资本市场要求产权结构具有()和流动性，为优势企业进行兼并重组提供一种资产形态转换和资产流动的机制。

下列岩石中，属于水成岩的是()。

专有技术通常是指生产某种商品的专利。

赫尔巴特说：“我想不到有任何无教学的教育，正如在相反的方面，我不承认有任何无教育的教学。”这体现的是()。

1925年，掀起全国范围内大革命高潮的是()

有以下程序段inti，n；for(i＝0；i＜8；i＋＋){n＝rand()％5；switch(n){case1：case3：printf("％d＼n"，n)；break；case2：case4：prin

Stratford-on-Avon,asweallknow,hasonlyoneindustry—WilliamShakespeare—.Buttherearetwodistinctlyseparateandincreas