文档库

最新最全的文档下载
当前位置:文档库 > 第四章 串----作业

第四章 串----作业

“第四章串”自测作业

单项选择题

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值:

(1)aaabcaaba

(2)abcabcacb

(3)babbabab

2.对S="aabcbabcaabcaaba",T="abcaaba",画出以T为模式串,S为目标串的

快速匹配过程。若S串长度为n,T串长度为m,问算法的时间复杂度为多少?