第四章串习题_数据结构

习题四串

一、单项选择题

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

return((3)___ ____)

}

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

void maxcomstr(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) __

} }

三、应用题

1．描述以下概念的区别：空格串与空串。

2．设有 A=””,B="mule"，C="old"，D="my",试计算下列运算的结果(注:A+B是CONCAT （A,B）的简写,A=" "的 " "含有两个空格)。

(a) A+B

(b) B+A

(c) D+C+B

(d) SUBSTR(B,3,2)

(e) SUBSTR(C,1,0)

(f) LENGTH(A)

(g) LENGTH(D)

(h) INDEX(B,D)

(i) INDEX(C,"d")

(j) INSERT(D,2,C)

(k) INSERT(B,1,A)

(l) DELETE(B,2,2)

(m) DELETE(B,2,0)

3．设主串S=‘xxyxxxyxxxxyxyx’，模式串T=‘xxyxy’。请问：如何用最少的比较次数找到T在S中出现的位置？相应的比较次数是多少？

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

5．已知：s ＝“（xyz）＋＊”，t ＝“（x＋z）＊y”。试利用联结、求子串和置换等基本运算，将 s 转化为 t 。

四、算法设计题

1．在顺序串上实现串的判等运算EQUAL(S,T)。

2．在链串上实现判等运算EQUAL(S,T)。

3．若S和T是用结点大小为1的单链表存储的两个串（S、T为头指针），设计一个算法将串S中首次与串T匹配的子串逆值。

4．以顺序存储结构表示串，设计算法。求串S中出现的第一个最长重复子串及其位置并分析算法的时间复杂度。（如果字符串的一个子串（其长度大于1）的各个字符均相同，则称之为等值子串。如果输入字符串S，以“！”作为结束标志。串S中不存在等值子串，则输出信息“无等值子串”，否则求出（输出）一个长度最大的等值子串。例如：若S=“abc123abc123!”，则输出“无等值子串”；若S=“abceebccadddddaaadd!”，则输出“ddddd”。）

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

第四章串

一、单项选择题

1．B

2. B

3．B

4．C

5. C

二、填空题

1．空、字符

2．由空格字符（ASCII值32）所组成的字符串空格个数

3．长度、相等、子、主

4．5

5．

6．（1）char s[ ] (2) j++ (3) i >= j

7．[题目分析]本题算法采用顺序存储结构求串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］）相等时，求出局部公共子串。若该子串长度大于已求出的最长公共子串（初始为０），则最长公共子串的长度要修改。

(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++

三、应用题

1．空格是一个字符，其ASCII码值是32。空格串是由空格组成的串，其长度等于空格的个数。空串是不含任何字符的串，即空串的长度是零。

2．(a)A+B “ mule”

(b)B+A “mule ”

(c)D+C+B “myoldmule”

(d)SUBSTR(B,3,2) “le”

(e)SUBSTR(C,1,0) “”

(f)LENGTH(A) 2

(g)LENGTH(D) 2

(h)INDEX(B,D) 0

(i)INDEX(C,”d”) 3

(j)INSERT(D,2,C) “myold”

(k)INSERT(B,1,A) “m ule”

(l)DELETE(B,2,2) “me”

(m)DELETE(B,2,0) “mule”

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

复杂度达到Ｏ（m＋n）。本题也可采用从后面匹配的方法，即从右向左扫描，比较６次成功。另一种匹配方式是从左往右扫描，但是先比较模式串的最后一个字符，若不等，则模式串后移；若相等，再比较模式串的第一个字符，若第一个字符也相等，则从模式串的第二个字符开始，向右比较，直至相等或失败。若失败，模式串后移，再重复以上过程。按这种方法，本题比较18次成功。

4．next和nextval值分别为和。

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’

四、算法设计题

1．const maxlen=串的最大长度;

typedef struct

{char ch [maxlen];

int curlen;

} string;

int EQUAL_string(string s,string t )

{ if (s.curlen!=t.curlen) return(0);

for (t=0; t

if (s.ch[t]!=t.ch[t] ) return(0);

return(1);

}

2．设单链表无头结点

const nodesize =用户定义的结点大小；

typedef struct node *pointer;

struct node

{char ch;

pointer next;

}

typedef pointer strlist;

int EQULA_strlist(strlist s ,strlist t )

{ while ((s!= null )&&(t!=null)&&(s->ch==t->ch))

{s=s->next;t=t->next;}

return((t= = null)&&(s= =null));

}

3．分析：首先判断串T是否为串S的子串，若串T是串S的子串对S中该子串逆置。

Int NZ_strlist (strlist s,strlist t)

{p=s->next;t=t->next;q=s;

while(p!=null)

{pp =p ; tt =t; /*判断串T是否为串S的子串*/

while ((tt!=null)&&(pp!=null)&&(pp->ch= =tt->ch))

{pp=pp->next;tt=tt->next;}

if (tt==null) /*串T是串S的子串对S中的该子串的位置*/

{qq=q->next; /* q是子串的第一个结点前趋pp是子串最后一个结点后继*/

while(qq!=pp)

{g=qq; qq= qq->next;

q->next =pp; pp=g;

}

q->next=pp; /*将该子串的前趋与逆置后的子串的相连*/

return(1);/*找到并逆置返1 */

}else {q=p;p=p->next;}

}

return(0);/*找不到匹配的串返0*/

}

4．[题目分析]设以字符数组s表示串，重复子串的含义是由一个或多个连续相等的字符组成的子串，其长度用max表示，初始长度为0，将每个局部重复子串的长度与max相比，若比max大，则需要更新max，并用index记住其开始位置。

int LongestString(char s[],int n)

//串用一维数组s存储，长度为n，本算法求最长重复子串，返回其长度。

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

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

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

else //上一个重复子串结束

{if(max

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

}

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

return(max);

}//算法结束

[算法讨论]算法中用i

即最后一个字符。子串长度的初值数为1，表示一个字符自然等于其身。

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

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

void InvertStore(char A[])

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

{ char ch;

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

scanf ("%c",&ch);

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

{InvertStore(A);

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

}

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

}//结束算法InvertStore。

数据结构第四章考试题库(含答案)

第四章串 一、选择题 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．0 B．012121111212 C．0 D．0 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分）】

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

第四章 一、简述下列每对术语的区别： 空串和空白串；串常量和串变量；主串和子串；静态分配的顺序串和动态分配的顺序串；目标串和模式串；有效位移和无效位移。 答： ●空串是指不包含任何字符的串，它的长度为零。 空白串是指包含一个或多个空格的串，空格也是字符。 ●串常量是指在程序中只可引用但不可改变其值的串。 串变量是可以在运行中改变其值的。 ●主串和子串是相对的，一个串中任意个连续字符组成的串就是这个串的子串，而包含子串的串就称为主串。 ●静态分配的顺序串是指串的存储空间是确定的，即串值空间的大小是静态的，在编译时刻就被确定。 动态分配的顺序串是在编译时不分配串值空间，在运行过程中用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)的返回值是什么?

数据结构练习第四章 串

数据结构练习第四章串 一、选择题 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）

数据结构课后习题及解析第四章

第四章习题 1. 设s=’I AM A STUDENT’,t=’GOOD’,q=’WORKER’。给出下列操作的结果： StrLength(s); SubString(sub1,s,1,7); SubString(sub2,s,7,1); StrIndex(s,’A’,4);StrReplace(s,’STUDENT’,q); StrCat(StrCat(sub1,t), StrCat(sub2,q)); 2. 编写算法，实现串的基本操作StrReplace(S,T,V)。 3. 假设以块链结构表示串，块的大小为1，且附设头结点。 试编写算法，实现串的下列基本操作： StrAsign(S,chars)； StrCopy(S,T)； StrCompare(S,T)； StrLength(S)； StrCat(S,T)； SubString(Sub,S,pos,len)。 4．叙述以下每对术语的区别：空串和空格串；串变量和串常量；主串和子串；串变量的名字和串变量的值。 5．已知：S=”(xyz)*”,T=”(x+z)*y”。试利用联接、求子串和置换等操作，将S转换为T. 6．S和T是用结点大小为1的单链表存储的两个串，设计一个算法将串S中首次与T匹配的子串逆置。 7．S是用结点大小为4的单链表存储的串,分别编写算法在第k个字符后插入串T，及从第k个字符删除len个字符。 以下算法用定长顺序串： 8．编写下列算法： （1）将顺序串r中所有值为ch1的字符换成ch2的字符。

（2）将顺序串r中所有字符按照相反的次序仍存放在r中。 （3）从顺序串r中删除其值等于ch的所有字符。 （4）从顺序串r1中第index 个字符起求出首次与串r2相同的子串的起始位置。 （5）从顺序串r中删除所有与串r1相同的子串。 9．写一个函数将顺序串s1中的第i个字符到第j个字符之间的字符用s2串替换。 10．写算法，实现顺序串的基本操作StrCompare(s,t)。 11．写算法，实现顺序串的基本操作StrReplace(&s,t,v)。 实习题 1．已知串S和T，试以以下两种方式编写算法，求得所有包含在S中而不包含在T中的字符构成的新串R，以及新串R中每个字符在串S中第一次出现的位置。 （1）利用CONCAT、LEN、SUB和EQUAL四种基本运算来实现。 （2）以顺序串作为存储结构来实现。 2．编写一个行编辑程序EDLINE，完成以下功能： （1）显示若干行：list [[n1]-[n2]]：显示第n1行到第n2行，n1缺省时，从第一行开始，n2缺省时，到最后一行， （2）删除若干行。del [[n1]-[n2]]： n1、n2说明同（1）。 （3）编辑第n行。edit n：显示第n行的内容，另输入一行替换该行。 （4）插入一行。ins n：在第n行之前插入一行。

第四章串习题_数据结构

习题四串 一、单项选择题 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

第4章习题答案

习题4 1.名词解释：串、空串、空格串、子串。 解：串是有限的字符序列，从数据结构角度讲，串属于线性结构。与线性表的不同之处在于串的元素是字符。 空串是不含任何字符的串，其长度为0。 空格是一个字符，其ASCII 码值是32。空格串是由空格组成的串，其长度等于空格的个数。 串中任意连续的若干字符组成的子序列称为该串的子串。 2.已知三个字符串分别为”“a abcaabcbca ab S =，”“caab S ='，”“bcb S =" 。利用串的基本 运算得到结果串为”“a aca caabcbca S ='" ，要求写出得到结果串3S 所用的函数及执行算法。 解：串'" S 可看作由以下两部分组成：”“a caabcbca 和”“a ca ，设这两部分分别叫串s1和s2， 要设法从S 、'S 、"S 中得到这两部分，然后使用连接操作连接s1和s2得到'" S 。 i=index();// s1=substr(S ,i,length(S )-i+1);//取出串s1 j=index(S ,"S );//求串" S 在串S 中的起始位置，S 串中”“bcb 后是”“a ca s2=substr(S ,j+3,length(S )-j-2);//形成串s2 '"S =concat(s1,s2); 3.已知字符串1S 中存放一段英文，写出算法),3,2,1(n S S S format ，将其按给定的长度n 格式化成两端对齐的字符串2S ，其多余的字符存入3S 。 解：题目要求将字符串S1拆分成字符串S2和S3，要求字符串S2“按给定长度n 格式化为两端对齐的字符串”，即长度为n 且首尾字符不能为空格字符。算法从左到右扫描字符串S1，找到第一个非空格字符，计数到n ，第n 个拷入字符串S2的字符不能为空格，然后将余下字符复制到字符串S3中。 void format(char *S1,char *S2,char *S3,int n){ char *p=S1,*q=S2; int i=0; while(*p!= '\0'&&*p==' ')p++;//滤掉S1左端空格 if(*p== '\0'){printf("字符串S1为空串或空格串\n");exit(0);} while(*p!= '\0'&&i

《数据结构与算法》第四章-串习题

《数据结构与算法》第二部分习题精选 一、填空题 1. 称为空串； 称为空白串。 2. 设S=“A;/document/Mary.doc”，则strlen(s)= , “/”的字符定位的位置为。 3. 子串的定位运算称为串的模式匹配，称为目标串，称为模式。 4. 设目标T=”abccdcdccbaa”，模式P=“cdcc”，则第次匹配成功。 5. 若n为主串长，m为子串长，则串的古典（朴素）匹配算法最坏的情况下需要比较字符的总次数为。 二、单选题 （）1. 串是一种特殊的线性表，其特殊性体现在： Ａ．可以顺序存储Ｂ．数据元素是一个字符 Ｃ．可以链式存储Ｄ．数据元素可以是多个字符 （）2.设有两个串p和q，求q在p中首次出现的位置的运算称作：Ａ．连接Ｂ．模式匹配Ｃ．求子串Ｄ．求串长（）3.设串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.设s=’I AM A STUDENT’, t=’GOOD’, q=’WORKER’, 求 Replac e(s,’STUDENT’,q)和 Concat(SubString(s,6,2), Concat(t,SubString(s,7,8)))。 2.已知主串 3.s=’ADBADABBAABADABBADADA’,模式串 pat=’ADABBADADA’。写出模式串的nextval函数值，并由此画出KMP算法匹配的全过程。 答案 一、填空题 1. 不包含任何字符（长度为0）的串由一个或多个空格（仅由空格符）组成的串 2. 20 3 3.被匹配的主串子串 4. 6 5. (n-m+1)*m 二、单选题 1. B 2. B 3. D 四、计算题 解：①Replace(s,’STUDENT’,q)＝’I AM A WORKER’ ②因为SubString(s,6,2)＝‘A ’；SubString(s,7,8)＝‘STUDENT’

《数据结构(C语言版 第2版)》(严蔚敏 著)第四章练习题答案

《数据结构（C语言版第2版）》（严蔚敏著） 第四章练习题答案 第4章串、数组和广义表 1．选择题 （1）串是一种特殊的线性表，其特殊性体现在（）。 A．可以顺序存储B．数据元素是一个字符 C．可以链式存储D．数据元素可以是多个字符若 答案：B （2）串下面关于串的的叙述中，（）是不正确的？ A．串是字符的有限序列B．空串是由空格构成的串 C．模式匹配是串的一种重要运算D．串既可以采用顺序存储，也可以采用链式存储 答案：B 解释：空格常常是串的字符集合中的一个元素，有一个或多个空格组成的串成为空格串， 零个字符的串成为空串，其长度为零。 （3）串“ababaaababaa”的next数组为（）。 A．012345678999 B．012121111212 C．011234223456 D．0123012322345 答案：C （4）串“ababaabab”的nextval为（）。 A．010104101B．010102101 C．010100011 D．010101011 答案：A （5）串的长度是指（）。 A．串中所含不同字母的个数B．串中所含字符的个数 C．串中所含不同字符的个数D．串中所含非空格字符的个数 答案：B 解释：串中字符的数目称为串的长度。 （6）假设以行序为主序存储二维数组A=array[1..100,1..100]，设每个数据元素占2个存储单 元，基地址为10，则LOC[5,5]=（）。 A．808 B．818 C．1010 D．1020 答案：B 解释：以行序为主，则LOC[5,5]=[（5-1）*100+（5-1）]*2+10=818。 （7）设有数组A[i,j]，数组的每个元素长度为3字节，i的值为1到8，j的值为1到10，数 组从内存首地址BA开始顺序存放，当用以列为主存放时，元素A[5,8]的存储首地址为（）。 A．BA+141 B．BA+180 C．BA+222 D．BA+225 答案：B 解释：以列序为主，则LOC[5,8]=[（8-1）*8+（5-1）]*3+BA=BA+180。 （8）设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第一元素， 其存储地址为1，每个元素占一个地址空间，则a85的地址为（）。 A．13 B．32 C．33 D．40

第四章串 习题

第四章串习题 一、选择题 1．串是一种特殊的线性表，其特殊性体现在（） A．可以顺序存储 B.数据元素是一个字符 C. 可以链式存储 D.数据元素可以是多个字符 2. 空串与空格字符组成的串的区别在于（）。 A.没有区别 B.两串的长度不相等 C.两串的长度相等 D.两串包含的字符不相同 3.有串S1=”ABCDEFG”, S2=”PQRST”, 假设函数con(x,y)返回x和y串的连接串,subs(s,i,j)返回串s的从数组序号为i（下标从0开始）的字符开始的j个字符组成的子串, len(s)返回串s 的长度,则con(subs(s1,2,len(s2)),subs(s1,len(s2),2))的结果串是( ) A.BCDEF B.BCDEFG C.BCPQRST D.CDEFGFG 4.若串s=”sfotware”,其子串的个数是( ) A.8 B.37 C.36 D.9 5. 一个子串在包含它的主串中的位置是指（）。 A.子串的最后那个字符在主串中的位置 B.子串的最后那个字符在主串中首次出现的位置 C.子串的第一个字符在主串中的位置 D.子串的第一个字符在主串中首次出现的位置 6. 下面的说法中，只有（）是正确的。 A.字符串的长度是指串中包含的字母的个数 B.字符串的长度是指串中包含的不同字符的个数 C.若T包含在S中，则T一定是S的一个子串 D.一个字符串不能说是其自身的一个子串 7. 两个字符串相等的条件是（）。 A.两串的长度相等 B.两串包含的字符相同 C.两串的长度相等，并且两串包含的字符相同 D.两串的长度相等，并且对应位置上的字符相同 8. 若SUBSTR（S，i，k）表示求S中从第i个字符开始的连续k个字符组成的子串的操作，则对于S=“Beijing＆Nanjing”，SUBSTR（S，4，5）=（）。 A. “ijing” B. “jing＆” C. “ingNa” D. “ing＆N” 9. 若INDEX（S，T）表示求T在S中的位置的操作，则对于S=“Beijing＆Nanjing”，T=“jing”，INDEX（S，T）=（）。 A.2 B.3 C.4 D.5 10. 若REPLACE（S，S1，S2）表示用字符串S2替换字符串S中的子串S1的操作，则对于S=“Beijing＆Nanjing”，S1=“Beijing”，S2=“Shanghai”，REPLACE（S，S1，S2）=（）。A. “Nanjing＆Shanghai” B. “Nanjing＆Nanjing” C. “ShanghaiNanjing” D. “Shanghai＆Nanjing” 11. 在长度为n的字符串S的第i个位置插入另外一个字符串，i的合法值应该是（）。 A.i＞0 B. i≤n C.1≤i≤n D.1≤i≤n+1 1

《数据结构》习题集：第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))的结果串是（）。 A、BCDEF B、BCDEFG C、BCPQRST D、BCDEFEF 2.空串和空格是相同的。（） A、正确 B、错误 3.若串S1=’ABCDEFG’，S2=’9898’，S3=’###’，S4=’012345，则执行下列语句后，其结果为（）。 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.串是一种特殊的线性表，其特殊性体现在（）。 A、可以顺序存储 B、数据元素是一个字符 C、可以链接存储 D、数据元素可以是多个字符 5.设有两个串p 和q，求q 在p 中首次出现的位置的运算称为（）。 A、连接 B、模式匹配 C、求子串 D、求串长 6.下面关于串的的叙述中，哪一个是不正确的？（） A．串是字符的有限序列B．空串是由空格构成的串 C．模式匹配是串的一种重要运算D．串既可以采用顺序存储，也可以采用链式存储 7.串的长度是指（） 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’，其长度为（）。 2.空串是（），其长度为（）。 3.设S1=’GOOD’，S2=’’，S3=’BYE!’，则S1、S2 和S3 连接后的结果是（）。 4.两个串相等的充分必要条件是（）。 5.串的两种最基本的存储方式是（）。 6.空格串是_________，其长度等于_________。

《数据结构及其应用》笔记含答案 第四章_串、数组和广义表

第4章串、数组和广义表 一、填空题 1、零个或多个字符组成的有限序列称为串。 二、判断题 1、稀疏矩阵压缩存储后，必会失去随机存取功能。（√） 2、数组是线性结构的一种推广，因此与线性表一样，可以对它进行插入，删除等操作。（╳） 3、若采用三元组存储稀疏矩阵，把每个元素的行下标和列下标互换，就完成了对该矩阵的转置运算。（╳） 4、若一个广义表的表头为空表，则此广义表亦为空表。（╳） 5、所谓取广义表的表尾就是返回广义表中最后一个元素。（╳） 三、单项选择题 1、串是一种特殊的线性表，其特殊性体现在（B）。 A．可以顺序存储B．数据元素是一个字符 C．可以链式存储D．数据元素可以是多个字符若 2、串下面关于串的的叙述中，（B）是不正确的？ A．串是字符的有限序列B．空串是由空格构成的串 C．模式匹配是串的一种重要运算D．串既可以采用顺序存储，也可以采用链式存储 解释：空格常常是串的字符集合中的一个元素，有一个或多个空格组成的串成为空格串，零个字符的串成为空串，其长度为零。 3、串“ababaaababaa”的next数组为（C）。 A．012345678999 B．012121111212 C．011234223456 D．0123012322345 4、串“ababaabab”的nextval为（A）。 A．010104101B．010102101 C．010100011 D．010101011 5、串的长度是指（B）。 A．串中所含不同字母的个数B．串中所含字符的个数 C．串中所含不同字符的个数D．串中所含非空格字符的个数 解释：串中字符的数目称为串的长度。 6、假设以行序为主序存储二维数组A=array[1..100,1..100]，设每个数据元素占2个存储单元，基地址为10，则LOC[5,5]=（B）。 A．808 B．818 C．1010 D．1020 解释：以行序为主，则LOC[5,5]=[（5-1）*100+（5-1）]*2+10=818。 7、设有数组A[i,j]，数组的每个元素长度为3字节，i的值为1到8，j的值为1到10，数组从内存首地址BA开始顺序存放，当用以列为主存放时，元素A[5,8]的存储首地址为（B）。A．BA+141 B．BA+180 C．BA+222 D．BA+225 解释：以列序为主，则LOC[5,8]=[（8-1）*8+（5-1）]*3+BA=BA+180。 8、设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第一元素，其存储地址为1，每个元素占一个地址空间，则a85的地址为（C）。 A．13 B．32 C．33 D．40 9、若对n阶对称矩阵A以行序为主序方式将其下三角形的元素(包括主对角线上所有元素)依次存放于一维数组B[1..(n(n+1))/2]中，则在B中确定a ij（i

数据结构练习题--串

第四章串 选择题 1．下面关于串的的叙述中，哪一个是不正确的？（） 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)))其结果为（） A．ABC###G0123 B．ABCD###2345 C．ABC###G2345 D．ABC###2345 E．ABC###G1234 F．ABCD###1234 G．ABC###01234 3．串的长度是指（） A．串中所含不同字母的个数 B．串中所含字符的个数 C．串中所含不同字符的个数 D．串中所含非空格字符的个数 4．串是一种数据对象和操作都特殊的线性表。（ T ） 填空题 1．空格串是指_由空格字符（ASCII值32）所组成的字符串__，其长度等于___空格个数__。2．组成串的数据元素只能是___字符_____。 3．一个字符串中_任意个连续的字符组成的子序列_______称为该串的子串。 4．INDEX（‘DATASTRUCTURE’，‘STR’）=____5____。 5．串是一种特殊的线性表，其特殊性表现在__其数据元素都是字符__；串的两种最基本的存储方式是__顺序存储__、_链式存储__；两个串相等的充分必要条件是__串的长度相等且两串中对应位置的字符也相等__。 6．下列程序判断字符串s 是否对称，对称则返回1，否则返回0；如 f("abba")返回1， f("abab")返回0； int f(_ char s[ ]_______) {int i=0,j=0; while (s[j])__ j++ ______; for(j--; i= j ______) }

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

数据结构(C语言版)习题及答案第四章习题 4.1选择题 1、空串与空格串是（B）。 A、相同 B、不相同Ｃ、不能确定 2、串是一种特殊的线性表，其特殊性体现在（B）。 A、可以顺序存储 B、数据元素是一个字符 C、可以链式存储 D、数据元素可以是多个字符 3、设有两个串p和q，求q在p中首次出现的位置的操作是（B）。 A、连接 B、模式匹配 C、求子串 D、求串长 4、设串1=“ABCDEFG”，2=“PQRST”函数trconcat（，t）返回和t串的连接串，trub（，i，j）返回串中从第i个字符开始的、由连续j 个字符组成的子串。trlength()返回串的长度。则trconcat（trub（1，2，trlength（2）），trub（1，trlength（2）， 2））的结果串是（D）。 A、BCDEF B、BCDEFG C、BCPQRST D、BCDEFEF 5、若串=“oftware”，其子串个数是（B）。 A、8 B、37 C、36 D、9 4.2简答题 1、简述空串与空格串、主串与子串、串名与串值每对术语的区别？

答：空串是指长度为0的串，即没有任何字符的串。 空格串是指由一个或多个空格组成的串，长度不为0。 子串是指由串中任意个连续字符组成的子序列，包含子串的串称为主串。串名是串的一个名称，不指组成串的字符序列。 串值是指组成串的若干个字符序列，即双引号中的内容。 2、两个字符串相等的充要条件是什么？ 答：条件一是两个串的长度必须相等 条件二是串中各个对应位置上的字符都相等。 3、串有哪几种存储结构？ 答：有三种存储结构，分别为：顺序存储、链式存储和索引存储。 4、已知两个串：1=”fgcdbcabcadr”,2=”abc”,试求两个串的长度，判断串2是否是串1的子串，并指出串2在串1中的位置。 答：（1）串1的长度为14，串2的长度为3。 （2）串2是串1的子串，在串2中的位置为9。 5、已知：1=〃I’matudent〃，2=〃tudent〃，3=〃teacher〃，试 求下列各操作的结果： trlength(1)；答：13 trconcat(2,3)；答：”tudentteachar” trdelub(1,4,10)；答：I’m

数据结构课后习题(第4-5章)

【课后习题】第4章 串 第5章 数组和广义表 网络工程2010级（ ）班 学号： 姓名： 题 号 一 二 三 四 总分 得 分 一、填空题（每空1分，共30分） 1. 串有三种机内表示方法： 、 和 ，其中前两种属于顺序存储结构，第三种属于 。 2. 若n 为主串长度，m 为子串长度，则串的BF （朴素）匹配算法最坏的情况下需要比较字符的总次数 为 ,T(n)= 。 3. 是任意串的子串；任意串S 都是S 本身的子串，除S 本身外，S 的其他子串称为S 的 。 4. 设数组a[1…50, 1…60]的基地址为1000，每个元素占2个存储单元，若以行序为主序顺序存储，则 元素a[32,58]的存储地址为 。 5. 对于数组，比较适于采用 结构够进行存储。 6. 广义表的深度是指_______。 7. 将一个100100 A 的三对角矩阵，按行优先存入一维数组B[297]中，A 中元素66,66A 在B 数组中的位置 k 为 。 8. 注意：a i,j 的k 为 2(i-1)+j-1,(i=1时j=1,2;1

《数据结构》第四章 串 习题

《数据结构》第四章串习题 基本概念题： 4-1 设S1 =“Data Structure Course”，S2 =“Structure”，S3 =“Base”，求：（1）Length(S1)；（2）Compare(S2, S3)； （3）Insert(S1, 5, S3)；（4）Delete(S1, 5, 9)； （5）SubString(S1, 5, 9, T)；（6）Search(S1, 0, S2)； （7）Replace(S1, 0, S2, S3) 4-2 什么叫串？串和字符在存储方法上有什么不同？空串和空格串是否相同，为什么？ 4-3 串是由字符组成的，长度为1的串和字符是否相同。为什么？ 4-4 串是不定长的，表示串的长度有几种方法？C语言中的串采用哪种方法？ 4-5 可以说串是数据类型固定为字符类型的线性表，但是串操作和线性表操作的主要不同之处在哪里？ 4-6 可以用几种存储方法存储串？ 4-7 分别写出串的静态数组存储结构和串的动态数组存储结构的结构体定义。 4-8 为什么动态数组结构下串的实现要增加撤消函数？ 复杂概念题： 4-9 令t1=“aaab”, t2=“abcabaa”, t3=“abcaabbabcabaacba”，试分别求出他们的next[j]值。 4-10 简述模式匹配的Brute-Force算法思想。简述模式匹配的KMP算法思想。 4-11 简述求子串的next[j]值的算法思想。 算法设计题： 4-12 设串采用静态数组存储结构，编写函数实现两个串的比较Compare(S, T)。要求比较结果有等于和不等于两种情况。 4-13 设串采用静态数组存储结构，编写函数实现两个串的比较Compare(S, T)。要求比较结果有大于、等于和小于三种情况。 4-14 设串采用动态数组存储结构，编写函数实现两个串的比较Compare(S, T)。要求比较结果有大于、等于和小于三种情况。对比本题和习题4-13的算法，说明串的静态数组存储结构和串的动态数组存储结构是否对编写串的比较算法有影响。 4-15 设串采用静态数组存储结构，编写函数实现串的替换Replace(S, start, T, V)，即要求在主串S中，从位置start开始查找是否存在子串T，若主串S中存在子串T，则用子串V 替换子串T，且函数返回1；若主串S中不存在子串T，则函数返回0。 4-16 设字符串采用静态数组的顺序存储结构， （1）编写算法删除字符串s中值等于ch的一个字符，并分析该算法的时间复杂度； （2）编写算法删除字符串s中值等于ch的所有字符。 4-17 设字符串采用单字符的链式存储结构，编写删除串s从位置i开始长度为k的子串的算法。 *4-18 设字符串采用块链存储结构，编写删除串s从位置i开始长度为k的子串的算法。 上机实习题： 4-19 在4.4.3节例4-6的基础上，编写比较 Brute-Force算法和KMP算法比较次数的程序。 4-20 设串采用静态数组存储结构，编写函数实现串的替换Replace(S, start, T, V)，

第4章 字符串 习题参考答案

第4章串习题参考答案 一、基础知识题 4.1 简述下列每对术语的区别： 空串和空格串；串常量与串变量；主串和子串；串变量的名字和串变量的值；静态分配的顺序串与动态分配的顺序串。 【解答】不含任何字符的串称为空串，其长度为0。仅含有空格字符的串称为空格串，其长度为串中空格字符的个数。空格符可用来分割一般的字符，便于人们识别和阅读，但计算串长时应包括这些空格符。空串在串处理中可作为任意串的子串。 用引号（数据结构教学中通常用单引号，而C语言中用双引号）括起来的字符序列称为串常量，串值可以变化的量称为串变量。 串中任意个连续的字符组成的子序列被称为该串的子串。包含子串的串又被称为该子串的主串。子串在主串中第一次出现的第一个字符的位置称子串在主串中的位置。 串变量的与其它变量一样，要用名字引用其值，串变量的名字也是标识符，串变量的值可以修改。 串的存储也有静态存储和动态存储两种。静态存储指用一维数组，通常一个字符占用一个字节，需要静态定义串的长度，具有顺序存储结构的优缺点。若需要在程序执行过程中，动态地改变串的长度，则可以利用标准函数malloc()和free()动态地分配或释放存储单元，提高存储资源的利用率。在C语言中，动态分配和回收的存储单元都来自于一个被称之为“堆”的自由存储区，故该方法可称为堆分配存储。类型定义如下所示： typedef struct { char *str; int length; }HString; 4.2设有串S=’good’，T=’I︼am︼a︼student’，R=’！’，求： （1）StringConcat(T，R) （2）SubString(T，8，7） （3）StringLength(T) （4）Index(T，’a’) （5）StringInsert(T，8，S) （6）Replace(T，SubString(T，8，7)，’teacher’) 【解答】 (1) StringConcat(T，R)=’I︼am︼a︼student！’ (2) SubString(T，8，7）=’student’ (3) StringLength(T)=14 (4) Index(T，’a’)=3 (5) StringInsert(T，8，S)=’I︼am︼a︼goodstudent’ (6) Replace(T，SubString(T，8，7)，’teacher’)= ’I︼am︼a︼teacher’ 4.3若串S1=‘ABCDEFG’，S2=‘9898’，S3=‘###’，S4=‘012345’，执行 concat(replace(S1，substr(S1，length(S2)，length(S3))，S3)，substr(S4，index(S2，‘8’)，length(S2))) 操作的结果是什么？ 【解答】 concat(replace(S1,substr(S1,length(S2),length(S3)),S3),substr(S4，index(S2,‘8’),length(S2))) = concat(replace(S1,substr(S1,4,3),S3),substr(S4,2,4)) = concat(replace(S1,’DEF’,S3),’1234’)

数据结构课后习题第四章

第四章串 习题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为：