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

本文格式为Word版，下载可任意编辑——《数据结构》习题集第4章串数据结构课后练习题第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、BCDEFB、BCDEFGC、BCPQRSTD、BCDEFEF2.空串和空格是一致的。（）

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###G0123B、ABCD###2345C、ABC###G2345D、ABC###2345E、ABC###G1234F、ABCD###1234G、ABC###012344.串是一种特别的线性表，其特别性表达在（）。

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.2.3.4.5.6.

设s=’I_AM_A_TEACHER’，其长度为（）。空串是（），其长度为（）。

设S1=’GOOD’，S2=’’，S3=’BYE!’，则S1、S2和S3连接后的结果是（）。两个串相等的充分必要条件是（）。串的两种最基本的存储方式是（）。

空格串是_________，其长度等于_________。

1/2

北京理工大学珠海学院计算机学院“数据结构〞课程组编制2023-3-1

数据结构课后练习题第4章串

7.设有两个串q和p，求q在p中首次出现的算法叫_________。8.串的连接运算不满足_________，满足_________。

四、简答题

1.已知以下字符串（假设采用定长存储结构）

a=’this’,b=’’,c=’good’,

d=’ne’,

f=’asample’,g=’is’

顺序执行以下操作后，S、T、U、V、Length(s)、Index(v,g)、Index(u,g)各是什么？

S=Concat(a,concat(Substr(f,2,7),Concat(b,Substr(a,3,2))))T=Replace(f,Substr(f,3,6),c)U=Concat(Substr(c,3,1),d)

V=Concat(S,Concat(b,Concat(T,Concat(b,U))))2.2执行以下函数会产生怎样的输出结果？

Voiddemonstrate(){

Strassign(s,’thisisabook’);

Replace(s,Substring(s,3,7),’eseare’);Strassign(t,Concat(s,’s’));Strassign(u,’xyxyxyxyxyxy’);Strassign(v,Substring(u,6,3));Strassign(w,’w’);

Printf(’t=’,t,’v=’,v,’u=’,Replace(u,v,w));}

3.设s=’Iamastudent’，t=’good’，q=’worker’。求strlength(s)，strlength(t)，substr(s,8,7)，substr(t,2,1)，

index(s,’a’)，index(s,t)，replace(s,’student’,q)，concat(substr(s,6,2),concat(t,substr(s,7,8)))。

五、算法设计题

1.串s和t采用堆存储，设计一个函数，求第一个在s而不在t中的字符的序号。2.采用堆存储