四章 串
一、选择题
1．下面关于串的的叙述中，哪一个是不正确的？（ ）【北方交通大学 2001 一、5（2分）】
a．串是字符的有限序列 b．空串是由空格构成的串
c．模式匹配是串的一种重要运算 d．串既可以采用顺序存储，也可以采用链式存储
2 若串s1=‘abcdefg’, s2=‘9898’ ,s3=‘###’,s4=‘012345’,执行
concat(replace(s1,substr(s1,length(s2),length(s3)),s3),substr(s4,index(s2,‘8’),length(s2)))
其结果为（ ）【北方交通大学 1999 一、5 （25/7分）】
a．abc###g0123 b．abcd###2345 c．abc###g2345 d．abc###2345
e．abc###g1234 f．abcd###1234 g．abc###01234
3．设有两个串p和q，其中q是p的子串，求q在p中首次出现的位置的算法称为（ ）
a．求子串 b．联接 c．匹配 d．求串长
【北京邮电大学 2000 二、4（20/8分）】【西安电子科技大学 1996 一、1 （2分）】
4．已知串s=‘aaab’,其next数组值为（ ）。【西安电子科技大学 1996 一、7 （2分）】
a．0123 b．1123 c．1231 d．1211
5．串 ‘ababaaababaa’ 的next数组为（ ）。【中山大学 1999 一、7】
a．012345678999 b．012121111212 c．011234223456 d．0123012322345
6．字符串‘ababaabab’ 的nextval 为（ ）
a．(0,1,0,1,04,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 )
【北京邮电大学 1999 一、1（2分）】
7．模式串t=‘abcaabbcabcaabdab’，该模式串的next数组的值为（ ），nextval数组的值为 （ ）。
a．0 1 1 1 2 2 1 1 1 2 3 4 5 6 7 1 2 b．0 1 1 1 2 1 2 1 1 2 3 4 5 6 1 1 2
c．0 1 1 1 0 0 1 3 1 0 1 1 0 0 7 0 1 d．0 1 1 1 2 2 3 1 1 2 3 4 5 6 7 1 2
e．0 1 1 0 0 1 1 1 0 1 1 0 0 1 7 0 1 f．0 1 1 0 2 1 3 1 0 1 1 0 2 1 7 0 1
【北京邮电大学 1998 二、3 （2分）】
8．若串s=’software’,其子串的数目是（ ）。【西安电子科技大学 2001应用 一、2（2分）】
a．8 b．37 c．36 d．9
9．设s为一个长度为n的字符串，其中的字符各不相同，则s中的互异的非平凡子串（非空且不同于s本身）的个数为（ ）。【中科院计算所 1997 】
a．2n-1 b．n2 c．(n2/2)+(n/2) d．(n2/2)+(n/2)-1 e. (n2/2)-(n/2)-1 f.其他情况
10．串的长度是指（ ）【北京工商大学 2001 一、6 （3分）】
a．串中所含不同字母的个数 b．串中所含字符的个数
c．串中所含不同字符的个数 d．串中所含非空格字符的个数
责任编辑：小草
