数据结构习题第四章串答案.docx

数据结构习题第四章串答案.docx

ID:51767528

大小:29.90 KB

页数:12页

时间:2020-03-15

数据结构习题第四章串答案.docx_第1页
数据结构习题第四章串答案.docx_第2页
数据结构习题第四章串答案.docx_第3页
数据结构习题第四章串答案.docx_第4页
数据结构习题第四章串答案.docx_第5页
资源描述:

《数据结构习题第四章串答案.docx》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库

1、第四章串一、选择题1.B2.E3.C4.A5.C6.A7.1D7.2F8.B注9.D10.B注:子串的定义是:串中任意个连续的字符组成的子序列,并规定空串是任意串的子串,任意串是其自身的子串。若字符串长度为n(n>0),长为n的子串有1个,长为n-1的子串有2个,长为n-2的子串有3个,……,长为1的子串有n个。由于空串是任何串的子串,所以本题的答案为:8*(8+1)/2+1=37。故选B。但某些教科书上认为“空串是任意串的子串”无意义,所以认为选C。为避免考试中的二意性,编者认为第9题出得好。二、判断题1.√2.√3.√三.填空题1.(1)由空格字符(ASCII值32)所组成的字符串(

2、2)空格个数2.字符3.任意个连续的字符组成的子序列4.55.O(m+n)6.011223127.010104218.(1)模式匹配(2)模式串9.(1)其数据元素都是字符(2)顺序存储(3)和链式存储(4)串的长度相等且两串中对应位置的字符也相等10.两串的长度相等且两串中对应位置的字符也相等。11.’xyxyxywwy’12.*s++=*t++或(*s++=*t++)!=‘’13.(1)chars[](2)j++(3)i>=j14.[题目分析]本题算法采用顺序存储结构求串s和串t的最大公共子串。串s用i指针(1<=i<=s.len)。t串用j指针(1<=j<=t.len)。算法思

3、想是对每个i(1<=i<=s.len,即程序中第一个WHILE循环),来求从i开始的连续字符串与从j(1<=j<=t.len,即程序中第二个WHILE循环)开始的连续字符串的最大匹配。程序中第三个(即最内层)的WHILE循环,是当s中某字符(s[i])与t中某字符(t[j])相等时,求出局部公共子串。若该子串长度大于已求出的最长公共子串(初始为0),则最长公共子串的长度要修改。程序(a):(1)(i+k<=s.len)AND(j+k<=t.len)AND(s[i+k]=t[j+k])//如果在s和t的长度内,对应字符相等,则指针k后移(加1)。(2)con:=false//s和t对应字符

4、不等时置标记退出(3)j:=j+k//在t串中,从第j+k字符再与s[i]比较(4)j:=j+1//t串取下一字符(5)i:=i+1//s串指针i后移(加1)。 程序(b):(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++15.(1)0(2)next[k]16.(1)i:=i+1(2)j:=j+1(3)i:=i-j+2(4)j:=1;(5)i-mt(或i:=i-j+1)(6)017.程序中递归调用(1)ch1<>midch//当读入不是分隔符&和输入结束符$时,继续读入字符(2)

5、ch1=ch2//读入分隔符&后,判ch1是否等于ch2,得出真假结论。(3)answer:=true(4)answer:=false(5)read(ch)(6)ch=endch18.(1)initstack(s)//栈s初始化为空栈。 (2)setnull(exp)//串exp初始化为空串。(3)chinopset//判取出字符是否是操作符。(4)push(s,ch)//如ch是运算符,则入运算符栈s。(5)sempty(s)//判栈s是否为空。(6)succ:=false//若读出ch是操作数且栈为空,则按出错处理。(7)exp(8)ch//若ch是操作数且栈非空,则形成部分中缀表达

6、式。(9)exp(10)gettop(s)//取栈顶操作符。(11)pop(s)//操作符取出后,退栈。  (12)sempty(s) //将pre的最后一个字符(操作数)加入到中缀式exp的最后。四.应用题 1.串是零个至多个字符组成的有限序列。从数据结构角度讲,串属于线性结构。与线性表的特殊性在于串的元素是字符。 2.空格是一个字符,其ASCII码值是32。空格串是由空格组成的串,其长度等于空格的个数。空串是不含任何字符的串,即空串的长度是零。 3.最优的T(m,n)是O(n)。串S2是串S1的子串,且在S1中的位置是1。开始求出最大公共子串的长度恰是串S2的长度,一般情况下,T(

7、m,n)=O(m*n)。 4.朴素的模式匹配(Brute-Force)时间复杂度是O(m*n),KMP算法有一定改进,时间复杂度达到O(m+n)。本题也可采用从后面匹配的方法,即从右向左扫描,比较6次成功。另一种匹配方式是从左往右扫描,但是先比较模式串的最后一个字符,若不等,则模式串后移;若相等,再比较模式串的第一个字符,若第一个字符也相等,则从模式串的第二个字符开始,向右比较,直至相等或失败。若失败,模式串后移,再重复以上过程。按

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。