首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
对于求取两个长度为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
37
问题
对于求取两个长度为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~5,将答案填入对应的解答栏内。配置WWW服务器是Linux操作平台的重要工作之一,而Apach是目前应用最为广泛的Web服务器产品之一。在Linux下安装ApacheWeb服务,Apache服务程序http启动时需要读取
阅读以下说明,回答问题1到问题5。将答案填入对应的解答栏内。某企业采用Windows2003操作系统部署企业虚拟专用网(VPN),将企业的两个异地网络通过公共Internet安全地互联起来。微软Windows2003操作系统当中对IPSec具备
阅读以下说明,回答问题1到问题5。将答案填入对应的解答栏内。某企业采用Windows2003操作系统部署企业虚拟专用网(VPN),将企业的两个异地网络通过公共Internet安全地互联起来。微软Windows2003操作系统当中对IPSec具备
note-bat脚本文件如下:time/t>>note.lognetstat-n-ptcp|find":3389">>note.logstartExplorer第一行代码用于记录用户登录的时间,“t
若网络管理员决定在企业内部增加WLAN接入功能,无线路由器基本参数设置如图1-2所示。网络管理员决定在无线AP上开启MAC地址过滤功能,若该AP的MAC地址过滤表如图1-3所示,则下面说法正确的是______。A.MAC地址为“00-OA-EB
阅读以下说明,回答问题。[说明]某学校计划部署校园网络,其建筑物分布如图1-11所示。根据需求分析结果,校园网规划要求如下:(1).信息中心部署在图书馆;(2).实验楼部署237个点,办公楼部署87个点,学生宿舍部署4
RAID级别是指磁盘阵列中硬盘的组合方式,不同级别的RAID为用户提供的磁盘阵列在性能上和安全性的表现上也有不同。以下(31)是具有磁盘镜像和双工功能的磁盘阵列。
文法G=({E),{+,*,(,),a},P,E),其中P由下列产生式组成E->E+E|E*E|(E)|a。它生成由a,+,*,(,)组成的算术表达式,该文法在乔姆斯基分层中属于(16)型文法,其对应的自动机是(17),如产生句子a*a+a,它的派生树是(
VirtualizationisanapproachtoITthatpoolsandshares(1)sothatutilizationisoptimizedandsuppliesautomaticallymeetd
随机试题
供应链信息的采集利用了________。
下列关于条件反射的描述,正确的是
腹部积块,质地较硬,固定不移,隐痛或刺痛,形体瘦,面色晦暗,宜选用‘
固体分散体具有速效作用是因为
监督、检查金融机构履行反洗钱义务的情况是中国人民银行应当履行的反洗钱职责。()
某班的数学、物理、化学的单科前三名分别是甲、乙、丙、丁、戊、己、庚、辛、壬9名同学,现要从这三个科目前三名中各选一名参加校级单科比赛,则甲和庚不能被同时选中的概率是()。
自动稳定器
Itissupposedtobethetimeofopportunityandadventure,beforemortgagesandmarriagehavetakentheirtoll.But【C1】______to
在下列表达式中,结果为字符型的是______。
A、AnexperimentinAntarctica.B、PartoftheLarsenIceShelf.C、PartoftheoceaninAntarctica.D、AnexpeditioninAntarctica.
最新回复
(
0
)