1、令s="abcabaa"，则它的特征向量next函数值和优化特征向量nextval函数值为(下标从0开始)：
A.next={0,1,1,1,2,3,2},nextval={0,1,1,0,1,2,1}
B.next={-1,0,0,-1,0,2,1},nextval={-1,0,0,0,1,2,1}
C.next={-1,0,0,0,1,2,1},nextval={-1,0,0,-1,0,2,1}
D.next={-1,0,0,0,1,2,1},nextval={-1,0,0,0,1,2,1}
C
规定next[1]=0
s[2]前，“a”,next[2]=重合个数0+1=1
s[3]前，“ab”,next[3]=重合个数0+1=1
s[4]前，“abc”,next[4]=重合个数0+1=1
s[5]前，“abca”,next[5]=重合个数1+1=2
s[6]前，“abcab”,next[6]=重合个数2+1=3
s[7]前，“abcaba”,next[7]=重合个数1+1=2
next[j]函数值为{0,1,1,1,2,3,2}（这里下标是从1开始）
题目中下标从0开始，故函数值都减1，得到
next={-1,0,0,0,1,2,1}。
规定nextval[1]=0（下标从1开始）
观察s[1]和s[2]，（下标从1开始），a和b不相同，故
nextval[2]=1
求nextval[3]时，看next[3]，next[3]=1，观察s[1]和s[3]，a和c不相等，故nextval[3]=next[3]=1
求nextval[4]时，next[4]=1,s[1]和s[4]为a和a，相等，nextval[4]=0
求nextval[5]时，next[5]=2,s[2]和s[5]为b和b，相同，看next[2]=1，比较s[1]和s[2]为a和b，不相同，则nextval[5]=next[2]=1
next[6]=3,s[3]和s[6]为c和a，不相同，nextval[6]=next[6]=3
next[7]=2,s[2]和s[7]为b和a，不相同，nextval[7]=2
综上可以得到nextval={0,1,1,0,1,3,2}
而题目中要求从下标0开始，则将其减1得到
{-1,0,0,-1,0,2,1}。
2、设主串 T = abaabaabcabaabc，模式串 S = abaabc，采用 KMP 算法进行模式匹配，到匹配成功时为止，在匹配过程中进行的单个字符间的比较次数是：
A.9
B.10
C.12
D.15
B
1.求S的next数组，(下标从0开始）next={-1,0,0,1,1,2}
2.开始匹配
abaabaabcabaaba
abaabc
当比较到s[5]和T[5]时，不成功，比较了6次
根据next[5]=2，将s移动到s[2]处和T[5]开始重新匹配比较：
abaabaabcabaaba
-----abaabc
比较4次，成功，结束匹配。
一共比较了6+4=10次。
3、串“ababaabab”的nextval为（ ）。
A.010104101
B.010102101
C.010100011
D.010101011
A
默认next[0]=-1;
next[1]是看s[1]之前的字符串“a”中前后重复的子串长度为0，（本身不算），故next[1]=0;
next[2]是看s[2]之前字符串"ab"中前后重复的子串长度为0，故next[2]=0;
next[3]是看s[3]之前字符串"aba"中前后重复子串长度为1，故next[3]=1;
next[4]是看s[4]之前字符串"abab"中前后重复子串长度为2，故next[4]=2;
next[5]……“ababa” ……重复子串长度为3，故next[5]=3;
next[6]……“ababaa”……1……next[6]=1;
next[7]……“ababaab”……2……next[7]=2;
next[8]……“ababaaba”……3……next[8]=3;
综上：next={-1,0,0,1,2,3,1,2,3}。
nextval[0]=-1,和next[0]的值一样；
nextval[1],next[1]=0,比较s[1]和s[0]，为a和b，
不相等，则nextval[1]=next[1]=0;
nextval[2],next[2]=0,比较s[2]和s[0]，为a和a，
相同，nextval[2]=nextval[ next[2] ]=nextval[0]=-1;
nextval[3],next[3]=1,比较s[3]和s[1]，为b和b，
相同,nextval[3]=nextval[next[3]]=nextval[1]=0;
nextval[4]，next[4]=2,比较s[4]和s[2]，为a和a，
相同，nextval[4]=nextval[ next[4] ]=nextval[2]=-1;
nextval[5],next[5]=3,比较s[5]和s[3]，为b和a，不相同，nextval[5]=next[5]=3;
nextval[6],next[6]=1,比较s[6]和s[1]，为b和b，
相同，nextval[6]=nextval[1]=0;
nextval[7],next[7]=2,比较s[7]和s[2]，为a和a，
相同，nextval[7]=nextval[2]=-1;
nextval[8],next[8]=3,比较s[8]和s[3]，为b和b
相同，nextval[8]=nextval[3]=0;
综上所述
nextval={-1,0,-1,0,-1,3,0,-1,0}
根据题目选项可得题目应该是下标从1开始的做法，故将函数值依次加1即可：
nextval={0,1,0,1,0,4,1,0,1}。
4、将两个字符串连接起来组成一个字符串时，选用函数（ ）。
A.strlen( )
B.strcpy( )
C.strcat( )
D.strcmp( )
C
5、设有两个串p和q，其中q是p的子串，求q在p中首次出现的位置的算法称为（ ）。
A.求子串
B.联接
C.模式匹配
D.求串长
C文章来源地址https://www.toymoban.com/news/detail-722218.html
6、串也是一种线性表，只不过( )。
A.数据元素均为字符
B.数据元素是子串
C.数据元素数据类型不受限制
D.表长受到限制
A
7、KMP算法下，长为n的字符串匹配长度为m的字串的时间复杂度为
A.O(N)
B.O(M+N)
C.O(M+LOGN)
D.O(N+LOGM)
B
8、下面关于串的叙述中，哪一个是不正确的
A.串是字符的有限序列
B.空串是由空格构成的串
C.模式匹配是串的一种重要运算
D.串既可以采用顺序存储，也可以采用链式存储
B
B.空串是长度为零的串。
9、若串S="software"，其子串的数目是
A.8
B.37
C.36
D.9
B
子串：n(n+1)/2+1
非空子串：n(n+1)/2
非空真子串：n(n+1)/2-1
10、串的长度是指
A.串中所含不同字母的个数
B.串中所含字符的个数
C.串中所含不同字符的个数
D.串中所含非空格字符的个数
B
11、下述对C语言字符数组的描述中错误的是（）。
A.字符数组可以存放字符串
B.字符数组中的字符串可以整体输入、输出
C.可以在赋值语句中通过赋值运算符"="对字符数组整体赋值
D.不可以用关系运算符对字符数组中的字符串进行比较
C
C.在赋值语句中通过赋值运算符"="对字符数组整体赋值，则就需要用到字符数组名，而对字符数组名进行操作时其会退化为常量指针，而进行赋值时左值必须是可以修改的变量。
12、设主串的长度为n，模式串的长度为m，则串匹配的KMP算法时间复杂度是( )。
A.O(m)
B.O(n)
C.O(n + m)
D.O(n×m)
C
13、下面关于字符串的程序，其输出结果是
#include <stdio.h>
voidfun(chars[], chart) {
inti=0;
while (s[i]) {
if (s[i] ==t)
s[i] =t-'a'+'A';
i++;
}
}
int main() {
charstr[100] ="abcdefg", c='d';
fun(str, c);
printf("%s\n", str);
return 0;
}A.abcdefg
B.abcDefg
C.ABCdEFG
D.ABCDEFG
B
14、设有两个串p和q，求q在p中首次出现的位置的运算称作( )。
A.连接
B.模式匹配
C.求子串
D.求串长
B
15、串是一种特殊的线性表，其特殊性体现在( )。
A.可以顺序存储
B.数据元素是一个字符
C.可以链接存储
D.数据元素可以是多个字符
B
16、设串s1=’ABCDEFG’，s2=’PQRST’，函数con (x,y)返回x和y串的连接串，subs(s,i,j)返回串s的从序号i的字符开始的j个字符组成的子串，len(s)返回串s的长度，则con (subs (s1,2,len (s2)), subs (s1,len (s2),2))的结果串是( )。
A.BCDEF
B.BCDEFG
C.BCPQRST
D.BCDEFEF
D
subs (s1,2,len (s2))返回s1中下标为2，长度为5的子串：BCDEF
subs (s1,len (s2),2)返回s1中下标为5，长度为2的子串：EF
17、字符串‘ababaabab’ 的nextval 为：
A.(0,1,0,1,0,4,1,0,1)
B.(0,1,0,1,0,2,1,0,1)
C.(0,1,0,1,0,0,0,1,1)
D.(0,1,0,1,0,1,0,1,1 )
A
a b a b a a b a b
0 0 1 2 3 1 2 3 4
next -1 0 0 1 2 3 1 2 3
next 0 1 1 2 3 4 2 3 4
nextval 0 1 0 1 0 4 1 0 1
18、已知字符串S为“abaabaabacacaabaabcc”，模式串t为“abaabc”。采用KMP算法进行匹配，第一次出现“失配”(s[i]≠t[j])时，i=j=5，则下次开始匹配时，i和j的值分别是()。
A.i=1,j=0
B.i=5,j=0
C.i=5,j=2
D.i=6,j=2
C
a b a a b c
0 0 1 1 2 0
next -1 0 0 1 1 2
next[j]=next[5]=2
当失配时，i不变，j回退到next[j]的位置并重新比较
即i=5，j=2
19、在用KMP算法进行模式匹配时，模式串“ababaaababaa”的next数组值为。
A.-1，0，1，2，3，4，5，6，7，8，9，9
B.-1，0，1，2，1，2，1，1，1，1，2，1
C.-1，0，0，1，2，3，1，1，2，3，4，5
D.-1，0，1，2，3，0，1，2，3，2，2，3
C
a b a b a a a b a b a a
0 0 1 2 3 1 1 2 3 4 5 1（最大相等前后缀）
（右移一位，第一位补-1）
next -1 0 0 1 2 3 1 1 2 3 4 5
20、Given a string T = abaabaabcabaabc and a pattern S = abaabc. if KMP method is used to match the pattern, then for how many times that the comparisons are made between pairs of characters before the success of matching?
A.9
B.10
C.12
D.15
B
a b a a b c
0 0 1 1 2 0
next -1 0 0 1 1 2
next 0 1 1 2 2 3
a b a a b a a b c a b a a b c
0 0 1 1 2 3 4 5 0 1 2 3 4 5 0
next -1 0 0 1 1 2 3 4 5 0 1 2 3 4 5
next 0 1 1 2 2 3 4 5 6 1 2 3 4 5 6
（next从-1开始字符串下标从0开始，next从0开始字符串下标从1开始）
123456
abaabaabcabaabc
abaabc（比较六次）
next[6]=3（或next[5]=2，取决于next数组从-1还是0开始）表示从模式串S第3个与主串第6个开始比较
123456
abaabaabcabaabc
-----abaabc（比较四次）
21、设主串 T = abaabaabaabcaabc，模式串 S = abaabc，采用 KMP 算法进行模式匹配，到匹配成功时为止，在匹配过程中进行的单个字符间的比较次数是：
A.9
B.10
C.14
D.15
C
a b a a b c
0 0 1 1 2 0
next -1 0 0 1 1 2
next 0 1 1 2 2 3
a b a a b a a b a a b c a a b c
0 0 1 1 2 3 1 2 3 4 2 0 1 1 2 0
next -1 0 0 1 1 2 3 1 2 3 4 2 0 1 1 2
next 0 1 1 2 2 3 4 2 3 4 5 3 1 2 2 3
123456
abaabaabaabcaabc
abaabc（比较六次）
next[6]=3表示从模式串S第3个与主串第6个开始比较
123456
abaabaabaabcaabc
-----abaabc（比较四次）
next[9]=3表示从模式串S第3个与主串第9个开始比较
123456789
abaabaabaabcaabc
-----------abaabc（比较四次）
22、令s="abaabc"，则它的特征向量next函数值和优化特征向量nextval函数值为(下标从0开始)
A.next={-1,0,0,1,1,2}, nextval={-1,0,-1,1,0,2}
B.next={0,1,1,1,2,2}, nextval={0,1,1,0,1,1}
C.next={-1,0,0,1,2,1}, nextval={-1,0,-1,1,0,1}
D.next={-1,0,1,1,1,2}, nextval={-1,0,-1,1,0,1}
A
a b a a b c
0 0 1 1 2 0
next -1 0 0 1 1 2
next 0 1 1 2 2 3
nextval 0 1 0 2 1 3
nextval -1 0 -1 1 0 2
23、已知串S=“aaab”，则next数组值为（ ）
A.1 1 2 3
B.1 2 3 1
C.0 1 2 3
D.1 2 1 1
C
a a a b
0 1 2 0
next -1 0 1 2
next 0 1 2 3
24、设串长为n，模式串长为m，则KMP 算法所需的附加空间为（ ）
A.O(n)
B.O(m+n)
C.O(m)
D.O(m*n)文章来源：https://www.toymoban.com/news/detail-722218.html
C
到了这里，关于数据结构与算法--字符串（单选题）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
