资源预览内容
第1页 / 共12页
第2页 / 共12页
第3页 / 共12页
第4页 / 共12页
第5页 / 共12页
第6页 / 共12页
第7页 / 共12页
第8页 / 共12页
第9页 / 共12页
第10页 / 共12页
亲,该文档总共12页,到这儿已超出免费预览范围,如果喜欢就下载吧!
资源描述
第四章 串 一、选择题 1.B2.E3.C4.A5.C6.A7.1D7.2F8.B注9.D10.B 注:子串的定义是:串中任意个连续的字符组成的子序列,并规定空串是任意串的子串,任意串是其自身的子串。若字符串长度为n(n0),长为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字符3任意个连续的字符组成的子序列 45 5.O(m+n)601122312 701010421 8(1)模式匹配 (2)模式串9(1)其数据元素都是字符(2)顺序存储(3)和链式存储(4)串的长度相等且两串中对应位置的字符也相等10两串的长度相等且两串中对应位置的字符也相等。11xyxyxywwy 12*s+=*t+ 或(*s+=*t+)!=013(1)char s (2) j+ (3) i = j14题目分析本题算法采用顺序存储结构求串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)相等时,求出局部公共子串。若该子串长度大于已求出的最长公共子串(初始为),则最长公共子串的长度要修改。程序(a):(1)(i+k=s.len)AND(j+k=t.len) AND(si+k=tj+k) /如果在s和t的长度内,对应字符相等,则指针k 后移(加1)。 (2)con:=false /s和t对应字符不等时置标记退出 (3)j:=j+k /在t串中,从第j+k字符再与si比较 (4)j:=j+1 /t串取下一字符(5)i:=i+1 /s串指针i后移(加1)。程序(b):(1) i+k=s.len & j+k=t.len & si+k=tj+k /所有注释同上(a) (2) con=0 (3) j+=k (4) j+ (5) i+15(1)0 (2)nextk16(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)ch1midch /当读入不是分隔符&和输入结束符$时,继续读入字符 (2)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) ch in opset /判取出字符是否是操作符。 (4) push (s,ch) /如ch是运算符,则入运算符栈s。 (5) sempty (s) /判栈s是否为空。 (6) succ := false /若读出ch是操作数且栈为空,则按出错处理。 (7) exp (8)ch /若ch是操作数且栈非空,则形成部分中缀表达式。 (9) exp (10) gettop(s) /取栈顶操作符。 (11) pop(s) /操作符取出后,退栈。(12) sempty(s) /将pre的最后一个字符(操作数)加入到中缀式exp的最后。四应用题串是零个至多个字符组成的有限序列。从数据结构角度讲,串属于线性结构。与线性表的特殊性在于串的元素是字符。空格是一个字符,其ASCII码值是32。空格串是由空格组成的串,其长度等于空格的个数。空串是不含任何字符的串,即空串的长度是零。最优的T(m,n)是O(n)。串S2是串S1的子串,且在S1中的位置是1。开始求出最大公共子串的长度恰是串S2的长度,一般情况下,T(m,n) =O(m*n)。朴素的模式匹配(BruteForce)时间复杂度是(mn),KMP算法有一定改进,时间复杂度达到(mn)。本题也可采用从后面匹配的方法,即从右向左扫描,比较次成功。另一种匹配方式是从左往右扫描,但是先比较模式串的最后一个字符,若不等,则模式串后移;若相等,再比较模式串的第一个字符,若第一个字符也相等,则从模式串的第二个字符开始,向右比较,直至相等或失败。若失败,模式串后移,再重复以上过程。按这种方法,本题比较18次成功。KMP算法主要优点是主串指针不回溯。当主串很大不能一次读入内存且经常发生部分匹配时,KMP算法的优点更为突出模式串的next函数定义如下: nextj= 根据此定义,可求解模式串t的next和nextval值如下:j1 2 3 4 5 6 7 8 9 10 11 12 t串a b c a a b b a b c a bnextj0 1 1 1 2 2 3 1 2 3 4 5nextvalj0 1 1 0 2 1 3 0 1 1 0 57解法同上题6,其next和nextval值分别为0112123422和0102010422。8解法同题6,t串的next和nextval函数值分别为0111232和0110132。9解法同题6,其next和nextval 值分别为011123121231和011013020131。10p1的next和nextval值分别为:0112234和0102102;p2的next和nextval值分别为:0121123和0021002。11next数组值为011234567 改进后的next数组信息值为010101017。12011122312。13next定义见题上面6和下面题20。串p的next函数值为:01212345634。14(1)S的next与nextval值分别为012123456789和002002002009,p的next与nextval值分别为012123和002003。 (2)利用BF算法的匹配过程: 利用KMP算法的匹配过程: 第一趟匹配: aabaabaabaac 第一趟匹配:aabaabaabaac aabaac(i=6,j=6) aabaac(i=6,j=6) 第二趟匹配: aabaabaabaac 第二趟匹配:aabaabaabaac aa(i=3,j=2) (aa)baac 第三趟匹配: aabaabaabaac 第三趟匹配:aabaabaabaac a(i=3,j=1) (成功) (aa)baac第四趟匹配: aabaabaabaac aabaac(i=9,j=6)第五趟匹配: aabaabaabaac aa(i=6,j=2)第六趟匹配: aabaabaabaac a(i=6,j=1)第七趟匹配: aabaabaabaac(成功) aabaac(i=13,j=7) 15(1)p的nextval函数值为0110132。(p的next函数值为0111232)。(2)利用KMP(改进的nextval)算法,每趟匹配过程如下: 第一趟匹配: abcaabbabcabaacbacba abcab(i=5,j=5) 第二趟匹配: abcaabbabcabaacbacba abc(i=7,j=3) 第三趟匹配: abcaabbabcabaacbacba a(i=7,j=1) 第四趟匹配: abcaabbabcabaac bacba (成功) abcabaa(i=15,j=8)16KMP算法的时间复杂性是O(m+n)。p的next和nextval值分别为01112212321和01102201320。17(1)p的nextval函数值为01010。(next函数值为01123) (2)利用所得nextval数值,手工模拟对s的匹配过程,与上面16题类似,为节省篇幅,故略去。18模式串T的next和nextval值分别为0121123和0021002。19第4行的pJ=pK语句是测试模式串的第J个字符是否等于第K个字符,如是,则指针J和K均增加1,继续比较。第6行的pJ=pK语句的意义是,当第J个字符在模式匹配中失配时,若第K个字符和第J个字符不等,则下个与主串匹配的字符是第K个字符;否则,若第K个字符和第J个字符相等,则下个与主串匹配的字符是第K个字符失配时的下一个(即NEXTVALK)。 该算法在最坏情况下的时间复杂度O(m2)。20(1)当模式串中第一个字符与主串中某字符比较不等(失配)时,next1=0表示模式串中已没有字符可与主串中当前字符si比较,主串当前指针应后移至下一字符,再和模式串中第一字符进行比较。 (2)当主串第i个字符与模式串中第j个字符失配时,若主串i不回溯,则假定模式串第k个字符与主串第i个字符比较,k值应满足条件1kj并且ppk-1=pj-k+1pj-1,即k为模式串向后移动的距离,k值有多个,为了不使向右移动丢失可能的匹配,k要取大,由于maxk表示移动的最大距离,所以取maxk,k的最大值为j-1。 (3)在上面两种情况外,发生失配时,主串指针i不回溯,在最坏情况下,模式串从第1个字符开始与主串第i个字符比较,以便不致丢失可能的匹配。21这里失败函数f,即是通常讲的模式串的ne
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号