第四章--串----作业.doc

“第四章串”自测作业

单项选择题

1．串的连接运算不满足???????????。

A.分配律????????B.交换律??????C.结合律??????D.都不满足

2．串是一种特殊的线性表，其特殊性体现在???????????。

A.可以顺序存储?????????B.数据元素是一个字符

C.可以链接存储?????????D.数据元素可以是多个字符

3．设有两个串p和q，求q在p中首次出现的位置的运算称作???????????。

A.?连接???????B.?模式匹配?????C.?求子串????????D.?求串长

4．串是一个???????????的序列。

A.不少于一个字母????B.有限个字符?

C.不少于一个字符?????D.空格或字母

5．已知串s=’ABCDEFGH’，则s的所有不同子串的个数为??????????。

A.8???????B.9??????C.36??????D.37

6.设串s1=’ABCDEFG’，s2=’PQRST’，函数concat(x，y)返回x和y串的连接串，substring(s，i，j)返回串s的从序号i的字符开始的j个字符组成的子串，Strlength(s)返回串s的长度，则concat(substing(s1，2，Strlength(s2))，substring(s1，len(s2)，2))的结果串是??????????。

A.BCDEF???????????????????????B.BCDEFG

C.BCPQRST?????????????????????D.BCDEFEF

填空题

1．两个串相等的充分必要条件是???????????。

2．空格串是???①???,其长度等于???②???。

3．模式串‘abaabade’的next函数值为???????????（请列表说明）。

4．在串S=’tuition’中，以t为首字符且值不相同的子串有?????????个，它们是?????????。

5.使用“求子串”substring(S,pos,len)和“联接”concat(S1,S2)的串操作，可从串s=’conduction’中的字符得到串t=’cont’，则求t的串表达式为???????????。

6.已知字符串p=’abcabcabbac’，则next(3)和next(6)分别为???①??、???②???。

7.设对主串’bcdbcddabcdbcdbac’和模式串’bcdbcdb’进行KMP模式匹配。第1趟匹配失败后，则下一趟匹配将由主串的第??①????个字符与模式串的第__②___字符开始比较（字符串中字符从1开始编号）。

综合题

计算下列串的next值：

aaabcaaba

abcabcacb

babbabab

对S=?aabcbabcaabcaaba?，T=?abcaaba?，画出以T为模式串，S为目标串的快速匹配过程。若S串长度为n，T串长度为m，问算法的时间复杂度为多少？