首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
对于求取两个长度为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
88
问题
对于求取两个长度为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~4,将解答填入对应栏内。虚拟专用网是虚拟私有网络(VirtualPrivateNetwork,VPN)的简称,它是一种利用公共网络来构建的私有专用网络。对于构建VPN来说,网络隧道(Tunneling)技术是个关键技术
阅读以下说明,回答问题1~5,将答案填入对应的解答栏内。配置WWW服务器是Linux操作平台的重要工作之一,而Apach是目前应用最为广泛的Web服务器产品之一。在Linux下安装ApacheWeb服务,Apache服务程序http启动时需要读取
阅读以下说明,回答问题1~5,将答案填入对应的解答栏内。配置WWW服务器是Linux操作平台的重要工作之一,而Apach是目前应用最为广泛的Web服务器产品之一。在Linux下安装ApacheWeb服务,Apache服务程序http启动时需要读取
阅读以下有关网络设备安装与调试的叙述,分析设备配置文件,回答问题1至问题3,把解答填入对应栏内。虚拟局域网(VirtualLAN)是与地理位置无关的局域网的一个广播域,由一个工作站发送的广播信息帧只能发送到具有相同虚拟网号的其他站点,可以形象地认
某Linux服务器上通过xinetd来对各种网络服务进行管理,该服务器上提供ftp服务,ftp服务器程序文件为/usr/bin/ftpd,ftp服务器的配置文件/etc/xinetd.d/ftp内容如下所示,目前该服务器属于开启状态:servic
IPSec安全体系结构包括AH,ESP和ISAKMP/Oakley等协议。其中,(4)为IP包提供信息源验证和报文完整性验证,但不支持加密服务;(5)提供加密服务;(6)提供密钥管理服务。(5)
阅读以下说明。回答以下问题,将解答填入答题纸对应的解答栏内。【说明】某公司计划部署园区网络,其建筑物分布如下图所示。根据需求分析结果,网络规划要求如下:1.网络中心机房在信息大楼。2.设计中心由于业
在网络的拓扑结构中,处于上层的结点称为(36)。只要有一个结点发生故障,网络通信就无法进行的结构是(37);数据单方向传输的拓扑结构是(38)。(39)允许某些站点具有优先级。交换式局域网属于(40)。
VirtualizationisanapproachtoITthatpoolsandshares(1)sothatutilizationisoptimizedandsuppliesautomaticallymeetd
VirtualizationisanapproachtoITthatpoolsandshares(1)sothatutilizationisoptimizedandsuppliesautomaticallymeetd
随机试题
《刑法》第232条规定:“故意杀人的,处死刑、无期徒刑或者十年以上有期徒刑。”法官对杀人案中的被告人依法判处无期徒刑,这体现了()
Notes:CPR心肺复苏campcounselor夏令营负责人WhattrainingwillalsobeofferedinthecourseinadditiontoCPRFirstAidskills?
摩托车后轮胎爆裂时,驾驶人应保持镇定,______,极力控制摩托车保持直线行驶,减速停车。
根据加拿大心血管病学会分类分级,Ⅲ级心绞痛是指
阳虚寒湿之体,痰饮聚久化热;或气血亏虚者,感受湿热之邪,可见胃肠先有宿食湿浊,积久化热,薰蒸秽浊上泛舌面;或血瘀气滞或湿热夹痰,可见
拦水缘石的施工应符合的规定有()。
承担支持农业政策性贷款任务的政策性银行是()。
我国公有制经济包括以下哪些经济形式()
Thefactoryproduceshalfamillionpairsofshoeseveryyear,80%______aresoldabroad.
Completetheformbelow.WriteONEWORDONLYforeachanswer.HOUSESERVICEINFORMATIONExampleAnswerNameBarbaraHill
最新回复
(
0
)