首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
对于求取两个长度为n的字符串的最长公共子序列(LCS)问题,利用(57)策略可以有效地避免子串最长公共子序列的重复计算,得到时间复杂度为O(n2)的正确算法。串<1,0,0,1,0,1,0,1,>和<0,1,0,1,1,0,1,1,>的最长公共子序列的长度
对于求取两个长度为n的字符串的最长公共子序列(LCS)问题,利用(57)策略可以有效地避免子串最长公共子序列的重复计算,得到时间复杂度为O(n2)的正确算法。串<1,0,0,1,0,1,0,1,>和<0,1,0,1,1,0,1,1,>的最长公共子序列的长度
admin
2008-02-15
77
问题
对于求取两个长度为n的字符串的最长公共子序列(LCS)问题,利用(57)策略可以有效地避免子串最长公共子序列的重复计算,得到时间复杂度为O(n
2
)的正确算法。串<1,0,0,1,0,1,0,1,>和<0,1,0,1,1,0,1,1,>的最长公共子序列的长度为(58)。
选项
A、分治
B、贪心
C、动态规划
D、分支一限界
答案
C
解析
本题考查的是动态规划算法策略的典型应用。LCS问题是利用动态规划策略解决的经典问题之一,利用动态规划求解该问题时可以通过查表得到已经计算出的子串的最长公共子序列,从而避免重复计算。利用动态规划算法可以得到题目中两个串的最长公共子序列长度为6,如“101011”。
转载请注明原文地址:https://kaotiyun.com/show/cbxZ777K
本试题收录于:
软件设计师上午基础知识考试题库软考中级分类
0
软件设计师上午基础知识考试
软考中级
相关试题推荐
阅读以下说明,回答问题1~3,将解答填入对应的解答栏内。某公司的分支机构通过一条DDN专线接入到公司总部,地址分配和拓扑结构如图5-1所示。在两台路由器之间可以使用静态路由,也可以使用动态路由。下面是分支机构路由器R1的配置命令列表,在空
下面是某路由器的部分配置信息,解释(n)处标有下划线部分的含义,将解答填入对应栏内。1.下面是某路由器的部分配置信息,解释(n)处标有下划线部分的含义,将解答填入对应栏内。[配置路由器信息]Currentconfiguratio
阅读以下说明,回答问题1到问题5。将答案填入对应的解答栏内。某企业采用Windows2003操作系统部署企业虚拟专用网(VPN),将企业的两个异地网络通过公共Internet安全地互联起来。微软Windows2003操作系统当中对IPSec具备
该网络采用核心层、汇聚层、接入层的三层架构。根据层次化网络设计的原则,数据包过滤、协议转换应在(11)层完成;(12)层提供高速骨=F线路;MAC层过滤和IP地址绑定在(13)层完成。(13)
该网络采用核心层、汇聚层、接入层的三层架构。根据层次化网络设计的原则,数据包过滤、协议转换应在(11)层完成;(12)层提供高速骨=F线路;MAC层过滤和IP地址绑定在(13)层完成。(11)
文件/etc/sysconfig/network-scripts/eth0用于存储网络配置信息,请根据图2-1填写下面的空缺信息,完成主机的配置。DEVICE=eth0HWADDR=(7)ONBOOT=yesBOOT
RSA是一种基于(31)原理的公钥加密算法。网络上广泛使用的PGP协议采用 RSA和IDEA 2种加密算法组成链式加密体系,这种方案的优点是(32)。PGP还可以对电子邮件进行认证,认证机制是用MD5算法产生(33)位的报文摘要,发送方用自己的RSA私钥对
DES加密算法采用的密码技术是(61),它采用(62)bit密钥对传输的数据进行加密。著名的网络安全系统Kerberos采用的是(63)加密技术,公钥密码是(64),常用的公钥加密算法有(65),它可以实现加密和数字签名。
按路由默认的优先级别从高到低的排序正确的是(50)。
VirtualizationisanapproachtoITthatpoolsandshares(1)sothatutilizationisoptimizedandsuppliesautomaticallymeetd
随机试题
A.曲马多B.羟考酮C.芬太尼D.吗啡E.氯丙嗪用于麻醉前给药和麻醉诱导的是
突触传递中,影响神经末梢递质释放量的关键因素是
患者,女,43岁。眩晕2个月,加重1周,昏眩欲仆,神疲乏力,面黃色咣白,时有心悸,夜寐欠安,舌淡,脉细。治疗应首选()
设y=sin(x+y),则()。
由于受教育程度和经历的不同,不同人对同条信息有不同的理解,这属于()障碍。
监理单位的投标书由( )组成。
在耐火砖的砌筑过程中,若是湿砌,在砌筑前应先进行()。
暂准进口的施工机械、工程车辆、安装用仪器应在规定期限内复运出境,超过规定期限,应从()开始按月征收进口关税和进口环节税。
“夫智者必量其力所能至而如从事焉”体现的教学原则是()
Thepovertylineistheminimumincomethatpeopleneedforanacceptablestandardofliving.Peoplewithincomesbelowthepove
最新回复
(
0
)