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

题目

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

相似考题

1.关于内含子的正确叙述是A、由编码序列组成B、含非编码序列和编码序列两部分组成C、由非编码序列组成D、也称断裂基因E、也称间隔基因

2.● 对于长度为m（m>1）的指定序列，通过初始为空的一个栈、一个队列后，错误的叙述是 （61） 。（61）A. 若入栈和入队的序列相同，则出栈序列和出队序列可能相同B. 若入栈和入队的序列相同，则出栈序列和出队序列可以互为逆序C. 入队序列与出队序列关系为1:1，而入栈序列与出栈序列关系是1:n(n≥1)D. 入栈序列与出栈序列关系为1:1，而入队序列与出队序列关系是1:n(n≥1)

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

4.对于长度为m(m>1)的指定序列，通过初始为空的一个栈、一个队列后，错误的叙述是()A.若入栈和入队的序列相同，则出栈序列和出队序列可能相同B.若入栈和入队的序列相同，则出栈序列和出队序列可以互为逆序C.入队序列与出队序列关系为1:1，而入栈序列和出栈序列关系是1：n(n>=1)D.入栈序列和出栈序列关系为1:1，而入队序列与出队序列关系是1：n(n>=1)

更多“给定一个由n个数组成的序列，要求该序列的最长单调上升子序列，请设”相关问题

  • 第1题：

    原核细胞信使RNA含有几个其功能所必需的特征区段，它们 ( )

    A、转录起始位点，尾部序列，由顺反子间区序列隔开的SD序列和ORF，茎环结构

    B、启动子，转录起始位点，前导序列，由顺反子间区序列隔开的SD序列和ORF，尾部序列，茎环结构

    C、启动子，SD序列，起始密码子，终止密码子，茎环结构

    D、转录起始位点，前导序列，由顺反子间区序列隔开的SD序列和ORF，尾部序列

    E、启动子，前导序列，由顺反子间区序列隔开的SD序列，茎环结构


    参考答案：A

  • 第2题：

    阅读以下说明和流程图，填补流程图中的空缺，将解答填入答题纸的对应栏内。 【说明】 下面流程图的功能是:在给定的一个整数序列中查找最长的连续递增子序列。设序列存放在数组 A[1:n](n≥2)中，要求寻找最长递增子序列 A[K: K+L-1] (即A[K]<A[K+1]<…<A[K+L-1])。流程图中，用 Kj 和Lj 分别表示动态子序列的起始下标和长度，最后输出最长递增子序列的起始下标 K 和长度 L。 例如，对于序列 A={1 ，2，4，4 ，5，6，8，9，4，5，8}，将输出K=4， L=5。

    【流程图】注:循环开始框内应给出循环控制变量的初值和终值，默认递增值为1，格式为: 循环控制变量=初值，终值


    正确答案：（1）n-1
    （2）Lj+1→Lj        
    （3）Lj > L     
    （4）Kj
    （5）i+1

  • 第3题：

    对于一个操纵子的组成，下列说法正确的是

    A．一个启动序列和一个编码基因

    B．一个启动序列和多个编码基因

    C．两个启动序列和两个编码基因

    D．多个启动序列和一个编码基因

    E．多个启动序列和多个编码基因


    正确答案：B
    40.答案[B] 解析：一个操纵子只含一个启动序列和数个可转录的编码基因。

  • 第4题：

    设输入序列是1、2、3、……、n，经过栈的作用后输出序列的第一个元素是n，则输出序列中第i个输出元素是()

    A.n-1-i
    B.n-i
    C.n+1-i
    D.不能确定

    答案：C
    解析：
    经过栈后的输出序列中第一个元素为n，代表从1至n是一次性全部人栈的，所以出栈序列刚好是入栈序列的倒序。

  • 第5题：

    设输入序列是1、2、3、……、n，经过栈的作用后输出序列的第一个元素是n，则输出序列中第i个输出元素是（）。

    • A、n-i
    • B、n-1-i
    • C、n+1-i
    • D、不能确定

    正确答案:C

  • 第6题：

    串是由有限个字符构成的连续序列，串长度为串中字符的个数，子串是主串中字符构成的有限序列。


    正确答案:错误

  • 第7题：

    已知一个最长线性序列码发生器的反馈函数是F（Q）=Q5Q6，试求：序列码的长度S=（）；需用触发器的个数N=（）


    正确答案:63；6

  • 第8题：

    若序列X={B，C，A，D，B，C，D}，Y={A，C，B，A，B，D，C，D}，请给出序列X和Y的一个最长公共子序列：（）


    正确答案:{B，A，B，C，D}或{C，A，B，C，D}或{C，A，D，C，D｝

  • 第9题：

    单选题
    已知序列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
    解析： 暂无解析

  • 第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））。
    解析： 暂无解析

  • 第11题：

    填空题
    一个串的任意个连续的字符组成的子序列称为该串的（），包含该子串的串称为（）。

    正确答案： 子串,主串
    解析： 暂无解析

  • 第12题：

    单选题
    下列调用序列的说法正确的是：（）。
    A

    如果在调用序列中没有一个子序列为所发生的某一个异常定义处理程序，则定义相应处理程序

    B

    如果在调用序列中没有一个子序列为所发生的某一个异常定义处理程序，则返回错误信息

    C

    如果在调用序列中没有一个子序列为所发生的某一个异常定义处理程序，则终止该程序

    D

    如果在调用序列中没有一个子序列为所发生的某一个异常定义处理程序，则程序中断


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

  • 第13题：

    对于求取两个长度为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”。

  • 第14题：

    关于外显子的正确理解是

    A、由非编码序列组成

    B、由非编码序列和编码序列两部分组成

    C、由编码序列组成

    D、也称断裂基因

    E、也称间隔基因


    参考答案：C

  • 第15题：

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

  • 第16题：

    给出一个由n个数组成的序列A[1…n]，要求找出它的最长单调上升子序列，设m[i]（1≤i≤n），表示以A[i]结尾的最长单调上升子序列的长度，则m[1]=1，m[i]（1

    • A、m[i]=1+max{0，m[k]（A[k]<A[i]，1≤k<i）}
    • B、m[i]=1+m[k]（k=i-1&&i>1）
    • C、m[i]=1+max{0，m[k]（A[k]≤A[i]，1≤k<i）}
    • D、m[i]=max{0，m[k]（A[k]<A[i]，1≤k<i）}

    正确答案:A

  • 第17题：

    一个串的任意个连续的字符组成的子序列称为该串的（），包含该子串的串称为（）。


    正确答案:子串；主串

  • 第18题：

    一个串中任意个连续字符组成的子序列称为该串的（）串，该串称为它的所有子串的（）串。


    正确答案:子；主

  • 第19题：

    下列调用序列的说法正确的是：（）。

    • A、如果在调用序列中没有一个子序列为所发生的某一个异常定义处理程序，则定义相应处理程序
    • B、如果在调用序列中没有一个子序列为所发生的某一个异常定义处理程序，则返回错误信息
    • C、如果在调用序列中没有一个子序列为所发生的某一个异常定义处理程序，则终止该程序
    • D、如果在调用序列中没有一个子序列为所发生的某一个异常定义处理程序，则程序中断

    正确答案:D

  • 第20题：

    某转录的启动子序列如下：5’-T A G C A T-3’。该序列的长度与野生型的启动子序列长度相比较的结果是：（）

    • A、该序列较长
    • B、该序列较短
    • C、该序列与野生型启动子的序列一致

    正确答案:B

  • 第21题：

    单选题
    原核细胞信使RNA含有几个其功能所必需的特征区段，它们（　）
    A

    转录起始位点，尾部序列，由顺反子间区序列隔开的SD序列和ORF，茎环结构

    B

    启动子，转录起始位点，前导序列，由顺反子间区序列隔开的SD序列和ORF，尾部序列，茎环结构

    C

    启动子，SD序列，起始密码子，终止密码子，茎环结构

    D

    转录起始位点，前导序列，由顺反子间区序列隔开的SD序列和ORF，尾部序列

    E

    启动子，前导序列，由顺反子间区序列隔开的SD序列，茎环结构


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

  • 第22题：

    填空题
    若序列X={B，C，A，D，B，C，D}，Y={A，C，B，A，B，D，C，D}，请给出序列X和Y的一个最长公共子序列：（）

    正确答案： {B，A，B，C，D}或{C，A，B，C，D}或{C，A，D，C，D｝
    解析： 暂无解析

  • 第23题：

    单选题
    设输入序列1、2、3、…、n经过栈作用后，输出序列中的第一个元素是n，则输出序列中的第i个输出元素是（）
    A

    n-i

    B

    n-1-i

    C

    n+l-i

    D

    不能确定


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

相关内容