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

admin2019-07-12 63

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

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

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

软考中级

相关试题推荐

随机试题

最新回复(0)

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

软考中级

根据[说明]中的描述，使用参与者列表的英文名称，给出ORS用例图中A1～A4所对应的参与者。根据[说明]中的描述，给出ORS用例图中(1)和(2)所对应的关系。

阅读以下说明，回答问题1～2，将解答填入对应的解答栏内。[说明]某程序的功能是输入三个正整数作为边长，判断三条边构成的三角形是否等边、等腰或是一般三角形。

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

填充流程图中①的判断条件。写出子程序A的功能，并顺序写出实现该功能的操作

上表中带下划线的为主码。请为还没有确定主码或是主码不合理的数据表选定最合适的主码。上面的关系模式中还有不是第二范式的，请将其转为第二范式。并确定新数据表的主码。

阅读以下说明，回答问题，将解答填入对应的解答栏内。[说明]给出一个接收三个数a、b、c作为三角形边长并输出三角形的类型的程序。程序代码如下所示：结点源代码行Areada,b,cB

民法中的平等原则是指()。A．法律面前人人平等B．男女平等C．民事法律关系中当事人地位平等D．民事活动的结果应当平等

简述流行性乙型脑炎实验室检查的特点。

下列哪种片剂要求在21±1℃的水中3分钟即可崩解分散

A、眶蜂窝织炎B、眼眶炎性假瘤C、视神经脑膜瘤D、甲状腺相关免疫眼病E、眼眶静脉曲张成人患者出现双眼眼球突出时，多见于（）

A．气虚B．气陷C．气滞D．气逆E．气闭

某男，49岁，患风湿痹痛5年，常出现腰膝酸软，四肢无力等表现，医生诊断后建议选用独活配伍桑寄生配合治疗。独活治疗头痛的治疗部位是()。

根据《企业所得税法》的规定，下列说法正确的有()。