首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
求解两个长度为n的序列X和Y的一个最长公共序列(如序列ABCBDAB和BDCABA的一个最长公共子序列为BCBA)可以采用多种计算方法。如可以采用蛮力法,对X的每一个子序列,判断其是否也是Y的子序列,最后求出最长的即可,该方法的时间复杂度为(62)。经分析
求解两个长度为n的序列X和Y的一个最长公共序列(如序列ABCBDAB和BDCABA的一个最长公共子序列为BCBA)可以采用多种计算方法。如可以采用蛮力法,对X的每一个子序列,判断其是否也是Y的子序列,最后求出最长的即可,该方法的时间复杂度为(62)。经分析
admin
2019-07-12
54
问题
求解两个长度为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
软件设计师上午基础知识考试
软考中级
相关试题推荐
阅读以下说明和图,回答问题1至问题3。【说明】某房屋租赁公司欲建立一个房屋租赁服务系统,统一管理房主和租赁者的信息,从而快速地提供租赁服务。该系统具有以下功能:1.登记房主信息。对于每名房主,系统需登记其姓名、住址和联系电话,并将这些信息
根据说明中的描述,使用表3-1给出的类的名称,给出图3-1中的A~F所对应的类。图3-1中缺少了一条关联,请指出这条关联两端所对应的类以及每一端的多重度。
阅读下列程序说明和C++代码,将应填入(n)处。【说明】“背包问题”的基本描述是:有一个背包,能盛放的物品总重量为S,设有N件物品,其重量分别为w1;w2,……,wn,希望从N件物品中选择若干件物品,所选物品的重量之和恰能放入该背包,即所选物品
根据E-R图中给出的词汇,按照“有关模式名(属性1,属性2,…)”的格式,将此E-R图转换为关系模式,并指出每个关系模式中的主码和外码,其中模式名根据需要取实体名或联系名。要求其中的关系模式至少属于第三范式。如下的SQL语言用于查询“在该银行中一笔贷款
【说明】设有关于银行借贷管理系统的E-R图。图中矩形表示实体,圆表示属性,双圆表示关键字属性,菱形表示实体间的联系。为了答题的方便,图中的实体和属性同时给出了中英文说明,回答问题时只需写出英文名即可。
阅读下列函数说明和C代码及流程图,将应填入(n)处的字句写在对应栏内[说明]分糖果问题是一个经典问题。问题描述如下:幼儿国有n(<20)个孩子围成一圈分糖果,老师先随机地发给每个孩子若干颗糖果,然后按以下规则调整:每个孩子同时将自己手中的糖果分
下列给定程序中,函数fun()的功能是:对N名学生的学习成绩,按从高到低的顺序找出前m(m≤10)名学生来,并将这些学生数据存放在一个动态分配的连续存储区中,此存储区的首地址作为函数值返回。注意:部分源程序给出如下。请勿改动主函数main和
利用存在的依赖关系构造一个图书馆的对象模型。张三到图书馆借阅一本书,两个月后,他把这本逾期的书返还给图书馆。画出这个场景的时序图。
工作流(Workflow)是针对业务流程中具有固定程序的常规活动而提出的一个概念,通过将业务流程分解,定义良好的任务、角色、规则和过程来进行执行和监控,达到提高生产组织水平和工作效率的目的。以下关于工作流叙述中,错误的是(1)。在UML中,用(2)
IP协议是TCP/IP体系结构(20)上的实用的协议。TCP协议是TCP/IP体系结构(21)上使用的协议。TCP/IP体系结构的(22)上没有专用的协议。SUP协议位于TCP/IP体系结构的(23)。
随机试题
吴老师的专制管理班级方式遭到学生的集体造反。经过一番思考后,吴老师决定让学生一起商量班级管理主题班会,让学生了解班级的不足和自己的责任;其次,把任务按小组分配给同学,组织学生开展小组竞争;再次,一起为班级建设提建议;最后,增强双方沟通。渐渐地班级中呈现出一
A.肾气不固证B.膀胱湿热证C.脾肾亏虚证D.肾虚水泛证E.脾阳虚证小便浑浊如米泔见于
出生45天,女,患儿发热3天,喂养困难,嗜睡,阵发性惊厥,咳嗽,平静时有喘鸣音,体温39.0℃,其治疗原则应为
中风病急性期治疗的关键是__________。
将金融市场分为一级市场和二级市场的分类标准是()。
通过加强质量管理可提高组织经济效益,主要有两个途经,包括()。
教师在“细胞中的元素和化合物”一节的备课时,先通过与班主任和其他任课教师的交流,了解了授课班级的学习风气。这属于备课中的()。
Thewatertapwasleaking(漏水)again,andthenoisewasdrivingCassiecrazy.Cassielookedatherwatch.Itwasnearlynineo
(2017年真题)甲、乙约定:甲赠与乙紫砂壶一把,该合同在乙结婚时生效。该合同属于()。
【B1】【B2】
最新回复
(
0
)