首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
对于求取两个长度为n的字符串的最长公共子序列(LCS)问题,利用(24)策略可以有效地避免子串最长公共子序列的重复计算,得到时间复杂度为O(n2)的正确算法。串 <1,0,0,1,O,1,0,1>和<0,1,0,1,1,0,1,1>的最长公共子序列的长度为
对于求取两个长度为n的字符串的最长公共子序列(LCS)问题,利用(24)策略可以有效地避免子串最长公共子序列的重复计算,得到时间复杂度为O(n2)的正确算法。串 <1,0,0,1,O,1,0,1>和<0,1,0,1,1,0,1,1>的最长公共子序列的长度为
admin
2019-03-11
99
问题
对于求取两个长度为n的字符串的最长公共子序列(LCS)问题,利用(24)策略可以有效地避免子串最长公共子序列的重复计算,得到时间复杂度为O(n
2
)的正确算法。串 <1,0,0,1,O,1,0,1>和<0,1,0,1,1,0,1,1>的最长公共子序列的长度为(25)。
选项
A、3
B、4
C、5
D、6
答案
B
解析
经常会遇到复杂问题不能简单地分解成几个子问题,而会分解出一系列子问题的情况。简单地采用把大问题分解成子问题,并综合子问题的解导出大问题解的方法,则问题求解的时间会按问题规模呈幂级数增加。为了节约重复求相同子问题的时间,引入一个数组,不管它们是否对最终解有用,把所有子问题的解存于该数组中,这就是动态规划法所采用的基本方法。
转载请注明原文地址:https://kaotiyun.com/show/jvRZ777K
本试题收录于:
软件设计师上午基础知识考试题库软考中级分类
0
软件设计师上午基础知识考试
软考中级
相关试题推荐
下面的OSPF网络由多个区域组成。在这些路由器中,属于主干路由器的是(1),属于自治系统边界路由器(ASBR)的是(2)。(1)
ICMP协议属于因特网中的(19)协议,ICMP协议数据单元封装在(20)中传送。(19)
若计算机采用8位整数补码表示数据,则______运算将产生溢出。
在OSPF网络中,路由器定时发出Hello分组与特定的邻居进行联系,在默认情况下,如果__________没有受到这种分组,就认为对方不存在了。(2008年下半年试题)
IEEE802.11定义的AdHoe网络是由无线移动结点组成的对等网,这种网络的特点是(62)。在这种网络中使用的DSDV(Destination-SequencedDistanceVector)路由协议是一种(63)。(62)
所谓移动IP是指(58);实现移动IP的关键技术是(59)。(59)
电话线路使用的带通滤波器的带宽为3kHz(300~3300Hz),根据奈奎斯特采样定理,最小采样频率应为(16)。
非对称加密算法中,加密和解密使用不同的密钥,下面的加密算法中(41)属于非对称加密算法。若甲、乙采用非对称密钥体系进行保密通信,甲用乙的公钥加密数据文件,乙使用(42)来对数据文件进行解密。(42)
阅读以下说明和流程图,从供选择的答案中选出应填入流程图(n)处的字句写在对应栏内。[说明]以下是某图像二元树存储与还原算法的主要思想描述。设一幅2n×2n的二值图像,以:“1”表示黑像素点,以“0”表示白像素点。图像二元树结构表示
现欲实现一个图像浏览系统,要求该系统能够显示.BMP、JPEG和GIF三种格式的文件,并且能够在Windows和Linux两种操作系统上运行。系统首先将BMP、JPEG和GIF三种格式的文件解析为像素矩阵,然后将像素矩阵显示在屏幕上。系统需具有较好的扩展性
随机试题
某政府投资社会保险基金,已知2000年投入40万元人民币,当年的收益率为20%,2000年的投资及收益又投入2001年,如果2001年末收益为150万,请问2001年的收益率?
下列发生在1958年的是()
A.分泌性腹泻B.渗透性腹泻C.渗出性腹泻D.动力性腹泻E.吸收不良性腹泻甲状腺功能亢进引起腹泻多属
口腔医师在确定拔牙适应证时首先应考虑的是
保和丸的组成药物中含有
某实行监理的工程,实施过程中发生下列事件:事件1:建设单位于2005年11月底向中标的监理单位发出监理中标通知书,监理中标价为280万元;建设单位与监理单位协商后,于2006年1月10日签订了委托监理合同。监理合同约定:合同价为260万元;因非监
下列情形中,可以引起诉讼时效中断的事由有()。
在日常教学中,由于学生表现良好,教师减少其家庭作业的量,教师这样的行为称为()。
奥苏伯尔提出的三个主要的影响有意义学习和迁移的认知结构变量是()。
怎样看待内部招聘的利弊?
最新回复
(
0
)