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

admin2013-05-11 91

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

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

软考中级

用户B收到用户A带数字签名的消息M，为了验证M的真实性，首先需要从CA获取用户的数字证书，并利用(1)验证该证书的真伪，然后利用(2)验证M的真实性。(2012年下半年试题)(1)

IEEE802．11定义了无线局域网的两种工作模式，其中的(1)模式是一种点对点连接的网络，不需要无线接入点和有线网络的支持。IEEE802．11g的物理层采用了扩频技术，工作在(2)频段。(2008年上半年试题)(2)

在异步通信中，每个字符包含1位起始位、7位数据位、1位奇偶校验位和2位终止位，若每秒钟传送100个字符，采用4相相位调制，则码元速率为(1)，有效数据速率为(2)。(2008年上半年试题)(1)

在Windows系统中监听发送给NT主机的陷入报文的程序是__________。(2012年下半年试题)

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

根据用户需求选择正确的网络技术是保证网络建立成功的关键，在选择网络技术时应考虑多种因素。下面各种考虑中，不正确的是()。

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

黄酮苷元糖苷化后，苷元的苷化位移规律是

粘弹剂在眼科手术中的作用主要包括

动物脑膜脑炎出现狂躁不安时，首选的治疗药物是

HⅣ脑膜炎奈菌

【2005年第127题】抗震设防烈度8度时，多少米以上的悬挑阳台和走廊等长悬臂结构需验算竖向地震作用?

足球比赛球门的宽度应为()。

我国公安机关的专政职能与民主职能的关系是()。

12个啤酒空瓶可以免费换1瓶啤酒，现有101个啤酒空瓶，最多可以免费喝到的啤酒为()。