第四章 串 一、选择题 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但某些教科书上认为"空串是任意串的子串"无意义,所以认为选C为避免考试中的二意性,编者认为第9题出得好二、判断题1.√2.√3.√三．填空题1．<1> 由空格字符〔ASCII值32所组成的字符串 <2>空格个数 2．字符3．任意个连续的字符组成的子序列 4．5 5.O6．01122312 7．01010421 8．<1>模式匹配 <2>模式串9．<1>其数据元素都是字符<2>顺序存储<3>和链式存储<4>串的长度相等且两串中对应位置的字符也相等10．两串的长度相等且两串中对应位置的字符也相等11．’xyxyxywwy’ 12．*s++=*t++ 或〔*s++=*t++!=‘\0’13．〔1char s[ ] <2> j++ <3> i >= j14．[题目分析]本题算法采用顺序存储结构求串s和串t的最大公共子串。
串s用i指针〔1<=i<=s.lent串用j指针〔1<=j<=t.len算法思想是对每个i〔1<=i<=s.len,即程序中第一个WHILE循环,来求从i开始的连续字符串与从j〔1<=j<=t.len,即程序中第二个ＷHILE循环开始的连续字符串的最大匹配程序中第三个〔即最内层的WHILE循环,是当s中某字符〔s［i］与t中某字符〔t［j］相等时,求出局部公共子串若该子串长度大于已求出的最长公共子串〔初始为０,则最长公共子串的长度要修改程序〔a：〔1〔i+k<=s.lenAND AND //如果在s和t的长度内,对应字符相等,则指针k 后移〔加1 〔2con:=false //s和t对应字符不等时置标记退出 〔3j:=j+k //在t串中,从第j+k字符再与s[i]比较 〔4j:=j+1 //t串取下一字符〔5i：=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．〔10 〔2next[k]16．〔1i：=i+1 〔2j:=j+1 <3>i:=i-j+2 <4>j:=1; <5>i-mt〔或i:=i-j+1 <6>017.程序中递归调用 〔1ch1<>midch //当读入不是分隔符&和输入结束符$时,继续读入字符 〔2ch1=ch2 //读入分隔符&后,判ch1是否等于ch2,得出真假结论。
〔3answer：=true 〔4answer：=false 〔5read〔ch 〔6ch=endch18．〔1initstack〔s /／栈s初始化为空栈 <2> setnull //串exp初始化为空串 <3> ch in opset //判取出字符是否是操作符 <4> push //如ch是运算符,则入运算符栈s <5> sempty //判栈s是否为空 <6> succ := false //若读出ch是操作数且栈为空,则按出错处理 <7> exp <8>ch //若ch是操作数且栈非空,则形成部分中缀表达式 <9> exp <10> gettop //取栈顶操作符 <11> pop //操作符取出后,退栈 <12 > sempty //将pre的最后一个字符〔操作数加入到中缀式exp的最后四．应用题 １．串是零个至多个字符组成的有限序列从数据结构角度讲,串属于线性结构。
与线性表的特殊性在于串的元素是字符 ２．空格是一个字符,其ASCII码值是32空格串是由空格组成的串,其长度等于空格的个数空串是不含任何字符的串,即空串的长度是零 ３．最优的T是O〔n串S2是串S1的子串,且在S1中的位置是1开始求出最大公共子串的长度恰是串S2的长度,一般情况下,T =O ４．朴素的模式匹配〔Brute－Force时间复杂度是Ｏ〔m＊n,KMP算法有一定改进,时间复杂度达到Ｏ〔m＋n本题也可采用从后面匹配的方法,即从右向左扫描,比较６次成功另一种匹配方式是从左往右扫描,但是先比较模式串的最后一个字符,若不等,则模式串后移；若相等,再比较模式串的第一个字符,若第一个字符也相等,则从模式串的第二个字符开始,向右比较,直至相等或失败若失败,模式串后移,再重复以上过程按这种方法,本题比较18次成功 ５．KMP算法主要优点是主串指针不回溯当主串很大不能一次读入内存且经常发生部分匹配时,KMP算法的优点更为突出． ６．模式串的next函数定义如下： next［j］= 根据此定义,可求解模式串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 bnext[j]0 1 1 1 2 2 3 1 2 3 4 5nextval[j]0 1 1 0 2 1 3 0 1 1 0 57．解法同上题6,其next和nextval值分别为0112123422和0102010422。
8．解法同题6,t串的next和nextval函数值分别为0111232和011013210．p1的next和nextval值分别为：0112234和0102102；p2的next和nextval值分别为：0121123和002100211．next数组值为011234567 改进后的next数组信息值为01010101712．01112231213．next定义见题上面6和下面题20串p的next函数值为：01212345634 〔2利用BF算法的匹配过程： 利用KMP算法的匹配过程： 第一趟匹配： aabaabaabaac 第一趟匹配：aabaabaabaac aabaac aabaac 第二趟匹配： aabaabaabaac 第二趟匹配：aabaabaabaac aa baac 第三趟匹配： aabaabaabaac 第三趟匹配：aabaabaabaac a <成功> baac第四趟匹配： aabaabaabaac aabaac第五趟匹配： aabaabaabaac aa第六趟匹配： aabaabaabaac a第七趟匹配： aabaabaabaac<成功> aabaac 15．〔1p的nextval函数值为0110132。
〔p的next函数值为0111232〔2利用KMP<改进的nextval>算法,每趟匹配过程如下： 第一趟匹配： abcaabbabcabaacbacba abcab 第二趟匹配： abcaabbabcabaacbacba abc 第三趟匹配： abcaabbabcabaacbacba a第四趟匹配： abcaabbabcabaac bacba <成功> abcabaa16．KMP算法的时间复杂性是O〔m+np的next和nextval值分别为01112212321和0110220132017．〔1p的nextval函数值为01010〔next函数值为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〔m220．〔1当模式串中第一个字符与主串中某字符比较不等〔失配时,next[1]=0表示模式串中已没有字符可与主串中当前字符s[i]比较,主串当前指针应后移至下一字符,再和模式串中第一字符进行比较 〔2当主串第i个字符与模式串中第j个字符失配时,若主串i不回溯,则假定模式串第k个字符与主串第i个字符比较,k值应满足条件1
进行模式匹配时,若主串第i个字符与模式串第j个字符发生失配,主串指针i不回溯,和主串第i个字符进行比较的是模式串的第next[j]个字符模式串的next函数值,只依赖于模式串,和主串无关,可以预先求出该算法的技术特点是主串指针i不回溯在经常发生"部分匹配"和主串很大不能一次调入内存时,优点特别突出22．失败函数〔即next的值只取决于模式串自身,若第。