长度为n的串s1与长度为2n的串s2的比较运算的时间复杂度是（）。 - 搜考题

违法和不良信息举报联系客服

免费注册登录

题目

长度为n的串s1与长度为2n的串s2的比较运算的时间复杂度是（）。

参考答案和解析

正确答案:O（n）

如果没有搜索结果或未解决您的问题，请直接联系老师获取答案。

相似问题和答案

第1题：

阅读以下函数fun(char *sl,char *s2){ int i=0;while(sl[i]==s2[i]&&s2[i]!='\0') i++;return(sl[i]=='\0'&&s2[i]=='\0');}此函数的功能是

A．将s2所指字符串赋给s1

B．比较s1和s2所指字符串的大小，若s1比s2的大，函数值为1，否则函数值为0

C．比较s1和s2所指字符串是否相等，若相等，函数值为1，否则函数值为0

D．比较s1和s2所指字符串的长度，若s1比s2的长，函数值为1，否则函数值为0

正确答案：C

第2题：

设有两个串s1和s2，求s2在s1中首次出现的位置的运算称为()。

A、求子串

B、求串长

C、联接

D、模式匹配

参考答案：D

第3题：

●试题五

阅读以下程序说明和C程序，将应填入(n)处的子句，写在答卷纸的对应栏内。

【程序说明】

函数int commstr(char *str1,char *str2,int *sublen)从两已知字符串str1和str2中，找出它们的所有最长的公共子串。如果最长公共子串不止1个，函数将把它们全部找出并输出。约定空串不作为公共子串。

函数将最长公共子串的长度送入由参数sublen所指的变量中，并返回字符串str1和str2的最长公共子串的个数。如果字符串str1和str2没有公共子串，约定最长公共子串的个数和最长公共子串的长度均为0。

【程序】

int strlen(char *s)

{char *t=s；

while(*++)；

return t-s-1;

}

intcommstr(char)*str1,char *str2,int *sublen

{char*s1,*s2；

int count=0,len1,len2,k,j,i,p;

len1=strlen(str1);

len2=strlen(str2);

if(len1>len2)

{s1=str1;s2=str2;}

else{len2=len1;s1=str2;s2=str1;}

for(j=len2;j>0;j--)/*从可能最长子串开始寻找*

{for(k=0; (1) <=len2;k++)/*k为子串s2的开始位置*/

{for(i=0;s1［ (2) ］!='＼0';i++;)/* i为子串s1的开始位置*/

{/* s1的子串与s2的子串比较*/

for(p=0;p<j)&& (3) ;p++);

if ( (4) )/*如果两子串相同*/

{for(p=0);p<j;p++}/*输出子串*/

printf("%c",s2［k+p］);

printf("＼n");

count++；/* 计数增1*/

}

}

}

if (count>0)break;

*sublen=(count>0)? (5) :0;

return count;

}

正确答案：

●试题五

【答案】(1)k+j(2)i+j-1(3)s1［i+p］==s2［k+p］(4)p==j或p>=j(5)j

【解析】略。

第4题：

设字符串s1='ABCDEFG',s2='PQRST',则运算s=CONCAT(SUB(s1，2，LEN(s2))，SUB(s1，LEN(s2，2))后的串值为(65)。

A．'ABCDEFEF'

B．'BCDEFG'

C．'BCPQRST'

D．'BCQR'

正确答案：A
解析：s=CONCAT(SUB(s1，2，5)，SUB(s1，5，2))=CONCAT(BCDEF，EF)=‘BDCEFEF’

第5题：

阅读以下程序说明和C程序，将应填入(n)处的子句，写在对应栏内。

【程序说明】

函数int commstr(char * str1，char * str2，int * sublen)从两已知字符串str1和str2中，找出它们的所有最长的公共子串。如果最长公共子串不止1个，函数将把它们全部找出并输出。约定空串不作为公共子串。

函数将最长公共子串的长度送入由参数sublen所指的变量中，并返回字符串str1和str2的最长公共子串的个数。如果字符串str1和str2没有公共子串，约定最长公共子串的个数和最长公共子串的长度均为0。

【程序】

int strlen(char * s)

{char *t=s;

while( * ++);

return t-s-1;

}

int commstr(char) *str1,char *str2,int *sublen

{ char*s1, *s2;

int count=0,len1 ,len2,k,j,i,p;

len1:=strlen(str1)

len2 = strlen(str2);

if(len1＞len2)

{s1=str1 ;s2=str2;}

else {len2 = len1;s1 = str2;s2 = str1;}

for(j=len2;j＞0;j--) /*从可能最长子串开始寻找*/

{for(k=0;(1)＜:len2;k++) /*k为子串s2的开始位置*/

{for(i=0;s1[(2)]!='\0';i++;) /*i为子串s1的开始位置*/

{ /*s1的子串与s2的子串比较*/

for (p=0;p＜j)&&(3);p++);

if ((4)) /*如果两子串相同*/

{for(p=0);p＜j;p++} /*输出子串*/

printf ("%c",s2[k+p]);

printf ("\n");

count++;/*计数增1 */

}

}

}

if (count＞0) break;

*sublen=(count＞0)?(5):0;

return count;

}

正确答案：(1)k+j (2)i+j-1 (3)s1[i+P]==s2[k+P] (4)P==j或p＞=j (5)j
(1)k+j (2)i+j-1 (3)s1[i+P]==s2[k+P] (4)P==j或p＞=j (5)j

第6题：

已知字符串S1中存放一段英文,写出算法format(s1,s2,s3,n),将其按给定的长度n格式化成两端对齐的字符串S2, 其多余的字符送S3。

参考答案：本题要求字符串s1拆分成字符串s2和字符串s3，要求字符串s2“按给定长度n格式化成两端对齐的字符串”，即长度为n且首尾字符不得为空格字符。算法从左到右扫描字符串s1，找到第一个非空格字符，计数到n，第n个拷入字符串s2的字符不得为空格，然后将余下字符复制到字符串s3中。
　　[算法描述]
　　void format (char *s1,*s2,*s3)
　　//将字符串s1拆分成字符串s2和字符串s3，要求字符串s2是长n且两端对齐
　　{char *p=s1, *q=s2;
　　int i=0;
　　while(*p!= '\0' && *p== ' ') p++;//滤掉s1左端空格
　　if(*p== '\0') {cout<<"字符串s1为空串或空格串"<　　while( *p!='\0' && i　　//字符串s1向字符串s2中复制
　　if(*p =='\0'){cout<<"字符串s1没有"<　　if(*(--q)==' ' ) //若最后一个字符为空格，则需向后找到第一个非空格字符
　　{p-- ; //p指针也后退
　　while(*p==' '&&*p!='\0') p++;//往后查找一个非空格字符作串s2的尾字符
　　if(*p=='\0')
　　{cout<<"s1串没有"<　　*q=*p; //字符串s2最后一个非空字符
　　*(++q)='\0'; //置s2字符串结束标记
　　}
　　*q=s3;p++; //将s1串其余部分送字符串s3。
　　while (*p!= '\0') {*q=*p; q++; p++;}
　　*q='\0'; //置串s3结束标记
　　}

第7题：

阅读以下函数 fun(char *sl，char *s2) { int i：0； while(sl[i]==s2[i]&&s2[i]!='\0') i++； return(sl[i]=='\0'&&s2[i]=='\0')； } 此函数的功能是

A．将s2所指字符申赋给s1

B．比较s1和s2所指字符串的大小，若s1比s2的大，函数值为1，否则函数值为0

C．比较s1和s2所指字符串是否相等，若相等，函数值为1，否则函数值为o

D．比较s1和s2所指字符串的长度，若s1比s2的长，函数值为1，否则函数值为o

正确答案：C
解析：在函数fun()中有两个字符型指针变量s1和s1，在函数中程序执行while循环，该循环退出条件有两个：一个是s1[i]!=s2[i](两个字符串不相等)；第二个是sl[i]和s2[i]相等均为“\0”(两个字符串相等)。循环退出后，执行return语句，即两个字符串相等则返回1，不相等则返回0。所以，C选项为所选。

第8题：

设串S的长度为n,则S的子串个数为n(n＋1)／2。()

此题为判断题(对，错)。

参考答案：错误

第9题：

以下说法中错误的是

A．strcpy(A,B)函数是将A字符串的内容复制到B字符串中

B．strlen(cha*s)返回字符串S的长度，未尾的字符不计算在内

C．char a[20]="string"；中字符串长度为6

D．strstr(S1,S2)函数在字符串S1中从左边开始查找字符串S2，若查找成功则返回S2在S1中首次出现的位置，否则返回NULL，如果S2为""，则返回S1。

正确答案：A
解析：strcpy( )函数的一般形式为：strcpy(to,from)，该函数将from字符串中的内容复制到to字符串中，故A项错误。

第10题：

阅读以下函数： fun(char*s1， char*s2) { int i=0; while(s1[i]==s2[i]&& s2[i]!='\0') i++; return(s1[i]==&& s2{i)!=='\0'); } 此函数的功能是( )。

A．将s2所指字符串赋给s1

B．比较s1和s2所指字符串的大小，若s1比s2的大，函数值为1，否则函数值为0

C．比较s1和s2所指字符串是否相等，若相等，函数值为1，否则函数值为0

D．比较s1和s2所指字符串的长度，若s1比s2的长，函数值为1，否则函数值为0

正确答案：C
解析：在函数fun()中有两个字符型指针变量s1和s2，在函数中程序执行while循环，该循环退出条件有两个：一个是 s1[i]!=s2[i](两个字符串不相等)；第二个是s1[i]和s2[i]相等均为\0(两个字符串相等)。循环退出后，执行return语句，即两个字符串相等则返回1，不相等则返回0。所以，C选项为所选。

更多相关问题

相关内容