算法与数据结构考研试题精析第二版串答案概要VIP免费

第四章串一、选择题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．字符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）ch1<>midch//当读入不是分隔符&和输入结束符$时，继续读入字符（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)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函数定义如下：...