itgle.com

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

题目
求解两个长度为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）
相似考题

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

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

3.阅读以下说明和流程图，填补流程图中的空缺，将解答填入答题纸的对应栏内。 【说明】 下面流程图的功能是:在给定的一个整数序列中查找最长的连续递增子序列。设序列存放在数组 A[1:n](n&ge;2)中，要求寻找最长递增子序列 A[K: K+L-1] (即A[K]<A[K+1]<&hellip;<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，格式为: 循环控制变量=初值，终值

4.阅读以下说明和C++ 程序，将应填入(n)处的字句写在对应栏内。[说明]试从含有n个int 型数的数组中删去若干个成分，使剩下的全部成分构成一个不减的子序列。设计算法和编写程序求出数组的不减子序列的长。[C++ 程序]include＜stdio.h＞define N 100int b[]={9,8,5,4,3,2,7,6,8,7,5,3,4,5,9,1};int a [N];define n sizeofb/sizeofb[0]void main ( ){kit k,i,j;(1)(2)for (i=1;i＜n; i++ ){for ( j=k;(3); j--);(4); /*长为 j+1 的子序列的终元素存储在 a[j+1]*/if ((5)k++; /*最长不减子序列长 k 增1*/}printf ( "K = %d\n ",k );}

参考答案和解析
答案：A
解析：
蛮力法，对X的每一个子序列，判断是否也是Y的子序列，其中，长度为n的序列X共有2^n个子序列，判断其是否是Y的子序列时间是n，因此是n*2^n；采用动态规划法自底向上实现时，根据递归公式，实际是关于i和j的两重循环，因此时间复杂度是n^2.
更多“求解两个长度为n的序列X和Y的一个最长公共子序列（如序列ABCBDAB和BDCABA的一个最长公共子序列为BCBA）可以采用多种计算方法。如可以采用蛮力法，对X的每一个子序列，判断其是否也是Y的子序列，最后求出最长的即可，该方法的时间复杂度为（ ）。经分析发现该问题具有最优子结构，可以定义序列长度分别为i和j的两个序列X和Y的最长公共子序列的长度为c[i,j]，如下式所示。 ”相关问题

  • 第1题：

    阅读以下说明和 C 代码，填补代码中的空缺，将解答填入答题纸的对应栏内。 【说明】 对一个整数序列进行快速排序的方法是：在待排序的整数序列中取第一个数作为基准值，然后根据基准值进行划分，从而将待排序列划分为不大于基准值者(称为左子序列)和大于基准值者(称为右子序列)，然后再对左子序列和右子序列分别进行快速排序， 最终得到非递减的有序序列。 函数 quicksort(int a[]，int n)实现了快速排序，其中，n 个整数构成的待排序列保存在数组元素 a[0]-a[n-1]中。

    【C 代码】 include < stdio.h> void quicksort(int a[] ，int n) { int i ，j; int pivot = a[0]; //设置基准值 i =0; j = n-l; while (i< j) { while (i<j &&（1）) j-- //大于基准值者保持在原位置 if (i<j) { a[i]=a[j]; i++;} while (i,j &&（2）) i++; //不大于基准值者保持在原位置 if (i<j) { a[j]=a[i]; j--;} } a[i] = pivot; //基准元素归位 if ( i>1) （3） ; //递归地对左子序列进行快速排序 if ( n-i-1>1 ) （4） ; //递归地对右子序列进行快速排序 } int main () { int i，arr[ ] = {23，56，9，75，18，42，11，67}; quicksort ( （5） ); //调用 quicksort 对数组 arr[ ]进行排序 for( i=0; i<sizeof(arr) /sizeof(int); i++ ) printf(" %d\t" ，arr[i]) ; return 0; }


    正确答案：
    (1) a[j]> pivot 或    a[j]>= pivot    或等价形式
    (2) a[i] <= pivot      或    a[i] < pivot      或等价形式
    (3) quicksort(a ,i) 或 quicksort(a,j)    或等价形式
    (4) quicksort(a+i+1，n-i-1)  或 quicksort(a+j+1，n-j -1)        或等价形式
    注: a+i+1可表示为 &a[i+1] ，a+j+1可表示为 &a[j+1]
    (5) arr，sizeof(arr)/sizeof(int)
    注: sizeof(arr)/sizeoftint) 可替换为 8

  • 第2题：

    在乳糖操纵子中，阻遏蛋白识别操纵子的是( )

    A.I基因
    B.0序列
    C.P序列
    D.Y基因

    答案：B
    解析：
    乳糖操纵子由Z、Y及A3个结构基因，1个操纵序列O，1个启动序列P及1个调节基因I组成。阻遏蛋白是I基因的编码产物，它可与O序列(操纵序列)结合，阻碍RNA聚合酶与P序列(启动序列)结合抑制转录起动，如有诱导剂存在，诱导剂可结合阻遏蛋白，使阻遏蛋白构象改变，导致与O序列解离，则转录起始，故应选B。

  • 第3题：

    阅读以下说明和C代码，填补代码中的空缺，将解答填入答题纸的对应栏内。
    [说明]
    对一个整数序列进行快速排序的方法是：在待排序的整数序列中取第一个数作为基准值，然后根据基准值进行划分，从而将待排序列划分为不大于基准值者(称为左子序列)和大于基准值者(称为右子序列)，然后再对左子序列和右子序列分别进行快速排序，最终得到非递减的有序序列。
    函数quicksort(int a[],int n)实现了快速排序，其中，n个整数构成的待排序列保存在数组元素a[0]～a[n-1]中。

    [C代码] #inclLade＜stdi0.h＞ void quicksort(inta[], int n) { int i,j; int pivot=a[0]; //设置基准值 i=0; j=n-1; while (i＜j){ while (i＜1 && ______) j--; //大于基准值者保持在原位置 if (i＜j) { a[i] =a[j]; i++;} while(i＜j&& ______) i++; //不大于基准值者保持在原位置 if (i＜1) { a[j] =a[i]; 1--;} } a[i]=pivot; //基准元素归位 if (i＞1 ) ______; //递归地对左孔序列进行快速排序 if (n-i-1＞1 ) ______; //递归地对右孔序列进行快速排序 } int main() { int i, arr[]={23,56,9,75,18,42,11,67}; quicksort(______); //调用quicksort对数组arr[]进行排序 for( i=0; i＜sizeof(arr)/sizeof(int); i++ ) printf("%d\t",arr[i]); return 0; }


    答案：
    解析：
    a[j]＞pivot 或 a[j]＞=pivot 或等价形式
    a[i]＜=pivot 或 a[i]＜pivot 或等价形式
    quicksort(a,i) 或 quicksort(a,j) 或等价形式
    quicksort(a+i+1,n-i-1) 或 quicksort(a+j+1，n-j-1) 或等价形式
    注：a+i+1可表示为&a[i+1]，a+j+1可表示为&a[j+1]
    arrsizeof(arr)/sizeof(int)
    注：sizeof(arr)/sizeof(int)可替换为8

    【解析】

    本题考查C程序设计基本技能及快速排序算法的实现。
    题目要求在阅读理解代码说明的前提下完善代码，该题目中的主要考查点为运算逻辑和函数调用的参数处理。
    程序中实现快速排序的函数为quicksort，根据该函数定义的首部，第一个参数为数组参数，其实质是指针，调用时应给出数组名或数组中某个元素的地址；第二个参数为整型参数，作用为说明数组中待排序列(或子序列)的长度。
    快速排序主要通过划分来实现排序。根据说明，先设置待排序列(或子序列，存储在数组中)的第一个元素值为基准值。划分时首先从后往前扫描，即在序列后端找出比基准值小或相等的元素后将其移到前端，再从前往后扫描，即在序列前端找出比基准值大的元素后将其移动到后端，直到找出基准值在序列中的最终排序位置。再结合注释，空(1)处应填入"a[j]＞pivot"，使得比基准值大者保持在序列后端。空(2)处应填入"a[i]＜=pivot"，使得不大于基准值者保持在前端。
    在完成1次划分后，基准元素被放入a[i]，那么分出来的左子序列由a[0]～a[i-1]这i个元素构成，右子序列由a[i+1]～a[n-1]构成，接下来应递归地对左、右子序列进行快排。因此，结合注释，空(3)应填入"quicksort(a,i)"或其等价形式，以对左子序列的i个元素进行快排，也可以用&a[0]代替其中的a，它们是等价的，a与&a[0]都表示数组的起始地址。
    空(4)所在代码实现对右子序列进行快排。右子序列由a[i+1]～a[n-1]构成，其元素个数为n-1-(i+1)+1，即n-i-1，显然元素a[i+1]的地址为&a[i+1]或a+i+1，所以空(4)应填入"quicksort(a+i+1,n-i-1)"或其等价形式。
    在main函数中，空(5)所在代码首次调用函数quicksort对main函数中的数组arr进行快排，因此应填入"arr,sizeof(arr)/sizeof(int)"或其等价形式。

  • 第4题：

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

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

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

  • 第5题：

    某地区1950-1990年的人均食物年支出和人均年生活费收入月度数据如表3-2所示。


    据此回答以下五题95-99。
    为判断该两组时间序列的平稳性，首先将人均食品支出和人均年生活费收入消除物价变动的影响，得到实际人均年食品支出(Y)和实际人均年生活费收入(X)，再对Y和X分别取对数，记y=lnY，x=lnX。对其进行ADF检验，结果如表3-3、表3-4所示，表明（　　）。

    A.x序列为平稳性时间序列，y序列为非平稳性时间序列
    B.x和y序列均为平稳性时间序列
    C.x和y序列均为非平稳性时间序列
    D.y序列为平稳性时间序列，x序列为非平稳性时间序列

    答案：C
    解析：
    从表3-3和表3-4可以看出，x和y序列的ADF检验统计量值均大于在1%、5%和10%显著性水平下的临界值，表明x和y序列均为非平稳性时间序列。

  • 第6题：

    给出一个由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

  • 第7题：

    已知序列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

  • 第8题：

    初级转录产物是（）。

    • A、以转录调控序列为模板转录的序列
    • B、以结构基因为模板转录的全部序列
    • C、以外显子为模板转录的序列
    • D、以内含子为模板转录的序列

    正确答案:B

  • 第9题：

    若序列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｝

  • 第10题：

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

  • 第11题：

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

  • 第12题：

    单选题
    给出一个由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）}


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

  • 第13题：

    阅读下列说明和C代码，回答问题l至问题3．将解答写在答题纸的对应栏内。

    【说明】

    计算一个整数数组a的最长递增子序列长度的方法描述如下：

    假设数组a的长度为n，用数组b的元素b[i]记录以a[i](0≤i<n)为结尾元素的最长

    递增子序列的长度，则数组a的最长递增子序列的长度为器；其中b[i]满足最优子结构，可递归定义为：

    【c代码】

    下面是算法的c语言实现。

    (1)常量和变量说明

    a：长度为n的整数数组，待求其最长递增子序列

    b：长度为n的数组，b[i]记录以a[i](0≤i<n)为结尾元素的最长递增子序列的长度，

    其中0≤i<n

    len:最长递增子序列的长度

    i.j:循环变量

    temp,临时变量

    (2)C程序

    include <stdio . h>

    int maxL （int *b. int n） {

    int i. temp =0;

    For（i = 0; i < n; i++）{

    if （b[i] > temp ）

    Temp= b[i];

    }

    Return temp;

    【问题l】（8分）

    根据说明和C代码,填充C代码中的空(1)～(4)。

    【问题2】（4分）

    根据说明和C代码，算法采用了(5)设计策略，时间复杂度为(6)（用O符号表示）。

    【问题3】（3分）

    已知数组a={3，10，5，15，6，8}，根据说明和C代码，给出数组b的元素值。


    正确答案：
    本题考查算法设计与分析以及用C程序设计语言来实现算法的能力。此类题目要求考生认真阅读题目对问题的描述，理解算法思想，并会用C程序设计语言来实现。【问题1】根据题干描述，用一个数组b来记录数组a每个子数组的最长递增子序列的长度，即b[i]记录a[0．．i]的最长递增子序列的长度。首先，只有一个元素的数组的最长递增子序列的长度为1，即给b[0]直接赋值1。因此，空(1)处填写“b[0]=1”。两重for循环中，第一重是从a数组的第二个元素开始，考虑每个子数组a[0....II]的最长递增子序列的长度，第二重是具体的计算过程。考虑子数组a[0..I]，其最长递增于序列的长度应该等于子数组a[O.i-l]中的比元素a[i]小的元素的最长递增子序列的长度加1，当然，可能存在多个元素比元素a[i]小，那么存在多个最长递增子序列的长度，此时，取最大者。因此，空处填写j<i”，即考虑子数组a[O...i-l]。空(3)处填写“a[j]<=a[i]”，要求元素值小于等于a[i]而且目前的长度应该小于当前考虑的子数组的最长子序列长度。空(4)处填写“b[i]=len+1”。简单的说，程序是根据题干给出的公式来实现的。另外，计算的过程不是采用递归的方式，而是以一种自底向上的方式进行的【问题2】从题干说明和C程序来看，这是一个最优化问题，而且问题具有最优子结构，一个序列的最长递增子序列由其子序列的最长递增子序列构成。在计算过程中采用了自底向上的方式来进行，这具有典型的动态规划特征。因此采用的是动态规划设计策略。C程序中，有两重for循环，因此时间复杂度为。【问题3】输入数组为数组a={3.10，5，15，6，8}，很容易得到，子数组a[0...0]，a[0．．1]．…，a[0....5]的最长递增子序列的长度分别为l，2，2，3,3，4，因此答案为b={I，2，2，3，4}。该题可以根据题干说明、C代码来计算。由于输入很简单，答案也可以从输入直接许算出来。试题四参考答案【问题1】(1)b[0]=I(2)j<i(3)a[j]<=a[i](4)b[i]=len+1【问题2】(5)动态规划(6)【问题3】b={1，2，2，3，3，4}

  • 第14题：

    阅读下列说明和C代码，回答问题，将解答填入答题纸的对应栏内。
    【说明】
    计算一个整数数组a的最长递增子序列长度的方法描述如下：
    假设数组a的长度为n，用数组b的元素b[i]记录以a[i](0≤i＜n)为结尾元素的最长递增子序列的长度为 ；其中b[i]满足最优子结构，可递归定义为：

    【C代码】
    下面是算法的C语言实现。
    （1）常量和变量说明
    a：长度为n的整数数组，待求其最长递增子序列
    b：长度为n的数组，b[i]记录以a[i](0≤ilen：最长递增子序列的长度
    i, j：循环变量
    temp：临时变量
    （2）C程序

    #include int maxL(int*b, int n) {int i, temp=0;for(i=0; itemp) temp=b[i]; } return temp;}int main() { int n,a[100], b[100], i, j, len; scanf("%d", &n); for(i=0;i
    【问题1】（8分）
    根据说明和C代码，填充C代码中的空（1）～（4）。
    【问题2】（4分）
    根据说明和C代码，算法采用了 （5） 设计策略，时间复杂度为 （6） （用O符号表示）。
    【问题3】（5分）
    已知数组a={3，10，5，15，6，8}，据说明和C代码，给出数组b的元素值。


    答案：
    解析：
    【问题1】
    （1）b[0]=1
    （2）j（3）a[j]<=a[i]
    （4）b[i]=len+1
    【问题2】（4分）
    （5）动态规划法
    （6）O(n2)
    【问题3】（5分）
    B={1，2，2，3，3，4}

  • 第15题：

    阅读下列说明和C代码，回答问题1至问题3，将解答写在答题纸的对应栏内。
    【说明】 计算两个字符串x和y的最长公共子串（Longest Common Substring）。 假设字符串x和字符串y的长度分别为m和n，用数组c的元素c[i][j]记录x中前i个字符和y中前j个字符的最长公共子串的长度。c[i][j]满足最优子结构，其递归定义为：




    计算所有c[i][j](0 ≤i ≤ m，0 ≤j ≤ n)的值，值最大的c[i][j]即为字符串x和y的最长公共子串的长度。根据该长度即i和j，确定一个最长公共子串。【C代码】(1)常量和变量说明 x，y：长度分别为m和n的字符串 c[i][j]：记录x中前i个字符和y中前j个字符的最长公共子串的长度 max：x和y的最长公共子串的长度 maxi, maXj：分别表示x和y的某个最长公共子串的最后一个字符在x和y中的位置（序号） (2)C程序#include
    < stdio.h>#include
    < string.h>int c[50][50];int maxi;int maxj;int lcs(char
    *x, int m, char *y, int n) { int i, j; int max= 0; maxi= 0; maxj = 0;for ( i=0;
    i < =m ; i++) c[i][0] = 0;for (i =1;
    i < = n; i++) c[0][i]=0;for (i =1;
    i < = m; i++) { for (j=1; j < = n; j++) { if (
    (1) ) {c[i][j] = c[i
    -1][j -1] + 1;if(max < c[i][j])
    { (2)
    ; maxi = i; maxj =j; }}else (3)
    ; } } return max;}void
    printLCS(int max, char *x) { int i= 0; if (max == 0) return; for (
    (4) ; i < maxi; i++)printf("%c",x[i]);}void main（ ）{ char* x= "ABCADAB"; char*y= "BDCABA"; int max= 0; int m = strlen(x); int n = strlen(y); max=lcs(x,m,y,n); printLCS(max , x);}
    【问题1】（8分）
    根据以上说明和C代码，填充C代码中的空（1）～（4）。
    【问题2】（4分）
    根据题干说明和以上C代码，算法采用了 （5） 设计策略。
    分析时间复杂度为 （6） （用O符号表示）。
    【问题3】（3分）
    根据题干说明和以上C代码，输入字符串x= "ABCADAB’，'y="BDCABA",则输出为 （7） 。


    答案：
    解析：
    【问题1】（8分）答案：（1）x[i-1]= =y[j-1] （2）max=c[i][j]（3）c[i][j]=0 （4）i=maxi-max

    【问题2】（4分）答案：动态规划、 O(m×n)或O(mn)

    【问题3】（3分）答案：AB根据题干和C代码，计算出下表的值。



    最大值为2。在计算过程中，我们记录第一个最大值，即表中阴影部分元素，因此得到最长公共子串为AB。

  • 第16题：

    阅读下列说明和C代码，回答下列问题。[说明] 计算一个整数数组a的最长递增子序列长度的方法描述如下： 假设数组a的长度为n，用数组b的元素b[i]记录以a[i](0≤i＜n”)为结尾元素的最长递增子序列的长度为



    其中b[i]满足最优子结构，可递归定义为：



    [C代码] 下面是算法的C语言实现。 10常量和变量说明 a:长度为n的整数数组，待求其最长递增子序列 b:长度为n的数组，b[i]记录以a[i](0≤i＜n”)为结尾元素的最长递增子序列的长度，其中0≤i＜n len:最长递增子序列的长度 i,j:循环变量 temp:临时变量 11C程序 # jnclude＜stdio,h＞ mtmaxL(int*b,mt n) { mt I, temp=0 for(i=0; i＜n; i++) { (b[i]＞temp) temp=b[i] return temp; int main12 { int n,a[100],b[100],i,j,len; scanf(" % d",&n); for(i=0;i＜n;i++) { scanf("% d",&a[i]); ___1___: for(i=1;i＜n;i++) { for(j=0,len=0;___2___;j++){ if( ___3___&&len＜b[j]) Ien=b[j] ___4___; } Printf("len:% d\n",maxL(b,n)) Primtf("\n") }1~4、 根据说明和C代码，填充C代码中的空______～______。5、 根据说明和C代码，算法采用了______设计策略，时间复杂度为______(用O符号表示)6、 已知数组a={3，10，5，15，6，8}，据说明和C代码，给出数组b的元素值。


    答案：
    解析：
    本题考查最长递增序列问题，是一种动态规划法，也考查时间复杂度的计算。1~4、b[0]=1 j＜=i a[j]＜=a[i] b[i]=len+15、动态规划法 O(n2) 　 　6、B={1，2，2，3，3，4}

  • 第17题：

    再分别对X和Y序列作1阶差分得△x和△y序列，对其进行平稳性检验，检验结果如表3-5和表3-6所示，从中可以看出（　　）。

    A.1阶差分后的x和y序列在10%的显著性水平均为平稳性时间序列
    B.x和y序列均为1阶单整序列
    C.1阶差分后的x和y序列在1%的显著性水平均为平稳性时间序列
    D.x和y序列均为0阶单整序列

    答案：A,B
    解析：
    从表3-5和表3-6可以看出，△x和△y序列的单位根检验统计量值分别约为-3．5586和-2．7080，均大于1%显著性水平下的临界值-3．6171，小于10%显著性水平下的临界值-2．6092，表明1阶差分后的x和y序列在10%的显著性水平均为平稳性时间序列，即x和y序列均为1阶单整序列。

  • 第18题：

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

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

    正确答案:B

  • 第19题：

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

  • 第20题：

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

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

    正确答案:D

  • 第21题：

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

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

    正确答案:B

  • 第22题：

    单选题
    原核生物乳糖操纵子不含有（　　）。
    A

    结构基因Z、Y、A

    B

    操纵序列O

    C

    启动序列P

    D

    增强子

    E

    调节基因I


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

  • 第23题：

    填空题
    若序列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｝
    解析： 暂无解析

相关内容