




已阅读5页,还剩3页未读, 继续免费阅读
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
习题四 串一、单项选择题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”,其子串的个数是( )。A8 B37 C36 D9二、填空题1含零个字符的串称为_串。任何串中所含_的个数称为该串的长度。2空格串是指_ _,其长度等于_ _。 3当且仅当两个串的_相等并且各个对应位置上的字符都_时,这两个串相等。一个串中任意个连续字符组成的序列称为该串的_串,该串称为它所有子串的_串。4INDEX(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 (sj)(2)_ _; for(j-; ij & si=sj; i+,j-); 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(jlength) 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 “(xz)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写一个递归算法来实现字符串逆序存储,要求不另设串存储空间。第四章 串一、单项选择题1B2. B3B4C5. C二、填空题1空、字符2 由空格字符(ASCII值32)所组成的字符串 空格个数 3长度、相等、子、主455011223126(1)char s (2) j+ (3) i = j7题目分析本题算法采用顺序存储结构求串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中某字符(si)与t中某字符(tj)相等时,求出局部公共子串。若该子串长度大于已求出的最长公共子串(初始为),则最长公共子串的长度要修改。(1) i+k=s.len & j+k=t.len & si+k=tj+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朴素的模式匹配(BruteForce)时间复杂度是(mn),KMP算法有一定改进,时间复杂度达到(mn)。本题也可采用从后面匹配的方法,即从右向左扫描,比较次成功。另一种匹配方式是从左往右扫描,但是先比较模式串的最后一个字符,若不等,则模式串后移;若相等,再比较模式串的第一个字符,若第一个字符也相等,则从模式串的第二个字符开始,向右比较,直至相等或失败。若失败,模式串后移,再重复以上过程。按这种方法,本题比较18次成功。4next和nextval值分别为0112123422和0102010422。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四、算法设计题1const 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; tch=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(in-1) if(si=si+1) i+; length+; else /上一个重复子串结束 if(maxlength) max=length; index=start; /当前重复子串长度大,则更新max i+;start=i;length=1; /初始化下一重复子串的起始位置和长度printf(“最长重复子串的长度为%d,在串中的位置%dn”,max,index);return(max);/算法结束算法讨论算法中用in-1来控制循环次数,因C数组下标从0 开始,故长度为n的串,其最后一个字符下标是n-1,当i最大为n-2时,条件语句中si+1正好是sn-1,即最后一个字符。子串长度的初值数为1,表示一个字符自然等于其身。算法的时间复杂度为O(n),每个字符与其后继比较一次。5题目分析实现字符串的逆置并不难,但本题“要求不另设串存储空间”来
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 降低水泥熟料黄心料的成本控制措施
- 医疗信息安全质控管理持续改进措施
- 2025年春五年级道法下册教学师资培训计划
- 写景作文我们的教室450字9篇范文
- 农产品市场开拓与运营合作协议
- 幼儿挑食造成营养不良的原因及措施
- 客家的春节700字15篇范文
- 重庆市万盛经济技术开发区关坝中学2024年九上数学期末复习检测试题含解析
- 人生不是拿来挥霍的450字(7篇)
- 2025三年级科学下册课堂管理计划
- 2025年春季XX中学团委工作总结:青春筑梦践初心笃行不怠踏征程
- 工业设计基础 1.1.1 工业设计基础课程简介
- 电焊证培训 考试试题及答案
- 期货培训课件模板
- 气切患者护理课件
- 青春期生理讲课件
- 2025-2030年中国财税服务行业市场深度调研及发展前景与投资研究报告
- 2024年咸阳市社区工作者计划招聘真题
- 2025年四川酒业茶业投资集团有限公司及下属子公司招聘笔试参考题库含答案解析
- 新能源汽车热管理系统的能量优化与梯级利用策略探讨
- 工程控制面试题及答案
评论
0/150
提交评论