北航计算机考研材料第四章串答案.doc

第四章串一、选择题l.B2.E3.C4. A5.C6. A7. ID7. 2F8.B注9. D10. B注：子串的定义是：串中任意个连续的字符组成的子序列，并规定空串是任意串的子串, 任意申是其自身的子出若字符出长度为n(n>0),长为n的子串有1个，长为n-1的子串 有2个，长为n-2的子串有3个，……，长为1的子串有n个由于空串是任何串的子串， 所以本题的答案为：8* (8+1) /2+1二37但某些教科书上认为“空串是任意串的子 帛”无意义，所以认为选C为避免考试中的二意性，编者认为第9题出得好二、判断题1. J2. J3. V%1. 填空题1. (1)由空格字符(ASCTT值32)所组成的字符串 (2)空格个数 2.字符3.任意个连续的字符组成的子序列 4. 5 5.0(m+n)6. 01122312 7. 01010421 8. (1)模式匹配 (2)模式串9. (1)其数据元素都是字符⑵顺序存储⑶和链式存储⑷串的长度相等且两串中对应位置 的字符也相等10. 两冷的长度相等且两冷中对应位置的字符也相等11. xyxyxywwy 12. *s++=*t++ 或(*s++=*t++) != \013. (1) char s[ ] (2) j++ (3) i >= j14. [题目分析]本题算法采用顺序存储结构求串s和串t的最大公共子申。

申s用i指针 (K=i<=s. len)t串用j指针(K=j<=t. len)算法思想是对每个i (K=i<=s. len,即程(i+k<=s. len) AND(j+k<=t. len) AND(s[i+k]=t[j+k])//如果在s和t的长度内，对应字符相等，则指针k后移(加Do con:=falsej：=j+kJ：=j+1 i： =i+l i+k〈二s. len con 二 0 (3)序中第一个WHILE循环),来求从i开始的连续字符串与从j (l<=j<=t.len,即程序中第二 个WHILE循环)开始的连续字符串的最大匹配G程序中第三个(即最内层)的WHILE循环, 是当s中某字符(s [i])与t中某字符(t [j])相等时，求出局部公共子申若该子串长 度大于己求出的最长公共子串(初始为0),则最长公共子串的长度要修改a)： (1)程序程序(2)(3)(4)(5)(b)： (1)(2)//s和t对应字符不等时置标记退出〃在t串中，从第j+k字符再与s[i]比较〃t串取下一•字符//s吊指针i后移(加1 )o&& j+k<=t. len && s[i+k]==t[j+k] //所有注释同上(a) j+=k ⑷ j++ (5) i++0 (2) next[k](2) j:=j+l(3)i:=i-j+2 (4)j:=1: (5)i-mt (或 i:=i-j+l) (6)015. (1)16. (1) i： =i+l <17. 程序中递归调用(1) chlOmidch 〃当读入不是分隔符&和输入结束符$时，继续读入字符(2) chl=ch2 〃读入分隔符&后，判chi是否等于ch2,得出真假结论。

3) answer： =true(4) answer： =false(5) read (ch)(6) ch=endch18. (1) initstack (s) //栈 s 初始化为空栈⑵⑶⑷⑸⑹⑺⑼setnull (exp) ch in opset push (s, ch) sempty (s) succ := falseexpexp(11) pop(s)(12) sempty(s)〃串exp初始化为空串//判取出字符是否是操作符〃如ch是运算符，则入运算符栈〃判栈s是否为空〃若读出ch是操作数且栈为空，则按出错处理8)ch 〃若ch是操作数且栈非空，则形成部分中缀表达式10) gettop(s) 〃取栈顶操作符〃操作符取出后，退栈〃将pre的最后一个字符(操作数)加入到中缀式exp的最So后1. 应用题1 .串是零个至多个字符组成的有限序列从数据结构角度讲，串属于线性结构与线性 表的特殊性在于串的元素是字符2 .空格是一个字符，其ASCII码值是32空格串是由空格组成的串，其长度等于空格 的个数空串是不含任何字符的串，即空串的长度是零3.最优的T(m, n)是0(n)串S2是串S1的子串，且在S1中的位置是1。

开始求出最 大公共子串的长度恰是串S2的长度,一般情况R T(m, n)=0(m*n)4 .朴素的模式匹配(Brute—Force)时间复杂度是O (m*n), KMP算法有一定改进, 时I可受杂度达到O(m+n)0本题也可采用从后而匹配的方法，即从右向左扫描，比较6次 成功另一种匹配方式是从左往右扫描，但是先比较模式串的最后一个字符，若不等，则模 式串后移；若相等，再比较模式串的第一个字符，若第一个字符也相等，则从模式串的第二 个字符开始，向右比较，直至相等或失败若失败，模式冷后移，再重复以上过程按这种 方法，本题比较18次成功5. KMP算法主要优点是主串指针不网溯当主串很大不能一次读入内存且经常发生部分 匹配时，KMP算法的优点更为突出.6 .模式串的next函数定义如卜：next [ j ]*1此集合不空时0 当/ = 1肘max{k I l

8. 解法同题6, t串的next和nextval函数值分别为0111232和01101329. 解法同题 6,其 next 和 nextval 值分别为 011123121231 和 01101302013110. p]的 next 和 nextval 值分别为：0112234 和 0102102； p2 的 next 和 nextval 值分别为:0121123 和 0021002c11. next数组值为011234567 改进后的next数组信息值为010101017,12. 01112231213. next定义见题上面6和卜面题23串p的next函数值为:0121234563414. (DS 的 next 与 nextval 值分别为 012123456789 和 002002002009,p 的 next 与 nextval值分别为012123和002003 o(2)利用BF算法的匹配过程： 第一趟匹配：aabaabaabaacaabaac(i=6, j=6)第二趟匹配：aabaabaabaacaa(i=3, j=2)第三趟匹配：aabaabaabaaca(i=3, j=l)第四趟匹配：aabaabaabaac aabaac (i=9,j=6)第五趟匹配：aabaabaabaac aa(i=6, j=2)第六趟匹配：aabaabaabaac a(i=6, j=l)第七趟匹配：aabaabaabaac (成功)aabaac(i=13, j=7)利用KMP算法的匹配过程：第一趟匹配：aabaabaabaac aabaac （i=6, j二6） 第二趟匹配：aabaabaabaac（aa）baac 第三趟匹配：aabaabaabaac （成功）（aa）baac15. （1） p 的 nextval 函数值为 0110132。

p 的 next 函数值为 0111232）2）利用KMP（改进的nextval）算法,每趟匹配过程如下:第一趟匹配：abcaabbabcabaacbacbaabcab（i=5,j=5）第二趟匹配：abcaabbabcabaacbacbaabc（i=7, j=3）第三趟匹配：abcaabbabcabaacbacbaa（i=7, j=l）第四趟匹配：abcaabbabcabaac bacba（成功） abcabaa（i=15, j=8）16. KMP算法的时间复杂性是0 （m+n）p 的 next 和 nextval 值分别为 01112212321 和 0110220132017. （Dp 的 nextval 函数值为 01010next 函数值为 01123）（2）利用所得nextval数值，手工模拟对s的匹配过程，与上面16题类似，为节省篇 幅，故略去18. 模式串T的next和nextval值分别为0121123和002100219. 第4行的p[J]=p[K]语句是测试模式串的第J个字符是否等于第K个字符，如是，则指 针J和K均增加1,继续比较第6行的p[J]=p[K]句的意义是，当第J个字符在模式匹 配中失配时，若第K个字符和第J个字符不等，则下个与主出匹配的字符是第K个字符；否 则，若第K个字符和第J个字符相等，则下个与主串匹配的字符是第K个字符失配时的下一 个（即 NEXTVAL [K]）o该算法在最坏情况下的时间复杂度0（站）。

20. （1）当模式串中第一个字符与主冷中某字符比较不等（失配）时，next[l]=0表示模式 串中巳没有字符可与主串中当前字符s[i]比较，主串当前指针应后移至下一字符，再和模 式串中第一字符进行比较2）当主串第i个字符与模式申中第j个字符失配时，若主串i不回溯，则假定模式 冷第k个字符与主串第i个字符比较，k值应满足条件Kk

22. 失败函数（即next）的值只取决于模式串自身，若第j个字符与主串第i个字符失配 时，假定主串不回溯,模式串用第k （即next[j]）个字符与第i个相比,有plpL =PE・・・pjT’，为了不因模式串右移与主串第i个字符比较而丢失可能的匹配，对于上式中 存在的多个k值，应取其中最大的一个这样，因j-k最小，即模式申向右滑动的位数最小, 避免因右移造成的可能匹配的丢失23. 仅从两冷含有相等。