数据结构练习第四章串一、选择题1．函数substr(“DATASTRUCTURE”，5，9)的返回值为（）。
A. “STRUCTURE”B.“DATA”C. “ASTRUCTUR”D. “DATASTRUCTURE”2．字符串的长度是指（）。
A. 串中不同字符的个数B. 串中不同字母的个数C. 串中所含字符的个数D. 串中不同数字的个数3．两个字符串相等的充要条件是（）。
A. 两个字符串的长度相等B. 两个字符串中对应位置上的字符相等C. 同时具备(A)和(B)两个条件D. 以上答案都不对4．关于串的叙述中，正确的是（）A．空串是只含有零个字符的串B.空串是只含有空格字符的串C.空串是含有零个字符或含有空格字符的串D.串是含有一个或多个字符的有穷序列5．下面关于串的的叙述中，哪一个是不正确的？（）A．串是字符的有限序列 B．空串是由空格构成的串C．模式匹配是串的一种重要运算 D．串既可以采用顺序存储，也可以采用链式存储6．设有两个串S1和S2，求S2在S1中首次出现的位置的运算称作( ) A．求子串 B.判断是否相等 C．模型匹配 D.连接7．若串S=’software’,其子串的数目是( )。
A．8 B．37 C．36 D．98．串的长度是指（）A．串中所含不同字母的个数 B．串中所含字符的个数C．串中所含不同字符的个数 D．串中所含非空格字符的个数9．串是一种特殊的线性表，其特殊性体现在( )。
A．数据元素是一个字符 B. 可以顺序存储C. 数据元素可以是多个字符D. 可以链接存储10．下面关于串的的叙述中，哪一个是不正确的（B）A. 串是字符的有限序列B. 空串是由空格构成的串C. 模式匹配是串的一种重要运算D. 串既可以采用顺序存储，也可以采用链式存储11．若串＝‘software’，其非平凡子串（非空且不同于串本身）的数目是（C）A. 8 B. 37 C. 35 D. 912．串是一种特殊的线性表，其特殊性体现在（B）A. 可以顺序存储B. 数组元素是一个字符C. 可以连续存储D. 数据元素可以是多个字符13. 下面关于串的的叙述中，哪一个是不正确的？（B）A．串是字符的有限序列B．空串是由空格构成的串C．模式匹配是串的一种重要运算D．串既可以采用顺序存储，也可以采用链式存储二、填空题1．两个串是相等的，当且仅当两个串的长度相等且___对应位置_____的字符都相同。
2．串是一种特殊的线性表，串常见的存储结构有顺序存储和_____链式存储_两种方式。
3．空格串是指_______，其长度等于_______。
(1) 由空格字符（ASCII值32）所组成的字符串 (2)空格个数4．一个字符串中________称为该串的子串。
任意个连续的字符组成的子序列5．字符串’ababaaab’的nextval函数值为________。
010104216．串是一种特殊的线性表，其特殊性表现在__(1)__；串的两种最基本的存储方式是__(2)__、__(3)__；两个串相等的充分必要条件是__(4)__。
(1)其数据元素都是字符(2)顺序存储(3)和链式存储(4)串的长度相等且两串中对应位置的字符也相等7．下列程序读入无符号16进制数（出现的字母为小写），将其转换为十进制数输出。
请将程序空缺部分补全。
int f(char *s)｛int n=0, i;for(i=0;s［i］!=’\0’; i++) n=n*16+ (1) ;return n;｝main()｛char s[10];scanf(“%s”,s); printf(“%d\n”, (2) );｝(1)(s[i]>=97?s[i]-87:s[i]-48) ∥‘a’到’f’的ASCII码是97到102(2)f(s)8．下列算法实现求采用顺序结构存储的串s和串t的一个最长公共子串。
void maxcomstr(orderstring *s,*t, int index, length){int i,j,k,length1,con;index=0;length=0;i=1;while (i<=s.len){j=1;while(j<=t.len){ if (s[i]==t[j]){ k=1;length1=1;con=1;while(con)if (1) _ { length1=length1+1;k=k+1; } else (2) __;if (length1>length) { index=i; length=length1; }(3)____;}else (4) ___;}(5) __} }[题目分析]本题算法采用顺序存储结构求串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，即程序中第二个while循环）开始的连续字符串的最大匹配。
程序中第三个（即最内层）的while循环，是当s中某字符(s[i])与t中某字符(t[j])相等时，求出局部公共子串。
若该子串长度大于已求出的最长公共子串（初始为０），则最长公共子串的长度要修改。
(1)i+k<=s.len && j+k<=t.len && s[i+k]==t[j+k]∥如果在s和t的长度内，对应字符相等，则指针k 后移（加1）（2）con=0 ∥s和t对应字符不等时置标记退出（3）j=j+k ∥在t串中，从第j+k字符再与s[i]比较（4）j=j+1 ∥t串取下一字符(5) i=i+1 ∥s串指针i后移（加1）。
9．试利用下列栈和串的基本操作完成下述填空题。
initstack(s) 置s为空栈；push(s,x) 元素x入栈;pop(s) 出栈操作;gettop(s) 返回栈顶元素；sempty(s) 判栈空函数；setnull(st) 置串st为空串；length(st) 返回串st的长度；equal(s1,s2) 判串s1和s2是否相等的函数；concat(s1,s2) 返回联接s1和s2之后的串；sub(s,i,1) 返回s中第i个字符；empty(st) 判串空函数FUNC invert(pre:string; VAR exp:string):boolean;{若给定的表达式的前缀式pre正确，本过程求得和它相应的表达式exp并返回“true”，否则exp为空串，并返回“false”。
已知原表达式中不包含括弧，opset为运算符的集合。
}VAR s:stack; i,n:integer; succ:boolean; ch: char;BEGINi:=1; n:=length(pre); succ:=true;(1)__; (2)__;WHILE (i<n) AND succ DOBEGIN ch:=sub（pre,i,l）;IF (3)_ THEN (4)__ELSE IF (5)__THEN (6)_ELSE BEGINexp:=concat((7)___,(8)____);exp:=concat((9)___,(10)___);(11)__;END;i:=i+1END;IF (12)___THENBEGIN exp:=concat(exp,sub(pre,n,1)); invert:=true ENDELSE BEGIN setnull(exp); invert:=false ENDEND;注意：每个空格只填一个语句。
（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 的最后三、判断题1．( )子串“ABC”在主串“AABCABCD”中的位置为2。
T2．（）KMP算法的特点是在模式匹配时指示主串的指针不会变小。
√3．（）设模式串的长度为m,目标串的长度为n，当n≈m且处理只匹配一次的模式时，朴素的匹配（即子串定位函数）算法所花的时间代价可能会更为节省。
√4．（）串是一种数据对象和操作都特殊的线性表。
√5．（）串长度是指串中不同字符的个数。
×6．( ) 如果两个串含有相同的字符，则这两个串相等。
X7．（）KMP算法的最大特点是指示主串的指针不回溯。
√四、简答题1．KMP算法(字符串匹配算法)较Brute(朴素的字符串匹配)算法有哪些改进? 朴素的模式匹配（Brute－Force）时间复杂度是Ｏ(m＊n），KMP算法有一定改进，时间复杂度达到Ｏ(m＋n）。
主要优点是主串指针不回溯。
当主串很大不能一次读入内存且经常发生部分匹配时，KMP算法的优点更为突出。
2．给出字符串‘abacabaaad’在KMP算法中的next和nextval数组。
模式串的next函数定义如下：根据此定义，可求解模式串’abacabaaad’的next和nextval值如下：j 1 2 3 4 5 6 7 8 9 10t串 a b a c a b a a a dnext[j] 0 1 1 2 1 2 3 4 2 2nextval[j] 0 1 0 2 0 1 0 4 2 23．模式匹配算法是在主串中快速寻找模式的一种有效的方法，如果设主串的长度为m，模式的长度为n，则在主串中寻找模式的KMP算法的时间复杂性是多少？如果，某一模式 P=’abcaacabaca’，请给出它的NEXT函数值及NEXT函数的修正值NEXTVAL之值。
KMP算法的时间复杂性是O（m+n）。
p的next和nextval值分别为01112212321和01102201320。
4．设目标为S=‘abcaabbcaaabababaabca’，模式为P=‘babab’。
（1）手工计算模式P的nextval数组的值；（2）写出利用求得的nextval数组，按KMP算法对目标S进行模式匹配的过程。
（1）p的nextval函数值为01010。