数据结构C语言版第四章 串

第四章串

重点难点

理解"串"类型定义中各基本操作的特点，并能正确利用它们进行串的其它操作；掌握串类型的各种存储表示方法；理解串的两种匹配算法。

典型例题

1、简述下列每对术语的区别：

空串和空白串；串常量和串变量；主串和子串；静态分配的顺序串和动态分配的顺序串；【解】

（1）空串是指不包含任何字符的串，它的长度为零。

空白串是指包含一个或多个空格的串，空格也是字符。

（2）串常量是指在程序中只可引用但不可改变其值的串。

串变量是可以在运行中改变其值的。

（3）主串和子串是相对的，一个串中任意个连续字符组成的串就是这个串的子串，而包含子串的串就称为主串。

（4）静态分配的顺序串是指串的存储空间是确定的，即串值空间的大小是静态的，在编译时刻就被确定。

动态分配的顺序串是在编译时不分配串值空间，在运行过程中用malloc和free等函数根据需要动态地分配和释放字符数组的空间(这个空间长度由分配时确定，也是顺序存储空间)。

2、以HString为存储表示，写一个求子串的算法。

【解】HString 是指以动态分配顺序串为存储表示，其定义为：

typedef struct {

char *ch;

int length;

}HString;

void *substr( HString *sub,HString *s,int pos,int len)

{//用sub返回串s的第pos个字符起长度为len的子串。sub初始时为一空串

//pos的合法位置为0<=pos<=s->length-1

int i;

if (pos<0||pos>s->length-1||len<=0)

Error("parameter error!");//参数不合法，子串为空串

if (s->length

sub->len=s->length-pos;//设置子串的串长

else sub->length=len; //设置子串的串长

sub->ch=(char *)malloc(len*sizeof(char));//为sub->ch申请结点空间

for(i=0;ilength;i++)//将s串中pos位置开始的共sub->length个字符复制到sub串中

sub->ch[i]=s->ch[pos+i];

}

3、若S和T是用结点大小为1的单链表存储的两个串，试设计一个算法找出S中第一个不在T中出现的字符。

【解】

查找过程是这样的，取S中的一个字符(结点)，然后和T中所有的字符一一比较，直到比完仍没有相同的字符时，查找过程结束，否则再取S中下一个字符，重新进行上述过程。算法如下：

链串的结构类型定义:

typedef struct node{

char data;

struct node *next;

}LinkStrNode; //结点类型

typedef LinkStrNode *LinkString; //LinkString为链串类型

LinkString S; //S是链串的头指针

char SearchNoin( LinkString S, LinkString T)

{//查找不在T中出现的字符

LinkStrNode *p,*q;

p=S;

q=T;

while (p)

{ //取S中结点字符

while(q&&p->data!=q->data)//进行字符比较

q=q->next;

if(q==NULL) return p->data;//找到并返回字符值

q=T; //指针恢复串T的开始结点

p=p->next;

}

printf("there's no such character.");

return NULL;｝

习题精选

一、.单项选择题

1.串是一种特殊的线性表，其特殊性体现在（）。

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

C．可以链式存储D．数据元素可以是多个字符若

2．串下面关于串的的叙述中，（）是不正确的？

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

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

3.串的长度是指（）。

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

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

4.设串s1=’ABCDEFG’，s2=’PQRST’，函数con(x,y)返回x和y串的连接串，subs(s, i, j)返回串s的从序号i开始的j个字符组成的子串，len(s)返回串s的长度，则con(subs(s1, 2, len(s2)), subs(s1, len(s2), 2))的结果串是：

Ａ．BCDEF Ｂ．BCDEFG Ｃ．BCPQRST Ｄ．BCDEFEF

二、算法设计

1.编写算法，实现下面函数的功能。函数void insert(char*s,char*t,int pos)将字符串t插入到字符串s中，插入位置为pos。假设分配给字符串s的空间足够让字符串t插入。（说明：不得使用任何库函数）

[题目分析]本题是字符串的插入问题，要求在字符串s的pos位置，插入字符串t。首先应查找字符串s的pos位置，将第pos个字符到字符串s尾的子串向后移动字符串t的长度，然后将字符串t复制到字符串s的第pos位置后。

对插入位置pos要验证其合法性，小于1或大于串s的长度均为非法，因题目假设给字符串s的空间足够大，故对插入不必判溢出。

void insert(char *s,char *t,int pos)

//将字符串t插入字符串s的第pos个位置。

{int i=1,x=0; char *p=s,*q=t; //p，q分别为字符串s和t的工作指针

if(pos<1) {printf(“pos参数位置非法\n”);exit(0);}

while(*p!=’\0’&&i

//若pos小于串s长度，则查到pos位置时，i=pos。

if(*p == '/0') {printf("%d位置大于字符串s的长度",pos);exit(0);}

else //查找字符串的尾

while(*p!= '/0') {p++; i++;} //查到尾时，i为字符‘\0’的下标，p也指向‘\0’。 while(*q!= '\0') {q++; x++; } //查找字符串t的长度x，循环结束时q指向'\0'。 for(j=i;j>=pos ;j--){*(p+x)=*p; p--;}//串s的pos后的子串右移，空出串t的位置。 q--; //指针q回退到串t的最后一个字符

for(j=1;j<=x;j++) *p--=*q--; //将t串插入到s的pos位置上

[算法讨论] 串s的结束标记('\0')也后移了，而串t的结尾标记不应插入到s中。

2.写一个递归算法来实现字符串逆序存储，要求不另设串存储空间。

[题目分析]实现字符串的逆置并不难，但本题“要求不另设串存储空间”来实现字符串逆序存储，即第一个输入的字符最后存储，最后输入的字符先存储，使用递归可容易做到。 void InvertStore(char A[])

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

{ char ch;

static int i = 0;//需要使用静态变量

scanf ("%c",&ch);

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

{InvertStore(A);

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

}

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

}//结束算法InvertStore。

3.写一个算法统计在输入字符串中各个不同字符出现的频度并将结果存入文件（字符串中的合法字符为A-Z这26个字母和0-9这10个数字）。

void Count（）

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

｛int i，num[36]；

char ch；

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

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

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

else if（‘A’<=ch<=‘Z’）｛i=ch-65+10;num[i]++；｝// 字母字符

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

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

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

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

｝// 算法结束。

数据结构课后习题答案第四章

第四章 一、简述下列每对术语的区别： 空串和空白串；串常量和串变量；主串和子串；静态分配的顺序串和动态分配的顺序串；目标串和模式串；有效位移和无效位移。 答： ●空串是指不包含任何字符的串，它的长度为零。 空白串是指包含一个或多个空格的串，空格也是字符。 ●串常量是指在程序中只可引用但不可改变其值的串。 串变量是可以在运行中改变其值的。 ●主串和子串是相对的，一个串中任意个连续字符组成的串就是这个串的子串，而包含子串的串就称为主串。 ●静态分配的顺序串是指串的存储空间是确定的，即串值空间的大小是静态的，在编译时刻就被确定。 动态分配的顺序串是在编译时不分配串值空间，在运行过程中用malloc和free等函数根据需要动态地分配和释放字符数组的空间(这个空间长度由分配时确定，也是顺序存储空间)。 ●目标串和模式串:在串匹配运算过程中，将主串称为目标串，而将需要匹配的子串称为模式串，两者是相对的。 ●有效位移和无效位移：在串定位运算中，模式串从目标的首位开始向右位移，每一次合法位移后如果模式串与目标中相应的字符相同，则这次位移就是有效位移(也就是从此位置开始的匹配成功)，反之，若有不相同的字符存在，则此次位移就是无效位移(也就是从此位置开始的匹配失败)。 二、假设有如下的串说明： char s1[30]="Stocktom,CA", s2[30]="March 5 1999", s3[30], *p; (1)在执行如下的每个语句后p的值是什么? p=stchr(s1,'t'); p=strchr(s2,'9'); p=strchr(s2,'6'); (2)在执行下列语句后，s3的值是什么? strcpy(s3,s1); strcat(s3,","); strcat(s3,s2); (3)调用函数strcmp(s1,s2)的返回值是什么?

数据结构C语言版第四章 串

第四章串 重点难点 理解"串"类型定义中各基本操作的特点，并能正确利用它们进行串的其它操作；掌握串类型的各种存储表示方法；理解串的两种匹配算法。 典型例题 1、简述下列每对术语的区别： 空串和空白串；串常量和串变量；主串和子串；静态分配的顺序串和动态分配的顺序串；【解】 （1）空串是指不包含任何字符的串，它的长度为零。 空白串是指包含一个或多个空格的串，空格也是字符。 （2）串常量是指在程序中只可引用但不可改变其值的串。 串变量是可以在运行中改变其值的。 （3）主串和子串是相对的，一个串中任意个连续字符组成的串就是这个串的子串，而包含子串的串就称为主串。 （4）静态分配的顺序串是指串的存储空间是确定的，即串值空间的大小是静态的，在编译时刻就被确定。 动态分配的顺序串是在编译时不分配串值空间，在运行过程中用malloc和free等函数根据需要动态地分配和释放字符数组的空间(这个空间长度由分配时确定，也是顺序存储空间)。 2、以HString为存储表示，写一个求子串的算法。 【解】HString 是指以动态分配顺序串为存储表示，其定义为： typedef struct { char *ch; int length; }HString; void *substr( HString *sub,HString *s,int pos,int len) {//用sub返回串s的第pos个字符起长度为len的子串。sub初始时为一空串 //pos的合法位置为0<=pos<=s->length-1 int i; if (pos<0||pos>s->length-1||len<=0) Error("parameter error!");//参数不合法，子串为空串 if (s->lengthlen=s->length-pos;//设置子串的串长 else sub->length=len; //设置子串的串长 sub->ch=(char *)malloc(len*sizeof(char));//为sub->ch申请结点空间 for(i=0;ilength;i++)//将s串中pos位置开始的共sub->length个字符复制到sub串中

严蔚敏数据结构c语言版习题集答案第四章串

读书破万卷下笔如有神 《一定能摸到红球吗？》说课稿 林银花 教材说明：一、１、课题：《一定能摸到红球吗？》 ２、本节内容的地位和作用 在现代社会中，人们面临着更多的机会和选择，常常需要在不确定情境中作出合理的决策,概率正是通过对不确定现象和事件发生的可能性的刻画,来为人们更好的制定决策提供依据和建议.本节内容又是 义务教育阶段,唯一培养学生从不确定的角度来观察世界的数学内容,让学生了解可能性是普遍的,有助于他们理解社会,适应生活. ３、教学目标设计： (１)认知目标： （Ａ）经历猜测．实验．收集与分析试验结果等过程 （Ｂ）体会事件的发生的不确定性知道事情发生的可能性有多大。 （２）、能力目标： (Ａ)经历游戏等的活动过程，初步认识确定事件和不确定事件 （Ｂ）在与其它人交流的过程中，能合理清晰地表达自己的思维过程； （３）、情感目标： （Ａ）通过创设游戏情境，让学生主动参与，做“数学实验”，激发学生学习的热情和兴趣，激活学生思维。 （Ｂ）在与他人的合作过程中，增强互相帮助、团结协作的精神。 （Ｃ）体会到在生活中我们可以从确定和不确定两方面分析一件事情. ４、本课重点、难点分析： 学习的重点是初步体验事情发生的确定性和不确定性. 学习的难点是确定事件发生的可能性大小. 学习本节知识应注意猜测,试验,收集与分析实验结果,从中体会事件发生的可能性及大小. 二、教学对象分析： 1、初一学生性格开朗活泼，对新鲜事物特别敏感，且较易接受，因此，教学过程中创设的问题情境应较生动活泼，直观形象，且贴近学生的生活，从而引起学生的有意注意。 2、初一学生的概括能力较弱，推理能力还有待不断发展，所以在教学时，可让学生充分试验, 收集，分析,帮助他们直观形象地感知。

严蔚敏《数据结构(c语言版)习题集》答案第四章串

《一定能摸到红球吗？》说课稿 林银花 一、教材说明： １、课题：《一定能摸到红球吗？》 ２、本节内容的地位和作用 在现代社会中，人们面临着更多的机会和选择，常常需要在不确定情境中作出合理的决策,概率正是通过对不确定现象和事件发生的可能性的刻画,来为人们更好的制定决策提供依据和建议.本节内容又是义务教育阶段,唯一培养学生从不确定的角度来观察世界的数学内容,让学生了解可能性是普遍的,有助于他们理解社会,适应生活. ３、教学目标设计： (１)认知目标： （Ａ）经历猜测．实验．收集与分析试验结果等过程 （Ｂ）体会事件的发生的不确定性知道事情发生的可能性有多大。 （２）、能力目标： (Ａ)经历游戏等的活动过程，初步认识确定事件和不确定事件 （Ｂ）在与其它人交流的过程中，能合理清晰地表达自己的思维过程； （３）、情感目标： （Ａ）通过创设游戏情境，让学生主动参与，做“数学实验”，激发学生学习的热情和兴趣，激活学生思维。 （Ｂ）在与他人的合作过程中，增强互相帮助、团结协作的精神。 （Ｃ）体会到在生活中我们可以从确定和不确定两方面分析一件事情. ４、本课重点、难点分析： 学习的重点是初步体验事情发生的确定性和不确定性. 学习的难点是确定事件发生的可能性大小. 学习本节知识应注意猜测,试验,收集与分析实验结果,从中体会事件发生的可能性及大小. 二、教学对象分析： 1、初一学生性格开朗活泼，对新鲜事物特别敏感，且较易接受，因此，教学过程中创设的问题情境应较生动活泼，直观形象，且贴近学生的生活，从而引起学生的有意注意。 2、初一学生的概括能力较弱，推理能力还有待不断发展，所以在教学时，可让学生充分试验,收集，分析,帮助他们直观形象地感知。 3、初一学生已经具备了一定的学习能力，所以本节课中，应多为学生创造自主学习、

数据结构练习第四章 串

数据结构练习第四章串 一、选择题 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．8 B．37 C．36 D．9 8．串的长度是指（） A．串中所含不同字母的个数 B．串中所含字符的个数 C．串中所含不同字符的个数 D．串中所含非空格字符的个数 9．串是一种特殊的线性表，其特殊性体现在( )。 A．数据元素是一个字符 B. 可以顺序存储 C. 数据元素可以是多个字符 D. 可以链接存储 10．下面关于串的的叙述中，哪一个是不正确的（B） A. 串是字符的有限序列 B. 空串是由空格构成的串 C. 模式匹配是串的一种重要运算 D. 串既可以采用顺序存储，也可以采用链式存储 11．若串＝‘software’，其非平凡子串（非空且不同于串本身）的数目是（C）A. 8 B. 37 C. 35 D. 9 12．串是一种特殊的线性表，其特殊性体现在（B） A. 可以顺序存储 B. 数组元素是一个字符 C. 可以连续存储 D. 数据元素可以是多个字符 13. 下面关于串的的叙述中，哪一个是不正确的？（B）

第四章 串答案52450

第四章串 注：子串的定义是：串中任意个连续的字符组成的子序列，并规定空串 是任意串的子串，任意串是其自身的子串。若字符串长度为n（n>0），长 为n的子串有1个，长为n-1的子串有2个，长为n-2的子串有3个，……， 长为1的子串有n个。由于空串是任何串的子串，所以本题的答案为：8* （8+1）/2+1=37。故选B。但某些教科书上认为“空串是任意串的子串” 无意义，所以认为选C。为避免考试中的二意性，编者认为第9题出得好。 二、判断题 三．填空题 1．(1) 由空格字符（ASCII值32）所组成的字符串 (2)空格个数 2．字符 3．任意个连续的字符组成的子序列4．5 5.O(m+n) 6．01122312 7．01010421 8．(1)模式匹配 (2)模式串 9．(1)其数据元素都是字符(2)顺序存储(3)和链式存储(4)串的长度相等且 两串中对应位置的字符也相等 10．两串的长度相等且两串中对应位置的字符也相等。 11．’xyxyxywwy’ 12．*s++=*t++ 或（*s++=*t++）!=‘\0’ 13．（1）char s[ ] (2) j++ (3) i >= j 14．[题目分析]本题算法采用顺序存储结构求串s和串t的最大公共子串。 串s用i指针（1<=i<=s.len）。t串用j指针（1<=j<=t.len）。算法思想 是对每个i（1<=i<=s.len，即程序中第一个WHILE循环），来求从i开始 的连续字符串与从j（1<=j<=t.len，即程序中第二个ＷHILE循环）开始的 连续字符串的最大匹配。程序中第三个（即最内层）的WHILE循环，是当 s中某字符（s［i］）与t中某字符（t［j］）相等时，求出局部公共子串。 若该子串长度大于已求出的最长公共子串（初始为０），则最长公共子串的 长度要修改。 程序（a）：（1）（i+k<=s.len）AND(j+k<=t.len) AND(s[i+k]=t[j+k]) //如果在s和t的长度内，对应字符相等，则指针k 后 移（加1）。

数据结构 习题 第四章 串 答案

第四章串 任意串是其自身的子串。若字符串长度为n（n>0），长为n的子串有1个，长为n-1的子串有2个，长为n-2的子串有3个，……，长为1的子串有n个。由于空串是任何串的子串，所以本题的答案为：8*（8+1）/2+1=37。故选B。但某些教科书上认为“空串是任意串的子串”无意义，所以认为选C。为避免考试中的二意性，编者认为第9题出得好。 二、判断题 三．填空题 1．(1) 由空格字符（ASCII值32）所组成的字符串 (2)空格个数 2．字符 3．任意个连续的字符组成的子序列 4．5 5.O(m+n) 6． 7． 8．(1)模式匹配 (2)模式串 9．(1)其数据元素都是字符(2)顺序存储(3)和链式存储(4)串的长度相等且两串中对应位置的字符也相等 10．两串的长度相等且两串中对应位置的字符也相等。 11．’xyxyxywwy’ 12．*s++=*t++ 或（*s++=*t++）!=‘\0’ 13．（1）char s[ ] (2) j++ (3) i >= j 14．[题目分析]本题算法采用顺序存储结构求串s和串t的最大公共子串。串s用i指针（1<=i<=s.len）。t串用j指针（1<=j<=t.len）。算法思想是对每个i（1<=i<=s.len，即程序中第一个WHILE循环），来求从i开始的连续字符串与从j（1<=j<=t.len，即程序中第二个ＷHILE循环）开始的连续字符串的最大匹配。程序中第三个（即最内层）的WHILE循环，是当s中某字符（s［i］）与t中某字符（t［j］）相等时，求出局部公共子串。若该子串长度大于已求出的最长公共子串（初始为０），则最长公共子串的长度要修改。 程序（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+1 //t串取下一字符 （5）i：=i+1 //s串指针i后移（加1）。 程序（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+1 （2）j:=j+1 (3)i:=i-j+2 (4)j:=1; (5)i-mt（或i:=i-j+1） (6)0 17.程序中递归调用 （1）ch1<>midch //当读入不是分隔符&和输入结束符$时，继续读入字符 （2）ch1=ch2 //读入分隔符&后，判ch1是否等于ch2，得出真假结论。 （3）answer：=true （4）answer：=false （5）read（ch） （6）ch=endch

目前最完整的数据结构1800题包括完整答案第四章串.

第四章串 一、选择题 1．下面关于串的的叙述中，哪一个是不正确的？（）【北方交通大学 2001 一、5（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))) 其结果为（）【北方交通大学 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．求串长 【北京邮电大学 2000 二、4（20/8分）】【西安电子科技大学 1996 一、1 （2分）】4．已知串S=‘aaab’,其Next数组值为（）。【西安电子科技大学 1996 一、7 （2分）】A．0123 B．1123 C．1231 D．1211 5．串‘ababaaababaa’的next数组为（）。【中山大学 1999 一、7】A．012345678999 B．012121111212 C．011234223456 D．0123012322345 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 ) 【北京邮电大学 1999 一、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 【北京邮电大学 1998 二、3 （2分）】 8．若串S=’software’,其子串的数目是（）。【西安电子科技大学 2001应用一、2（2分）】 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算法的特点是在模式匹配时指示主串的指针不会变小。（）【北京邮电大学 2002 一、4 （1分）】 2．设模式串的长度为m,目标串的长度为n，当n≈m且处理只匹配一次的模式时，朴素的匹

《数据结构》第四章习题参考答案

《数据结构》第四章习题 一、判断题（在正确说法的题后括号中打“√”，错误说法的题后括号中打“×”） 1、KMP算法的特点是在模式匹配时指示主串的指针不会变小。( √) 2、串是一种数据对象和操作都特殊的线性表。( √) 3、只包含空白字符的串称为空串（空白串）。( ×) 4、稀疏矩阵压缩存储后，必会（不会）失去随机存取功能。( ×) 5、使用三元组表示稀疏矩阵的非零元素能节省存储空间。( √) 6、插入与删除操作是数据结构中最基本的两种操作，因此这两种操作在数组中也经常使用。（×） 7、若采用三元组表存储稀疏矩阵，只要把每个元素的行下标和列下标互换（错的），就完成了对该矩阵的转置运算。（×） 二、单项选择题 1．下面关于串的的叙述中，哪一个是不正确的？（ B ） A．串是字符的有限序列B．空串是由空格构成的串（空串是长度为零的串）C．模式匹配是串的一种重要运算D．串既可以采用顺序存储，也可以采用链式存储2．有串S1=’ABCDEFG’，S2 = ’PQRST’，假设函数con(x,y)返回x和y串的连接串，subs(s,i,j)返回串s的从序号i的字符开始的j个字符组成的子串，len(s)返回中s的长度，则con(subs(s1,2,len(s2)),subs(s1,len(s2),2))的结果串是（ D ）。 A．BCDEF B．BCDEFG C．BCPQRST D．CDEFGFG 3、串的长度是指（ B ） A．串中所含不同字母的个数B．串中所含字符的个数 C．串中所含不同字符的个数D．串中所含非空格字符的个数 三、填空题 1、串是一种特殊的线性表，其特殊性表现在_数据元素为字符，操作集也不同__；串的两种最基本的存储方式是_顺序存储_、__ 链式存储_；两个串相等的充分必要条件是__两串的长度相等且两串中对应位置的字符也相等__。 2、设正文串长度为n，模式串长度为m，则串匹配的KMP算法的时间复杂度为_O(m+n)__。 3、模式串P=‘abaabcac’的next函数值序列为_{-1,0,0,1,1,2,0,1}___。 4、已知数组A[0..9,0..9]的每个元素占5个存储单元，将其按行优先次序存储在起始地址为1000的连续的内存单元中，则元素A[6，8]的地址为__1340___。 四、综合题 1、KMP算法较Brute-Force算法有哪些改进? 【解答】 朴素的模式匹配（Brute－Force）时间复杂度是O（m*n），KMP算法有一定改进，时间复杂度达到O（m＋n）。KMP算法主要优点是主串指针不回溯。当主串很大不能一次读入内存且经常发生部分匹配时，KMP算法的优点更为突出。 2、课本P183 4.1题 【解答】 A[2][2] = 644+2*n+2 = 676 A[3][3] = 644+3*n+3 = 692 3、课本P184 4.7题

数据结构(C语言版)习题及答案第四章

习题 4.1选择题 1、空串与空格串是（B）。 A、相同 B、不相同Ｃ、不能确定 2、串是一种特殊的线性表，其特殊性体现在（B）。 A、可以顺序存储 B、数据元素是一个字符 C、可以链式存储 D、数据元素可以是多个字符 3、设有两个串p和q，求q在p中首次出现的位置的操作是（B）。 A、连接 B、模式匹配 C、求子串 D、求串长 4、设串s1=“ABCDEFG”，s2=“PQRST”函数strconcat（s，t）返回s和t串的连接串，strsub（s，i，j）返回串s中从第i个字符开始的、由连续j个字符组成的子串。strlength(s)返回串s的长度。则strconcat（strsub（s1，2，strlength（s2）），strsub（s1，strlength（s2），2））的结果串是（D）。 A、BCDEF B、BCDEFG C、BCPQRST D、BCDEFEF 5、若串s=“software”，其子串个数是（B）。 A、8 B、37 C、36 D、9 4.2简答题 1、简述空串与空格串、主串与子串、串名与串值每对术语的区别？ 答：空串是指长度为0的串，即没有任何字符的串。 空格串是指由一个或多个空格组成的串，长度不为0。 子串是指由串中任意个连续字符组成的子序列，包含子串的串称为主串。 串名是串的一个名称，不指组成串的字符序列。 串值是指组成串的若干个字符序列，即双引号中的内容。 2、两个字符串相等的充要条件是什么？ 答：条件一是两个串的长度必须相等 条件二是串中各个对应位置上的字符都相等。 3、串有哪几种存储结构？ 答：有三种存储结构，分别为：顺序存储、链式存储和索引存储。 4、已知两个串：s1=”fg cdb cabcadr”, s2=”abc”, 试求两个串的长度，判断串s2是否是串s1的子串，并指出串s2在串s1中的位置。 答：（1）串s1的长度为14，串s2的长度为3。 （2）串s2是串s1的子串，在串s2中的位置为9。 5、已知：s1=〃I’m a student〃，s2=〃student〃，s3=〃teacher〃，试求下列各操作的结果： strlength(s1)；答：13 strconcat(s2,s3)；答：”studentteachar” strdelsub(s1,4,10)；答：I’m 6、设s1=”AB”，s2=”ABCD”，s3=”EFGHIJK，试画出它们在各种存储结构下的结构图。答： 顺序存储方式下：

数据结构课后习题第四章

第四章串 习题4 一、选择题 1.串是一种特殊的线性表，其特殊性体现在（）。 A.可以顺序存储 B.数据元素是一个字符 C.可以连接存储 D.数据元素可以是多个字符 2.有两个串P和Q，求P在Q中首次出现的位置的运算称为（）。 A.模式匹配 B.联接 C.求子串 D.求串长 3.设S为一个长度为n的字符串，其中的字符各不相同，则S中的互异的非平凡子串（非空且不同于S本身）的个数为（）。 A.n2 B.（n2/2）+（n/2） C.（n2/2）+（n/2）-1 D.（n2/2）-（n/2）-1 4.设串s1=“ABCDEFG”,s2=“PQRST”，函数concat（x，y）返回x和y串的连接串，subString（s，i，j）返回串s的从序号i的字符开始的j个字符组成的子串，Strlength（s）返回串s的长度，则concat（subString（s1，2，Strlength （s2）），subString(s1，Strlength（s2），2)））的结果串是（）。 A.BCDEF B.BCDEFG C.BCPQRST D.BCDEFEF 5.顺序串中，根据空间分配方式的不同，可分为（）。 A.直接分配和间接分配 B.静态分配和动态分配 C.顺序分配和链式分配 D.随机分配和固定分配 6.设串S=“abcdefgh”，则S的所有非平凡子串（除空串和S自身的串）的个数是（）。

A.8 B.37 C.36 D.35 7.设主串的长度为n，模式串的长度为m，则串匹配的KMP算法时间复杂度是（）。 A.O(m) B.O（n） C.O（m+n） D.O（n*m） 8.已知串S=“aaab”，其next数组值为（）。 A.0123 B.1123 C.1231 D.1211 二丶填空题 1.在空串和空格串中，长度不为0的是（）。 2.空格串是指（），其长度等于（）。 3.按存储结构的不同，串可分为（）、（）和（）。 4.C语言中，以字符（）表示串值的终结。 5.在块链串中，为了提高存储密度，应该增大（）。 6.假设每个字符占1个字节，若结点大小为4个字节的链串的存储密度为50％，则其每个指针占（）个字节。 7.串操作虽然较多，但都可以通过五中基本操作（）、（）、（）、（）和（）构成的最小子集中的操作来实现。 8.设串S=“Ilikecomputer.”，T=“com”，则Length（S）=（），Index（S,T,1）=（）。 9.在KMP算法中，next[j]只与（）串有关，而与（）串无关。 10.字符串“ababaaab”的nextval函数值为（）。 11.两个字符串相等的充分必要条件是（）。 12.实现字符串复制的函数strcpy为：

《数据结构》习题集：第4章 串

第4章串 一、选择题 1.设串s1=’ABCDEFG’，s2=’PQRST’，函数Concat(x,y)返回x 和y 串的连接串，Substr(s,i,j)返回串s 从序号i 开始 的j 个字符组成的子串，length(s)返回串s 的长度，则Concat(Substr(s1,2,length(s2)),Substr(s1,length(s2),2))的结果串是（D ）。 A、BCDEF B、BCDEFG C、BCPQRST D、BCDEFEF 2.空串和空格是相同的。（ B ） A、正确 B、错误 3.若串S1=’ABCDEFG’，S2=’9898’，S3=’###’，S4=’012345，则执行下列语句后，其结果为（E ）。 replace(s1,Substr(s1,4,length(s3)),s3)； Concat(s1,Substr(s4,index(s2,’8’),length(s2))) A、ABC###G0123 B、ABCD###2345 C、ABC###G2345 D、ABC###2345 E、ABC###G1234 F、ABCD###1234 G、ABC###01234 4.串是一种特殊的线性表，其特殊性体现在（D ）。 A、可以顺序存储 B、数据元素是一个字符 C、可以链接存储 D、数据元素可以是多个字符 5.设有两个串p 和q，求q 在p 中首次出现的位置的运算称为（B ）。 A、连接 B、模式匹配 C、求子串 D、求串长 6.下面关于串的的叙述中，哪一个是不正确的？（ B ） A．串是字符的有限序列B．空串是由空格构成的串 C．模式匹配是串的一种重要运算D．串既可以采用顺序存储，也可以采用链式存储 7.串的长度是指（B ） A．串中所含不同字母的个数B．串中所含字符的个数 C．串中所含不同字符的个数D．串中所含非空格字符的个数 二、判断题 1.子串定位函数的时间复杂度在最坏的情况下为O（n*m），因此子串定位函数没有实际利用价值。 2.设有两个串p 和q，其中q 是p 的子串，把q 在p 中首次出现的位置作为子串q 在p 中的位置的算法称为 匹配。√ 3.KMP 算法的最大特点是指示主串的指针不需要回朔。√ 三、填空题 1.设s=’I_AM_A_TEACHER’，其长度为（14 ）。 2.空串是（零个字符的串），其长度为（0 ）。 3.设S1=’GOOD’，S2=’’，S3=’BYE!’，则S1、S2 和S3 连接后的结果是（GOOD BYE!）。 4.两个串相等的充分必要条件是（两个串的长度相等且对应位置字符相同）。 5.串的两种最基本的存储方式是（顺序存储方式和链接存储方式）。 6.空格串是_由空格组成的非空串________，其长度等于串中空格字符的个数_________。

数据结构第四章串习题及答案

习题四串 一、单项选择题 1．下面关于串的的叙述中，哪一个是不正确的？（） A．串是字符的有限序列 B．空串是由空格构成的串 C．模式匹配是串的一种重要运算 D．串既可以采用顺序存储，也可以采用链式存储2．串是一种特殊的线性表，其特殊性体现在（）。 A．可以顺序存储 B．数据元素是一个字符 C．可以链接存储 D．数据元素可以是多个字符 3．串的长度是指（） A．串中所含不同字母的个数 B．串中所含字符的个数 C．串中所含不同字符的个数 D．串中所含非空格字符的个数 4．设有两个串p和q，其中q是p的子串，求q在p中首次出现的位置的算法称为（）A．求子串 B．联接 C．匹配 D．求串长 5．若串S=“software”,其子串的个数是（）。 A．8 B．37 C．36 D．9 二、填空题 1．含零个字符的串称为______串。任何串中所含______的个数称为该串的长度。 2．空格串是指__ __，其长度等于__ __。 3．当且仅当两个串的______相等并且各个对应位置上的字符都______时，这两个串相等。一个串中任意个连续字符组成的序列称为该串的______串，该串称为它所有子串的______串。 4．INDEX（‘DATASTRUCTURE’，‘STR’）=________。 5．模式串P=‘abaabcac’的next函数值序列为________。 6．下列程序判断字符串s 是否对称，对称则返回1，否则返回0；如 f("abba")返回1， f("abab")返回0； int f((1)__ ______) {int i=0,j=0; while (s[j])(2)___ _____; for(j--; i