数据结构第四章串习题及答案.doc

《数据结构第四章串习题及答案.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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

2、串的个数是（）。A．8B．37C．36D．9二、填空题1．含零个字符的串称为______串。任何串中所含______的个数称为该串的长度。2．空格串是指____，其长度等于____。3．当且仅当两个串的______相等并且各个对应位置上的字符都______时，这两个串相等。一个串中任意个连续字符组成的序列称为该串的______串，该串称为它所有子串的______串。4．INDEX（‘DATASTRUCTURE’，‘STR’）=________。5．模式串P=‘abaabcac’的next函数值序列为________。6．下列程序判断字符串s是否对称，对称则返回1，否则返回0；如f("

3、abba")返回1，f("abab")返回0；intf((1)________){inti=0,j=0;while(s[j])(2)________;for(j--;i

4、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(4)___;}(5)__}}第四章串一、单项选择题1．B2.B3．B4．C5.C二、填空题1．空、字符2．由空格字符（ASCII值32）所组成的字符串空格个数3．长度、相等、子、主4．55．011223126．（1）chars[](2)j++(3)i>=j7．[题目分析]本题算法采用顺序存储结构求串s和串t的最大公共子

5、串。串s用i指针（1<=i<=s.len）。t串用j指针（1<=j<=t.len）。算法思想是对每个i（1<=i<=s.len，即程序中第一个WHILE循环），来求从i开始的连续字符串与从j（1<=j<=t.len，即程序中第二个ＷHILE循环）开始的连续字符串的最大匹配。程序中第三个（即最内层）的WHILE循环，是当s中某字符（s［i］）与t中某字符（t［j］）相等时，求出局部公共子串。若该子串长度大于已求出的最长公共子串（初始为０），则最长公共子串的长度要修改。(1)i+k<=s.len&&j+k<=t.len&&s[i+k]==t[j+k]//所有注释同上（a）(2)con=0

6、(3)j+=k(4)j++(5)i++