1．下面关于串的的叙述中，哪一个是不正确的？（ E ）
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)))其结果为（E  ）A．ABC###G012
3  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中首次出现的位置的算法称为（C）。
A．求子串B．联接C．匹配D．求串长
4．已知串S=‘aaab’，其Next数组值为（A ）。
A．0123        B．1123 C．1231 D．1211
5．串‘ababaaababaa’的next数组为（C ）。
A．012345678999    B．012121111212
C．011234223456    D．0123012322345
6．字符串‘ababaabab’的nextval 为（A）。
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数组的值为（D ）， nextval数组的值（F）。
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’，其子串的数目是（B ）。
A．8 B．37 C．36 D．9
题注：子串的定义是：串中任意个连续的字符组成的子序列，并规定空串是任意串的子串，任意串是其自身的子串。若字符串长度为n（n>0），长为n的子串有1个，长为n-1的子串有2个，长为n-2的子串有3个，……，长为1的子串有n个。由于空串是任何串的子串，所以本题的答案为：8*（8+1）/2+1=37。故选B。
9．设S为一个长度为n的字符串，其中的字符各不相同，则S中的互异的非平凡子串（非空且不同于S本身）的个数为（D ）。
A．2n-1    B．n2  C．(n2/2)+(n/2)
D．(n2/2)+(n/2)-1      E. (n2/2)-(n/2)-1  F.其他情况
10．串的长度是指（ B ）
A．串中所含不同字母的个数B．串中所含字符的个数
C．串中所含不同字符的个数D．串中所含非空格字符的个数
1．空格串是指  (1) 由空格字符（ASCII值32）所组成的字符串，其长度等于  (2) 空格个数。
2．组成串的数据元素只能是字符。
3．一个字符串中____任意个连续的字符组成的子序列____称为该串的子串。
4．INDEX（‘DATASTRUCTURE’，‘STR’）=_5_。
5．设正文串长度为n，模式串长度为m，则串匹配的KMP算法的时间复杂度为_ O(m+n)__。6．模式串P=‘abaabcac’的next函数值序列为____01122312____。
7．字符串’ababaaab’的nextval函数值为____01010421____。
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）= ___’xyxyxywwy’___。
12．实现字符串拷贝的函数 strcpy为：
void strcpy(char *s , char *t) /*copy t to s*/
{ while  (___*s++=*t++ 或（*s++=*t++）!=‘\0’__)
}
13．下列程序判断字符串s 是否对称，对称则返回1，否则返回0；如 f("abba")返回1，f("abab")返回0；
int f(___(1) char s[ ] ___)
{int i=0,j=0;
while (s[j])____ (2) j++ ____;
for(j--; i<j  && s[i]==s[j]; i++,j--);
return(___ (3) i >= j ____)
}
14．完善算法：求KMP算法中next数组。
PROC get _next(t:string,V AR next:len] OF integer);
BEGIN
j:=1; k:=__(1)0__;  next[1]:=0;
WHILE j<t.len DO
字符串长度17模式串长度8IF k=0 OR t.ch[j]=t.ch[k] THEN BEGIN j:=j+1; k:=k+1;
next[j]:=k;END
ELSE k:=__(2) next[k]__;
END;
15．下面函数index用于求t是否为s的子串，若是返回t第一次出现在s中的序号(从1开始计)，否则返回0。
例如:s=‘abcdefcdek’，t=‘cde’，则indse(s,t)=3, index(s,’aaa’)=0 。已知t，s的串长
分别是mt,ms
index(s,t,ms,mt);
FUNC
i:=1;j:=1;
WHILE  (i<ms) AND (j<mt) DO
IF s[i]=t[j] THEN  [__(1) i：=i+1__; __（2）j:=j+1 __]
ELSE [__(3)i:=i-j+2 __; __(4)j:=1; __ ]
IF j>mt THEN  return __(5)i-mt（或i:=i-j+1）__; ELSE  return __(6)0__
ENDF;
三、应用题
1．已知模式串t=‘abcaabbabcab’写出用KMP法求得的每个字符对应的next和nextval函数值。
解答：已知模式串t=‘abcaabbabcab’写出用KMP法求得的每个字符对应的next和nextval 函数值。
答：根据此定义，可求解模式串t的next和nextval值如下：
j    1  2  3  4  5  6  7  8  9  10 11 12
t串  a  b  c  a  a  b  b  a  b  c  a  b
next[j]  0  1  1  1  2  2  3  1  2  3  4  5
nextval[j] 0  1  1  0  2  1  3  0  1  1  0  5
2．已知KMP串匹配算法中子串为babababaa，写出next数组改进后的next数组信息值（要求写出数组下标起点）。
答：next数组值为011234567  改进后的next数组信息值为010101017。
3．设目标为t=‘abcaabbabcabaacbacba’，模式为p=‘abcabaa’
（1）计算模式p的naxtval函数值；
（2）不写出算法，只画出利用KMP算法进行模式匹配时每一趟的匹配过程。
答：（1）p的nextval函数值为0110132。（p的next函数值为0111232）。
（2）利用KMP(改进的nextval)算法，每趟匹配过程如下：
第一趟匹配： abcaabbabcabaacbacba        abcab(i=5,j=5)
第二趟匹配： abcaabbabcabaacbacba        abc(i=7,j=3)
第三趟匹配： abcaabbabcabaacbacba        a(i=7,j=1)
第四趟匹配： abcaabbabcabaac bacba(成功) abcabaa(i=15,j=8)
四、算法设计
1．以顺序存储结构表示串，设计算法。求串S中出现的第一个最长重复子串及其位置并分析算法的时间复杂度。
解答：以顺序存储结构表示串，设计算法。求串S中出现的第一个最长重复子串及其位置并分析算法的时间复杂度。
[题目分析]设以字符数组s表示串，重复子串的含义是由一个或多个连续相等的字符组成的子串，其长度用max表示，初始长度为0，将每个局部重复子串的长度与max相比，若比max大，则需要更新max，并用index记住其开始位置。
int LongestString(char s[],int n)//串用一维数组s存储，长度为n，本算法求最长重复子串，返回其长度。
index=0,max=0; //index记最长的串在s串中的开始位置，max记其长度
{int
int length=1,i=0,start=0;  //length记局部重复子串长度，i为字符数组下标
while(i<n-1)
if(s[i]==s[i+1]) {i++; length++;}
else //上一个重复子串结束
{if(max<length) {max=length; index=start; } //当前重复子串长度大，则更新max
i++;start=i;length=1; //初始化下一重复子串的起始位置和长度
}
printf(“最长重复子串的长度为%d，在串中的位置%d\n”，max,index);
return(max);
}//算法结束
[算法讨论]算法中用i<n-1来控制循环次数，因C数组下标从0 开始，故长度为n的串，其最后一个字符下标是n-1，当i最大为n-2时，条件语句中s[i+1]正好是s[n-1]，即最后一个字符。子串长度的初值数为1，表示一个字符自然等于其身。
算法的时间复杂度为O(n），每个字符与其后继比较一次。
2、写一个递归算法来实现字符串逆序存储，要求不另设串存储空间。
[题目分析]实现字符串的逆置并不难，但本题“要求不另设串存储空间”来实现字符串逆序存储，即第一个输入的字符最后存储，最后输入的字符先存储，使用递归可容易做到。
void InvertStore(char A[])//字符串逆序存储的递归算法。
{  char ch;
static int i = 0;//需要使用静态变量
("%c",&ch);
scanf
if (ch!= '.') { //规定'.'是字符串输入结束标志
InvertStore(A);
ch;//字符串逆序存储}
=
A[i++]
'\0'; //字符串结尾标记}//结束算法InvertStore
A[i]
=

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