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

admin2019-07-12 60

问题求解两个长度为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://www.kaotiyun.com/show/zQCZ777K

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

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

相关试题推荐

随机试题

最新回复(0)

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

软考中级

根据说明中的描述，使用表3-1给出的类的名称，给出图3-1中的A～F所对应的类。根据说明中的描述，给山图3-1中(1)～(6)处的多重度。

(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]问题1中伪代码的时间复杂度为(6)(用O符号表示)。

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

根据这张通知书所提供的信息，设计了一个E-R模型，如图12-6所示。请将(n)处补充完整。将问题1中的E-R模型(图12-6)转换成4个关系数据模型，要求标注主码和外码。

请补充函数fun()，该函数的功能是将字符串tt中的大写字母都改为对应的小写字母，其他字符不变。例如，若输入“AreyoucomefromSichuan?”，则输入“areyoucomefromsi-chuan?”。注意：部分源程

运行Web浏览器的计算机与网页所在的计算机要建立(66)连接，采用(67)协议传输网页文件。

在比较常见的公共传输系统中，(32)是以模拟技术为基础的电路交换网络；(33)是基于城域网协议的包交换公共数据网络；(34)提供基于线路交换的端到端的数字连接通道。帧中继的典型速率范围是(35)。

急性炎症脱髓鞘性多发性神经病的临床表现特点，下列哪项不符合

我国行政执法人员可依行政处罚简易程序进行执法活动，下列选项哪些体现了该程序的特点?()

对《污水综合排放标准》的第一类污染物，()一律在车间或车间处理设施排放口采样，其最高允许排放浓度必须达到《污水综合排放标准》要求。

下列关于复合式组织结构的优缺点的表述中，不正确的一项为()。

可比性要求同一企业前后各期要提供相互可比的会计信息。()

行政处罚的立法目的是()。

设A，B是两个n阶实对称矩阵，并且A正定．证明：(1)存在可逆矩阵P，使得PTAP，PTBP都是对角矩阵；(2)当|ε|充分小时，A+εB仍是正定矩阵．

Onedayabusinessmanwasgoingtoanothertowntosellhisgoods(货物).Hedecidedtotaketenservants(仆人)withhim.Theywould

A、Edwardwillcertainlybehereontime.B、Nobodywillbehereontime.C、HeisnotsurewhetherEdwardwillbehereontime.D、