网友您好， 请在下方输入框内输入要搜索的题目：

题目内容 （请给出正确答案）

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

参考答案

更多 “已知序列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）” 相关考题
考题 对n个记录的序列进行堆排序,最坏情况下的时间复杂度为______。 A、O(logn)B、O(nlogn)C、O(n)D、O(n^2)
查看答案
考题 下面程序段的时间复杂度为( )。for (i=0; ifor (j=0; jA[i][j]=i*j; A. O (m2)B. O (n2)C. O (m*n)D. O (m+n)
查看答案
考题 下面程序段的时间复杂度是()。for(i=0;in;i＋＋)for(j=1;jm;j＋＋)A[i][j]=0; A、O(n)B、O(m+n+1)C、O(m+n)D、O(m*n)
查看答案
考题 将长度为n的单链表链接在长度为m的单链表之后的算法的时间复杂度为() A、O(m+n)B、O(n)C、O(m)D、O(1)
查看答案
考题 使用二分查找算法在一个有序序列中查找一个元素的时间复杂度为()A.O(N)B.O(logN)C.O(N*N)D.O(N*logN)
查看答案
考题 下面程序段的时间复杂度是()。for(j=0;jfor(k=0;ka[j][k]=j*k; A、O(m2)B、O(n2)C、O(m*n)D、O(m+n)
查看答案
考题 下面程序段的时间复杂度是()。s=0;for(i=0;ifor(j=0;js＋=B[i][j];sum=s; A、O(m2)B、O(n2)C、O(m*n)D、O(m+n)
查看答案
考题 阅读下列函数说明和C代码，填入(n)处。[说明]以下C语言程序实现了生成从里到外是连续的自然数排列的回旋矩阵，矩阵形式如下：7 6 5 168 1 4 159 2 3 1410 11 12 13程序的变量说明如下：x1：矩阵上边界；x2：矩阵下边界；y1：矩阵左边界；y2：矩阵右边界；s：数组元素升降标记，s等于1为升，s等于-1为降；a[]：存放矩阵元素的数组。仔细阅读C语言程序源码，将(n)处的语句补充完整。(注：每处仅一个语句)[C程序]include＜stdio.h＞void main ( ){const int N=20;int i=0,j=0,a[N][N],n;int m,x1,x2,y1,y2,s;while (1){Printf ("\ninput matrix row N( N＞=2): ");scanf ("%d",n);printf ("\n");if (n＞=2)break;}m=n*n;x1=0; y1=0; x2=n; y2=n;if(n%2==0){j=n-1; y2=n-1; s=1;}else{i=n-1; y1=1; s=-1; }while (1){if (s==1){for (i; i＜x2; i++) a[i][j]=m--;i--;j--;(1)for (j;j＞=y1;j--) a[i][j]=m--;j++;i--;y1++;(2)}else{for (i;i＞=x1;i--)a[i][j]=m--;i++;j++;(3)for (j;j＜y2;j++)(4)(5)i++;(6)S=i;}if (m＜1) break;}for (i=O;i＜n; i++){for (j=O;j＜n;j++)printf ("%6d",a[i][j]);printf ("\n");}printf ("\n");}
查看答案
考题 将长度为n的单链表链接到长度为m的单链表之后的算法的时间复杂度是()。 A.O(1)B.O(n)C.O(m)D.O(m+n)
查看答案
考题 下面程序段的时间复杂度为 ( ) for(i=0;i＜m;i++) for(j=0;j＜n;j++) A[i][j]=i*j;A．O(m2)B．O(n2)C．O(m*n)D．O(m+n)
查看答案
考题 对长度为n的关键字序列进行堆排序的空间复杂度为 ( )A．O(log2n)B．O(1)C．O(n)D．O(n*log2n)
查看答案
考题 用快速排序的方法对包含n个关键字的序列进行排序，最坏情况下执行的时间为A．O(n)B．O(log2n)C．O(nlog2n)D．O(n2)
查看答案
考题 下面算法是实现对n个整数的序列进行选择排序，其中序列的“长度”n为问题的规模。该算法的时间复杂度为(11)。 void select_sort(int a[]，int n){ //将a中整数序列重新排列成从小到大有序的整数序列 for(i=0；i＜n-1；++i){ j=i； for(k=i+1；k＜n；++k)if(a[k]＜a[j])j=k； if(j!=i){w=a[j]；a[j]；a[i]；a[i]=w} )//select_sortA．O(n2)B．O(n3)C．O(n4)D．O(n)
查看答案
考题 对于求取两个长度为n的字符串的最长公共子序列问题，利用(41)策略可以有效地避免子串最长公共子序列的重复计算，得到时间复杂度为O(n2)的正确算法。A．贪心B．分治C．分支-限界D．动态规划
查看答案
考题 对n个关键字的序列进行快速排序，平均情况下的空间复杂度为_______A.O（1）B.O（logn）C.O（n）D.O（nlogn）
查看答案
考题 对于求取两个长度为n的字符串的最长公共子序列(LCS)问题，利用(24)策略可以有效地避免子串最长公共子序列的重复计算，得到时间复杂度为O(n2)的正确算法。串 ＜1，0，0，1，O，1，0，1＞和＜0，1，0，1，1,0,1，1＞的最长公共子序列的长度为(25)。A．分治B．贪心C．动态规划D．分支—限界
查看答案
考题 在二维数组M[0．．．n，0．．．m]中，访问某个元素的平均时间复杂度为______。A．O(1)B．O(nm)C．O(m+n)D．O(nn)
查看答案
考题 求解两个长度为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的单链表接在长度为m的单链表之后的算法时间复杂度为()。A.O(n) B.0(1) C.O(m) D.O(m+n)
查看答案
考题 将长度为n的单链表连接在长度为m的单链表之后的算法的时间复杂度为（）。A、O（1）B、O（n）C、O（m）D、O（m+n）
查看答案
考题 下面程序的时间复杂度为（）。 for（i=0；iA、O（m2）B、O（n2）C、O（m×n）D、O（m+n）
查看答案
考题 给定一个由n个数组成的序列，要求该序列的最长单调上升子序列，请设计对应的算法并分析其时间复杂度，如果时间复杂度劣于O（nlogn）的，将其优化为O（nlogn）时间复杂度的算法。
查看答案
考题 下面程序的时间复杂度为（）。 for（i=0；iA、O（m×n×t）B、O（m+n+t）C、O（m+n×t）D、O（m×t+n）
查看答案
考题 若序列X={B，C，A，D，B，C，D}，Y={A，C，B，A，B，D，C，D}，请给出序列X和Y的一个最长公共子序列：（）
查看答案
考题 判断题我(wǒ)喜欢(xǐhuān)猫(māo)，但是(dànshì)丈夫(zhàngfu)小(xiǎo)喜欢(xǐhuān)，所以(suǒyǐ)到(dào)现在(xiànzài)家里(jieli)也(yě)没有(méiyǒu)猫(māo)。我(wǒ)希望(xīwàng)有一天(yǒuyītiān)能(néng)有(yǒu)一(yī)个(gè)小(xiǎo)猫(māo)。★我(wǒ)丈夫(zhàngfu)想(xiǎng)要(yào)一(yī)个(gè)小(xiǎo)猫(māo)。（　　）A 对B 错
查看答案
考题 单选题已知序列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）
查看答案
考题 问答题给定一个由n个数组成的序列，要求该序列的最长单调上升子序列，请设计对应的算法并分析其时间复杂度，如果时间复杂度劣于O（nlogn）的，将其优化为O（nlogn）时间复杂度的算法。
查看答案
热门标签
最新试卷