数据结构测试（长春理工大学精品课）
第4章串
一、选择题
1．下面关于串的的叙述中，哪一个是不正确的？（）查看答案
A．串是字符的有限序列B．空串是由空格构成的串
C．模式匹配是串的一种重要运算D．串既可以采用顺序存储，也可以采用链式存储
正确答案是B
解释：空串是什么字符都没的串，空格串是由空格组成的串。

收起
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)))其结果为（）查看答案
A．ABC###G0123 B．ABCD###2345 C．ABC###G2345 D．ABC###G1234
正确答案是D收起
3．已知串S=‘aaab’,其Next数组值为（）。

查看答案
A．0123 B．1123 C．1231 D．1211
正确答案是A
解释：j=1时，next[j]取0收起
4．若串S=‘software’,其子串的数目是（）。

查看答案
A．8 B．37 C．36 D．9
正确答案是B
解释：长度为1的子串有8个，长度为2的子串有7个......长度为8的子串有1个，还有一个空串，8+7+6+5+4+3+2+1+1=37个。

收起
5．串的长度是指（）查看答案
A．串中所含不同字母的个数B．串中所含字符的个数
C．串中所含不同字符的个数D．串中所含非空格字符的个数
正确答案是B
解释：串的定义由字符组成的序列。

收起
二、填空题
1．组成串的数据元素只能是________。

查看答案
正确答案是字符收起
2．INDEX（‘DATASTRUCTURE’，‘STR’）=________。

查看答案
正确答案是5
解释：求子串的位置，匹配后子串第一个字符在主串中的位置。

收起
3．知U=‘xyxyxyxxyxy’；t=‘xxy’；
ASSIGN（S，U）；
ASSIGN（V，SUBSTR（S，INDEX（s，t），LEN（t）+1））；
ASSIGN（m，‘ww’）
REPLACE（S，V，m）= ________。

查看答案
正确答案是‘xyxyxywwy’
解释：s串中为‘xyxyxyxxyxy’v串中为‘xxyx’m串中为‘ww’，所以在s串中用m串替换v串，即为答案。

收起
4．模式串P=‘abaabcac’的next函数值序列为________。

查看答案
正确答案是01122312
解释：根据求next[j]的算法收起
5．一个字符串中________称为该串的子串。

查看答案
正确答案是任意个连续的字符组成的子序列
解释：子串必须是连续字符序列收起
6．空格串是指__(1)__，其长度等于___(2)__。

查看答案
正确答案是(1) 由空格字符（ASCII值32）所组成的字符串(2)空格的个数
收起
三、应用题
1．已知模式串t=‘abcaabbabcab’写出用KMP法求得的每个字符对应的next和nextval函数值。

查看答案解：
根据求next[j]的定义，可求解模式串t的next和nextval值如下：
收起
2．设字符串S=‘aabaabaabaac'，P=‘aabaac'
（1）给出S和P的next值和nextval值；
（2）若S作主串，P作模式串，试给出利用BF算法和KMP算法的匹配过程。

查看答案
解：
（1）S的next与nextval值分别为012123456789和002002002009，p的next与nextval值分别为012123和002003。

（2）利用BF算法的匹配过程：利用KMP算法的匹配过程：
第一趟匹配：aabaabaabaac 第一趟匹配：aabaabaabaac
aabaac(i=6,j=6) aabaac(i=6,j=6)
第二趟匹配：aabaabaabaac 第二趟匹配：aabaabaabaac
aa(i=3,j=2) (aa)baac
第三趟匹配：aabaabaabaac 第三趟匹配：aabaabaabaac a(i=3,j=1) (成功) (aa)baac
第四趟匹配：aabaabaabaac
aabaac(i=9,j=6)
第五趟匹配：aabaabaabaac
aa(i=6,j=2)
第六趟匹配：aabaabaabaac
a(i=6,j=1)
第七趟匹配：aabaabaabaac
(成功) aabaac(i=13,j=7)
收起。