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

admin2013-05-11 58

问题对于求取两个长度为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)的正确算法。

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

软考中级

网络管理系统的配置管理最主要的功能是(1)。下列选项中不属于网络管理系统安全管理部分功能的是(2)，不属于网络管理协议的是(3)。(3)

IEEE802．11i标准增强了WLAN的安全性。下面关于802．11i的描述中，错误的是________。(2008年下半年试题)

根据通信信号的传输方式，可以分为(1)、(2)。(1)

以下列出的IP地址中，不能作为目标地址的是(1)，不能作为源地址的是(2)。(2008年上半年试题)(2)

若某计算机采用8位整数补码表示数据，则运算()将产生溢出。

为了解决RIP协议形成路由环路的问题可以采用多种方法，下面列出的方法中效果最好的是()。

图6—9表示了某个数据的两种编码，这两种编码分别是()。

下面是快速排序的伪代码，请填补其中的空缺；伪代码中的主要变量说明如下。A：待排序数组p，r:数组元素下标，从p到rq:划分的位置x：枢轴元素i：整型变量，用于描述数组下标。下标小于或等于i的元素的值小于或等于枢轴

冲击波”病毒属于(8)类型的病毒，它利用Windows操作系统的(9)漏洞进行快速传播。

活跃期宫口扩张异常：第二产程胎头下降异常：

某事业单位以银行存款购入3年期国债，支付投资价款100万元，则下列会计处理正确的有()。

下边这个“金字塔”中每格数字都是该格所对应的下面两格数字之和，如，16是4和12之和。则问号代表的数字是()。

小张通过对20余位专家的访谈得出了“幼儿园教师在职培训”的误区、问题、对策建议，并将其总结为五点。他从专家访谈中得出五条建议的方法是

解决“三农”问题的根本途径是()

J2SDK的基本命令中用于Java类文件归档的是【】。

What’stheproblem?

Whentravelerslackanawarenessof【51】timeisregulatedinaforeigncountry,theycanexpecttofeelsomewhatdisoriented.S

Motherinsistedthat______.