第4章-串(习题).doc

第四章 串
一、选择题
1.下面关于串得得叙述中,哪一个就是不正确得？( )(2 分)
A.串就是字符得有限序列 B.空串就是由空格构成得串
C.模式匹配就是串得一种重要运算 D.串既可以采用顺序存储,也可以采用链式存储
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))) 其结果为( )(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.求串长(2 分)
4.已知串S=‘aaab’,其Next 数组值为( )。(2 分)
A.0123 B.1123 C.1231 D.1211
5.串 ‘ababaaababaa’ 得next 数组为( )。
A.9 B.2 C.6 D.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 )(2 分)
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
(2 分)
8.若串S=’software’,其子串得数目就是( )。(2 分)
A.8 B.37 C.36 D.9
9.设S 为一个长度为n 得字符串,其中得字符各不相同,则S 中得互异得非平凡子串(非空且不同于S本身)得个数为( )。
A.2n1 B.n2 C.(n2/2)+(n/2) D.(n2/2)+(n/2)1 E、 (n2/2)(n/2)1 F、其她情况
10.串得长度就是指( )(3 分)
A.串中所含不同字母得个数 B.串中所含字符得个数
C.串中所含不同字符得个数 D.串中所含非空格字符得个数
二、判断题
1.KMP 算法得特点就是在模式匹配时指示主串得指针不会变小。( ) (1 分)
2.设模式串得长度为m,目标串得长度为n,当n≈m 且处理只匹配一次得模式时,朴素得匹配(即子串定位函数)算法所花得时间代价可能会更为节省。( ) (1 分)
3.串就是一种数据对象与操作都特殊得线性表。( )(1 分)
二、填空题
1.空格串就是指__(1)__,其长度等于___(2)__。(2 分)
2.组成串得数据元素只能就是________。 (1 分)
3.一个字符串中________称为该串得子串 。(1 分)
4.INDEX(‘DATASTRUCTURE’, ‘STR’)=________。 (2 分)
5.设正文串长度为n,模式串长度为m,则串匹配得KMP 算法得时间复杂度为________。
6.模式串P=‘abaabcac’得next 函数值序列为________。(2 分)
7.字符串’ababaaab’得nextval 函数值为________。(2 分)
8.设T 与P 就是两个给定得串,在T 中寻找等于P 得子串得过程称为__(1)__,又称P 为__(2)__。(16/6 分)
9.串就是一种特殊得线性表,其特殊性表现在__(1)__;串得两种最基本得存储方式就是__(2)__、__(3)__;两个串相等得充分必要条件就是__(4)__。 (4 分)
10.两个字符串相等得充分必要条件就是_______。(2 分)
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)= ________。 (5 分)
12.实现字符串拷贝得函数 strcpy 为:
void strcpy(char *s , char *t) /*copy t to s*/
{ while (________)
} (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<j && s[i]==s[j]; i++,j);
return((3)_______)
} (3 分)
14.下列算法实现求采用顺序结构存储得串s 与串t 得一个最长公共子串。
程序(a)
PROCEDURE maxstr(VAR s,t : orderstring; VAR index,length : integer);
VAR i,j,k,length1:integer; con:boolean;
BEGIN
index :=0; length :=0; i :=1;
WHILE(i<=s、len) DO
[j:=1;
WHILE (j<=t、len) DO
[ IF (s[i]=t[j]) THEN
[ k:=1; length1:=1; con:=true;
WHILE con DO
IF (1)__THEN [length1:=length1+1;k:=k+1;] ELSE(2) _;
IF (length1>length) THEN [index:=i; length:=length1; ]
(3)____;
]
ELSE (4)____;
]
(5) ___;
]
END;
程序(b)
void maxstr(orderstring *s,*t; int index, length)
{int i,j,k,length1,con;
index=0;length=0;i=1;
while (i<=s、len)
{j=1;
while(j<=t、len)
{ if (s[i]= =t[j])
{ k=1;length1=1;con=1;
while(con)
if (1) _ { length1=length1+1;k=k+1; } else (2) __;
if (length1>length) { index=i; length=length1; }
(3)____;
}
else (4) ___;
}
(5) __
} } (10 分)
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<t、len DO
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;(4 分)
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 (i<ms) AND (j<mt) DO
IF s[i]=t[j] THEN [ (1)__; (2)__]
ELSE [ (3)___; (4)_ ]
IF j>mt THEN return (5)____; ELSE return (6)__
ENDF;(6 分)
17.阅读下列程序说明与pascal 程序,把应填入其中得( )处得字句写在答题纸上。
程序说明:本程序用于判别输入得字符串就是否为如下形式得字符串:W&M$ 其中,子字符串M 就是子字符串W 得字符反向排列,在此假定W 不含有字符&与字符$,字符&用作W 与M 得分隔符,字符$用作字符串得输入结束符。例如,对输入字符串ab&ba$、11&12$、ab&dd$、&$,程序将分别输出Ok、(就是),No、(不就是)。
程序
PROGRAM accept(input,output);
CONST midch=’&’; endch=’$’;
VAR an:boolean; ch:char;
PROCEDURE match(VAR answer: boolean);
VAR ch1,ch2:char; f:boolean;
BEGIN
read(ch1);
IF ch1<>endch
THEN IF (1)__
THEN BEGIN match(f);
IF f THEN BEGIN read(ch2); answer:=(2)_ END ELSE answer:=false
END
ELSE (3)___
ELSE (4)___
END;
BEGIN
writeln(‘Enter String:’);
match(an);
IF an THEN BEGIN
(5)__ IF (6)_ THEN writeln(‘Ok、’) ELSE writeln(‘No、’)
END
ELSE writeln(‘No、’)
END、 (15 分)
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<n) AND succ DO
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;
注意:每个空格只填一个语句。
四、应用题
1.名词解释:串 (3 分)
2.描述以下概念得区别:空格串与空串。(2 分)
3.两个字符串S1 与S2 得长度分别为m 与n。求这两个字符串最大共同子串算法得时间复杂度为T(m,n)。估算最优得T(m,n),并简要说明理由。 (6 分)
4.设主串S=‘xxyxxxyxxxxyxyx’,模式串T=‘xxyxy’。请问:如何用最少得比较次数找到T 在S 中出现得位置？相应得比较次数就是多少？ (8 分)
5.KMP 算法(字符串匹配算法)较Brute(朴素得字符串匹配)算法有哪些改进? ((2分)
6.已知模式串t=‘abcaabbabcab’写出用KMP 法求得得每个字符对应得next 与nextval 函数值。(10 分)
7.给出字符串‘abacabaaad’在KMP 算法中得next 与nextval 数组。(5 分)
8.令t=‘abcabaa’,求其next 函数值与nextval 函数值。 (6 分)
9.已知字符串‘cddcdececdea’,计算每个字符得next 与nextval 函数得值。
10.试利用KMP 算法与改进算法分别求p1=‘abaabaa’与p2=‘aabbaab’得next 函数与nextval 函数。(8 分)
11.已知KMP 串匹配算法中子串为babababaa,写出next 数组改进后得next 数组信息值(要求写出数组下标起点)。
12.求模式串T=‘abcaabbac' 得失败函数Next(j)值。(5 分)
13.字符串得模式匹配KMP 算法中,失败函数(NEXT)就是如何定义得?计算模式串p=‘aabaabaaabc’中各字符得失败函数值、 (10 分)
14.设字符串S=‘aabaabaabaac',P=‘aabaac'
(1)给出S 与P 得next 值与nextval 值;
(2)若S 作主串,P 作模式串,试给出利用BF 算法与KMP 算法得匹配过程。(15 分)
15.设目标为t=‘abcaabbabcabaacbacba’,模式为p=‘abcabaa’
(1)计算模式p 得naxtval 函数值;(5 分)
(2)不写出算法,只画出利用KMP 算法进行模式匹配时每一趟得匹配过程。(10 分)
16.模式匹配算法就是在主串中快速寻找模式得一种有效得方法,如果设主串得长度为m,模式得长度为n,则在主串中寻找模式得KMP 算法得时间复杂性就是多少？如果,某一模式 P=’abcaacabaca’,请给出它得NEXT 函数值及NEXT 函数得修正值NEXTVAL 之值。(5 分)
17.设目标为S=‘abcaabbcaaabababaabca’,模式为P=‘babab’,
(1)手工计算模式P 得nextval 数组得值;(5 分)
(2)写出利用求得得nextval 数组,按KMP 算法对目标S 进行模式匹配得过程。(10 分)
18.用无回溯得模式匹配法(KMP 法)及快速得无回溯得模式匹配法求模式串T 得next[j]值,添入下面表中:

kmp 法求得得next[j]值
快速无回溯法求得得next[j]值(25/4 分)
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 1 BEGIN
2 2 J:=1;NEXTVAL[1]:=0;K:=0
3 3 REPEAT
4 4 IF (K=0) OR (P[J]=P[K])
5 5 THEN [ J:=J+1;K:=K+1;
6 6 IF P[J]=P[K]
7 7 THEN NEXTVAL[J]:=NEXTVAL[K]
8 8 ELSE NEXTVAL[J]:=K ]
9 9 ELSE K:=NEXTVAL[K]
10 10 UNTIL J=m
11 11 END;
算法中第4 行有P[J]=P[K],第六行中也有P[J]=P[K]。两处比较语句相同。请分析说明此两处比较语句得含义就是什么？分析此算法在最坏情况下得时间复杂度就是多少？(6 分)
20.在字符串模式匹配得KMP 算法中,求模式得next 数组值得定义如下:

请问:
(1)当j=1 时,为什么要取next[1]=0？
(2)为什么要取max{K},K 最大就是多少？
(3)其它情况就是什么情况,为什么取next[j]=1?(8 分)
21.给出KMP 算法中失败函数f 得定义,并说明利用f 进行串模式匹配得规则,该算法得技术特点就是什么？ (8 分)
22. 在模试匹配KMP 算法中所用失败函数f 得定义中,为何要求p1p2……pf(j)为p1p2……pj 两头匹配得真子串？且为最大真子串？(7 分)
23.如果两个串含有相等得字符,能否说它们相等？(5 分)
24.设S1,S2 为串,请给出使S1//S2=S2//S1 成立得所有可能得条件(//为连接符)。(3 分)
25.已知:s ＝'(xyz)＋＊',t ＝'(x＋z)＊y'。试利用联结、求子串与置换等基本运算,将 s 转化为 t 。(5 分)
第五部分、算法设计
1.设s、t 为两个字符串,分别放在两个一维数组中,m、n 分别为其长度,判断t 就是否为s 得子串。如果就是,输出子串所在位置(第一个字符),否则输出0。(注:用程序实现) (10
分)
2.输入一个字符串,内有数字与非数字字符,如:ak123x456 17960?302gef4563,将其中连续得数字作为一个整体,依次存放到一数组ａ中,例如123 放入ａ［０］,456 放入ａ［１］,… … 。编程统计其共有多少个整数,并输出这些数。(13 分)
3. 以顺序存储结构表示串,设计算法。求串S 中出现得第一个最长重复子串及其位置并分析算法得时间复杂度。(15 分)
类似本题得另外叙述有:
(1)如果字符串得一个子串(其长度大于1)得各个字符均相同,则称之为等值子串。试设计一算法,输入字符串S,以“！”作为结束标志。如果串S 中不存在等值子串,则输出信息“无等值子串”,否则求出(输出)一个长度最大得等值子串。
例如:若S=“abc123abc123!”,则输出“无等值子串”;若S=“abceebccadddddaaadd!”,则输出“ddddd”。
4.假设串得存储结构如下所示,编写算法实现串得置换操作。(15 分)
TYPE strtp =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 插入。(说明:不得使用任何库函数)(10 分)
6.设计一个二分检索得算法,在一组字符串中找出给定得字符串,假设所有字符串得长度为4。
(1)简述算法得主要思想;(3 分)
(2)用PASCAL 语言分别对算法中用到得类型与变量作出说明;(3 分)
(3)用类PASCAL 语言或自然语言写算法得非递归过程; (8 分)
(4)分析该算法得最大检索长度;(3 分)
(5)必要处加上中文注释。(3 分)
7.设计一PASCAL 或C 语言得函数 atoi(x)、其中X 为字符串,由09 十个数字符与表示正负数得‘’组成,返回值为整型数值 。(7 分)
8.已知字符串S1 中存放一段英文,写出算法format(s1,s2,s3,n),将其按给定得长度n 格式化成两端对齐得字符串S2, 其多余得字符送S3。(15 分)
9.串以静态存储结构存储,结构如下所述,试实现串操作equal 算法、
CONST maxlen=串被确认得最大长度
TYPE strtp=RECORD
ch:ARRAY[1、、maxlen] OF char;
curlen:0、、maxlen
END;
(以一维数组存放串值,并设指示器curlen 指示当前串长) (12 分)
10.编写程序,统计在输入字符串中各个不同字符出现得频度并将结果存入文件(字符串中得合法字符为AZ 这26 个字母与09 这10 个数字)。(10 分)
11.写一个递归算法来实现字符串逆序存储,要求不另设串存储空间。
12.已知三个字符串分别为s=’ab…abcaabcbca…a’,s’=’caab’, s’’=’bcb’。利用所学字符串基本运算得函数得到结果串为:s’’’=’caabcbca…aca…a’,要求写出得到上结果串S’’’所用得函数及执行算法。(10 分)
13.S=“S1S2…Sn”就是一个长为N 得字符串,存放在一个数组中,编程序将S 改造之后输出:
(1)将S 得所有第偶数个字符按照其原来得下标从大到小得次序放在S 得后半部分;
(2)将S 得所有第奇数个字符按照其原来得下标从小到大得次序放在S 得前半部分;
例如:S=‘ABCDEFGHIJKL’,则改造后得S 为‘ACEGIKLJHFDB’。
14.编一程序,对输入得一表达式(字符串),输出其TOKEN 表示。表达式由变量A,B,C,常数(数字)0,1,…,9,运算符+,*与括号“(”,“)”组成。首先定义符号得类码:
其次定义符号得TOKEN 表示:

其中NAMEL 就是变量名表(不允许有相同名),CONST 就是常量表(不允许有相同数)。
例如,假设有表达式(A+A*2)+2*B*3#,则将生成如下TOKENL:(20 分)