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

admin2019-07-12 29

问题求解两个长度为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)。

下面是快速排序的伪代码，请填补其中的空缺；伪代码中的主要变量说明如下。A：待排序数组p，r:数组元素下标，从p到rq:划分的位置x：枢轴元素i：整型变量，用于描述数组下标。下标小于或等于i的元素的值小于或等于枢轴

图(a)中只有一个外部实体E1。使用【说明】中的词语，给出E1的名称。在进行系统分析与设计时，面向数据结构的设计方法(如Jackson方法)也被广泛应用。简要说明面向数据结构设计方法的基本思想及其适用场合。

该程序的控制流图中A～E分别是什么?计算控制流图的McCabe环路复杂性。

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

计算机中常用的一种检错码是CRC，即(4)码。在进行编码过程中要使用(5)运算。假设使用的生成多项式是C(x)=x4+x3+x+1。原始报文为11001010101，则编码后的报文为(6)。CRC码(7)的说法是正确的。在无线电通信中采用7中取3定比码，它

计算机中常用的一种检错码是CRC，即(4)码。在进行编码过程中要使用(5)运算。假设使用的生成多项式是C(x)=x4+x3+x+1。原始报文为11001010101，则编码后的报文为(6)。CRC码(7)的说法是正确的。在无线电通信中采用7中取3定比码，它

女性，30岁。发热伴牙龈出血三周。查体：贫血貌，脾肋下3cm，胸骨压痛(+)，血红蛋白70g／L，白细胞14．0×109／L，血小板35×109／L，骨髓增生明显活跃，原始细胞占0．62，为进一步诊断，应首选的检查是

根据我国《合同法》，当事人约定由债务人向第三人履行债务的，债务人未向第三人履行债务或者履行债务不符合约定的，谁有权主张违约责任?()

下列选项不属于人工燃气的是()。

在机械设备结构可靠性设计要点中，()的目的在于提高可靠性，如果盲目采用，或设计不当将会因增加体积、质量和费用而导致相反的效果。

引起中断的中断源有5种，分别为I/O中断，数据通道中断，时钟中断，程序中断和

Gary:Itisgenerallyheldthatonecanpickupaforeignlanguageeasilywhenundertheageofeight.Ifyouimmerseachild

Cellscannotremainaliveoutsidecertainlimitsoftemperature,andmuchnarrowerlimitsmarkthebound-ariesofeffectivefunc

Adulteducationdevelopsfastrecentlypartlybecause______.TheAmericanAssociationforAdultandContinuingEducationissi