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

admin2019-07-12 43

问题求解两个长度为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)

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

软考中级

阅读下列说明和C代码，将应填入(n)处的字句写在对应栏内。【说明】栈(Stack)结构是计算机语言实现中的一种重要数据结构。对于任意栈，进行插入和删除操作的一端称为栈顶(StockTop)，而另一端称为栈底(StockBottom)。栈的基

使用说明中的词语，给出上述顶层数据流图中的外部实体E1～E4的名称。上述0层数据流图中缺少了4条数据流，根据说明及顶层数据流图提供的信息，分别指出这4条数据流的起点和终点。

数据流图12-2缺少了两条数据流，请采用说明中的词汇给出此数据流名称，并指出方向。请补齐下列数据字典条目：系统命令=____输入信息=个人资料=档案维护=_

企业信息整合、共享需要一个代表企业身份的信息，该信息应该具有唯一性和易管理性，上述表格中信息项(1)代表企业身份最合适。请用200字以内文字简要说明WebService涉及到的主要协议及其作用(XML、HTTP等除外)。

消化性溃疡最典型的症状是

关于麻疹的流行病学特点，不正确的是

道德的特点不包括()

下面各项工作内容属于竖向规划修建性详细阶段的是()。

下列关于气体灭火系统控制组件的安装中，不符合要求的是()。

个案会谈是社会工作者与服务对象进行的有目的的专业谈话。下列关于会谈的说法，正确的是()。

(04年)计算曲面积分其中∑是曲面z=1一x2一y2(z≥O)的上侧．

Inthecurrentimmigrationwave,somethingmarkedlydifferentishappeninghereinthemiddleofthegreatAmerican"meltingpot

TheAmericanAcademyofPediatrics(AAP)justreleaseditsupdatedguidelinesforchildren’smediause.Therecommendations

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

软考中级

阅读下列说明和C代码，将应填入(n)处的字句写在对应栏内。【说明】栈(Stack)结构是计算机语言实现中的一种重要数据结构。对于任意栈，进行插入和删除操作的一端称为栈顶(StockTop)，而另一端称为栈底(StockBottom)。栈的基

使用说明中的词语，给出上述顶层数据流图中的外部实体E1～E4的名称。上述0层数据流图中缺少了4条数据流，根据说明及顶层数据流图提供的信息，分别指出这4条数据流的起点和终点。

数据流图12-2缺少了两条数据流，请采用说明中的词汇给出此数据流名称，并指出方向。请补齐下列数据字典条目：系统命令=__________输入信息=__________个人资料=__________档案维护=_______

企业信息整合、共享需要一个代表企业身份的信息，该信息应该具有唯一性和易管理性，上述表格中信息项(1)代表企业身份最合适。请用200字以内文字简要说明WebService涉及到的主要协议及其作用(XML、HTTP等除外)。

消化性溃疡最典型的症状是

关于麻疹的流行病学特点，不正确的是

道德的特点不包括()

下面各项工作内容属于竖向规划修建性详细阶段的是()。

下列关于气体灭火系统控制组件的安装中，不符合要求的是()。

个案会谈是社会工作者与服务对象进行的有目的的专业谈话。下列关于会谈的说法，正确的是()。

(04年)计算曲面积分其中∑是曲面z=1一x2一y2(z≥O)的上侧．

Inthecurrentimmigrationwave,somethingmarkedlydifferentishappeninghereinthemiddleofthegreatAmerican"meltingpot

TheAmericanAcademyofPediatrics(AAP)justreleaseditsupdatedguidelinesforchildren’smediause.Therecommendations

数据流图12-2缺少了两条数据流，请采用说明中的词汇给出此数据流名称，并指出方向。请补齐下列数据字典条目：系统命令=____输入信息=个人资料=档案维护=_