求解两个长度为n的序列X和Y的一个最长公共序列(如序列ABCBDAB和BDCABA的一个最长公共子序列为BCBA)可以采用多种计算方法。如可以采用蛮力法，对X的每一个子序列，判断其是否也是Y的子序列，最后求出最长的即可，该方法的时间复杂度为(62)。经分析

admin2019-07-12 33

问题求解两个长度为n的序列X和Y的一个最长公共序列(如序列ABCBDAB和BDCABA的一个最长公共子序列为BCBA)可以采用多种计算方法。如可以采用蛮力法，对X的每一个子序列，判断其是否也是Y的子序列，最后求出最长的即可，该方法的时间复杂度为(62)。经分析发现该问题具有最优子序列，可以定义序列成都分别为i和j的两个序列X和Y的最长公共子序列的成都为C[i，j]如下式所示。该方法的时间复杂度为(63)。

(62)

选项 A、O(n²)
B、O(n²lgn)
C、O(n³)
D、O(n2ⁿ)

答案D

解析

转载请注明原文地址:https://jikaoti.com/ti/Z6G7FFFM

本试题收录于：软件设计师上午基础知识考试题库软考中级分类

软件设计师上午基础知识考试

软考中级

相关试题推荐

随机试题

最新回复(0)

软件设计师上午基础知识考试

软考中级

表10-5所给出的类并不完整，根据[说明]和表10-4，将图10-4中的(a)～(c)处补充完整。识别关联的多重度是面向对象建模过程中的一个重要步骤。根据[说明]中给出的描述，完成图10-4中的(1)～(6)。

(1)nv[i-1][j]≥nv[i-1][j-p[i]]+v[i](2)nv[i][j]＝nv[i-1][j](3)j＝j-p[i]问题1中伪代码的时间复杂度为(6)(用O符号表示)。

阅读以下说明，回答问题1～2，将解答填入对应的解答栏内。[说明]某程序的功能是输入三个正整数作为边长，判断三条边构成的三角形是否等边、等腰或是一般三角形。

该程序的控制流图中A～E分别是什么?用基本路径覆盖法给出测试路径。

指出哪张图的哪些文件可以不必画出。根据系统功能和数据流图填充下列数据字典条目中的(1)和(2)：试题得分表二准考证号+{课程名+成绩}考生名册=报名号+准考证号+姓名+通信地址+出生年份+文化程度+职业考生通知单=(1)

用户数据报协议UDP是一种(64)的协议。

男性，58岁。突然出现呼吸困难、胸痛及咯血，怀疑患肺血栓栓塞症，应特别注意是否存在

粉末镜检可见果皮的表皮细胞表面有微细的角质线纹，且散见油细胞的药材是（）

蛔虫病流行范围广、感染率高的原因不包括

某女，77岁。久病，疲乏无力，纳食减少，腹部胀满，喜揉喜按，舌胖嫩苔润，脉细弱无力。其证属

会员制交易所的开支从盈利和会员每年上缴的年会费中取得，盈余部分按出资比例以红利形式分给会员。()

()是受聘任教、晋升工资、实施奖惩的依据。

Comparisonsweredrawnbetweenthedevelopmentoftelevisioninthe20thcenturyandthediffusionofprintinginthe15thand1

在考生文件夹下有一个工程文件sj5．vbp，程序代码中已经写入部分代码，要求根据下面的描述在窗体模块中定义3个名称分别为readdatal、readdata2和writedata的Sub过程。请先装入工程文件sj5．vbp，然后完成以下操作：

Howlongistheregistrationperiodfortheorientationmeeting?

Whatisthepassagemainlyabout?