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

admin2013-05-11 77

问题对于求取两个长度为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)的正确算法。

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

软考中级

在异步通信中，每个字符包含1位起始位，7位数据位，1位奇偶校验位和1位终止位，每秒钟传送200个字符，采用DPSK调制，则码元速率为(1)，有效数据速率为(2)。(2012年下半年试题)(1)

下图表示了某个数据的两种编码，这两种编码分别是(1)，该数据是(2)。(2009年下半年试题)(1)

网络用户只能接收但不能发送E-mail，不可能的原因是__________。(2010年下半年试题)

2．某客户端采用ping命令检测网络连接故障时，发现可以ping通127．0．0．1及本机的IP地址，但无法ping通同一网段内其他工作正常的计算机的IP地址。该客户端的故障可能是__________。(2008年上半年试题)

ARP协议的作用是(1)，它的协议数据单元封装在(2)中传送。ARP请求是采用(3)方式发送的。(2012年上半年试题)(1)

根据用户需求选择正确的网络技术是保证网络建立成功的关键，在选择网络技术时应考虑多种因素。下面各种考虑中，不正确的是()。

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

BGP是在______之间传播路由的协议。

(2016年4月第11题)某企业按照高于国外同类产品生产厂家的产品质量标准进行生产和销售，该企业采取的市场动态质量战略属于()

下肢髂股静脉血栓形成患者的临床特点是

男，45岁，近半年恶心，食欲差，近一周呕吐，少尿，15年前曾验尿常规：蛋白(++)，RBC1～3／HP。查体：BP23／12．2kPa(172／92mmHg)，皮肤粗糙，无黄疸，双肺无明显啰音，HR90次／分。律齐，肝脾未及，双下肢水肿。Hb6．0

关于霍乱，错误的描述是

可导致双端固定桥固位不良的是A．基牙轴面聚合度小B．桥体强度不足C．两端的基牙数目不等D．一端基牙过短E．一端固位体的固位力略高于另一端

下列各项个人所得中，免征个人所得税的项目是()。

某企业全年制度工作日为250天，两班制，每班有效工作时间为7．5小时。已知钳工车间生产面积为145平方米，每件产品占用生产面积5平方米，该车间单件产品时间定额为1．5小时。该钳工车问的年生产能力为()件。

你作为铁路公安发现火车站检票员工作不认真，经常让闲散人员进站，针对这种状况你需要找他谈谈，请现场模拟。

Perhapsoneofthebest-knownaccidentaldiscoveryisSirAlexander【M1】______Fleming’sdiscoveryofpenicillin.In1922Flemin