2023年7月20日发(作者：)

第4章 串 自测卷 姓名 班级

题号

题分

得分

一

20

二

15

三

15

四

20

五

30

总分

100

一、填空题

1. 称为空串； 称为空白串。

2. 设S=“A;/document/”，则strlen(s)= , “/”的字符定位的位置为 。

4. 子串的定位运算称为串的模式匹配； 称为目标串， 称为模式。

5. 设目标T=”abccdcdccbaa”，模式P=“cdcc”，则第 次匹配成功。

6. 若n为主串长，m为子串长，则串的古典匹配算法最坏的情况下需要比较字符的总次数为 。

二、单选题

（ ）1. 串是一种特殊的线性表，其特殊性体现在：

Ａ．可以顺序存储 Ｂ．数据元素是一个字符

Ｃ．可以链式存储 Ｄ．数据元素可以是多个字符

（ ）2. 设有两个串p和q，求q在p中首次出现的位置的运算称作：

Ａ．连接 Ｂ．模式匹配 Ｃ．求子串 Ｄ．求串长

（ ）3. 设串s1=’ABCDEFG’，s2=’PQRST’，函数con(x,y)返回x和y串的连接串，subs(s, i, j)返回串s的从序号i开始的j个字符组成的子串，len(s)返回串s的长度，则con(subs(s1, 2, len(s2)), subs(s1, len(s2),

2))的结果串是：

Ａ．BCDEF Ｂ．BCDEFG Ｃ．BCPQRST Ｄ．BCDEFEF

三、简答题

1. KMP算法的设计思想是什么？它有什么优点？

四、计算题

1. 【严题集4.3①】设s=’I AM A STUDENT’, t=’GOOD’, q=’WORKER’,

求Replace(s,’STUDENT’,q) 和Concat(SubString(s,6,2), Concat(t,SubString(s,7,8)))。

2. 【严题集4.8②】 已知主串s=’ADBADABBAABADABBADADA’,模式串pat=’ADABBADADA’。写出模式串的nextval函数值，并由此画出KMP算法匹配的全过程。

1

五、算法设计题

1. 【严题集4.12③】 编写一个实现串的置换操作Replace(&S, T, V)的算法。

2. 【严题集4.10③】写出将字符串反序的递推或递归算法，例如字符串为“abcsxw”，反序为“wxscba”

2