第4章  串 自测卷              姓名              班级                 
空值是指零长度的字符串
题号
一
二
三
四
五
总分
题分
20
15
15
20
30
100
得分
一、填空题
1.                               称为空串；                                    称为空白串。
2. 设S=“A;/document/Mary.doc”，则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. 【严题集4.12③】 编写一个实现串的置换操作Replace(&S, T, V)的算法。
2. 【严题集4.10③】写出将字符串反序的递推或递归算法，例如字符串为“abcsxw”，反序为“wxscba”

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