违法和不良信息举报 联系客服
免费注册 登录

最长公共子序列算法利用的算法是（）。

题目
单选题
最长公共子序列算法利用的算法是（）。
A

分支界限法

B

动态规划法

C

贪心法

D

回溯法

如果没有搜索结果或未解决您的问题，请直接 联系老师 获取答案。
相似问题和答案

第1题：

算法是解决问题的步骤序列，正确的序列是( )

①分析问题;②提出问题;③设计算法

A.②①③

B.①②③

C.①③②

D.②③①


正确答案：A

第2题：

加密算法若按照密钥的类型划分可以分为()两种。

A.非对称密钥加密算法和对称密钥加密算法

B.公开密钥加密算法和分组密码算法

C.序列密码算法和分组密码算法

D.序列密码算法和公开密钥加密算法


答案A

第3题：

实现最长公共子序列利用的算法是()

A.分治策略

B.动态规划法

C.贪心法

D.回溯法


参考答案：B

第4题：

实现最长公共子序列利用的算法是（）。

  • A、分治策略
  • B、动态规划法
  • C、贪心法
  • D、回溯法

正确答案:B

第5题：

采用贪心算法保证能求得最优解的问题是（ ）

A.0-1背包
B.矩阵连乘
C.最长公共子序列
D.邻分（分数）背包

答案：D
解析：
动态规划算法适合解决0-1背包问题，贪心法适合解决部分背包（邻分（分数）背包）问题。

第6题：

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

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”。

第7题：

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



采用自底向上的方法实现该算法，则时间复杂度为（请作答此空）

A.O（n^2）
B.O（n^21gn）
C.O（n^3）
D.O（n2^n）

答案：A
解析：
蛮力法，对X的每一个子序列，判断是否也是Y的子序列，其中，长度为n的序列X共有2^n个子序列，判断其是否是Y的子序列时间是n，因此是n*2^n；采用动态规划法自底向上实现时，根据递归公式，实际是关于i和j的两重循环，因此时间复杂度是n^2.

第8题：

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

A．分治

B．贪心

C．动态规划

D．分支一限界


正确答案：C
解析：本题考查的是动态规划算法策略的典型应用。LCS问题是利用动态规划策略解决的经典问题之一，利用动态规划求解该问题时可以通过查表得到已经计算出的子串的最长公共子序列，从而避免重复计算。利用动态规划算法可以得到题目中两个串的最长公共子序列长度为6，如“101011”。

第9题：

选择优化货位的算法是（）

  • A、最大时间算法和距离参数算法
  • B、最大时间算法和最长距离算法
  • C、最短时间算法和重量参数算法
  • D、时间参数算法和最大距离参数算法

正确答案:A

第10题：

给定一个由n个数组成的序列，要求该序列的最长单调上升子序列，请设计对应的算法并分析其时间复杂度，如果时间复杂度劣于O（nlogn）的，将其优化为O（nlogn）时间复杂度的算法。


正确答案: 假设当前已求出m[1..i-1]，当前保留的状态集合为S，下面计算m[i]。
1、若存在状态k∈S，使得x[k]=x[i]，则状态m[i]必定不需保留，不必计算。因为，不妨设m[i]=m[j]+1，则x[j] 2、否则，m[i]=1+max{m[j]|x[j] 3、若2成立，则我们往S中增加了一个状态，为了保持S的性质，我们要对S进行维护，若存在状态k∈S，使得m[i]=m[k]，则我们有x[i]x[i]，j∈S}。于是状态k应从S中删去。
从性质D和算法描述可以发现，S实际上是以x值为关键字（也是以m值为关键字）的有序集合。若使用平衡树实现有序集合S，则该算法的时间复杂度为O（n*logn）。（每个状态转移的状态数仅为O（1），而每次状态转移的时间变为O（logn））。

更多相关问题
相关内容