网友您好， 请在下方输入框内输入要搜索的题目：
题目内容
（请给出正确答案）
填空题
两个字符串S1和S2的长度分别为m和n，求这两个字符串最大共同子串的时间复杂度为T（m，n），这最优的时间复杂度为（）。
参考答案
参考解析
解析：
暂无解析
更多 “填空题两个字符串S1和S2的长度分别为m和n，求这两个字符串最大共同子串的时间复杂度为T（m，n），这最优的时间复杂度为（）。” 相关考题
考题
●试题四阅读下列程序说明和C程序，将应填入(n)处的字句写在答卷纸的对应栏内。【程序说明】该程序定义了两个子函数strsort和strmerge。它们分别实现了将一个字符串按字母顺序排序和将两个字符串合并排序，并删去相同字符。在主函数里，先输入两个字符串s1和s2，然后调用strsort函数对它们分别排序，然后调用strmerge函数将s1和s2合并，将合并后的字符串赋给字符串s3，最后输出字符串s3。【程序】#includestdio.hvoid strmerge(char*a，char*b，char*c)//将字符串a，b合并到字符串c中{char t,*w；w=c；while( (1) ){//找到字符串a，b当前字符中较小的字符if(*a*b){t=*a；(2) ；}else if(*a*b){t=*b;(3) ；}else//字符串a，b当前字符相等{t=*a；a++;b++;}if( (4) )//开始，可直接赋值*w=t;else if(t!=*w)//如果a，b中较小的当前字符与c中当前字符不相等，才赋值 (5) ；}if(*a!=\′＼0′)//如果字符串a还没有结束，则将a的剩余部分赋给cwhile(*a!=′＼0′)if(*a!=*w){*(++w)=*a；a++;}else(6) ；if(*6!=′＼0′)//如果字符串b还没有结束，则将b的剩余部分赋给cwhile(*b!=′＼0′)if(*b!=*w){*(++w)=*b；b++;}elseb++;(7) ；}void strsort(char*s)//将字符串S中的字符排序{int i，j，n；char t，*w;W=S;for(n=0；*w!=′＼0′；n++)//得到字符串长度nw++;for(i=0；in-1；i++)//对字符串s进行排序，按字母先后顺序for(j=i+1；jn；j++)if( (8) ){t=s[i]；s[i]=s[j]； (9) ；}}void main(){char s1[100]，s2[100]，s3[100]；printf("＼nPlease，input the first string：")；scanf("％s"，s1)；printf("＼nPlease input the second string：")；scanf("%s"，s2)；strsort(s1)；//将字符串s1排序strsort(s2)；//将字符串s2排序printf("％s＼n"，s1)；printf("％s＼n"，s2)；s3[0]=′＼0′；//字符串s3的第一个字符先置′＼0′结束标志(10) //将s1和s2合并，按照字母顺序排列，//且要删去相同字符，存入s3中printf("%s"，s3)；}
考题
设有如下定义:inta=1,b=2,c=3,d=4,m=2,n=2;则执行表达式:(m=ab)while(*y＋＋);return(y－x－1);}的功能是()
A、求字符串的长度B、比较两个字符串的大小C、将字符串x复制到字符串yD、将字符串X连接到字符串Y后面
考题
请编写函数proc，该函数的功能是：将放在字符串数组中的M个字符串(每串的长度不超过N)，按顺序合并组成一个新的字符串。 例如，若字符串数组中的M个字符串为： ABCD BCDEFG CDEFGHI 则合并后的字符串内容应该是ABCDBCDEFGCDEF—GHl。 注意：部分源程序给出如下。 请勿改动main函数和其他函数中的任何内容，仅在函数proc的花括号中填人所编写的若干语句。 试题程序： includestdio．h includeconio．h define M 3 define N 20 void proc(char arr[M][N]，char*b) {} void main { char str[M][N]={"ABCD"，"BCDEFG"，" CDEFGHI"}，i； char arr[100]={" ")； printf("The string：＼n")； for(i=0；iM；i++) puts(str[i])； printf("＼n")； proc(str，arr)； printf("The A string：＼n")； printf("％s"，arr)； printf("＼n＼n")； }
考题
对于求取两个长度为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．分支一限界
考题
请编写函数fun()，该函数的功能是：将放在字符串数组中的M个字符串(每串的长度不超过N)，按J顷序合并组成一个新的字符串。例如，若字符串数组中的M个字符串为AAAABBBBBBBCC则合并后的字符串内容应该是AAAABBBBBBBCC注意：部分源程序给出如下。请勿改动主函数main和其他函数中的任何内容，仅在函数fun的花括号中填入所编写的若干语句。试题程序：include ＜conio. h＞define M 3define N 20void fun (char a [M] [N], char *b){}main ( ){char w [M] [N] ={"AAAA", "BBBBBBB", "CC"}, i;char a[100]={" "};printf ("The string: \n ");for (i=0; i＜M; i++)puts (w[i]);printf (" \n ");fun (w, a);printf ("The A string: \n ");printf("%s ",a);printf("\n\n ");}
考题
对于求取两个长度为n的字符串的最长公共子序列问题，利用(41)策略可以有效地避免子串最长公共子序列的重复计算，得到时间复杂度为O(n2)的正确算法。A．贪心B．分治C．分支-限界D．动态规划
考题
读下列程序说明和C程序，将应填入(n)处。【程序说明】该程序定义了两个子函数strsort和strmerge。它们分别实现了将一个字符串按字母顺序排序和将两个字符串合并排序，并删去相同字符。在主函数里，先输入两个字符串s1和s2，然后调用strsort函数对它们分别排序，然后调用strmerge函数将s1和s2合并，将合并后的字符串赋给字符串s3，最后输出字符串s3。【程序】include＜stdio.h＞void strmerge(char，a，char *b，char *c) //将字符串a，b合并到字符串c中{char t，*w；w=c；while((1)){//找到字符串a，b当前字符中较小的字符if(*a＜ *b){t= *a；(2)；{else if (*a＞*b){t= *b；(3)；}else //字符串a，b当前字符相等{t= *a；a++；b++；}if((4)) //开始，可直接赋值*w=t；else if(t!=*w)//如果a，b中较小的当前字符与c中当前字符不相等，才赋值(5)；}if(*a!=\'\0') //如果字符串a还没有结束，则将a的剩余部分赋给Cwhile(*a!='\0')if(*a!=*w){*(++w)=*a；a++；}else(6)；if(*6!='\0') //如果字符串b还没有结束，则将b的剩余部分赋给cwhile(*b!='\0')if(*b! = *w){*(++w)=*b；b++；}elseb++；(7)；}void strsort(char*s) //将字符串S中的字符排序{int i，j，n；char t，*w；W=S；for(n=0；*w!='\0'；n++) //得到字符串长度nw++；for(i=0；i＜n-1；i++) //对字符串s进行排序，按字母先后顺序for(j=i+1；j＜n；j++)if((8)){t=s[i]；s[i]=s[j]；(9)；}}void main(){char s1[100]，s2[100]，s3[100]；printf("\nPlease，input the first string：")；scanf("%s"，s1)；printf("\nPlease input the second string：")；scanf("%s"，s2)；strsort(s1)； //将字符串s1排序strsort(s2)； //将字符串s2排序printf("%s\n"，s1)；printf("%s\n"，s2)；s3[0]='\0'； //字符串s3的第一个字符先置'\0'结束标志(10) //将s1和s2合并，按照字母顺序排列，//且要删去相同字符，存入s3中printf("%s"，s3)；}
考题
阅读以下说明和C函数，填补代码中的空缺(1)～(5)，将解答填入答题纸的对应栏内。【说明】函数removeDuplicates(char *str)的功能是移除给定字符串中的重复字符，使每种字符仅保留一个，其方法是：对原字符串逐个字符进行扫描，遇到重复出现的字符时，设置标志，并将其后的非重复字符前移。例如，若str指向的字符串为“aaabbbbscbsss”，则函数运行后该字符串为“abse”。【c代码】void removeDuplicates (char *str)int i,len = strlen (str); ／*求字符串长度*／If( (l) )return;／*空串或长度为1的字符串无需处理*lfor（i=0;i＜len;i++) {Int flag =O； ／*字符是否重复标志*／int m：for(m =( 2 ); m＜len; m++){if（str[i]==str[m] ) {__(3)_；break;}}if (flag){Int n，idx = m;／*字符串第idx字符之后、与str [i]不同的字符向前移*／For( n=idx+l; nlen. n++)if ( str[n]!= str[i]) {str[idx]= str[n]； (4);}Str[(5)]=\0; /* 设置字符串结束标志*／}}}
考题
阅读以下说明和流程图，填补流程图中的空缺，将解答填入答题纸的对应栏内。
[说明]
下面流程图的功能是：在给定的两个字符串中查找最长的公共子串，输出该公共子串的长度L及其在各字符串中的起始位置(L=0时不存在公共字串)。例如，字符串"The light is not bright tonight"与"Tonight the light is not bright"的最长公共子串为"he light is not bright"，长度为22，起始位置分别为2和10。
设A[1:M]表示由M个字符A[1]，A[2]，…，A[M]依次组成的字符串；B[1:N]表示由N个字符B[1]，B[2]，…，B[N]依次组成的字符串，M≥N≥1。
本流程图采用的算法是：从最大可能的公共子串长度值开始逐步递减，在A、B字符串中查找是否存在长度为L的公共子串，即在A、B字符串中分别顺序取出长度为L的子串后，调用过程判断两个长度为L的指定字符串是否完全相同(该过程的流程略)。
[流程图]
考题
阅读以下说明和C函数，填补代码中的空缺，将解答填入答题纸的对应栏内。
[说明]
函数removeDuplicates(chai *str)的功能是移除给定字符串中的重复字符，使每种字符仅保留一个，其方法是：对原字符串逐个字符进行扫描，遇到重复出现的字符时，设置标志，并将其后的非重复字符前移。例如，若str指向的字符串为"aaabbbbscbsss"，则函数运行后该字符串为"absc"。
[C代码] voidremoveDuplicates(char *str) { inti,len=strlen(str); /*求字符串长度*/ if(______)return; /*空串或长度为1的字符串无需处理*/ for(i=0;i＜len;i++){ int flag=0; /*字符是否重复标志*/ int m; for(m=______; m＜len;m++){ if(Str[i]==str[m]){ ______; break; } } if (flag) { int n,idx=m; /*将字符串第idx字符之后、与str[i]不同的字符向前移*/ for(n=idx+1; n＜len; n++) if(Str[n]!=str[i]){ str[idx]=str[n];______; } str[______]='\0'; /*设置字符串结束标志*/ } } }
考题
求解两个长度为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）
考题
阅读下列说明和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
#include
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 i i (1) ) {c[i][j] = c[i
-1][j -1] + 1;if(max { (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 【问题1】（8分）
根据以上说明和C代码，填充C代码中的空（1）～（4）。
【问题2】（4分）
根据题干说明和以上C代码，算法采用了 （5） 设计策略。
分析时间复杂度为 （6） （用O符号表示）。
【问题3】（3分）
根据题干说明和以上C代码，输入字符串x= "ABCADAB’，'y="BDCABA",则输出为 （7） 。
考题
填空题长度为n的串s1与长度为2n的串s2的比较运算的时间复杂度是（）。
热门标签
最新试卷
