首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
求解两个长度为n的序列X和Y的一个最长公共序列(如序列ABCBDAB和BDCABA的一个最长公共子序列为BCBA)可以采用多种计算方法。如可以采用蛮力法,对X的每一个子序列,判断其是否也是Y的子序列,最后求出最长的即可,该方法的时间复杂度为(62)。经分析
求解两个长度为n的序列X和Y的一个最长公共序列(如序列ABCBDAB和BDCABA的一个最长公共子序列为BCBA)可以采用多种计算方法。如可以采用蛮力法,对X的每一个子序列,判断其是否也是Y的子序列,最后求出最长的即可,该方法的时间复杂度为(62)。经分析
admin
2019-07-12
56
问题
求解两个长度为n的序列X和Y的一个最长公共序列(如序列ABCBDAB和BDCABA的一个最长公共子序列为BCBA)可以采用多种计算方法。如可以采用蛮力法,对X的每一个子序列,判断其是否也是Y的子序列,最后求出最长的即可,该方法的时间复杂度为(62)。经分析发现该问题具有最优子序列,可以定义序列成都分别为i和j的两个序列X和Y的最长公共子序列的成都为C[i,j]如下式所示。该方法的时间复杂度为(63)。
(63)
选项
A、O(n
2
)
B、O(n
2
lgn)
C、O(n
3
)
D、O(n2
n
)
答案
A
解析
第62题一个给定的序列的子序列,就是将给定序列中零个或多个元素去掉之后得到的结果。序列ABCBDAB去掉划线的字符ABCBDAB得到的BCBA就是它的一个子序列。一个序列的子序列有2
n
个,将X、Y的所有子序列都检查过后即可求出X、Y的最长公共子序列。这种方式的时间复杂度为O(n2
n
)。
第63题引进一个二维数组c
[j]表示X的i位和Y的j位之前的最长公共子序列的长度,按照公式将数值填入下表。
此时,c
[j]中最大的数就是X和Y的最长公共子序列的长度,等于4。该算法的时间复杂度为O(n
2
)。
转载请注明原文地址:https://kaotiyun.com/show/zQCZ777K
本试题收录于:
软件设计师上午基础知识考试题库软考中级分类
0
软件设计师上午基础知识考试
软考中级
相关试题推荐
使用[说明]中给出的词汇,将数据流图10-1中(1)~(4)处的数据流补充完整。使用[说明]中给出的词汇,将数据流图10-2中的(5)~(8)补充完整。
根据说明中的描述,使用表3-1给出的类的名称,给出图3-1中的A~F所对应的类。图3-1中缺少了一条关联,请指出这条关联两端所对应的类以及每一端的多重度。
图(a)中只有一个外部实体E1。使用【说明】中的词语,给出E1的名称。使用【说明】中的词语,给出图(b)中的数据存储D1~D4的名称。
阅读下列说明,回答问题1至问题3,将解答填入对应栏内。【说明】某餐厅供应各种标准的营养套餐。假设菜单上共有n项食物m1,m2,…,mn,每项食物mi的营养价值为vi,价格为pi其中i=1,2,…,n,套餐中每项食物至多出现一次。客人常需要一个算法
该程序的控制流图中A~E分别是什么?为各测试路径设计测试用例。
指出哪张图的哪个文件可以不必画出。指出数据流图4-1和数据流图4-2中错误的数据流。
阅读下列算法说明和算法,将应填入(n)的字句写在答题纸的对应栏内。【说明】下列最短路径算法的具体流程如下:首先构造一个只含n个顶点的森林,然后依权值从小到大从连通网中选择不使森林中产生回路的边加入到森林中去,直至该森林变成一棵树为止,这棵树
阅读下列程序说明,将在空缺处填入正确的内容。【程序说明】定义一个多边形结构:structpolygon实现以下内容:(1)建立该结构的链表:create函数是创建链表,每输入一个结点的数据,就把该结点加入到链表当中,它返回创建的链表的头指
阅读以下关于某订单管理系统的技术说明、部分UML类图及Java程序,将Java程序中(1)~(5)空缺处的语句填写完整。[说明]某订单管理系统的部分UML类图如图5-16所示。在图5-16中,Product表示产品,Pro
请阅读以下技术说明、类图及Java代码,根据要求将(1)~(7)空缺处的内容填写完整。[说明]已知某企业的采购审批是分级进行的,即根据采购金额的不同由不同层次的主管人员来审批,主任可以审批5万元以下(不包括5万元)的采购单,副董事长可以审
随机试题
乳突双15°侧位又称为
甲公司委派业务员王某去乙公司购买钢材,王某持盖章空白合同书以及采购钢材授权委托书前往。甲、乙公司于2010年3月1日签订钢材买卖合同,约定由乙公司代办托运,货交承运人丙公司后即视为完成交付。钢材总价款为100万元,货交丙公司后甲公司付50万元货款,货到甲公
工程地质的节理可以用()描述。
境内个人和境外个人外汇账户境内划转按跨境交易进行管理。()
在新课程背景下,教育评价的根本目的是()。
《桃花源记》中描述:“缘溪行,忘路之远近。忽逢桃花林,……林尽水源,便得一山,山有小口,仿佛若有光。便舍船,从口入。初极狭,才通入。复行数十步,豁然开朗。土地平旷,屋舍俨然,有良田美池桑竹之属。”“桃花源”的地形最可能是()。
李娜说,作为一个科学家。她知道没有一个科学家喜欢朦胧诗,而绝大多数科学家都擅长逻辑思维。因此,至少有些喜欢朦胧诗的人不擅长逻辑思维。以下哪一项的推理结构和题干的推理结构最为类似?
为了保证公司网络的安全运行,预防计算机病毒的破坏,可以在计算机上采取的方法是:
Over1billionpeoplelackadequatehousing.Thesepeoplearefoundineverycountryoftheworldand,indeed,inalmosteveryc
A、Sellingouttravelers’checks.B、Savingsomeofthechecks.C、Lendinghersomeofthechecks.D、Gettingmoretravelers’checks
最新回复
(
0
)