数据结构第四章考试.题库-(含答案~).doc

|第四章 串一、选择题1下面关于串的的叙述中，哪一个是不正确的？（ ） 【北方交通大学 2001 一、5（2 分） 】A串是字符的有限序列 B空串是由空格构成的串C模式匹配是串的一种重要运算 D串既可以采用顺序存储，也可以采用链式存储2 若串 S1=ABCDEFG, S2=9898 ,S3=#,S4=012345,执行concat(replace(S1,substr(S1,length(S2),length(S3),S3),substr(S4,index(S2,8),length(S2)其结果为（ ） 【北方交通大学 1999 一、5 （25/7 分） 】AABC#G0123 BABCD#2345 CABC#G2345 DABC#2345EABC#G1234 FABCD#1234 GABC#012343设有两个串 p 和 q，其中 q 是 p 的子串，求 q 在 p 中首次出现的位置的算法称为（ ）A求子串 B联接 C匹配 D求串长【北京邮电大学 2000 二、4（20/8 分） 】 【西安电子科技大学 1996 一、1 （2 分） 】4已知串 S=aaab,其 Next 数组值为（ ） 。 【西安电子科技大学 1996 一、7 （2 分） 】A0123 B1123 C1231 D12115串 ababaaababaa 的 next 数组为（ ） 。 【中山大学 1999 一、7】A012345678999 B012121111212 C011234223456 D01230123223456字符串ababaabab 的 nextval 为（ ）A(0,1,0,1,04,1,0,1) B(0,1,0,1,0,2,1,0,1)C(0,1,0,1,0,0,0,1,1) D(0,1,0,1,0,1,0,1,1 )【北京邮电大学 1999 一、1（2 分） 】7模式串 t=abcaabbcabcaabdab，该模式串的 next 数组的值为（ ） ，nextval 数组的值为 （ ） 。 A0 1 1 1 2 2 1 1 1 2 3 4 5 6 7 1 2 B0 1 1 1 2 1 2 1 1 2 3 4 5 6 1 1 2C0 1 1 1 0 0 1 3 1 0 1 1 0 0 7 0 1 D0 1 1 1 2 2 3 1 1 2 3 4 5 6 7 1 2 E0 1 1 0 0 1 1 1 0 1 1 0 0 1 7 0 1 F0 1 1 0 2 1 3 1 0 1 1 0 2 1 7 0 1【北京邮电大学 1998 二、3 （2 分） 】8若串 S=software,其子串的数目是（ ） 。 【西安电子科技大学 2001 应用 一、2（2 分） 】A8 B37 C36 D99设 S 为一个长度为 n 的字符串，其中的字符各不相同，则 S 中的互异的非平凡子串（非空且不同于 S 本身）的个数为（ ） 。 【中科院计算所 1997 】A2n-1 Bn2 C(n2/2)+(n/2) D(n2/2)+(n/2)-1 E. (n2/2)-(n/2)-1 F.其他情况10串的长度是指（ ） 【北京工商大学 2001 一、6 （3 分） 】A串中所含不同字母的个数 B串中所含字符的个数C串中所含不同字符的个数 D串中所含非空格字符的个数二、判断题1KMP 算法的特点是在模式匹配时指示主串的指针不会变小。 （ ） 【北京邮电大学 2002 一、4 （1 分） 】2设模式串的长度为 m,目标串的长度为 n，当 nm 且处理只匹配一次的模式时，朴素的匹配（即子串定位函数）算法所花的时间代价可能会更为节省。 （ ） 【长沙铁道学院 1998 一、1 (1 分)】3串是一种数据对象和操作都特殊的线性表。 （ ） 【大连海事大学 2001 1、L (1 分)】二、填空题1空格串是指_(1)_，其长度等于_(2)_。 【西安电子科技大学 2001 软件 一、4（2 分） 】2组成串的数据元素只能是_。 【中山大学 1998 一、5 （1 分） 】3一个字符串中_称为该串的子串 。 【华中理工大学 2000 一、3（1 分） 】4INDEX（DATASTRUCTURE ， STR ）=_。 【福州大学 1998 二、4 (2 分)】5设正文串长度为 n，模式串长度为 m，则串匹配的 KMP 算法的时间复杂度为_。 【重庆大学 2000 一、4】|6模式串 P=abaabcac的 next 函数值序列为_。 【西安电子科技大学 2001 软件 一、6（2 分） 】7字符串ababaaab的 nextval 函数值为_。 【北京邮电大学 2001 二、4 （2 分） 】8设 T 和 P 是两个给定的串，在 T 中寻找等于 P 的子串的过程称为_(1)_，又称 P 为_(2)_。【西安电子科技大学 1998 二、5 （16/6 分） 】9串是一种特殊的线性表，其特殊性表现在_(1)_；串的两种最基本的存储方式是_(2)_、_(3)_；两个串相等的充分必要条件是_(4)_。 【中国矿业大学 2000 一、3 （4 分） 】10两个字符串相等的充分必要条件是_。 【西安电子科技大学 1999 软件 一、1 （2 分） 】11知 U=xyxyxyxxyxy；t=xxy ；ASSIGN（S，U） ；ASSIGN（V，SUBSTR（S，INDEX（s，t） ，LEN（t）+1） ） ；ASSIGN（m， ww）求 REPLACE（S，V，m）= _。 【东北大学 1997 一、1 (5 分)】12实现字符串拷贝的函数 strcpy为：void strcpy(char *s , char *t) /*copy t to s*/ while (_) 【浙江大学 1999 一、5 (3 分)】13下列程序判断字符串s 是否对称，对称则返回1，否则返回0；如 f(“abba“)返回1，f(“abab“)返回0； int f(1)_)int i=0,j=0;while (sj)(2)_;for(j-; ilength) THEN index:=i; length:=length1; (3)_; ELSE (4)_;(5) _;END;程序(b)void maxcomstr(orderstring *s,*t; int index, length)int i,j,k,length1,con;index=0;length=0;i=1;|while (ilength) index=i; length=length1; (3)_; else (4) _;(5) _ 【上海大学 2000 一、2 （10 分） 】15完善算法：求 KMP 算法中 next 数组。PROC get _next(t:string,VAR next:ARRAY1.t.len OF integer);BEGIN j:=1; k:=(1)_; next1:=0;WHILE jmt THEN return (5)_; ELSE return (6)_ENDF;【南京理工大学 1999 三、2 （6 分） 】17阅读下列程序说明和 pascal 程序,把应填入其中的（ ）处的字句写在答题纸上。程序说明：本程序用于判别输入的字符串是否为如下形式的字符串:WCONST midch= endch=$;VAR an:boolean; ch:char;PROCEDURE match(VAR answer: boolean);VAR ch1,ch2:char; f:boolean;BEGINread(ch1);|IF ch1= j14题目分析本题算法采用顺序存储结构求串 s 和串 t 的最大公共子串。串 s 用 i 指针（1midch /当读入不是分隔符&和输入结束符$时，继续读入字符（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) 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 的最后。四应用题串是零个至多个字符组成的有限序列。从数据结构角度讲，串属于线性结构。与线性表的特殊性在于串的元素是字符。空格是一个字符，其 ASCII 码值是 32。空格串是由空格组成的串，其长度等于空格的个数。空串是不含任何字符的串，即空串的长度是零。最优的 T(m,n)是 O（n）。串 S2 是串 S1 的子串，且在 S1 中的位置是 1。开始求出最大公共子串的长度恰是串 S2 的长度，一般情况下，T(m,n) =O(m*n)。朴素的模式匹配（BruteForce）时间复杂度是（mn），KMP 算法有一定改进，时间复杂度达到（mn）。本题也可采用从后面匹配的方法，即从右向左扫描，比较次成功。另一种匹配方式是从左往右扫描，但是先比较模式串的最后一个字符，若不等，则模式串后移；若相等，再比较模式串的第一个字符，若第一个字符也相等，则从模式串的第二个字符开始，向右比较，直至相等或失败。若失败，模式串后移，再重复以上过程。按这种方法，本题比较 18 次成功。KMP 算法主要优点是主串指针不回溯。当主串很大不能一次读入内存且经常发生部分匹配时，KMP 算法的优点更为突出模式串的 next 函数定义如下：|nextj=根据此定义，可求解模式串 t 的 next 和 nextval 值如下：j 1 2 3 4 5 6 7 8 9 10 11 12t 串 a b c a a b b a b c a bnextj 0 1 1 1 2 2 3 1 2 3 4 5nextvalj 0 1 1 0 2 1 3 0 1 1 0 57解法同上题 6，其 next 和 nextval 值分别为 0112123422 和 0102010422。8解法同题 6，t 串的 next 和 nextval 函数值分别为 0111232 和 0110132。9解法同题 6，其 next 和 nextval 值分别为 011123121231 和 011013020131。10p1 的 next 和 nextval 值分别为：0112234 和 0102102；p2 的 next 和 nextval 值分别为：0121123 和0021002。11next 数组值为 011234567 改进后的 next 数组信息值为 010101017。12011122312。13next 定义见题上面 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)第四趟匹配： abcaabbabcabaac bacba(成功) abcabaa(i=15,j=8)16KMP 算法的时间复杂性是 O（m+n）。p 的 next 和 nextval 值分别为 01112212321 和 01102201320。