“第四章 串”自测作业
单项选择题
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开始编号）。
综合题
1. 计算下列串的next值：
字符串长度17模式串长度8(1) aaabcaaba
(2) abcabcacb
(3) babbabab
2. 对S=aabcbabcaabcaaba，T=abcaaba，画出以T为模式串，S为目标串的快速匹配过程。若S串长度为n，T串长度为m，问算法的时间复杂度为多少？

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