文档介绍：第四章串
一、选择题
,哪一个是不正确的?( )【北方交通大学 2001 一、5(2分)】
,也可以采用链式存储
2 若串S1=‘ABCDEFG’, S2=‘9898’,S3=‘###’,S4=‘012345’,执行
concat(replace(S1,substr(S1,length(S2),length(S3)),S3),substr(S4,index(S2,‘8’),length(S2)))
其结果为( )【北方交通大学 1999 一、5 (25/7分)】
###G0123 ###2345 ###G2345 ###2345
###G1234 ###1234 ###01234
,其中q是p的子串,求q在p中首次出现的位置的算法称为( )
【北京邮电大学 2000 二、4(20/8分)】【西安电子科技大学 1996 一、1 (2分)】
=‘aaab’,其Next数组值为( )。【西安电子科技大学 1996 一、7 (2分)】
‘ababaaababaa’的next数组为( )。【中山大学 1999 一、7】
********** ********** **********
‘ababaabab’的nextval 为( )
A.(0,1,0,1,04,1,0,1) B.(0,1,0,1,0,2,1,0,1)
C.(0,1,0,1,0,0,0,1,1) D.(0,1,0,1,0,1,0,1,1 )
【北京邮电大学 1999 一、1(2分)】
=‘abcaabbcabcaabdab’,该模式串的next数组的值为( ),nextval数组的值为( )。
1 1 1 2 2 1 1 1 2 3 4 5 6 7 1 2 1 1 1 2 1 2 1 1 2 3 4 5 6 1 1 2
1 1 1 0 0 1 3 1 0 1 1 0 0 7 0 1 1 1 1 2 2 3 1 1 2 3 4 5 6 7 1 2
1 1 0 0 1 1 1 0 1 1 0 0 1 7 0 1 1 1 0 2 1 3 1 0 1 1 0 2 1 7 0 1
【北京邮电大学 1998 二、3 (2分)】
=’software’,其子串的数目是( )。【西安电子科技大学 2001应用一、2(2分)】
,其中的字符各不相同,则S中的互异的非平凡子串(非空且不同于S本身)的个数为( )。【中科院计算所 1997 】
-1 C.(n2/2)+(n/2) D.(n2/2)+(n/2)-1 E. (n2/2)-(n/2)-1
( )【北京工商大学 2001 一、6 (3分)】
二、判断题
。( )【北京邮电大学 2002 一、4 (1分)】
,目标串的长度为n,当n≈m且处理只匹配一次的模式时,朴素的匹配(即子串定位函数)算法所花的时间代价可能会更为节省。( )【长沙铁道学院 1998 一、1 (1分)】
。( )【大连海事大学 2001 1、L (1分)】
二、填空题
(1)__,其长度等于___(2)__。【西安电子科技大学 2001软件一、4(2分)】
。【中山大学 1998 一、5 (1分)】
。【华中理工大学 2000 一、3(1分)】
(‘DATASTRUCTURE’, ‘STR’)=________。【福州大学 1998 二、4 (2分)】
,模式串长度为m,则串匹配的KMP算法的时间复杂度为________。
【重庆大学 2000 一、4】
=‘abaabcac’的next函数值序列为________。【西安电子