《数据结构》习题集:第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.空格串是_由空格组成的非空串________,其长度等于串中空格字符的个数_________。

7.设有两个串q 和p,求q 在p 中首次出现的算法叫_______匹配__。

8.串的连接运算不满足____交换律_____,满足______结合律___。

四、简答题

1.已知下列字符串(假设采用定长存储结构)

a=’this’,

b=’ ’,

c=’good’,

d=’ne’,

f=’a sample’,

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))))

答s=this sample is;t=’a good one;u=one;

v=this sample is a good one;

length(s)=14;index(v,g)=3;index(u,g)=0

2.2执行以下函数会产生怎样的输出结果?

Void demonstrate(){

Strassign(s,’this is a book’);

Replace(s,Substring(s,3,7),’ese are’);

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));

}

t=these are books; v=yxy; u=xwxwxw

3.设s=’I am a student’,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)))。

strlength(s)=14;strlength(t)=4;substr(s,8,7)=student;substr(t,2,1)=o;

index(s,’a’)=3; index(s,t)=0; replace(s,’student’,q)= I am a worker;

concat(substr(s,6,2)=a ; concat(t,substr(s,7,8))=a good student;

五、算法设计题

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

int search(Hstring s,Hstring t){

int I=0,flag=1;

while(I

if(s.ch[i]!=t.ch[i])flag=0;I++

}

if(flag) return –1;

else return I-1;

}

2.采用堆存储串s,设计函数删除s 中第I 个字符开始的j 个字符。

int delij(Hstring &s,int I,int j){

int k;

if(I<0||j<0) return 0

if(I+j>s.length) j=s.length-I;

for(k=I+j;k

s.length-=j;

return 1;

}

3.若x 和y 是采用堆存储的串,设计一个比较两个串是否相等的函数。

int compare(Hstring x,Hstring y){

int I=0,flag=1;

if(x.length!=y.length)return 0;

else{

while(I

if(x.ch[i]!=y.ch[i])flag=0;

I++;

}

Return flag;

}

}

相关推荐
相关主题
热门推荐