第四章串答案.doc

第四章 串 一、选择题 1.B 2.E 3.C 4.A 5.C 6.A 7.1D 7.2F 8.B注 9.D 10.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．5 5.O(m+n) 6 7 8．(1)模式匹配 (2)模式串 9．(1)其数据元素都是字符(2)顺序存储(3)和链式存储(4)串的长度相等且两串中对应位置的字符也相等 10．两串的长度相等且两串中对应位置的字符也相等。 11．’xyxyxywwy’ 12．*s++=*t++ 或（*s++=*t++）!=‘\0’ 13．（1）char s[ ] (2) j++ (3) i = j 14．[题目分析]本题算法采用顺序存储结构求串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)0 17.程序中递归调用 （1）ch1midch //当读入不是分隔符和输入结束符$时，继续读入字符 （2）ch1=ch2 //读入分隔符后，判ch1是否等于ch2，得出真假结论。 （3）answer：=true （4）answer：=false （5）read（ch） （6）ch=endch 18．（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的最后。