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

admin2019-07-12 62

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

(62)

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

答案D

解析

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

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

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

软考中级

相关试题推荐

随机试题

最新回复(0)

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

软考中级

根据问题描述，填写图10-3实体联系图中(1)～(4)处联系的类型。根据实体联系图10-3，填写挂号单、门诊处方、处方明细和药品库关系模式中的空(5)～(8)处，并指出挂号单、门诊处方和处方明细关系模式的主键。

阅读以下说明和JAVA2代码，将应填入(n)处的字句写在对应栏内。[说明]以下程序实现了在applet里移动图形文件，仔细阅读代码和相关注释，将程序补充完整。[代码6-1]importjava.awt.*;impo

阅读下列程序和控制流图，将应填入(n)的字句。【程序】下面是一段求最大值的程序，其中datalist是数据表，n是datalist的长度。intGetMax(intn，intdatalist[]){intk=0；

计算机中常用的一种检错码是CRC，即(4)码。在进行编码过程中要使用(5)运算。假设使用的生成多项式是C(x)=x4+x3+x+1。原始报文为11001010101，则编码后的报文为(6)。CRC码(7)的说法是正确的。在无线电通信中采用7中取3定比码，它

买壳上市

Doyouknowinsurance(保险)?Buyinginsuranceisa【56】bywhichpeoplecanprotectthemselves【57】largelosses.Protectionagainst

高浓度维生素C可使多项干化学指标出现假阴性，但不包括

下列关于精神康复的主要内容，说法错误的是

A．劳神过度B．外邪侵袭C．先天不足D．情志因素导致心血虚的因素是

[2006年第81题]有一引水虹吸管，出口通大气(图6．2—4)。已知h1=1．5m，h2=3m，不计水头损失，取动能修正系数α=1，则断面c—c中心处的压强pc为()。

严禁砍伐或者迁移古树名木。因特殊需要迁移古树名木，必须()。

上诉场景中，甲承包商的诉讼时效期间届满的时间是(　　)。根据《民法通则》的规定，在诉讼时效期间最后6个月内，因不可抗力或者其他障碍不能行使请求权的，诉讼时效(　　)。

借贷记账法的特点有()。

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

软考中级

根据问题描述，填写图10-3实体联系图中(1)～(4)处联系的类型。根据实体联系图10-3，填写挂号单、门诊处方、处方明细和药品库关系模式中的空(5)～(8)处，并指出挂号单、门诊处方和处方明细关系模式的主键。

阅读以下说明和JAVA2代码，将应填入(n)处的字句写在对应栏内。[说明]以下程序实现了在applet里移动图形文件，仔细阅读代码和相关注释，将程序补充完整。[代码6-1]importjava.awt.*;impo

阅读下列程序和控制流图，将应填入(n)的字句。【程序】下面是一段求最大值的程序，其中datalist是数据表，n是datalist的长度。intGetMax(intn，intdatalist[]){intk=0；

多媒体技术的关键在于解决动态图像和声音的存储与传输问题。若不经压缩，以 VGA640×480点阵存储一幅256色的彩色图像大约需(56)MB存储空间，以9600bit/s的速度传输这幅图像大约需(57)秒，按我国电视PAL标准每秒25幅，一张650MB的光

计算机中常用的一种检错码是CRC，即(4)码。在进行编码过程中要使用(5)运算。假设使用的生成多项式是C(x)=x4+x3+x+1。原始报文为11001010101，则编码后的报文为(6)。CRC码(7)的说法是正确的。在无线电通信中采用7中取3定比码，它

买壳上市

Doyouknowinsurance(保险)?Buyinginsuranceisa【56】bywhichpeoplecanprotectthemselves【57】largelosses.Protectionagainst

高浓度维生素C可使多项干化学指标出现假阴性，但不包括

下列关于精神康复的主要内容，说法错误的是

A．劳神过度B．外邪侵袭C．先天不足D．情志因素导致心血虚的因素是

[2006年第81题]有一引水虹吸管，出口通大气(图6．2—4)。已知h1=1．5m，h2=3m，不计水头损失，取动能修正系数α=1，则断面c—c中心处的压强pc为()。

严禁砍伐或者迁移古树名木。因特殊需要迁移古树名木，必须()。

上诉场景中，甲承包商的诉讼时效期间届满的时间是( )。根据《民法通则》的规定，在诉讼时效期间最后6个月内，因不可抗力或者其他障碍不能行使请求权的，诉讼时效( )。

借贷记账法的特点有()。

上诉场景中，甲承包商的诉讼时效期间届满的时间是(　　)。根据《民法通则》的规定，在诉讼时效期间最后6个月内，因不可抗力或者其他障碍不能行使请求权的，诉讼时效(　　)。