第4章 串

第4章串4.1选择题1．下面关于串的的叙述中，哪一个是不正确的？（）A）串是字符的有限序列B）空串是由空格构成的串C）模式匹配是串的一种重要运算D）串既可以采用顺序存储，也可以采用链式存储【答案】B【解析】空串是不含任何字符的串，即空串的长度是零。空格串是由空格组成的串，其长度等于空格的个数。2．设有两个串p和q，其中q是p的子串，求q在p中首次出现的位置的算法称为（）A）求子串B）联接C）匹配D）求串长【答案】C3．若串s=software，其子串个数是（）A）8B）37C）36D）9【答案】C【解析】s的长度为8，长度为8的子串有1个，长度为7的子串有2个，长度为6的子串有3个，长度为5的子串有4个，…，长度为1的子串有8个，共有(1+8)*8/2=36个。4．串的长度是指（）A）串中所含不同字母的个数B）串中所含字符的个数C）串中所含不同字符的个数D）串中所含非空格字符的个数【答案】B5．若串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###G0123B）ABCD###2345C）ABC###G2345D）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###G12344.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仅有一个字符的情况）的数倍，而且长串就好象是由数个短串经过连接操作得到的。