《数据结构与算法》第四章-串习题.docx

《《数据结构与算法》第四章-串习题.docx》由会员分享，可在线阅读，更多相关《《数据结构与算法》第四章-串习题.docx（2页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据结构与算法第二部分习题精选一、填空题.称为空串； 称为空白串。1 .设 S= u A;/document/Mary.doc 则 strlen(s)=，/的字 符定位的位置为 O.子串的定位运算称为串的模式匹配，称为目标串，一 称为模式。2 .设目标T=abccdcdccbaa”，模式P=cdcc”，则第 次匹配成功。3 .若n为主串长，m为子串长，则串的古典(朴素)匹配算法最坏 的情况下需要比较字符的总次数为 o二、单选题()1.串是一种特殊的线性表，其特殊性体现在：A.可以顺序存储B.数据元素是一个字符C.可以链式存储 D.数据元素可以是多个字符()2.设有两个串p和q,求q在p中首次出

2、现的位置的运算称作：A .连接 B.模式匹配 C.求子串 D.求串长()3.设串 sl=ABCDEFG, s2=PQRST,函数 con(x,y)返回 x 和 y 串的连接串，subs(s, i,j)返回串s的从序号i开始的j个字符组成的子 串，len(s)返回串 s 的长度,则 con(subs(sl, 2, len(s2), subs(sl, len(s2), 2)的结果串是：A . BCDEFB . BCDEFGC . BCPQRSTD. BCDEFEF三、计算题.设 s=I AM A STUDENT, t=,GOOD, q=WORKER,求 Replace(s,STUDENTq)和Co

3、ncat(SubString(s,6,2), Concat(t,SubString(s,7,8)。1 .已知主串. s=,ADBADABBAABADABBADADA 模 式 串 pat=，ADABBADADAL写出模式串的nextval函数值，并由此画 出KMP算法匹配的全过程。答案一、填空题1.不包含任何字符(长度为0)的串 由一个或多个空格(仅由空格符)组成的串2.20 33.被匹配的主串 子串 4. 65. (n-m+l)*m二、单选题1.B 2, B 3. D四、计算题解： R叩lace(s,STUDENT,q) = I AM A WORKER因为 SubString(s,6,2)= A ； SubString(s,7,8)= STUDENTConcat(t,SubString(s,7,8) = OOD STUDENT5所以 Concat(SubString(s,6,2), Concat(t,SubString(s,7,8) = A GOODSTUDENT 2.解：（由演示程序得知）nextval函数值为0 1 02 1 0 1 040 在第12个字符处发现匹配！s=,ADBADABBAABADABBADADA,pat=,ADABBADADA,