求解两个长度为n的序列X和Y的一个最长公共子序列(如序列ABCBDAB和BDCABA的一个最长公共子序列为BCBA)可以采用多种计算方法。经分析发现该问题具有最优子结构，可以定义序列长度分别为i和j的两个序列X和Y的最长公共子序列的长度为c[i,j]，

admin2018-11-21 29

问题求解两个长度为n的序列X和Y的一个最长公共子序列(如序列ABCBDAB和BDCABA的一个最长公共子序列为BCBA)可以采用多种计算方法。
经分析发现该问题具有最优子结构，可以定义序列长度分别为i和j的两个序列X和Y的最长公共子序列的长度为c[i,j]，如下式所示。

采用自底向上的方法实现该算法，则时间复杂度为_____________。

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

答案A

解析本题考查算法设计与分析的基本知识。要求考生熟悉典型的算法设计技术及其典型的问题的求解。
应用蛮力法求解最长公共子序列时，其思路在题干已经给出。对X的每一个子序列，判断其是否也是Y的子序列，那么长度为n的序列X的子序列数是2ⁿ，而判断一个子序列是否也是Y的子序列的时间是n，因此时间复杂度为O(n2ⁿ)。
而采用动态规划自底向上的方法求解时，题干也给出了最优子结构和递归式的定义，因此很容易看出算法的时间复杂度实际上就是i和j的两重循环，时间复杂度为O(n²)。

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

本试题收录于：嵌入式系统设计师上午基础知识考试题库软考中级分类

嵌入式系统设计师上午基础知识考试

软考中级

相关试题推荐

随机试题

最新回复(0)

嵌入式系统设计师上午基础知识考试

软考中级

两个公司希望通过Internet　进行安全通信，保证从信息源到目的地之间的数据传输以密文形式出现，而且公司不希望由于在中间节点使用特殊的安全单元而增加开支，最合适的加密方式是(10)，使用的会话密钥算法应该是(11)。

微机A和微机B采用同样的CPU，微机A的主频为800MHz而微机B为1200MHz。若微机A的平均指令执行速度为40MIPS，则微机A的平均指令周期为(6)ns，微机B的平均指令执行速度为(7)MIPS。

计算机病毒是(8)。特洛伊木马一般分为服务器端和客户端，如果攻击主机为A，目标主机为B，则(9)。

为了解决进程间的同步和互斥问题，通常采用一种称为(21)机制的方法。若系统中有5个进程共享若干个资源R，每个进程都需要4个资源R，那么使系统不发生死锁的资源R的最少数目是(22)。

白盒测试通常采用的方法是(30)，(31)不属于白盒测试用例设计方法。黑盒测试也称为功能测试，它不能发现(32)。

关于源程序功能性注释不正确的说法是(28)。

上市公司发生下列情形时，属于证券法律制度禁止其增发股票的有()。(2011年)

[*]

下列哪些物质既是糖氧化分解的中间产物或产物又是糖异生的原料

根据库氏(Couinand)肝脏分段法错误的是

在编报招股说明书时，发行人除应披露非经常性损益项目和金额外，还应当对重大非经常性损益项目的内容增加必要的附注说明。(　　)

对变现能力较差的抵押物，其抵押率应适当提高。()

开放系统互连基本参考模型OSI将计算机网络通信功能划分为七层。()

1，3，3，9，12，36，42，()。

YouwillheararadiopresenterinterviewingaveryfamousSeniorHRManagerinthetop500fortunecalledKarlaDeCaprio.F

InParagraph1,"I’msurpriseditwasthatmuch"meanstheauthorthinks______.InMainetheauthorhadtodrivetoabookstor

嵌入式系统设计师上午基础知识考试

软考中级

两个公司希望通过Internet 进行安全通信，保证从信息源到目的地之间的数据传输以密文形式出现，而且公司不希望由于在中间节点使用特殊的安全单元而增加开支，最合适的加密方式是(10)，使用的会话密钥算法应该是(11)。

微机A和微机B采用同样的CPU，微机A的主频为800MHz而微机B为1200MHz。若微机A的平均指令执行速度为40MIPS，则微机A的平均指令周期为(6)ns，微机B的平均指令执行速度为(7)MIPS。

计算机病毒是(8)。特洛伊木马一般分为服务器端和客户端，如果攻击主机为A，目标主机为B，则(9)。

为了解决进程间的同步和互斥问题，通常采用一种称为(21)机制的方法。若系统中有5个进程共享若干个资源R，每个进程都需要4个资源R，那么使系统不发生死锁的资源R的最少数目是(22)。

白盒测试通常采用的方法是(30)，(31)不属于白盒测试用例设计方法。黑盒测试也称为功能测试，它不能发现(32)。

关于源程序功能性注释不正确的说法是(28)。

上市公司发生下列情形时，属于证券法律制度禁止其增发股票的有()。(2011年)

[*]

下列哪些物质既是糖氧化分解的中间产物或产物又是糖异生的原料

根据库氏(Couinand)肝脏分段法错误的是

在编报招股说明书时，发行人除应披露非经常性损益项目和金额外，还应当对重大非经常性损益项目的内容增加必要的附注说明。( )

对变现能力较差的抵押物，其抵押率应适当提高。()

开放系统互连基本参考模型OSI将计算机网络通信功能划分为七层。()

1，3，3，9，12，36，42，()。

YouwillheararadiopresenterinterviewingaveryfamousSeniorHRManagerinthetop500fortunecalledKarlaDeCaprio.F

InParagraph1,"I’msurpriseditwasthatmuch"meanstheauthorthinks______.InMainetheauthorhadtodrivetoabookstor

两个公司希望通过Internet　进行安全通信，保证从信息源到目的地之间的数据传输以密文形式出现，而且公司不希望由于在中间节点使用特殊的安全单元而增加开支，最合适的加密方式是(10)，使用的会话密钥算法应该是(11)。

在编报招股说明书时，发行人除应披露非经常性损益项目和金额外，还应当对重大非经常性损益项目的内容增加必要的附注说明。(　　)