串

1

数据结构练习第四章串

一保密心得体会 、选择题

1．函数substr(“DATASTRUCTURE”，5，9)的返回值为（）。

A.“STRUCTURE”B.“DATA”

C.“ASTRUCTUR”D.“DATASTRUCTURE”

2．字符串的长度是指（）。

A.串中不同字符的个数B.串中不同字母的个数

C.串中所含字符的个数D.串中不同数字的个数

3．两个字符串相等的充要条件是（）。

A.两个字符串的长度相等B.两个字符串中对应位置上的字符相等

C.同时具备(A)和(B)两个条件D.以上答案都不对

4．关于串的叙述中，正确的是（）

A．空串是只含有零个字符的串

B.空串是只含有空格字符的串

C.空串是含有零个字符或含有空格字符的串

D.串是含有一个或多个字符的有穷序列

5．下面关于串的的叙述中，哪一个是不正确的？（）

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

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

存储

6．设有两个串S1和S2，求S2在S1中首次出现的位置的运算称作()

A．求子串B.判断是否相等C．模型匹配D.连接

7．若串S=’software’,其子串的数目是()。

A．8B．37C．36D．9

8．串的长度是指（）

A．串中所含不同字母的个数B．串中所含字符的个数

C．串中所含不同字符的个数D．串中所含非空格字符的个数

9．串是一种特殊的线性表，其特殊性体现在()。

A．数据元素是一个字符B.可以顺序存储

C.数据元素可以是多个字符D.可以链接存储

10．下面关于串的的叙述中，哪一个是不正确的（B）

A.串是字符的有限序列

B.空串是由空格构成的串

C.模式匹配是串的一种重要运算

D.串既可以采用顺序存储，也可以采用链式存储

11．若串＝‘software’，其非平凡子串（非空且不同于串本身）的数目是（C）

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

12．串是一种特殊的线性表，其特殊性体现在（B）

A.可以顺序存储B.数组元素是一个字符

C.可以连续存储D.数据元素可以是多个字符

13.下面关于串的的叙述中，哪一个是不正确的？（B）

2

A．串是字符的有限序列

B．空串是由空格构成的串

C．模式匹配是串的一种重要运算

D．串既可以采用顺序存储，也可以采用链式存储

二、填空题

1．两个串是相等的，当且仅当两个串的长度相等且___对应位置_____的字符都

相同。

2．串是一种特殊的线性表，串常见的存储结构有顺序存储和_____链式存储_两

种方式。

3．空格串是指_______，其长度等于_______。(1)由空格字符（ASCII值32）

所组成的字符串(2)空格个数

4．一个字符串中________称为该串的子串。任意个连续的字符组成的子序列

5．字符串’ababaaab’的nextval函数值为___小鸡英文 _____。01010421

6．串是一种特殊的线性表，其特殊性表现在__(1)__；串的两种最基本的存储方

式是__(2)__、__(3)__；两个串相等的充分必要条件是__(4)__。(1)其数据元素

都是字符

(2)顺序存储

(3)和链式存储

(4)串的长度相等且两串中对应位置的字符也相等

7．下列程序读入无符号16进制数（出现的字母为小写），将其转换为十进制数

输出。请将程序空缺部分补全。

intf(char*s)

｛intn=0,i;

for(i=0;s［i］!=’0’;i++)n=n*16+(1);

returnn;

｝

main()

｛chars[10];

scanf(“%s”,s);printf(“%汉代礼仪 dn”,(2));

｝

(1)(s[i]>=97?s[i]-87:s[i]-48)∥‘a’到’f’的ASCII码是97到102

(2)f(s)

8．下列算法实现求采用顺序结构存储的串s和串t的一个最长公共子串。

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

{inti,j,k,length1,con;

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

while(i<=)

{j=1;

while(j<=)

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

{k=1;length1=1;con=1;

while(con)

if(1)_{length1=length1+1;k=k+1;}el(2)__;

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

3

(3)____;

}

el(4)___;

}

(5)__

}}

[题目分析]本题算法采用顺序存储结构求串s和串t的最大公共子串。串s用i

指针（1<=i<=）。t串用j指针（1<=j<=）。算法思想是对每个i

（1<=i<=，即程序中第一个while循环），来求从i开始的连续字符串与

从j（1<=j<=，即程序中第二个while循环）开始的连续字符串的最大匹

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

字符(t[j])相等时，求出局部公共子串。若该子串长度大于已求出的最长公共子

串（初始为０），则最长公共子串的长度要修改。

(1)i+k<=&&j+k<=&&s[i+k]==t[j+k]

∥如果在s和t的长度内，对应字符相等，则指针k后移（加1）

（2）con=0∥s和t对应字符不等时置标记退出

（3）j=j+k∥在t串中，从第j+k字符再与s[i]比较

（4）j=j+1∥t串取下一字符

(5)i=i+1∥s串指针i后移（加1）。

9．试利用下列栈和串的基本操作完成下述填空题。

initstack(s)置s为空栈；

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

pop(s)出栈操作;

gettop(s)返回栈顶元素；

mpty(s)判栈空函数；

tnull(st)置串st为空串；

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

equal(s1,s2)判串s1和s2是否相等的函数；

concat(s1,s2)返回联接s1和s2之后的串；

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

empty(st)判串空函数

FUNCinvert(pre:string;VARexp:string):boolean;

{若给定的表达式的前缀式pre正确，本过程求得和它相应的表达式exp并返回

“true”，否则exp为空串，并返回“fal”。已知原表达式中不包含括弧，

opt为运算符的集合。}

VARs:stack;i,n:integ决战东北 er;succ:boolean;ch:char;

BEGIN

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

(1)__;(2)__;

WHILE(i

BEGINch:=sub（pre,i,l）;

IF(3)_THEN(4)__

ELSEIF(5)__THEN(6)_

ELSEBEGIN

4

exp:=concat((7)___,(8)____);

exp:=concat((9)___,(10)___);

(11)__;

END;

i:=i+1

END;

IF(12)___THEN

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

ELSEBEGINtnull(exp);invert:=falEND

END;

注意：每个空格只填一个语句。

（1）initstack（s）∥栈s初始化为空栈

(2)tnull(exp)∥串exp初始化为空串

(3)chinopt∥判取出字符是否是操作符

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

(5)mpty(s)∥判栈s是否为空

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

(7)exp

(8)ch∥若ch是操作数且栈非空，则形成部分中缀表达式

(9)exp

(10)gettop(s)∥取栈顶操作符

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

(12)mpty(s)∥将pre的最后一个字符（操作数）加入到中缀式exp

的最后

三、判断题

1．()子串“ABC”在主串“AABCABCD”中的位置为2。T

2．（）KMP算法的特点是在模式匹配时指示主串的指针不会变小。√

3．（）设模式串的长度为m,目标串的长度为n，当n≈m且处理只匹配一次的

模式时，朴素的匹配（即子串定位函数）算法所花的时间代价可能会更为节省。

√

4．（）串是一种数据对象和操作都特殊的线性表。√

5．（）串长度是指串中不同字符的个数。

6．()如果两个串含有相同的字符，则这两个串相等。X

7．（）KMP算法的最大特点是指示主串的指针不回溯。√

四、简答题

1．KMP算法(字符串匹配算法)较Brute(朴素的字符串匹配)算法有哪些改进?

朴素的模式匹配（Brute－Force）时间复杂度是Ｏ(m＊n），KMP算法有一定改

进，时间复杂度达到Ｏ(m＋n）。主要优点是主串指针不回溯。当主串很大不能

一次读入内存且经常发生部分匹配时，KMP算法的优点更为突出。

2．给出字符串‘abacabaaad’在KMP算法中的next和nextval数组。

模式串的next函数定义如下：

5

根据此定义，可求解模式串’abacabaaad’的next和nextval值如下：

3．模式匹配算法是在主串中快速寻找模式的一种有效的方法，如果设主串的长

度为m，模式的长度为n，则在主串中寻找模式的KMP算法的时间复杂性是多少？

如果，某一模式P=’abcaacabaca’，请给出它的NEXT函数值及NEXT函数的修

正值NEXTVAL之值。

KMP算法的时间复杂性是O（m+n）。

p的next和nextval值分别为和。

4．设目标为S=‘abcaabbcaaabababaabca’，模式为P=‘babab’。

（1）手工计算模式P的nextval数组的值；

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

（1）p的nextval函数值为01010。（next函数值为01123）

（2）利用所得nextval数值，手工模拟对s的匹配过程。

5．s是字符数组，s[0]中存放的是该字符串的有效长度，假设s[1..7]中字符串

的内容为“abcabaa”，说明下列程序的功能及执行结果。

#definelen8

intk,n[len]；

chars[len]=“7abcabaa”；

voidunknown3(charT[]）

{inti,j;

i=1;n[1]=0;j=0;

while(i

{if(j==0||T[i]==T[j])

{++i;++j;

if(T[i]!=T[j])n[i]=j;eln[i]=n[j];

}

elj=n[j];

}数学名词

}

main()

j

t串abacabaaad

next[j]

nextval[j]

6

{unknown3(s);for(k=1;k

本程序的功能是求字符串的nextval函数，程序执行结果是0110132。

6．给出KMP算法中失败函数f的定义，并说明利用f进行串模式匹配的规则，

该算法的技术特点是什么？

这里失败函数f，即是通常讲的模式串的next函数，其定义见本章应用题的第5

题。

进行模式匹配时，若主串第i个字符与模式串第j个字符发生失配，主串指针i

不回溯，和主串第i个字符进行比较的是模式串的第next[j]个字符。模式串的

next函数值，只依赖于模式串，和主串无关，可以预先求出。

该算法的技术特点是主串指针i不回溯。在经常发生“部分匹配”和主串很大不

能一次调入内存时，优点特别突出。

7．已知：s='(xyz)+＊'，t='(x+z)*y'。试利用联结、求子串和置换等基本运算，

将s转化为t。【北方交通大学1996一.3（5分）】

题中所给操作的含义如下：

∥：连接函数，将两个串连接成一个串

substr（s,i,j）：取子串函数，从串s的第i个字符开始，取连续j个字符形

成子串

replace（s1,i,j,s2）：置换函数，用s2串替换s1串中从第i个字符开始的连

续j个字符

本题有多种解法，下面是其中的一种：

（1）s1=substr(s,3,1）∥取出字符：‘y’

（2）s2=substr(s,6,1）∥取出字符：‘+’

（3）s3=substr(s,1,5）∥取出子串：‘(xyz)’

（4）s4=substr(s,7,1）∥取出字符：‘*’

（5）s5=replace(s3,3,1,s2）∥形成部分串：‘（x+z）’

（6）s=s5∥s4∥s1∥形成串t即‘（x+z）*y’

8.已知模式串pat=’ADABBADADA’,写出该模式串的next函数值和nextval

值；（4分）

五、应用题

模式串t=’abaabc’，求t的next函数值。

j123456

模式串abaabc

next[j]

【解答】

j123456

模式串abaabc

next[j]011223

7

评分标准：全题4分，错误酌情扣分

六、算法设计题

1．设计在顺序存储结构上实现求子串算法。

voidsubstring(chars[],longstart,longcount,chart[])

{

longi,j,length=strlen(s);

if(start<1||start>length)printf("Thecopypositioniswrong");

elif(start+count-1>length)printf("Toocharacterstobe

copied");

el{for(i=start-1,j=0;i

t[j]='0';}

}

2．设s、t为两个字符串，分别放在两个一维数组中，m、n分别为其长度，判

断t是否为s的子串。如果是，输出子串所在苹果备份在哪里 位置（第一个字符），否则输出0。

（注：用程序实现）

【中科院研究生院2003九(15分)】【南京航空航天大学1997九(10分)】

[题目分析]判断字符串t是否是字符串s的子串，称为串的模式匹配，其基本思

想是对串s和t各设一个指针i和j，i的值域是0..m-n，j的值域是0..n-1。

初始值i和j均为0。模式匹配从s

0

和t

0

开始，若s

0

=t

0

，则i和j指针增加1，

若在某个位置s

i

!=t

j

，则主串指针i回溯到i=i-j+1，j仍从0开始，进行下一

轮的比较，直到匹配成功（j>n-1），返回子串在主串的位置（i-j）。否则，当

i>m-n则为匹配失败。

intindex(chars[],t[],intm,n)

∥字符串s和t用一维数组存储，其长度分别为m和n

∥本算法求字符串t在字符串s中的第一次出现,匹配成功输出t串在s中的位

置,否则输出0

{inti=0,j=0;

while(i<=m-n&&j<=n-1)

if(s[i]==t[j]){i++;j++;}∥对应字符相等，指针后移

el{i=i-j+1;j=0;}∥对应字符不相等，i回溯，j仍为0

if(i<=m-n&&j==n){printf(“t在s串中位置

是%d”,i-n+1);return(i-n+1);}∥匹配成功

elreturn(0);∥匹配失败

}∥算法index结束

main()∥主函数

{chars[],t[];intm,n,i;

scanf(“%d%d”,&m,&n);∥输入两字符串的长度

scanf(“%s”,s);∥输入主串

scanf(“%s”,t);∥输入子串

i=index(s,t,m,n);

}∥程序结束

[程序讨论]因用C语言实现，一维数组的下标从0开始，m-1是主串最后一个字

符的下标，n-1是t串的最后一个字符的下标。若匹配成功，最佳情况是s串下

标0到n-1的字符与t匹配，时间复杂度为O(n）；匹配成功的最差情况是，每

8

次均在t的最后一个字符才失败，直到s串的下标为m-n时成功，其时间复杂度

为O((m-n)*n)，即O(m*n)。失败的情况是s串的第m-n个字符比t串某字符比

较失败，时间复杂度为O(m*n)。之所以串s的指针i最大到m-n，是因为在m-n

之后,所剩串的长度已经小于子串长度n，故不必再去比较。算法中未讨论输入

错误(如s串长度小于t串长度）。

另外，根据子串的定义，返回值i-n+1是子串在主串中的位置，子串在主串中的

下标是i-n。

3．以顺序存储结构表示串，设计算法。求串S中出现的第一个最长重复子串及

其位置并分析算法的时间复杂度。【东南大学2000五（15分）】【西北大学

2002六（15分）】

[题目分析]设以字符数组s表示串，重复子串的含义是由一个或多个连续相等的

字符组成的子串，其长度用max表示，初始长度为0，将每个局部重复子串的长

度与max相比，若比max大，则需要更新max，并用index记住其开始位置。

intLongestString(chars[])

∥串用一维数组s存储,本算法求最长重复子串，返回其长度

{intindex=0,max=0;∥index记最长的串在s串中的开始位置，max记其长度

intlength=1,i=0,start=0;∥length记局部重复子串长度，i为字符数组下标

while(s[i]!=’0’)

if(s[i]==s[i+1]){i++;length++;}

el∥上一个重复子串结束

{if(max

则更新max

i++;start=i;length=1;∥初始化下一重复子串的起始位置和长度

}

printf(“最长重复子串的长度为%d，在串中的位置%dn”，max,index);

return(max);

}∥算法结束

算法的时间复杂度为O(n），每个字符与其后继比较一次。

4．编写程序，统计在输入字符串中各个不同字符出现的频度并将结果存入文件

（字符串中的合法字符为A-Z这26个字母和0-9这10个数字）。【西北大学2000

四(10分)】

［问题分析］由于字母共26个，加上数字符号10个共36个，所以设一长36

的整型数组，前10个分量存放数字字符出现的次数，余下存放字母出现的次数。

从字符串中读出数字字符时，字符的ASCII代码值减去数字字符‘0’的ASCII

代码值，得出其数值(0..9)，字母的ASCII代码值减去字符‘A’的ASCII代码

值加上10，存入其数组的对应下标分量中。遇其它符号不作处理，直至输入字

符串结束。

voidCount（）

∥统计输入字符串中数字字符和字母字符的个数

｛inti，num[36]；

charch；

for（i＝0；i<36；i++）num[i]＝０；∥初始化

while（（ch＝getchar（））!=‘#’）∥‘#’表示输入字符串结束

if（ch>=‘0’&&ch<=‘9’）｛i=ch－48;num[i]++；｝∥数字字符

9

elif（ch>=‘A’&&ch<=‘Z’）｛i=ch-65+10;num[i]++；｝∥字

母字符

for（i=0；i<10；i++）∥输出数字字符的个数

printf（“数字％d的个数＝％dn”，i，num[i]）；

for（i＝10；i<36；i++）∥求出字母字符的个数

printf（“字母字符％c的个数＝％dn”，i＋55，num[i]）；

｝∥算法结束。

5．写出一个递归算法来实现字符串逆序存储。【中科院研究生院2004四(7分)】

[题目分析]实现字符串的逆置并不难，但本题“要求不另设串存储空间”来实现

字符串逆序存储，共同抗疫作文 即第一个输入的字符最后存储，最后输入的字符先存储，使用

递归可容易做到。

voidInvertStore(charA[])

∥字符串逆序存储的递归算法

{charch;

staticinti=0;∥需要使用静态变量

scanf("%c",&ch);

if(ch!='.')∥规定'.'是字符串输入结束标志

{InvertStore(A);

A[i++]=ch;∥字符串逆序存储

}

A[i]='0';∥字符串结尾标记

}∥结束算法InvertStore

6．S=“S

1

S

2

…S

n

”是一个长为N的字符串，存放在一个数组中，编程序将S改造

之后输出：

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

部分；

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

部分；

例如：

S=‘ABCDEFGHIJKL’

则改造后的S为‘ACEGIKLJHFDB’。【中科院计算所1995】

[题目分析]对读入的字符串的第奇数个字符，直接放在数组前面，对第偶数个字

符，先入栈，到读字符串结束，再将栈中字符出栈，送入数组中。限于篇幅，这

里编写算法，未编程序。

voidReArrangeString()

∥对字符串改造，将第偶数个字符放在串的后半部分，第奇数个字符前半部分。

{charch,s[],stk[];∥s和stk是字符数组（表示字符串）和字符

栈

inti=1,j;∥i和j字符串和字符栈指针

while((ch=getchar())!=’#’)s[i++]=ch;∥读入字符串,’#’是字符串结束

标志

s[i]=’0’;∥字符数组中字符串结束标志

i=1;j=1;

while(s[i])∥改造字符串

10

{if(i%2==0)stk[i/2]=s[i];els[j++]=s[i];

i++;

}∥while

i--;i=i/2;∥i先从’0’后退，然后其含义是第偶

数字符的个数

while(i>0)s[j++]=stk[i--]∥将第偶数个字符逆序填入原字符数组

}

7．若x和y是两个采用顺序结构存储的串，编写一个比较两个串是否相等的函

数。

【中国航天科研机构2005六(7分)】

[题目分析]两串相等指长度相等且对应位置的字符相同。以下算法设串采用堆结

构存储。

intStringEqual(STRINGx,STRINGy)

∥本算法判断两个顺序存储的串x和y是否相等，相等返回1，否则返回0

{if(!=)return(0);

p=;q=;

while(p&&q&&*p==*q){p++;q++;}∥对应字符相等，指针后移

if(!p&&!q)return(1);elreturn(0);

}

8．设计一个程序，使输入的句子按如下方式改造之后输出:

(1)单词之间只留一个空格做间隔；

(2)句子结束后必须紧跟句号；

(3)如果把句子的单词从左到右依次编号为1，2，3，…则对于第奇数个

单词，只要直接复制就行了，而对于第偶数个单词，应按反序打印。例如：

输入句子是:thisisasillyprogram;

改造后的输出是:thissiayllisprogram.

【中国科学技术大学1995十六.2(15分)】

#include

voidtransf(char*s)

∥本算法将串s按要求改造

{char*s,sk[];∥sk是栈，存储第偶数个单词

inti,j,k,flag,finished=0;∥flag是单词开始与结束的标记

scanf(“%s”,s);

i=j=k=flag=0;∥k是单词个数，用于标记奇数或偶数单词

while(*s!=’0’&&!finished)

switch(*s)

{ca‘’:while(*s!=’0’&&*s==’’)s++;∥滤去前导空格

if(flag==1)∥单词结束

{if(k%2==0)∥第偶数个单词逆置

while(i>0注册资金多少对公司有什么影响 )s[++j]=sk[i--];

s[++j]=’’;∥用一个空格分割单词

}；

flag=0;s++;break;

ca‘;’:while(s[j]==’’)j--;∥分号为句子结束标志

11

s[++j]=’.’;finished=1;break;∥句子结束后要紧跟句号

default:if(flag==0){flag=1;k++;}∥开始新单词

if(k%2==1)s[++j]=*s++;∥奇数单词直接复制

elsk[++i]=*s++;∥偶数单词进栈

}∥switch

}

main()

{chars[];

scanf(“%s”,s);transf(s);

}

9．试设计一个C算法（或C程序）：用单链表作存储结构，以回车为结束标志，

输入一个任意长度的字符串；然后判断该字符串是否为“回文”（正向读和反向

读时，串值相同的字符串称为“回文”），输出信息“Yes”或“No”；最后删

除字符串并释放全部空间。例如：

若输入“ABCD12321DCBA”是回文，则输出“Yes”;

若输入“ABCD123DCBA”，不是回文，则输出“No”。

要求：定义相关数据类型，不得使用数组（顺序表）作字符串的存诸结构和辅助

存储空间。假定字符串的长度为n,试分析上述算法的时间复杂度。【华中科技

大学2004五(10分)】

[题目分析]利用栈存放字符串的前半部分，将后半部分与栈中弹出元素比较。

intSymmetry(Linkedlisthead,intn)

∥本算法判断数据域为字符且长为n的单链表是否是“回文”，返回1或0

表示成功或失败

{chars[];∥字符栈，容量足够大

p=head->next∥设链表带头结点

inti=0;

while(i<=n/2)∥前一半字符入栈，链表指针后移

{s[i]=p->data;p=p->next;i++;}

if(n%2==1)p=p->next;∥若链表有奇数个结点，则跳过中间结点

while(p)

if(p->data==s[i]){p=p->next;i--;}

elbreak;∥不是回文

if(!p&&i==0)return(1);

elreturn(0);

}