最长公共子序列算法利用的算法是（）。A、分支界限法B、动态规划法C、贪心法D、回溯法

题目

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

  • A、分支界限法
  • B、动态规划法
  • C、贪心法
  • D、回溯法
相似考题

1.实现最长公共子序列利用的算法是()A.分治策略B.动态规划法C.贪心法D.回溯法

2.算法是解决问题的步骤序列，正确的序列是( )①分析问题;②提出问题;③设计算法A.②①③B.①②③C.①③②D.②③①

3.对于求取两个长度为n的字符串的最长公共子序列问题，利用(41)策略可以有效地避免子串最长公共子序列的重复计算，得到时间复杂度为O(n2)的正确算法。A．贪心B．分治C．分支-限界D．动态规划

4.对于求取两个长度为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．分支一限界

更多“最长公共子序列算法利用的算法是（）。”相关问题

  • 第1题：

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

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

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

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

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


    答案A

  • 第2题：

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

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

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

  • 第3题：

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

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

    正确答案:B

  • 第4题：

    加密算法若按照密匙的类型划分可以分为（）两种。

    • A、公开密匙加密算法和对称密匙加密算法
    • B、公开密匙加密算法和算法分组密码
    • C、序列密码和分组密码
    • D、序列密码和公开密匙加密算法

    正确答案:A

  • 第5题：

    算法是指令的有限序列。


    正确答案:正确

  • 第6题：

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

    • A、 非对称密钥加密算法和对称密钥加密算法
    • B、 公开密钥加密算法和分组密码算法
    • C、 序列密码算法和分组密码算法
    • D、 序列密码算法和公开密钥加密算法

    正确答案:A

  • 第7题：

    按照密钥类型，加密算法可以分为（）。

    • A、.序列算法和分组算法
    • B、序列算法和公用密钥算法
    • C、公用密钥算法和分组算法
    • D、公用密钥算法和对称密钥算法

    正确答案:D

  • 第8题：

    单选题
    按照密钥类型，加密算法可以分为（）。
    A

    .序列算法和分组算法

    B

    序列算法和公用密钥算法

    C

    公用密钥算法和分组算法

    D

    公用密钥算法和对称密钥算法


    正确答案： A
    解析： 暂无解析

  • 第9题：

    单选题
    Apriori算法是一种常见的（）。
    A

    关联规则发现算法

    B

    聚类分析算法

    C

    分类算法

    D

    序列模式发现算法


    正确答案： B
    解析： 暂无解析

  • 第10题：

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

    分治策略

    B

    动态规划法

    C

    贪心法

    D

    回溯法


    正确答案： A
    解析： 暂无解析

  • 第11题：

    单选题
    下面不属于对称算法的是（）
    A

    DES算法

    B

    序列算法

    C

    MAC

    D

    数字签名


    正确答案： B
    解析： 暂无解析

  • 第12题：

    单选题
    根据3GPP的相关协议规定，AKA算法属于（）算法。
    A

    非标准化算法

    B

    对称算法

    C

    非对称算法

    D

    序列算法


    正确答案： C
    解析： 暂无解析

  • 第13题：

    求解两个长度为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.

  • 第14题：

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

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

    正确答案:A

  • 第15题：

    给定一个由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））。

  • 第16题：

    对初始状态为递增序列的表按递增序列排序，最省时间的事（）算法，最费时间的是（）算法。


    正确答案:插入排序；快速排序

  • 第17题：

    Apriori算法是一种常见的（）。

    • A、关联规则发现算法
    • B、聚类分析算法
    • C、分类算法
    • D、序列模式发现算法

    正确答案:A

  • 第18题：

    简述序列密码算法和分组密码算法的不同。


    正确答案: 序列密码：
    明文长度可以小于1字节，有记忆；加密不仅与密钥和明文有关，还与当前状态有关，也叫状态密码；设计关键在于密钥序列产生器，使生成的密钥序列尽可能高的不可预测性。
    分组密码：
    明文分成比较大的块，无记忆；每块使用相同的加密函数进行处理；增加记忆模块，形成一种序列密码；设计关键在于加解密算法，是明文密文之间的关联在密钥控制下尽可能复杂；

  • 第19题：

    下面属于对称算法的是（）

    • A、数字签名
    • B、序列算法
    • C、RSA算法
    • D、数字水印

    正确答案:B

  • 第20题：

    单选题
    已知序列X={x1，x2，…，xm}，序列Y={y1，y2，…，yn}，使用动态规划算法求解序列X和Y的最长公共子序列，其最坏时间复杂度为（）。
    A

    O（m*n）

    B

    O（m+n）

    C

    O（m*2n）

    D

    O（n*2m）


    正确答案： A
    解析： 暂无解析

  • 第21题：

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

    分支界限法

    B

    动态规划法

    C

    贪心法

    D

    回溯法


    正确答案： C
    解析： 暂无解析

  • 第22题：

    问答题
    给定一个由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））。
    解析： 暂无解析

  • 第23题：

    单选题
    针对给定的HMM模型，寻找与给定观察字符序列对应的最佳状态序列可采用（）
    A

    前向算法；

    B

    后向算法；

    C

    Viterbi算法；

    D

    Baum-Welch算法


    正确答案： C
    解析： 暂无解析

相关内容