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

admin2018-11-21 78

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

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

软考中级

在编制监理规划时，有关监理措施的内容应突出(58)。

《中华人民共和国专利法》及其实施规定，确定发明和实有新型专利权的保护范围的依据是(1)。《中华人民共和国专利法》规定，专利侵权的诉讼时效是自专利权人或者利害关系人得知或应当得知侵权行为之日起(2)。

下面关于网络系统设计原则的论述，正确的是(13)。

计算机系统中用来连接CPU、内存储器和I/O接口的总线称为系统总线。(1)总线属于系统总线技术的一种。

强心苷加强心肌收缩性的作用来自下述哪个部位

某社区社会工作者上门动员居民参加定期举办的邻里恳谈会。其中一位居民表示自己平时很忙，有空的时候会来，但据社会工作者的观察，这位居民有很多闲暇时间。针对该居民的情况，社会工作者适当的做法有()。

文人画是中国传统绘画中重要的风格流派，自兴起，、朝以后成为中国画坛的主流。它在创作上张扬个性．强调、、、等多种艺术的结合。

曹某是某学校初中一年级的学生。平时喜欢恶作剧，不遵守课堂纪律，并屡教不改，不断有学生前来反映情况，表现出对曹某的不满。面对这种情况，以下做法最为合适的是：

共同侵权人实施侵权行为造成他人损害的，承担的民事责任可能包括()。

软件需求分析阶段的主要任务是()。

Oneisnotguiltyuntilhe______.

Manypeoplewronglybelievethatwhenpeoplereacholdage,theirfamiliesplacetheminnursinghomes.Theyareleftinthe【C1】

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

软考中级

在编制监理规划时，有关监理措施的内容应突出(58)。

《中华人民共和国专利法》及其实施规定，确定发明和实有新型专利权的保护范围的依据是(1)。《中华人民共和国专利法》规定，专利侵权的诉讼时效是自专利权人或者利害关系人得知或应当得知侵权行为之日起(2)。

下面关于网络系统设计原则的论述，正确的是(13)。

计算机系统中用来连接CPU、内存储器和I/O接口的总线称为系统总线。(1)总线属于系统总线技术的一种。

强心苷加强心肌收缩性的作用来自下述哪个部位

某社区社会工作者上门动员居民参加定期举办的邻里恳谈会。其中一位居民表示自己平时很忙，有空的时候会来，但据社会工作者的观察，这位居民有很多闲暇时间。针对该居民的情况，社会工作者适当的做法有()。

文人画是中国传统绘画中重要的风格流派，自________兴起，________、________朝以后成为中国画坛的主流。它在创作上张扬个性．强调________、________、________、________等多种艺术的结合。

曹某是某学校初中一年级的学生。平时喜欢恶作剧，不遵守课堂纪律，并屡教不改，不断有学生前来反映情况，表现出对曹某的不满。面对这种情况，以下做法最为合适的是：

共同侵权人实施侵权行为造成他人损害的，承担的民事责任可能包括()。

软件需求分析阶段的主要任务是()。

Oneisnotguiltyuntilhe______.

Manypeoplewronglybelievethatwhenpeoplereacholdage,theirfamiliesplacetheminnursinghomes.Theyareleftinthe【C1】

文人画是中国传统绘画中重要的风格流派，自兴起，、朝以后成为中国画坛的主流。它在创作上张扬个性．强调、、、等多种艺术的结合。