第四章:串
第四章 串
一、选择题
1.下面关于串的的叙述中,哪一个是不正确的?( )
A .串是字符的有限序列 B.空串是由空格构成的串
C .模式匹配是串的一种重要运算 D.串既可以采用顺序存储,也可以采用链式存储
2 若串S 1=‘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分)】
A .ABC###G0123 B.ABCD###2345 C.ABC###G2345 D.ABC###2345
E .ABC###G1234 F.ABCD###1234 G.ABC###01234
3.设有两个串p 和q ,其中q 是p 的子串,求q 在p 中首次出现的位置的算法称为( )
A .求子串 B.联接 C.匹配 D.求串长
4.已知串S=‘aaab ’, 其Next 数组值为( )。
A .0123 B.1123 C.1231 D.1211
5.串 ‘ababaaababaa ’ 的next 数组为( )。【中山大学 1999 一、7】
A .[1**********]9 B.[1**********]2 C.[1**********]6 D.[1**********]45
6.字符串‘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 )
7.模式串t=‘abcaabbcabcaabdab ’,该模式串的next 数组的值为( ),nextval
数组的值为 ( )。
A .0 1 1 1 2 2 1 1 1 2 3 4 5 6 7 1 2 B.0 1 1 1 2 1 2 1 1 2 3 4 5 6 1 1 2
C .0 1 1 1 0 0 1 3 1 0 1 1 0 0 7 0 1 D.0 1 1 1 2 2 3 1 1 2 3 4 5 6 7 1 2
E .0 1 1 0 0 1 1 1 0 1 1 0 0 1 7 0 1 F.0 1 1 0 2 1 3 1 0 1 1 0 2 1 7 0 1
8.若串S=’software ’, 其子串的数目是( )。
A .8 B.37 C.36 D.9
9.设S 为一个长度为n 的字符串,其中的字符各不相同,则S 中的互异的非平凡子串(非
空且不同于S 本身)的个数为( )。【中科院计算所 1997 】
A .2n-1 B.n2 C.(n2/2)+(n/2) D.(n2/2)+(n/2)-1 E. (n2/2)-(n/2)-1
F. 其他情况
10.串的长度是指( )【北京工商大学 2001 一 、6 (3分)】
A .串中所含不同字母的个数 B.串中所含字符的个数
C .串中所含不同字符的个数 D.串中所含非空格字符的个数
二、判断题
1.KMP 算法的特点是在模式匹配时指示主串的指针不会变小。( )
2.设模式串的长度为m, 目标串的长度为n ,当n ≈m 且处理只匹配一次的模式时,朴素的匹
配(即子串定位函数)算法所花的时间代价可能会更为节省。( )
3.串是一种数据对象和操作都特殊的线性表。( )
三.填空题
1.空格串是指__(1)__,其长度等于___(2)__。
2.组成串的数据元素只能是________。 【中山大学 1998 一 、5 (1分)】
3.一个字符串中________称为该串的子串 。
4.INDEX (‘DATASTRUCTURE ’, ‘STR ’)=________。
5.设正文串长度为n ,模式串长度为m ,则串匹配的KMP 算法的时间复杂度为________。
6.模式串P=‘abaabcac ’的next 函数值序列为________。
7.字符串’ababaaab ’的nextval 函数值为________。
8.设T 和P 是两个给定的串,在T 中寻找等于P 的子串的过程称为__(1)__,又称P 为__(2)__。
9.串是一种特殊的线性表,其特殊性表现在__(1)__;串的两种最基本的存储方式是__(2)__、__(3)__;两个串相等的充分必要条件是__(4)__。
10.两个字符串相等的充分必要条件是_______。
11.知U=‘xyxyxyxxyxy ’;t=‘xxy ’;
ASSIGN (S ,U );
ASSIGN (V ,SUBSTR (S ,INDEX (s ,t ),LEN (t )+1));
ASSIGN (m ,‘ww ’)
求REPLACE (S ,V ,m )= ________。 【东北大学 1997 一、1 (5分) 】
12.实现字符串拷贝的函数 strcpy为:
void strcpy(char *s , char *t) /*copy t to s*/
{ while (________)
} 【浙江大学 1999 一、5 (3分) 】
13.下列程序判断字符串s 是否对称,对称则返回1,否则返回0;如 f("abba")返回1,
f("abab")返回0; int f((1)________)
{int i=0,j=0; while (s[j])(2)________;
for(j--; i
} 【浙江大学 1999 一、6 (3分) 】
15.完善算法:求KMP 算法中next 数组。
PROC get _next(t:string,VAR next:ARRAY[1..t.len] OF integer);
BEGIN j:=1; k:=(1)__; next[1]:=0;
WHILE j
IF k=0 OR t.ch[j]=t.ch[k] THEN BEGIN j:=j+1; k:=k+1; next[j]:=k ;END
ELSE k:=(2)___;
END;
16.下面函数index 用于求t 是否为s 的子串,若是返回t 第一次出现在s 中的序号(从1
开始计) ,否则返回0。
例如:s=‘abcdefcdek’,t=‘cde’,则indse(s,t)=3, index(s,’aaa’)=0 。已知t ,
s 的串长分别是mt,ms
FUNC index(s,t,ms,mt);
i:=1;j:=1;
WHILE (imt THEN return (5)____; ELSE return (6)__
ENDF;
18.试利用下列栈和串的基本操作完成下述填空题。
initstack(s) 置s 为空栈;
push(s,x) 元素x 入栈;
pop(s) 出栈操作;
gettop(s) 返回栈顶元素;
sempty(s) 判栈空函数;
setnull(st) 置串st 为空串;
length(st) 返回串st 的长度;
equal(s1,s2) 判串s1和s2是否相等的函数;
concat(s1,s2) 返回联接s1和s2之后的串;
sub(s,i,1) 返回s 中第i 个字符;
empty(st) 判串空函数
FUNC invert(pre:string; VAR exp:string):boolean;
{若给定的表达式的前缀式pre 正确,本过程求得和它相应的表达式exp 并返回“true ”,
否则exp 为空串,并返回“false ”。已知原表达式中不包含括弧,opset 为运算符的集
合。}
VAR s:stack; i,n:integer; succ:boolean; ch: char;
BEGIN
i:=1; n:=length(pre); succ:=true; (1)__; (2)__;
WHILE (i
BEGIN ch:=sub(pre,i,l ); IF (3)_ THEN (4)__ ELSE IF (5)__THEN (6)_
ELSE BEGIN exp:=concat((7)___,(8)____); exp:=concat((9)___,(10)___); (11)__;
END;
i:=i+1
END; IF (12)___THEN
BEGIN exp:=concat(exp,sub(pre,n,1)); invert:=true END
ELSE BEGIN setnull(exp); invert:=false END
END;
注意:每个空格只填一个语句。 【清华大学 1996 八】
四 、应用题
1.名词解释:串
2.描述以下概念的区别:空格串与空串。
3.两个字符串S1和S2的长度分别为m 和n 。求这两个字符串最大共同子串算法的时间复
杂度为T(m,n)。估算最优的T(m,n),并简要说明理由。
4.设主串S=‘xxyxxxyxxxxyxyx ’,模式串T=‘xxyxy ’。请问:如何用最少的比较次数找
到T 在S 中出现的位置?相应的比较次数是多少?
5.KMP 算法(字符串匹配算法) 较Brute(朴素的字符串匹配) 算法有哪些改进?
6.已知模式串t=‘abcaabbabcab ’写出用KMP 法求得的每个字符对应的next 和nextval
函数值。
7.给出字符串‘abacabaaad ’在KMP 算法中的next 和nextval 数组。
8.令t=‘abcabaa ’, 求其next 函数值和nextval 函数值。
9.已知字符串‘cddcdececdea ’,计算每个字符的next 和nextval 函数的值。10.试利用
KMP 算法和改进算法分别求p1=‘abaabaa ’和p2=‘aabbaab ’的next 函数和nextval 函数。
11.已知KMP 串匹配算法中子串为babababaa, 写出next 数组改进后的next 数组信息值(要
求写出数组下标起点)。【西南交通大学 2000 二 、2】
12.求模式串T=‘abcaabbac' 的失败函数Next(j)值。
13.字符串的模式匹配KMP 算法中, 失败函数(NEXT)是如何定义的? 计算模式串p=
‘aabaabaaabc ’中各字符的失败函数值. 【石油大学 1998 一、2 (10分) 】
14.设字符串S=‘aabaabaabaac' ,P=‘aabaac'
(1)给出S 和P 的next 值和nextval 值;
(2)若S 作主串,P 作模式串,试给出利用BF 算法和KMP 算法的匹配过程。
15.设目标为t=‘abcaabbabcabaacbacba ’, 模式为p=‘abcabaa ’
(1)计算模式p 的naxtval 函数值;(5分)
(2)不写出算法, 只画出利用KMP 算法进行模式匹配时每一趟的匹配过程。
16.模式匹配算法是在主串中快速寻找模式的一种有效的方法,如果设主串的长度为m ,模式的长度为n ,则在主串中寻找模式的KMP 算法的时间复杂性是多少?如果,某一模式 P=’abcaacabaca ’,请给出它的NEXT 函数值及NEXT 函数的修正值NEXTVAL 之值。
17.设目标为S=‘abcaabbcaaabababaabca ’,模式为P=‘babab ’,
(1)手工计算模式P 的nextval 数组的值;(5分)
(2)写出利用求得的nextval 数组,按KMP 算法对目标S 进行模式匹配的过程。 (5分)
18.用无回溯的模式匹配法(KMP 法)及快速的无回溯的模式匹配法求模式串T 的next[j]值,添入下面表中:
19.在改进了的(无回溯)字符串模式匹配中,要先求next 数组的值。下面是求nextval 值的算法。
TYPE SAR=ARRAY[1..m] OF INTEGER;
PTY=ARRAY[1..m] OF CHAR;
PROCEDURE next2(P:PTY;VAR NEXTVAL:SAR);
{在模式P 中求nextval 数组的值}
1 BEGIN
2 J:=1;NEXTVAL[1]:=0;K:=0
3 REPEAT
4 IF (K=0) OR (P[J]=P[K])
5 THEN [ J:=J+1;K:=K+1;
6 IF P[J]=P[K]
7 THEN NEXTVAL[J]:=NEXTVAL[K]
8 ELSE NEXTVAL[J]:=K ]
9 ELSE K:=NEXTVAL[K]
10 UNTIL J=m
11 END;
算法中第4行有P[J]=P[K],第六行中也有P[J]=P[K]。两处比较语句相同。请分析说明此两处比较语句的含义是什么?分析此算法在最坏情况下的时间复杂度是多少?【北京邮电大学 1993 二、2(6分)】
20.在字符串模式匹配的KMP 算法中,求模式的next 数组值的定义如下:
next [j ]=
请问:
(1)当j=1时,为什么要取next[1]=0?
(2)为什么要取max{K},K最大是多少?
(3)其它情况是什么情况,为什么取next[j]=1?
21.给出KMP 算法中失败函数f 的定义,并说明利用f 进行串模式匹配的规则,该算法的技术特点是什么?
22. 在模试匹配KMP 算法中所用失败函数f 的定义中,为何要求p 1p 2„„p f(j)为p 1p 2„„p j 两头匹配的真子串?且为最大真子串?
23.如果两个串含有相等的字符,能否说它们相等?
24.设S1,S2为串,请给出使S1//S2=S2//S1成立的所有可能的条件(//为连接符)。
25.已知:s =' (xyz )+*' ,t =' (x +z )*y' 。试利用联结、求子串和置换等基本运算,将 s 转化为 t 。
第 五 部分、算法设计
1.设s 、t 为两个字符串,分别放在两个一维数组中,m 、n 分别为其长度,判断t 是否为s 的子串。如果是,输出子串所在位置(第一个字符),否则输出0。(注:用程序实现)
2.输入一个字符串,内有数字和非数字字符,如:ak123x456 17960?302gef4563,将其中连续的数字作为一个整体,依次存放到一数组a中,例如123放入a[0],456放入a[1],„ „ 。编程统计其共有多少个整数,并输出这些数。【上海大学 1998 一 (13分)】
3. 以顺序存储结构表示串,设计算法。求串S 中出现的第一个最长重复子串及其位置并分析算法的时间复杂度。【东南大学 2000 五 (15分)】 类似本题的另外叙述有:
(1)如果字符串的一个子串(其长度大于1)的各个字符均相同,则称之为等值子串。试设计一算法,输入字符串S ,以“!”作为结束标志。如果串S 中不存在等值子串,则输出信息“无等值子串”,否则求出(输出)一个长度最大的等值子串。
例如:若S=“abc123abc123!”,则输出“无等值子串”;若
S=“abceebccadddddaaadd!”,则输出“ddddd”。
4.假设串的存储结构如下所示,编写算法实现串的置换操作。
TYPE strt p =RECORD
ch: ARRAY[1..maxlen] OF char;
curlen:0..maxlen
END;
5.函数void insert(char*s,char*t,int pos)将字符串t 插入到字符串s 中,插入位置为pos 。请用c 语言实现该函数。假设分配给字符串s 的空间足够让字符串t 插入。(说明:不得使用任何库函数)
8.已知字符串S1中存放一段英文,写出算法format(s1,s2,s3,n),将其按给定的长度n 格式化成两端对齐的字符串S2, 其多余的字符送S3。
(以一维数组存放串值,并设指示器curlen 指示当前串长)
10.编写程序,统计在输入字符串中各个不同字符出现的频度并将结果存入文件(字符串中的合法字符为A-Z 这26个字母和0-9这10个数字)。
12.已知三个字符串分别为s=’ab „abcaabcbca „a ’,s ’=’caab ’, s’’=’bcb ’。利用所学字符串基本运算的函数得到结果串为:s ’’’=’caabcbca „aca „a ’,要求写出得到上结果串S ’’’所用的函数及执行算法。
13.S=“S1S2„Sn ”是一个长为N 的字符串,存放在一个数组中,编程序将S 改造之后输出:
(1)将S 的所有第偶数个字符按照其原来的下标从大到小的次序放在S 的后半部分;
(2)将S 的所有第奇数个字符按照其原来的下标从小到大的次序放在S 的前半部分; 例如:
S=‘ABCDEFGHIJKL ’
则改造后的S 为‘ACEGIKLJHFDB ’。