答案及解析：[填空题]求解两个长度为n的序列X和Y的一个最长公共子序列（如序列ABCBDAB和BDCABA的一个最长公共子序列为BCBA）可以采用多种计算方法。如可以采用蛮力法，对X的每一个子序列，判断其是否也是Y的子序列

问题：

[填空题] 求解两个长度为n的序列X和Y的一个最长公共子序列（如序列ABCBDAB和BDCABA的一个最长公共子序列为BCBA）可以采用多种计算方法。如可以采用蛮力法，对X的每一个子序列，判断其是否也是Y的子序列，最后求出最长的即可，该方法的时间复杂度为（　　）。经分析发现该问题具有最优子结构，可以定义序列长度分别为i和j的两个序列X和Y的最长公共子序列的长度为C[i,j]，如下式所示。
中级软件设计师,历年真题,2017年下半年（上午）《软件设计师》真题

采用自底向上的方法实现该算法，则时间复杂度为（　　）。
问题1选项
A.O(n2)
B.O(n2lgn)
C.O(n3)
D.O(n2n)
问题2选项
A.O(n2)
B.O(n2lgn)
C.O(n3)
D.O(n2n)

Tags：软件水平考试中级软件设计师试题及答案

答案解析：

╋纠错

您可能感兴趣的问题

在（）中，项目经理的权力最小。
1. 对象和类是面向对象中两个重要的概念，关于对象和类，不正确的是（）。 A.对象是类的实例 B.类是对象的抽象 C.一个类只能产生一个对象 D.类中包含方法和属性
12. （）可以对预先定义好的策略中涉及的网络访问行为实施有效管理，而对策略之外的网络访问行为则无法控制。 A.入侵防护系统（IPS） B.防火墙（FW） C.虚拟专业网络（VPN） D.分布式拒
25. 项目管理的五大过程组中的（）过程组，与戴明环中的检查和行动环节对应。 A.启动 B.执行 C.规划 D.监控
关于变更管理的描述，不正确的是:（）。 A.每次变更通过评审后，都应重新确定基准 B.必须采用变更管理工具 C.明确变更工作中评估、评审、执行的职责 D.评估变更的可能影响
（）负责批准和监督项目集的人员。 A.项目集治理委员会 B.项目经理 C.项目集发起人 D.项目集经理
下列哪些不是新型物流配送具备的特征 ( )
HTTP 是指( ) A.
层次数据模型是 ( ) 。 A.
目前普遍采用的 EDI 通信模式为 ( )