2025年数据结构与算法真题集锦及详细解答

第四章串

一、选择题

1.下面有关事的的论述中，哪一种是不对的的？（）【北方交通大学一、5（2分）】

A.串是字符的有限序列B.空串是由空格构成的串

C.模式匹配是串的一种重要运算D.串既可以采用次序存储，也可以采用链式存储

2若串S产'ABCDEFG',S2='9898',S3='###',S4=‘012345,，执行

concal(replace(SI,substr(SI,length(S2),length(S3)),S3),substr(S4,index(S2,*8*),length(S2)))

其成果为()【北方交通大学1999一、5(25/7分)】

A.ABC###G0123B.ABCD###2345C.ABC###G2345D.ABC###2345

E.ABC###G1234F.ABCD###⑵4G.ABC###01234

3.设有两个串p和q,其中q是p的子串，求q在P中初次出现的位置的算法称为（）

A.求子串B.联接C.匹配D.求串长

【北京邮电大学二、4（20/8分）】【西安电子科技大学1996—、1（2分）】

4.已知串S:'aaab',其Next数组值为（）。【西安电子科技大学1996—、7（2分）】

A.0123B.1123C.1231D.1211

5.串'ababaaababaa'的next数组为()。【中山大学1999—、7]

A.B.C.D.5

6.字符串4ababaabab,的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分）】

7.模式串t=fabcaabbcabcaabdabT,该模式串的next数组的值为（）»nextval数组的值为)o

A.01112211123456712B.01112121123456112

C.01110013101100701D.01112231123456712

E.01100111011001701F.0110213101102701

【北京邮电大学1998二、3（2分）】

8.若串S='software',其子串的数目是（【西安电子科技大学应用2（2分分

A.8B.37C.26D.9

9.设S为一种长度为n的字符串，其中的字符各不相似，则S中的互异的非平凡子串（非空且不一样于S

自身）的个数为（）。【中科院计算所1997]

A.2n-lB.n2C.（n2/2）+（n/2）D.（n2/2）+（n/2）-1E.（n2/2）-（n/2）-1F.其他状况

10.串的长度是指（）【北京工商大学一、6（3分）】

A.串中所含不一样字母的个数B.串中所含字符的个数

C.串中所含不一样字符的个数D.串中所含非空格字符的个数

二、判断题

1.KMF算法的特点是在模式匹配时指示主串的指针不会变小。（〉【北京邮电大学一、4（1分）】

2.设模式串的长度为m,目的串的长度为n,当n和m且处理只匹配一次的模式时，朴素的匹配（即子串定

位函数）算法所花的时间代价也许会更为节省。（）【长沙铁道学院1998一、1（1分）】

3.串是一种数据对象和操作都特殊的线性表。（）【大连海事大学1、L（1分）】

二、填空题

1.空格串是指（D,其长度等于（2）.【西安电子科技大学软件一、4（2分）】

2.构成串的数据元素只能是_______。【中山大学1998—、5（1分）】

3.一种字符串中称为该串的子串。【华中理工大学一、3（1分）】

4.INDEX（'DATASTRUCTURE','STR'）=________。【福州大学1998二、4（2分）】

5.设正文串长度为n,模式串长度为m,则串匹配的KMP算法的时间复杂度为_______。

【重庆大学一、4】

6.模式串P='abaabcac'的next函数值序列为_______。【西安电子科技大学软件一、6（2分）】

7.字符串'ababaaab'的nextval函数值为_______。【北京邮电大学二、4（2分）】

8.设T和P是两个给定的串，在T中寻找等于P的子串的过程称为，又称P为⑵。

【西安电子科技大学1998二、5(16/6分)】

9.申是一•种特殊的线性表，其特殊性表目前(1):串的两种最基本的存储方式是(3)；

两个串相等的充足必要条件是」k。【中国矿业大学一、3(4分)】

10.两个字符串相等的充足必要条件是______。【西安电子科技大学1999软件一、1(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)=________»【东北大学1997一、1(5分)】

12.实现字符串拷贝的函数strcpy为：

voidstrcpy(char*s,char*t)/*copyttos*/

{while(________)

}【浙江天学1999一、5(3分)】

13.下列程序判断字符串s与否对称，对称则返回1,否则返回0：如f("abba")返回1,f("abab")返回0：

intf(GJ)

{inti=0,j=0;

while(s[.j])(2);

for(j-;i<j&&s[i]==s[j];i++,j-);

return((3))

}【浙江大学1999一、6(3分)】

14.下列算法实现求采用次序构造存储的串s和串t的一种最长公共子串。

程序(a)

PROCEDUREmaxcomstr(V?\Rs,t:orderstring;VARindex,length:integer);

VARi,j,k,lengthl:integer;con:boolean;

BEGIN

index:=0;length:=0;i:=1;

WHILE(i<=s.len)DO

[j：=l；

WHILE(j<=t.len)DO

[IF(s[i]=t[j])THEN

[k:=1;lengthl:=1;con:=true;

WHILEconDO

IFUJTHEN[lengthl:=lengthl+l;k:=k+l;]ELSE②;

IF(lcngthl>lcngth)THEN[indcx:=i;lcnglh:=lengthl;]

(3);

]

ELSEU);

]

(5);

]

END;

程序(b)

voidmaxcomstr(orderstring*s,*t;intindex,length)

{inti,j,k,lengthI,con;

index=0;length=0;i=l;

whi1e(i<=s.len)

{j=l；

while(j<=t.len)

{if(s[i]==t[j])

{k=l;lengthL=I;con=l;

while(con)

if(1){lengthl=lengthl+l;k=k+l：}else(2);

if(lengthl>length){index=i;length=length1;}

(3);

)

elseX4)；

}

(5)

}}【上海大学一、2：10分)】

15.完善算法：求KMP算法中next数组。

PROCget_next(t:string,VARnext:ARRAY[1..t.len]OFinteger);

BEGIN

j:=1;k:=(l);next[1]:=0;

WHILEj<t.lenDO

IFk=0ORt.ch[j]=t.ch[k]THENBEGINj:=j+l;k:=k+l;next[j]:=k;END

ELSEk:=(2);

END;

【中山大学1998四、1(4分靖

16.下面函数index用于求t与否为s的子串，若是返回t第一次出目前s中的序号(从1开始计)，否则

返回0。

例如：s='abcdefcdek',t='cd?',则indse(s,t)=3,index(s,*aaa*)=0。已知t,s的吕长分别

是mt,ms

FINCindex(s,t,ms,mt);

i：=l；j：=l；

WHILE(i<ms)AND(j<mt)DD

IFs[i]=t[j]THEN[⑴；(2)_]

ELSE[13)_;]

IFj>mtTHENreturn⑨____:ELSEreturn®

ENDF;

【南京理工大学1999三、2(5分)】

17.阅读下列程序阐明和pascal程序，把应填入其中的()处的字句写在答题纸上。

程序阐明：

本程序用于鉴别输入的字符串与否为如下形式的字符串：

W&.MS其中，子字符串M是子字符串W的字符反向排列，在此假定W不具有字符&和字符$,字符&用作

“'与M的分隔符，字符$用作字符串的输入结束符。

例如，对输入字符串ab&ba$、ab&dd$、&$，程序将分别输出0k.(是)，No.(不是)。

程序

PROGRAMaccept(input,output);

CONSTmidch=,&';endch=,$';

VARan:boolcan;ch:char;

PROCEDUREmatch(V.ARanswer:boolean);

VARchi,ch2:char;f:boolean;

BEGIN

read(chi);

IFchlOendch

THENIF£1)

THENBEGINmatch(f);

IFfTHENBEGINread(ch2);answer.⑵ENDELSEanswer:=false

END

ELSE13)

ELSE(4)

END;

BEGIN

writeln(iEnterString:,);

match(an);

IFanTHENBEGIN

(5)IF(6)THENwriteln('Ok.')ELSEwriteln('No.')

END

ELSEwriteln('No.')

END.【上海海运学院1998七（15分）】

18.试运用下列栈和串的基本操作完毕下述填空题。

iritstack(s)置s为空栈：

push(s,x)元素x入栈；

pcp(s)出栈操作；

gettop(s)返回栈顶元素；

sempty(s)判栈空函数：

setnull(st)置串st为空串；

length(st)返回率st的长度；

ccual(si,s2)判串si和s2与否相等的函数;

ccncat(si,s2)返回联接si和s2之后的串；

sub(s,i,1)返回s中第i个字符：

empty(st)判串空函数

FINCinvert（pre:string;VARexp:string）:boolean;

｛若给定的体现式的前缀式pre对的，本过程求得和它对应的体现式exp并返回“true"，否则exp

为空串，并返回“false”。已知原体现式中不包括括弧，0Pset为运算符的集合。｝

VARs:stack：i,n:integer;succ:boolean;ch:char;

BEGIN

i:=1;n:=length(pre);succ:=true;

(1)；⑵；

WHILE(i<n)ANDsuccDO

BEGINch:=sub(pre,i,1)；

IF(3)THEN(4)_

ELSEIF15)THEN

ELSEBEGIN

exp:=concat((7)(8));

cxp:=concat((9)(10));

⑴)；

END;

i:=i+l

END;

IF(12)THEN

BEGINexp:=concat(exp.sub(pre,n,1));invert:=trueEND

ELSEBEGINsetnul1(exp);invert:=falseEND

END;

注意：每个空格只填一种语句。【清华大学1996A]

四、应用题

1.名词解释：串【大连海事1996—、10（1分）】【河海大学1998二、5（3分）】

2.描述如下概念的区别：空格串与空串。【大连海事大学1996三、2、（1）（2分）】

3.两个字符串S1和S2的长度分别为m和n。求这两个字符串最大共同子串算法的时间复杂度为T（m,n）。

估和最优的T（m,n）,并简要阐明理由。【北京工业大学1996一、5（6分）】

4.设主串S='xxyxxxyxxxxyxyx',模式串T='xxyxy'。请问：怎样用至少的比较次数找到T在S中出现

的位置？对应的比较次数是多少？【大连海事大学四（8分）】

5.KVP免法（字符串匹配算法）较Brute（朴素的字符串匹配）算法有哪些改善？【大连海事大学1996三、1（（2

分）】

6.已知模式串t=<abcaabbabcab,写出用KMP法求得的每个字符对应的next和nextval函数值。

【北京邮电大学1997三（10分）】

7.给出字符串'abacabaaad'在KMP算法中的next和nextval数组。【北京邮电大学三、1（5分）】

8.令t='abcabaa',求其next函数值和nextval函数值。【北方交通大学1994—（6分）】

9.已知字符串'cddcdccecdea',计算每个字符的ncxl和nexlval函数的值。【南京邮电大学一2】

10.试运用KMP算法和改善第法分别求pl='abaabaa'和p2='aabbaab'的next函数和nextva.函数。

【东南大学1999一、6（8分）】

11.已知KMP串匹配算法中子串为babababaa,写出next数组改善后的next数组信息值（规定写巴数组下

标起点）。【西南交通大学二、2]

12.求模式串丁=<abcaabbac，的失败函数Ncxl（j）值。【西安交通大学1996四、4（5分）】

13.字符串的模式匹配KMP和法中，失败函数（NEXT）是怎样定义的？计算模式串p='aabaabaaabc'中各字

符的失败函数值.【石油大学1998一、2（10分）】

14.设字符串S=faabaabaabaac>»P=*aabaac,

（I）给出S和P的next值和nextval值；

（2）若S作主串，P作模式串，试给出运用BF算法和KMP算法的匹配过程。

【北方交通大学1998Z1（15分）】

15.设目的为1='abcaabbabcabaacbacba',模式为p=*abcabaa,

（I）计算模式p的naxtval函数值：（5分）

（2）不写出算法，只画出运用KMn算法进行模式匹配时每一趟的匹配过程。（5分）

【清华大学1998八（10分）】

16.模式匹配算法是在主串中迅速寻找模式的一种有效的措施，假如设主串的长度为m,模式的长度为n,

则在主串中寻找模式的KMP算法的时间复杂性是多少？假如，某一模式P='abcaacabaca',请给出它的

NEXT函数值及NEXT函数的修正值NEXTVAL之值。【上海交通大学一（5分）】

17.设目的为5='abcaabbcaaabababaabca',模式为P='babab',

（I）手工计算:模式P的nextval数组的值：（5分）

（2）写出运用求得的nextval数组，按KVP算法对目的S进行模式匹配的过程。（5分）

【清华大学1997四（10分）】

18.用无回溯的模式匹配法（KMP法）及迅速的无向溯的模式匹配法求模式串T的next[j]值，添入下面表

中：

j1234567

taabbaab

kmp法求得的next[j]值

迅速无回溯法求得的值

【北京邮电大学1992三、1（25/4分）】

19.在改善了的（无回溯）字符串模式匹配中，要先求next数组的值。下面是求nextval值的算法。

TYPESAR=ARRAY[1..m]OFINTEGER;

PTY=ARRAY[1..m]OFCHAR;

PROCEDUREnext2（P:PTY;VARNEXTVAL:SAR）;

（在模式P中求nextval数组的值｝

1BEGIN

2J:=1;NEXTVAL[1]:=O;K:=O

3REPEAT

4IF(K=0)OR(P[J]=P[K])

5THEN[J:=J+1;K:=KH;

6IFP[J]=P[K]

7THENNEXTVAL[J]:=NEXTVAL[K]

8ELSENEXTVAL[J]:=K]

9ELSEK:=NEXTVAL[K]

10UNTILJ=m

11END;

和法中第4行有P[J]=P[K],第六行中也有P[J]=P[K]o两处比较语句相似。请分析阐明此两处比较语

句的含义是什么？分析此算法在最坏状况下的时间复杂度是多少？【北京邮电大学1993二、2（6分）】

20.在字符串模式匹配的KMP算法中，求模式的next数组值的定义如下：

next[j]=

请问：

（D当j=l时，为何要取ncxl[l]=0?

（2）为何要取max{K},K最大是多少？

（3）其他状况是什么状况，为何取next[j]=l?【北京邮电大学1994二（8分）】

21.给出KMP算法中失败函数f的定义，并阐明运用f进行串模式匹配的规则，该算法的技术特点是什么？

【东南大学1993—、3（9分）1997—、2（8分）一、6（6分）】

22.在模试匹配KMP算法中所用失败函数f的定义中，为何规定p,p2……p”■为p.p2……pj两头匹配的真

子串？且为最大真子串？【东南大学1996一、3（7分）】

23.假如两个串具有相等的字符，能否说它们相等？【西安电子科技大学软件一、3（5分）】

24.设S1,S2为串，请给出使S"/S2=S2〃S1成立的所有也许的条件（〃为连接符）。

【长沙铁道学院1997三、5（3分）】【国防科技大学1999-]

25.已知：s='（xyz）+*',t='（x+z）*y'。试运用联结、求子串和置换等基本运算，将s转化

为tO

【北方交通大学1996—、3（5分）】【山东科技大学一、6（5分）】

第五部分、算法设计

1.设s、t为两个字符串，分别放在两个一维数组中，m、n分别为其长度，判断t与否为s的子串。假如

是，输出子串所在位置（第一种字符），否则输出0。（注：用程序实现）【南京航空航天大学1997九（1（）

分）】

2.输入一种字符串，内有数字和非数字字符，如：ak123x456I7960?302gef4563,将其中持续的数字作为

一种整体，依次寄存到一数组a中，例如123放入a[0],456放入a[1],.....。编程记录其共

有多少个整数，并输出这些数。【上海大学1998一（13分）】

3.以次序存储构造表达半，设计算法。求串S中出现的第一种最长反复子串及其位置并分析算法的时间

复杂度。【东南大学五（15分）】

类似本题的此外论述有:

（1）假如字符串的一种子串（其长度不小于1）的各个字符均相似，则称之为等值子串。试设计一算

法，输入字符串S,以“！”作为结束标志。假如串S中不存在等值子串，则输出信息“无等值子串”，否

则求出（输出）一种长度最大的等值子串。

例如:若S="abcl23abe123!”，则输出“无等值子串"：若S="abceebccadddddaaadd!”，则输出“ddddd”。

【华中科技大学】

4.假设串的存储构造如下所示，编写算法实现串的置换操作。【清华大学1995五（15分）】

TYPEstrtp=RECORD

ch:ARRAY[1..maxlen]OFchar;

curlen:0..maxlen

END;

5.函数voidinsert（char*s,char*l,intpos）将字符串l插入到字符串s中，插入位置为pos4请用c

语言实现该函数。假设分派给字符串s的空间足够让字符用t插入。（阐明：不得使用任何库函数）

【北京航空航天大学六（10分）】

6.设计一种二分检索的郛法，在一组字符串中找出给定的字符串，假设所有字符串的长度为4。

（I）简述算法的重要思想：（3分）

（2）用PASCAL语言分别对算法中用到的类型和变量作出阐明：（3分）

（3）用类PASCAL语言或自然语言写算法的非递归过程；（8分）

（4）分析该算法的最大检索长度：（3分）

（5）必要处加上中文注释。（3分）

【山东工业大学1995八（2（）分）】

7.设计一PASCAL或C语言的函数atoi（x）.其中X为字符串，由0—9十个数字符和表达正负数的'-'构成，

返回值为整型数值。【浙江大学1994二（7分）】

8.已知字符串S1中寄存一段英文，写出算法format（sl,s2,s3,n）,将其按给定的长度n格式化成两端对

齐的字符串S2,其多出的字符送S3。【首都经贸大学1998三、8（15分）】

9.串以静态存储构造存储，构造如下所述，试实现串操作equal算法.

CONSTmaxlen二串被确认的最大长度

TYPEstrtp=RECORI）

ch:ARRAY[1..maxlen]OFchar;

curlen:0..maxlen

END;

（以一维数组寄存串值，并设指示器curlen指示目前串长）【北京轻工业大学1998一（12分）】

10.编写程序，记录在输入字符串中各个不一样字符出现的频度并珞成果存入文献（字符串中的合法字符

为A-Z这26个字母和0-9这10个数字）。【西北大学四（10分）】

11.写一种递归算法来实现字符串逆序存储，规定不另设申存储空间。【西南交通大学三、2】

12.已知三个字符串分别为s='ab…abcaabcbca…a',s'='caab',s''='bcb\运用所学字符串基

本运算的函数得到成果串为：s'"='caabcbca-aca-a,,规定写出得到上成果串S'''所用的函数及执

行算法。【东北大学1998—、1（10分）】

13.S="S1S2…Sn”是一种长为N的字符串，寄存在一种数组中，编程序将S改造之后输出：

（1）将S的所有第偶数个字符按照其本来的下标从大到小的次序放在S的后半部分：

（2）将S的所有第奇数个字符按照其本来的下标从小到大的次序放在S的前半部分：

例如：

S=*ABCDEFGHIJK1/

则改造后的S为'ACEGIKLJHFDB'。【中科院计算所1995]

14.编一程序，对输入的一体现式（字符串），输出其TOKEN表达。体现式由变量A,B,C,常数（数字）

0,1,…，9,运算符+,*和括号构成。首先定义符号的类码：

符号变量常量*+()

类码012345

另一方面定义符号的TOKEN表达:

其中NAMEL是变量名表（不容许有相似名），CONST是常量表（不容许有相似数）。

例如,假设有体现式（A+A*2）例*B*3#,则将生成如下TOKENL：

【吉林大学1995—(20分)】

第四章串

一、选择题

l.B2.E3.C4.A5.C6.A7.ID7.2F8.B注9.D10.B

注：子串的定义是：串中任意个持续的字符陶成的子序列，并规定空串是任意串的子串，任意串是

其自身的子串。若字符串长度为n(n>0),长为n的子串有1个，长为n-1的子串有2个，长为n-2的子

串有3个，……，长为1的子串有n个。由于空串是任何串的子申，因此木题的答案为：8*(8+1)/2+1=370

故选B。但某些教科书上认为“空串是任意串的子串”无意义，因此认为选C。为防止考试中的二道性，编

者认为第9题出得好。

二、判断题

1.J2.J3.J

三.填空题

1.(1)由空格字符(ASCII值32)所构成的字符串(2)空格个数2.字符

3任意个持续的字符构成的子序

列4.55.0(m+n)

6.011223127.010104218.(1)模式匹配(2)模式串

9.(1)其数据元素都是字符(2)次序存储(3)和链式存储(4)串的长度相等且两串中对应位置的字符也相等

10.两串的长度相等且两串中对应位置的字符也相等。

11.'xyxyxywwy>12.*s++=*l++或(*s++=*l++)!='\0'

13.(1)chars[](2)j++(3)i>=j

14.[题目分析]本题算法采用次序存储构造求串s和串t的最大公共子串。串s用i指针(l<=i〈=s.len)。

t串用j指针(l<="=t.len)o免法思想是对每个i(l<=i<=s.len,即程序中第一种WHILE循环)，来

求从i开始的持续字符串与从jlen,即程序中第二个WEILE循环)开始的持续字符串的最大匹

配。程序中第三个(即最内层)的WHILE循环，是当s中某字符(s[i])与(中某字符(t[j])相等

时，求出局部公共子串。若该子串长度不小于己求出的最长公共子串(初始为0),则最长公共子串的长

度要修改。

程序(a)：(1)(i+k<=s.len)AND(j+k<=t.len)AND(s[i+k]=t[j+k])

〃假如在s和t的长度内，对应字符相等，则指针k后移(加1)。

(2)con:=false//s和t对应字符不等时置标识退出

(3)j:=j+k〃在t串中，从第j+k字符再与s[i]比较

(4)j:=j+l//t串取F一字符

(5)i：=i+l//s串指针i后移(加1)0

程序(b)：(1)i+k<=s.len&&j+k<=t.len&&s(i+k]==t[j+k]〃所有注释同上(a)

(2)con=0(3)j+=k(4)j++(5)i++

15.(1)0(2)next[k]

16.(1)i：=i+l(2)j:=j+l(3)i:=i-j+2(4)j:=l;(5)i-ml(或i:=i-」+l)(6)0

17.程序中递归调用

(1)chlOmidch〃当读入不是分隔符&和输入结束符$时，继续读入字符

(2)chl=ch2〃读入分隔符&后，判chi与否等于ch2,得出真假结论。

(3)answer：=true

(4)answer：=false

(5)read(ch)

(6)ch=endch

18.(1)initstack(s)//栈s初始化为空栈。

(2)setnul1(exp)〃串exp初始化为空串。

(3)chinopset〃判取出字符与否是操作符。

(4)push(s,ch)〃如ch是运算符，则入运算符栈

(5)sempty(s)〃判栈s与否为空。

(6)succ:=false〃若读出ch是操作数且栈为空，则按出错处理。

(7)exp(8)ch〃若ch是操作数且栈非空，则形成部分口缀体现

式。

(9)exp(10)gettop(s)〃取栈顶操作符。

(11)pop(s)〃操作符取出后，退栈。

(12)sempty(s)〃将pre的最终一种字符(操作数)加入到中缀式exp的最终。

四.应用题

1.串是零个至多种字符构成的有限序列。从数据构造角度讲，串属于线性构造。与线性表的特殊性在

于串的元素是字符。

2.空格是一种字符，其ASCII码值是32。空格串是由空格构成的串，其长度等于空格的个数。空串是

不含任何字符的串，即空串的长度是零。

3.最优的T(m,n)是0(n)。串S2是串S1的子串，且在S1中的位置是1。开始求出最大公共子串的

长度恰是串S2的长度，一般状况下，T(m,n)=0(m*n)o

4.朴素的模式匹配(Brute-Force)时间复杂度是O(m*n),KMP算法有一定改善，时间复杂度到

达0(m+n)o本题也可采用从背面匹配的措施，即从右向左扫描，比较6次成功。另一种匹配方式是从

左往右扫描，不过先比较模式串的最终一种字符，若不等，则模式事后移；若相等，再比较模式图的第一

种字符，若第一种字符也相等，则从模式串的第二个字符开始，向右比较，直至相等或失败。若矢败，模

式串后移，再反复以上过程。按这种措施，本题比较18次成功。

5.KMP算法重要长处是主串指针不回溯。当主串很大不能一次读入内存且常常发生部分匹配时，KMP

算法的长处更为突出.

6.模式串的next函数定义如下:

next[j]=

根据此定义，可求解模式串t的next和nextval值如下:

j123456789101112

1串abcaabbabcab

nexlfj]011122312345

nextval(j]011021301105

7.解法同上题6.其next和nextval值分别为和010422.

8.解法同题6,t串的next和nextval函数值分别为0111232和0110132。

9.解法同题6,其next和nextval值分别为和01101301。

10.pl的next和ncxlval值分别为：0112234和0102102；p2的ncxl和ncxlval值分别为：0121123和

0021002o

11.next数组值为改善后的next数组信息值为。

12.o

13.next定义见题上面6和下面题2。。串p的next函数值为：。

14.(1)S的next与nextval值分别为和0000,p的next与nextval值分别为012123和00。

(2)运用BF算法的匹配过程:运用KMP算法的匹配过程:

第一趟匹配：aabaabaabaac第一趟匹配:aabaabaabaac

aabaac(i=6,j=6)

aabaac(i=6,j=6)

第二趟匹配：aabaabaabaac第二趟匹配:aabaabaabaac

aa(i=3,j=2)

(aa)baac

第三趟匹配：aabaabaabaac第三趟匹配:aabaabaabaac

a(i=3,j=l)(成功)

(aa)baac

第四趟匹配：aabaabaabaac

aabaac(i=9,j=6)

第五趟匹配：aabaabaabaac

aa(i=6,j=2)

第六趟匹配：aabaabaabaac

a(i=6,j=l)

第七趟匹配：aabaabaabaac

(成功)aabaac(i=13,j=7)

15.(Dp的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=l)

第四趟匹配：abcaabbabcabaacbacba

(成功)abcabaa(i=15,j=8)

16.KMP算法的时间复杂性是0(m+n)。

p的next和nextval值分别为和0110220。

17.(I)p的nextval函数值为01010。(next函数值为01123)

(2)运用所得nextval数值，手工模拟对s的匹配过程，与上面16题类似，为节省篇幅，故略

去。

18.模式串T的next和nextval值分别为0121123和0021002c

19.第4行的p[J]=p[K]语句是测试模式串的第J个字符与否等于第K个字符，如是，则指针J和K均增

长1,继续比较。第6行的p[J]=p[K]语句的意义是，当第J个字符在模式匹配中失配时，若第K人字符和

第J个字符不等，则下个与主串匹配的字符是第K个字符；否则，若第K个字符和第J个字符相等，则下

个与主串匹配的字符是第K个字符失配时的下一种(即NEXTVAL[K])。

该算法在最坏状况下的时间复杂度0(m，)。

20.(1)当模式串中第一