数据结构第4章串答案

郑大考研网祝您考研成功！可为你提供郑大各专业历年考研真题和相关笔记！郑大考研网论坛郑大考研网热线：13633846090第四章串一、选择题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．任意个连续的字符组成的子序列4．55.O(m+n)6．011223127．010104218．(1)模式匹配(2)模式串9．(1)其数据元素都是字符(2)顺序存储(3)和链式存储(4)串的长度相等且两串中对应位置的字符也相等10．两串的长度相等且两串中对应位置的字符也相等。11．’xyxyxywwy’12．*s++=*t++或（*s++=*t++）!=‘\0’13．（1）chars[](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中某字符（s［i］）与t中某字符（t［j］）相等时，求出局部公共子串。若该子串长度大于已求出的最长公共子串（初始为０），则最长公共子串的长度要修改。程序（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对应字符不等时置标记退出（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）ch1midch//当读入不是分隔符&和输入结束符$时，继续读入字符（2）ch1=ch2//读入分隔符&后，判ch1是否等于ch2，得出真假结论。（3）answer：=true（4）answer：=false（5）read（ch）（6）ch=endch郑大考研网祝您考研成功！可为你提供郑大各专业历年考研真题和相关笔记！郑大考研网论坛郑大考研网热线：1363384609018．（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是操作数且栈非空，则形成部分中缀表达式。(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)。４．朴素的模式匹配（Brute－Force）时间复杂度是Ｏ（m＊n），KMP算法有一定改进，时间复杂度达到Ｏ（m＋n）。本题也可采用从后面匹配的方法，即从右向左扫描，比较６次成功。另一种匹配方式是从左往右扫描，但是先比较模式串的最后一个字符，若不等，则模式串后移；若相等，再比较模式串的第一个字符，若第一个字符也相等，则从模式串的第二个字符开始，向右比较，直至相等或失败。若失败，模式串后移，再重复以上过程。按这种方法，本题比较18次成功。５．KMP算法主要优点是主串指针不回溯。当主串很大不能一次读入内存且经常发生部分匹配时，KMP算法的优点更为突出．６．模式串的next函数定义如下：next［j］=其它情况当此集合不空时‘且时当1}'...''...jk1|kmax{101111jkjkppppj根据此定义，可求解模式串t的next和nextval值如下：j123456789101112t串abcaabbabcabnext[j]011122312345nextval[j]0110213011057．解法同上题6，其next和nextval值分别为0112123422和0102010422。8．解法同题6，t串的next和nextval函数值分别为0111232和0110132。9．解法同题6，其next和nextval值分别为011123121231和011013020131。10．p1的next和nextval值分别为：0112234和0102102；p2的next和nextval值分别为：郑大考研网祝您考研成功！可为你提供郑大各专业历年考研真题和相关笔记！郑大考研网论坛郑大考研网热线：136338460900121123和0021002。11．next数组值为011234567改进后的next数组信息值为010101017。12．011122312。13．next定义见题上面6和下面题20。串p的next函数值为：01212345634。14．（1）S的next与nextval值分别为012123456789和002002002009，p的next与nextval值分别为012123和002003。（2）利用BF算法的匹配过程：利用KMP算法的匹配过程：第一趟匹配：aabaabaabaac第一趟匹配：aabaabaabaacaabaac(i=6,j=6)aabaac(i=6,j=6)第二趟匹配：aabaabaabaac第二趟匹配：aabaabaabaacaa(i=3,j=2)(aa)baac第三趟匹配：aabaabaabaac第三趟匹配：aabaabaabaaca(i=3,j=1)(成功)(aa)baac第四趟匹配：aabaabaabaacaabaac(i=9,j=6)第五趟匹配：aabaabaabaacaa(i=6,j=2)第六趟匹配：aabaabaabaaca(i=6,j=1)第七趟匹配：aabaabaabaac(成功)aabaac(i=13,j=7)15．（1）p的nextval函数值为0110132。（p的next函数值为0111232）。（2）利用KMP(改进的nextval)算法，每趟匹配过程如下：第一趟匹配：abcaabbabcabaacbacbaabcab(i=5,j=5)第二趟匹配：abcaabbabcabaacbacbaabc(i=7,j=3)第三趟匹配：abcaabbabcabaacbacbaa(i=7,j=1)第四趟匹配：abcaabbabcabaacbacba(成功)abcabaa(i=15,j=8)16．KMP算法的时间复杂性是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行的p[J]=p[K]语句是测试模式串的第J个字符是否等于第K个字符，如是，则指针J和K均增加1，继续比较。第6行的p[J]=p[K]语句的意义是，当第J个字符在模式匹配中失配时，若第K个字符和第J个字符不等，则下个与主串匹配的字符是第K个字符；否则，若第K个字符和第J个字符相等，则下个与主串匹配的字符是第K个字符失配时的下一个（即NEXTVAL[K]）。该算法在最坏情况下的时间复杂度O（m2）。20．（1）当模式串中第一个字符与主串中某字符比较不等（失配）时，next[1]=0表示模式郑大考研网祝您考研成功！可为你提供郑大各专业历年考研真题和相关笔记！郑大考研网论坛郑大考研网热线：13633846090串中已没有字符可与主串中当前字符s[i]比较，主串当前指针应后移至下一字符，再和模式串中第一字符进行比较。（2）当主串第i个字符与模式串中第j个字符失配时，若主串i不回溯，则假定模式串第k个字符与主串第i个字符比较，k值应满足条件1kj并且‘p１…pk-1’=‘pj-k+1…pj-1’，即k为模式串向后移动的距离，k值有多个，为了不使向右移动丢失可能的匹配，k要取大，由于max{k}表示移动的最大距离，所以取max{k}，k的最大值为j-1。（3）在上面两种情况外，发生失配时，主串指针i不回溯，在最坏情况下，模式串从第1个字符开始与主串第i个字符比较，以便不致丢失可能的匹配。21．这里失败函数f，即是通常讲的模式串的next函数，其定义见本章应用题的第6题。进行模式匹配时，若主串第i个字符与模式串第j个字符发生失配，主串指针i不回溯，和主串第i个字符进行比较的是模式串的第next[j]个字符。模式串的next函数值，只依赖于模式串，和主串无关，可以预先求出。该算法的技术特点是主串指针i不回溯。在经常发生“部分匹配”和主串很大不能一次调入内存时，优点特别突出。22．失败函数（即next）的值只取决于模式串自身，若第j个字符与主串第i个字符失配时，假定主串不回溯，模式串用第k（即next[j]）个字符与第i个相比，有‘p1…pk-1’=‘pj-k+1…pj-1’，为了不因模式串右移与主串第i个字符比较而丢失可能的匹配，对于上式中存在的多个k值，应取其中最大的一个。这样，因j-k最小，即模式串向右滑动的位数最小，避免因右移造成的可能匹配的丢失。23．仅从两串含有相等的字符，不能判定两串是否相等，两串相等的充分必要条件是两串长度相等且对应位置上的字符相同（即两串串值相等）。24．（1）s1和s2均为空串；（2）两串之一为空串；（3）两串串值相等（即两串长度相等且对应位置上的字符相同）。（4）两串中一个串长是另一个串长（包括串长为1仅有一个字符的情况）的数倍，而且长串就好象是由数个短串经过连接操作得到的。25、题中所给操作的含义如下：//：连接函数，将两个串连接成一个串substr（s,i,j）：取子串函数，从串s的第i个字符开始，取连续j个字符形成子串replace（