数据结构习题3.doc

数据结构课后练习题 第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、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#G0123 B、ABCD#2345 C、ABC#G2345 D、ABC#2345 E、ABC#G1234 F、ABCD#1234 G、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. 设s=I_AM_A_TEACHER，其长度为（14）。【】2. 空串是（0个字符），其长度为（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 isT=a goodU=oneV=this sample is a good oneLength(s)=14Index(v,g)=3Index(u,g)=02. 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 booksv=yxyu=xwxwxw3. 设 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)=14Strlength(t)=4Substr(s,8,7)=studentSubstr(t,2,1)=oIndex(s,a)=3Index(s,t)=0Replace(s, student,q)=I am a workerConcat(substr(s,6,2),concat(t,substr(s,7,8)=a good student4. 已知s=(XYZ)+*,t=(X+Z)*Y,利用联接、求子串和转换等基本操作，将s转化为t。【，百度知道】答：（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. 串 s 和t 采用堆存储，设计一个函数，求第一个在s 而不在t 中的字符的序号。【，】答：int search(Hstring s, Hstring t)2. 3. int i = 0;4. int count = 1;5. while(i s.length & i t.length & count)6. 7. if(s.chi != t.chi)8. count = 0;9. i+10. 11. if(count)12. return -1;13. else14. return i-1;15. 2采用堆存储串 s，设计函数删除s 中第I 个字符开始的j 个字符。【，】答：int dele(Hstring &s, int i, int j)16. int k;17. if(i0 | j s.length)20. j = s.length - 1;21. for(k = i+j; k s.length; k+)22. s.chk-j = s.chk;23. s.length -= j;24. return i;25. 3若 x 和y 是采用堆存储的串，设计一个比较两个串是否相等的函数。【】答：int substr(Hstring s, Hstring t)26. 27. int sub = 1;28. if(s.length != t.length)29. return 0;30.