第四章串习题_数据结构

《第四章串习题_数据结构》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、习题四串一、单项选择题1．下面关于串的的叙述中，哪一个是不正确的？（）A．串是字符的有限序列B．空串是由空格构成的串C．模式匹配是串的一种重要运算D．串既可以采用顺序存储，也可以采用链式存储2．串是一种特殊的线性表，其特殊性体现在（）。A．可以顺序存储B．数据元素是一个字符C．可以链接存储D．数据元素可以是多个字符3．串的长度是指（）A．串中所含不同字母的个数B．串中所含字符的个数C．串中所含不同字符的个数D．串中所含非空格字符的个数4．设有两个串p和q，其中q是p的子串，求q在p中首次出现的位置的算法称

2、为（）A．求子串B．联接C．匹配D．求串长5．若串S=“software”,其子串的个数是（）。A．8B．37C．36D．9二、填空题1．含零个字符的串称为______串。任何串中所含______的个数称为该串的长度。2．空格串是指____，其长度等于____。3．当且仅当两个串的______相等并且各个对应位置上的字符都______时，这两个串相等。一个串中任意个连续字符组成的序列称为该串的______串，该串称为它所有子串的______串。4．INDEX（‘DATASTRUCTURE’，‘STR’）=

3、________。5．模式串P=‘abaabcac’的next函数值序列为________。6．下列程序判断字符串s是否对称，对称则返回1，否则返回0；如f("abba")返回1，f("abab")返回0；intf((1)________){inti=0,j=0;while(s[j])(2)________;for(j--;i

4、rderstring*s,*t;intindex,length){inti,j,k,length1,con;index=0;length=0;i=1;while(i<=s.len){j=1;while(j<=t.len){if(s[i]==t[j]){k=1;length1=1;con=1;while(con)if(1)_{length1=length1+1;k=k+1;}else(2)__;if(length1>length){index=i;length=length1;}(3)____;}else(

5、4)___;}(5)__}}三、应用题1．描述以下概念的区别：空格串与空串。2．设有A=””,B="mule"，C="old"，D="my",试计算下列运算的结果(注:A+B是CONCAT（A,B）的简写,A=""的""含有两个空格)。(a)A+B(b)B+A(c)D+C+B(d)SUBSTR(B,3,2)(e)SUBSTR(C,1,0)(f)LENGTH(A)(g)LENGTH(D)(h)INDEX(B,D)(i)INDEX(C,"d")(j)INSERT(D,2,C)(k)INSERT(B,1,A)(

6、l)DELETE(B,2,2)(m)DELETE(B,2,0)3．设主串S=‘xxyxxxyxxxxyxyx’，模式串T=‘xxyxy’。请问：如何用最少的比较次数找到T在S中出现的位置？相应的比较次数是多少？4．给出字符串‘abacabaaad’在KMP算法中的next和nextval数组。5．已知：s＝“（xyz）＋＊”，t＝“（x＋z）＊y”。试利用联结、求子串和置换等基本运算，将s转化为t。四、算法设计题1．在顺序串上实现串的判等运算EQUAL(S,T)。2．在链串上实现判等运算EQUAL(S,T

7、)。3．若S和T是用结点大小为1的单链表存储的两个串（S、T为头指针），设计一个算法将串S中首次与串T匹配的子串逆值。4．以顺序存储结构表示串，设计算法。求串S中出现的第一个最长重复子串及其位置并分析算法的时间复杂度。（如果字符串的一个子串（其长度大于1）的各个字符均相同，则称之为等值子串。如果输入字符串S，以“！”作为结束标志。串S中不存在等值子串，则输出信息“无等值子串”，否则求出（输出）一个长度最大的等值子串。例如：若S=“abc123abc123!”，则输出“无等值子串”；若S=“abceebcc

8、adddddaaadd!”，则输出“ddddd”。）5．写一个递归算法来实现字符串逆序存储，要求不另设串存储空间。第四章串一、单项选择题1．B2.B3．B4．C5.C二、填空题1．空、字符2．由空格字符（ASCII值32）所组成的字符串空格个数3．长度、相等、子、主4．55．011223126．（1）chars[](2)j++(3)i>=j7．[题目分析]本题算法采用顺序存储结构求串s和串t的最大公共子串。串s用i指针（1<=