首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
对于求取两个长度为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
108
问题
对于求取两个长度为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~6,将答案填入对应的解答栏内。某公司有一个局域网,在ISP申请了Internet接入,接入方式是以太网,ISP分配给了一个固定的IP地址为222.152.199.33、子网掩码为255.255.255.252、默认网关为2
阅读以下说明,回答问题1到问题5。将答案填入对应的解答栏内。某企业采用Windows2003操作系统部署企业虚拟专用网(VPN),将企业的两个异地网络通过公共Internet安全地互联起来。微软Windows2003操作系统当中对IPSec具备
xinetd可使用only_from、no_access以及access_time等参数对用户进行访问控制。若服务器上ftp服务的配置信息如下所示:serviceftp{only-from=192.168.3.0/24
文件/etc/sysconfig/network-scripts/eth0用于存储网络配置信息,请根据图2-1填写下面的空缺信息,完成主机的配置。DEVICE=eth0HWADDR=(7)ONBOOT=yesBOOT
文件/etc/sysconfig/network-scripts/eth0用于存储网络配置信息,请根据图2-1填写下面的空缺信息,完成主机的配置。DEVICE=eth0HWADDR=(7)ONBOOT=yesBOOT
阅读以下说明,回答问题。[说明]某学校计划部署校园网络,其建筑物分布如图1-11所示。根据需求分析结果,校园网规划要求如下:(1).信息中心部署在图书馆;(2).实验楼部署237个点,办公楼部署87个点,学生宿舍部署4
在网络的拓扑结构中,处于上层的结点称为(36)。只要有一个结点发生故障,网络通信就无法进行的结构是(37);数据单方向传输的拓扑结构是(38)。(39)允许某些站点具有优先级。交换式局域网属于(40)。
SNMPc是一个通用的多用户分布式网络管理平台,采用(21)轮询机制,具有高度的可伸缩性。假设有一个局域网,管理站每15分钟轮询被管理设备一次,一次查询访问需要的时间是200ms,则管理站最多可以支持(22)台网络设备。
阅读下列函数说明、图和C代码,回答问题[说明]在进行文法分析的时候,通常需要检测一个单词是否在我们的单词列表里。为了提高查找和定位的速度,通常都要画出与单词列表所对应的单词查找树。程序构造一棵二叉排序树,每个节点存储一个单词,按字典序列,
文法G=({E),{+,*,(,),a},P,E),其中P由下列产生式组成E->E+E|E*E|(E)|a。它生成由a,+,*,(,)组成的算术表达式,该文法在乔姆斯基分层中属于(16)型文法,其对应的自动机是(17),如产生句子a*a+a,它的派生树是(
随机试题
《学会生存》一书指出:“可能平等地受教育,这只是平等的必要条件,而不是它的充分条件……平等的机会必须包括同样成功的机会”“机会平等是要肯定每一个人都能受到适当的教育,而且这种教育的进度和方法是适合个人特点的。”这主要阐述了()。
数字通信比模拟通信抗干扰能力强。()
治疗心衰使用扩张血管药硝普钠时护士除观察血压、心率外,还应注意( )。
下列属于导致我国儿童伤害死亡第一位的是()
某男性工人,先后从事煤矿开采工和矿场采石工,年龄45岁,工龄10年以上。因主诉咳嗽、气短、胸痛就诊。X线胸片呈现肺纹理增加,伴有块状阴影和典型结节,诊断时应注意哪种尘肺
监理单位应根据所承担的监理任务,组建驻工地监理机构。监理机构一般由()组成。
商业银行的经营是其对所开展的各种业务活动的()。
下列各项中,属于认定层次重大错报风险的是()。
在司法实践中,应当强调法律效果优于社会效果。()
It’safactoflifeinthe21st-centuryworkplace:Thebossmaywellbewatchinghisemployees,especiallyiftheyuseacompute
最新回复
(
0
)