对于求取两个长度为n的字符串的最长公共子序列问题，利用(57)策略可以有效地避免子串最长公共子序列的重复计算，得到时间复杂度为O(n2)的正确算法。

admin2013-05-11 89

问题对于求取两个长度为n的字符串的最长公共子序列问题，利用(57)策略可以有效地避免子串最长公共子序列的重复计算，得到时间复杂度为O(n²)的正确算法。

选项 A、贪心
B、分治
C、分支—限界
D、动态规划

答案D

解析对于求取两个长度为n的字符串的最长公共子序列(LCS)问题，是利用动态规划策略解决的经典问题之一。利用动态规划策略求解该问题时可以通过查表得到已经计算出的子串的最长公共子序列，从而避免重复计算。例如，利用动态规划算法可以得到串＜1,0,0,1,0,1,0,1＞和＜0,1,0,1,1,0,1,1＞的最长公共子序列的长度为6，如“101011”。

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

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

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

软考中级

相关试题推荐

随机试题

最新回复(0)

对于求取两个长度为n的字符串的最长公共子序列问题，利用(57)策略可以有效地避免子串最长公共子序列的重复计算，得到时间复杂度为O(n2)的正确算法。

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

软考中级

在一个由多台路由器构成的网络中，一条途经多个路由器的线路断开了，判断是哪一个路由器发生故障的命令是(1)。在发现跨路由器ping不通的情况下，可用配置管理工具收集(2)信息进行分析。(2)

局域网参考模型中，两个子系统的同等实体按照协议进行通信，在一个系统中，上下层之间则通过接口进行通信，用__________来定义接口。

RIP协议中可以使用多种方法防止路由循环，在以下选项中不属于这些方法的是__________。(2011年上半年试题)

tracert命令通过多次向目标发送皿来确定到达目标的路径，在连续发送的多个IP数据包中，(2)字段都是不同的。(2009年上半年试题)(1)

32位的IP地址可以划分为网络号和主机号两部分。以下地址中，(1)不能作为目标地址，(2)不能作为源地址。(20l1年下半年试题)(1)

若某公司创建名字为www．business．com的虚拟主机，则需要在()服务器中添加地址记录。

在OSI参考模型中，实现端到端的应答、分组排序和流量控制功能的协议层是()。

阅读以下说明，回答问题1～4，将解答填入对应的解答栏内。[说明]假设二叉树采用链式存储方式存储，编写一个后序遍历二叉树的非递归方式。Voidpostorder(btreeB){btreestack[m0

在喷射除锈中，输料导管通径的选择可按喷嘴直径的3～4倍来确定。

三叉神经痛的患者疼痛部位在颊部及下颌关节区者，其罹患支是

名义年收益率为20％，对于半年付息一次的债券而言，则年实际收益率为()。

业主委员会应当在召开业主大会会议()日前将会议通知及有关材料以书面形式在物业管理区域内公告。

苏铁最为出名的奇景是()。

文书承办工作的内容包括()

Whatisthemainpurposeofthiscall?

Inareactionagainstatoo-rigid,overrefinedclassicalcurriculum,someeducationalphilosophershaveswungsharplytoanesp

对于求取两个长度为n的字符串的最长公共子序列问题，利用(57)策略可以有效地避免子串最长公共子序列的重复计算，得到时间复杂度为O(n2)的正确算法。

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

软考中级

在一个由多台路由器构成的网络中，一条途经多个路由器的线路断开了，判断是哪一个路由器发生故障的命令是(1)。在发现跨路由器ping不通的情况下，可用配置管理工具收集(2)信息进行分析。(2)

局域网参考模型中，两个子系统的同等实体按照协议进行通信，在一个系统中，上下层之间则通过接口进行通信，用__________来定义接口。

RIP协议中可以使用多种方法防止路由循环，在以下选项中不属于这些方法的是__________。(2011年上半年试题)

tracert命令通过多次向目标发送皿来确定到达目标的路径，在连续发送的多个IP数据包中，(2)字段都是不同的。(2009年上半年试题)(1)

32位的IP地址可以划分为网络号和主机号两部分。以下地址中，(1)不能作为目标地址，(2)不能作为源地址。(20l1年下半年试题)(1)

若某公司创建名字为www．business．com的虚拟主机，则需要在()服务器中添加地址记录。

在OSI参考模型中，实现端到端的应答、分组排序和流量控制功能的协议层是()。

阅读以下说明，回答问题1～4，将解答填入对应的解答栏内。[说明]假设二叉树采用链式存储方式存储，编写一个后序遍历二叉树的非递归方式。Voidpostorder(btree*B){btree*stack[m0

在喷射除锈中，输料导管通径的选择可按喷嘴直径的3～4倍来确定。

三叉神经痛的患者疼痛部位在颊部及下颌关节区者，其罹患支是

名义年收益率为20％，对于半年付息一次的债券而言，则年实际收益率为()。

业主委员会应当在召开业主大会会议()日前将会议通知及有关材料以书面形式在物业管理区域内公告。

苏铁最为出名的奇景是()。

文书承办工作的内容包括()

Whatisthemainpurposeofthiscall?

Inareactionagainstatoo-rigid,overrefinedclassicalcurriculum,someeducationalphilosophershaveswungsharplytoanesp

阅读以下说明，回答问题1～4，将解答填入对应的解答栏内。[说明]假设二叉树采用链式存储方式存储，编写一个后序遍历二叉树的非递归方式。Voidpostorder(btreeB){btreestack[m0