对于求取两个长度为n的字符串的最长公共子序列问题，利用(57)策略可以有效地避免子串最长公共子序列的重复计算，得到时间复杂度为O(n2)的正确算法。

admin2013-05-11 62

问题对于求取两个长度为n的字符串的最长公共子序列问题，利用(57)策略可以有效地避免子串最长公共子序列的重复计算，得到时间复杂度为O(n²)的正确算法。

选项 A、贪心
B、分治
C、分支—限界
D、动态规划

答案D

解析对于求取两个长度为n的字符串的最长公共子序列(LCS)问题，是利用动态规划策略解决的经典问题之一。利用动态规划策略求解该问题时可以通过查表得到已经计算出的子串的最长公共子序列，从而避免重复计算。例如，利用动态规划算法可以得到串＜1,0,0,1,0,1,0,1＞和＜0,1,0,1,1,0,1,1＞的最长公共子序列的长度为6，如“101011”。

转载请注明原文地址:https://kaotiyun.com/show/A1RZ777K

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

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

软考中级

相关试题推荐

随机试题

最新回复(0)

对于求取两个长度为n的字符串的最长公共子序列问题，利用(57)策略可以有效地避免子串最长公共子序列的重复计算，得到时间复杂度为O(n2)的正确算法。

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

软考中级

X．509证书标准是一种由发布者数字签名的用于绑定(1)和其持有者身份的数据结构。发布者是证书的颁发者，它(2)；(3)和公开密钥的绑定是证书的核心内容。它们的绑定是通过(垒)实现的。(3)

X．509证书标准是一种由发布者数字签名的用于绑定(1)和其持有者身份的数据结构。发布者是证书的颁发者，它(2)；(3)和公开密钥的绑定是证书的核心内容。它们的绑定是通过(垒)实现的。(2)

采用CRC进行差错校验，生成多项式为G(X)=X4+X+1，信息码字为10111，则计算出的CRC校验码是__________。(2010年上半年试题)

在Windows环境下，DHCP客户端可以使用(1)命令重新获得IP地址，这时客户机向DHCP服务器发送一个(2)数据包来请求租用IP地址。(2008年上半年试题)(2)

虚拟存储器是为了使用户可运行比主存容量大得多的程序，它要在()之间进行信息动态调度，这种调度是由操作系统和硬件两者配合来完成的。

关于编译Linux内核的说法，错误的是__________。

WindowsServer2003中的IIS为Web服务提供了许多选项，利用这些选项可以更好地配置Web服务的性能、行为和安全等。如下图所示属性对话框中，“限制网络带宽”选项属于(48)选项卡。

TraditionalIPpacketforwardinganalyzesthe(1)IPaddresscontainedinthenetworklayerheaderofeachpacketasthepacke

A．心、脾、肾B．肺、肝、肾C．肝、脾、心D．肺、脾、肾E．肝、脾、肾(1991年第97，98题)水肿的病位在()

某患者在输液过程中，出现呼吸困难、气促、咳嗽、咳粉红色样痰，听诊两肺有湿性啰音，你认为：(1)病人出现何种反应?(2)发生的原因是什么?(3)护理的措施有哪些?

下列药物中不是治疗心力衰竭的正性肌力药物的是

以下没有每日价格波动限制的有()。

资本主义基本经济规律即______规律。

嘉兴市自明清时即有“人文之邦”的美誉。()

根据以下资料，回答下列问题。2008年初中和高中在校学生均高于全省平均水平的设区市有几个?()

某选区应选人大代表2人，超过半数选民参加了投票，代表候选人按得票多少的排序为杨某、叶某、李某、张某，其中仅杨某获得过半数选票。对此情形，下列做法不符合法律规定的是

设A，B均为3阶矩阵，且满足AB=2A+B，其中A=，则｜B－2E｜=________．

FoodSafetyandFoodborneIllnessesFoodsafetyisanincreasinglyimportantpublichealthissue.Governmentsalloverthew