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

admin2013-05-11 83

问题对于求取两个长度为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://kaotiyun.com/show/A1RZ777K

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

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

软考中级

相关试题推荐

随机试题

最新回复(0)

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

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

软考中级

X．509证书标准是一种由发布者数字签名的用于绑定(1)和其持有者身份的数据结构。发布者是证书的颁发者，它(2)；(3)和公开密钥的绑定是证书的核心内容。它们的绑定是通过(垒)实现的。(3)

X．509证书标准是一种由发布者数字签名的用于绑定(1)和其持有者身份的数据结构。发布者是证书的颁发者，它(2)；(3)和公开密钥的绑定是证书的核心内容。它们的绑定是通过(垒)实现的。(1)

在SNMP中，管理进程查询代理中一个或多个变量的值所用报文名称为(1)，该报文的默认目标端口是(2)。(2010年下半年试题)(2)

E1载波的基本帧由32个子信道组成。其中30个子信道用于传送语音数据，2个子信道(1)用于传送控制信令。该基本帧的传送时间为(2)。(2009年下半年试题)(1)

下面关于ATM网基本原理的说法，__________是错误的。

在Windows环境下，DHCP客户端可以使用(1)命令重新获得IP地址，这时客户机向DHCP服务器发送一个(2)数据包来请求租用IP地址。(2008年上半年试题)(2)

以下关于网络安全设计原则的说法，错误的是()。

对于文法G(S)：S→S+aT|aT|+aTT→aT|a对于句型aT+aaa，(28)是该句型的直接短语，(29)是该句型的句柄。

热力学第一定律和第二定律表明的是隔离体系能量守恒定律和隔离体系过程方向和限度。()

腱鞘囊肿的治疗要点不包括

A．首剂现象B．高血压危象C．刺激性子咳D．踝部水肿E．电解质和物质代谢紊乱ACEI的主要不良反应是

在招股说明书中，发行人应披露有关股本的情况，主要包括()

语言符号的任意性

对事件A，B，已知0＜P(A)＜1，P(B)＞0，P(B｜A)＝P(B｜)．则：【】

下列选项中，哪些是按照文件的用途划分的文件分类?()

下列工具中，不属于结构化分析的常用工具的是()。

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

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

软考中级

X．509证书标准是一种由发布者数字签名的用于绑定(1)和其持有者身份的数据结构。发布者是证书的颁发者，它(2)；(3)和公开密钥的绑定是证书的核心内容。它们的绑定是通过(垒)实现的。(3)

X．509证书标准是一种由发布者数字签名的用于绑定(1)和其持有者身份的数据结构。发布者是证书的颁发者，它(2)；(3)和公开密钥的绑定是证书的核心内容。它们的绑定是通过(垒)实现的。(1)

在SNMP中，管理进程查询代理中一个或多个变量的值所用报文名称为(1)，该报文的默认目标端口是(2)。(2010年下半年试题)(2)

E1载波的基本帧由32个子信道组成。其中30个子信道用于传送语音数据，2个子信道(1)用于传送控制信令。该基本帧的传送时间为(2)。(2009年下半年试题)(1)

下面关于ATM网基本原理的说法，__________是错误的。

在Windows环境下，DHCP客户端可以使用(1)命令重新获得IP地址，这时客户机向DHCP服务器发送一个(2)数据包来请求租用IP地址。(2008年上半年试题)(2)

以下关于网络安全设计原则的说法，错误的是()。

对于文法G(S)：S→S+aT|aT|+aTT→*aT|*a对于句型aT+a*a*a，(28)是该句型的直接短语，(29)是该句型的句柄。

热力学第一定律和第二定律表明的是隔离体系能量守恒定律和隔离体系过程方向和限度。()

腱鞘囊肿的治疗要点不包括

A．首剂现象B．高血压危象C．刺激性子咳D．踝部水肿E．电解质和物质代谢紊乱ACEI的主要不良反应是

在招股说明书中，发行人应披露有关股本的情况，主要包括()

语言符号的任意性

对事件A，B，已知0＜P(A)＜1，P(B)＞0，P(B｜A)＝P(B｜)．则：【】

下列选项中，哪些是按照文件的用途划分的文件分类?()

下列工具中，不属于结构化分析的常用工具的是()。

对于文法G(S)：S→S+aT|aT|+aTT→aT|a对于句型aT+aaa，(28)是该句型的直接短语，(29)是该句型的句柄。