首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
对于求取两个长度为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
106
问题
对于求取两个长度为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,将解答填人答题纸对应的解答栏内。【说明】某公司通过PIX防火墙接入Internet,网络拓扑如图所示。在防火墙上利用show命令查询当前配置信息如下:PIX#showconfignameifeth0outsi
网络A的WWw服务器上建立了一个Web站点,对应的域名是www.abc.edu。DNS服务器1上安装WindowsServer2003操作系统并启用DNS服务。为了解析www服务器的域名,在所示的对话框中,新建一个区域的名称是(1);在图6—4所示的对
阅读以下说明,回答问题1~2,将解答填入对应栏内。VPN是通过公用网络Internet将分布在不同地点的终端联接而成的专用网络。目前大多采用IPsec实现IP网络上端点间的认证和加密服务。某路由器的部分配置信息如下所示,请解释其中标有下划线
IPSec安全体系结构包括AH,ESP和ISAKMP/Oakley等协议。其中,(4)为IP包提供信息源验证和报文完整性验证,但不支持加密服务;(5)提供加密服务;(6)提供密钥管理服务。(6)
文件/etc/sysconfig/network-scripts/eth0用于存储网络配置信息,请根据图2-1填写下面的空缺信息,完成主机的配置。DEVICE=eth0HWADDR=(7)ONBOOT=yesBOOT
阅读以下说明,根据要求回答问题。[说明]某公司网络结构如图1-23所示,通过在路由器上配置访问控制列表ACL来提高内部网络和Web服务器的安全。根据图1-23的配置,补充完成下面路由器的配置命令:Router(config)
阅读以下说明,回答问题。[说明]某学校计划部署校园网络,其建筑物分布如图1-11所示。根据需求分析结果,校园网规划要求如下:(1).信息中心部署在图书馆;(2).实验楼部署237个点,办公楼部署87个点,学生宿舍部署4
阅读以下说明,回答以下问题,将解答填入答题纸对应的解答内。【说明】某学校计划部署园区网络,本部和分校区地理分布如图1—1所示。根据需求分析结果,网络规划部分要求如下:(1)网络中心机房在信息中心。(2)要求
在内部排序中,通常要对被排序数据序列进行多趟扫描。各种排序方法有其不同的排序实施过程和(时间)复杂性。对给定的整数序列(541,132,984,746,518,181,946,314,205,827)进行从小到大的排序时,采用冒泡排序的第一趟扫描结果是(6
DES加密算法采用的密码技术是(61),它采用(62)bit密钥对传输的数据进行加密。著名的网络安全系统Kerberos采用的是(63)加密技术,公钥密码是(64),常用的公钥加密算法有(65),它可以实现加密和数字签名。
随机试题
Whilemanyworkersarewillingtolearnnewskillsorcompletelyretraintoimprovetheirfutureemployability,fewfeeltheyar
A.紫苏B.荆芥C.香薷D.麻黄E.生姜用于止血。宜炒炭用的药物是
患者,男,36岁,患"慢性肾炎"8年。症见小便不利,肢体浮肿,四肢沉重,腹痛下利,纳差,腰酸,苔白不渴,脉沉者。治宜选用
设A为n阶方阵,且|A|=a≠0,则|A*|等于()。
建设项目的实际造价是()。
吊装载荷包括()。
监理公司在设计阶段建设监理工作的主要任务是()。
下列各项中,按规定应计入企业营业外收入的有()。
简述社会主义教育目的的精神实质。
党的“从群众中来,到群众中去”的工作方法是
最新回复
(
0
)