第4章  串
4.1　选择题
1．下面关于串的的叙述中，哪一个是不正确的？（  ）
A）串是字符的有限序列         
B）空串是由空格构成的串
C）模式匹配是串的一种重要运算 
D）串既可以采用顺序存储，也可以采用链式存储
【答案】B
【解析】空串是不含任何字符的串，即空串的长度是零。空格串是由空格组成的串，其长度等于空格的个数。
2．设有两个串空值是指零长度的字符串p和q，其中q是p的子串，求q在p中首次出现的位置的算法称为（  ）
A）求子串        B）联接          C）匹配            D）求串长
【答案】C
3．若串s="software"，其子串个数是（  ）
A）8        B）37            C）36              D）9
【答案】C
【解析】s的长度为8，长度为8的子串有1个，长度为7的子串有2个，长度为6的子串有3个，长度为5的子串有4个，…，长度为1的子串有8个，共有(1+8)*8/2=36个。
4．串的长度是指（  ）
A）串中所含不同字母的个数     
B）串中所含字符的个数
C）串中所含不同字符的个数     
D）串中所含非空格字符的个数
【答案】B
5．若串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
【解析】函数concat(x,y)返回x和y的连接串，substr(s,i,j)返回串s的从序号i的字符开始的j个字符组成的子串，length(s)返回串s的长度。replase(s,t,v)用v替换s中出现的所有与t相等的子串,index(s,t,i)当s中存在与t值相同的子串时，返回它在s中的第i个字符之后第一次出现的位置。
substr(S1,length(S2),length(S3))=substr(S1,4,3)= "DEF";
replase(S1,substr(S1,length(S2),length(S3)),S3)=replase(S1, "DEF",S3)= "ABC###G";
substr(S4,index(S2, '8'),length(S2))=substr(S4,2,4)= "1234";
concat(replace(S1,substr(S1,length(S2),length(S3)),S3),substr(S4,index(S2, '8'),length(S2)))=concat("ABC###G", "1234")= "ABC###G1234"
4.2　填空题
1．空格串是指_____________，其长度等于_____________。
【答案】（1）由空格字符（ASCII值32）所组成的字符串  （2）空格个数
2．组成串的数据元素只能是_____________。
【答案】字符
【解析】串是一种特殊的线性表，其特殊性在于串中的元素只能是字符型数据。
3．设正文串长度为n，模式串长度为m，则串匹配的KMP算法的时间复杂度为_____________。
【答案】O(m+n)
【解析】朴素的模式匹配（Brute－Force）时间复杂度是Ｏ（m*n），KMP算法有一定改进，时间复杂度达到Ｏ（m＋n）。
4．两个字符串相等的充分必要条件是_____________。
【答案】两串的长度相等且两串中对应位置上的字符也相等。
5．一个字符串中_____________称为该串的子串 。
【答案】任意个连续的字符组成的子序列
4.3 　判断题
1．KMP算法的特点是在模式匹配时指示主串的指针不会变小（  ）
【答案】√
【解析】KMP算法的改进在于：每当一趟匹配过程中出现字符比较不相等时，不需回溯主串指针，而是利用已经得到的“部分匹配”的结果将模式向右“滑动”尽可能远的一段距离后，继续进行比较。
2．串是一种数据对象和操作都特殊的线性表（  ）
【答案】√
【解析】串是一种特殊的线性表，其特殊性在于串中的元素只能是字符型数据。字符型数据的操作符合字符型数据的操作规范，具有它的特殊性。
3．如果一个串中的所有字符均在另一串中出现，那么说明前者是后者的子串（    ）
【答案】×
【解析】一个字符串中任意个连续的字符组成的子序列称为该串的子串，注意其中字符的连续性。
4.4 　应用题
1．描述以下概念的区别：空格串与空串。
【答案】空格是一个字符，其ASCII码值是32。空格串是由空格组成的串，其长度等于空格的个数。空串是不含任何字符的串，即空串的长度是零。
2．设S1，S2为串，请给出使S1/*S2=S2/*S1成立的所有可能的条件（/*为连接符）。
【答案】
（1）s1和s2均为空串；
（2）两串之一为空串；
（3）两串串值相等（即两串长度相等且对应位置上的字符相同）。
（4）两串中一个串长是另一个串长（包括串长为1仅有一个字符的情况）的数倍，而且长串就好象是由数个短串经过连接操作得到的。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。