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

1、第四章 串一、选择题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#

2、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 c011234

3、223456 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

4、 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(

5、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串是一种数据对象和操作都特殊的线性表。（ ）【大连海事大学

6、 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字符

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，

8、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-; ij & si=sj; i+,

9、j-); return(3)_) 【浙江大学 1999 一、6 (3分)】14下列算法实现求采用顺序结构存储的串s和串t的一个最长公共子串。程序（a）procedure maxcomstr(var s,t : orderstring; var index,length : integer);var i,j,k,length1:integer; con:boolean;begin index :=0; length :=0; i :=1;while(i=s.len) do j:=1; while (jlength) then index:=i; length:=length1; (3)_; el

10、se (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 (i=s.len) j=1;while(jlength) 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 int

11、eger);begin j:=1; k:=(1)_; next1:=0; while jt.len do if k=0 or t.chj=t.chk then begin j:=j+1; k:=k+1; nextj:=k;endelse k:=(2)_;end;【中山大学 1998 四、1 （4分）】16下面函数index用于求t是否为s的子串，若是返回t第一次出现在s中的序号(从1开始计)，否则返回0。例如:s=abcdefcdek，t=cde,则indse(s,t)=3, index(s,aaa)=0 。已知t，s的串长分别是mt,ms func index(s,t,ms,mt);i:=1

12、;j:=1;while (ims) and (jmt then return (5)_; else return (6)_endf;【南京理工大学 1999 三、2 （6分）】17阅读下列程序说明和pascal程序,把应填入其中的（ ）处的字句写在答题纸上。程序说明：本程序用于判别输入的字符串是否为如下形式的字符串:w&m$ 其中,子字符串m是子字符串w的字符反向排列,在此假定w不含有字符&和字符$,字符&用作w与m的分隔符,字符$用作字符串的输入结束符。例如,对输入字符串ab&ba$、11&12$、ab&dd$、&$,程序将分别输出ok.(是),no.(不是)。程序program accep

13、t(input,output);const midch=&; endch=$;var an:boolean; ch:char;procedure match(var answer: boolean); var ch1,ch2:char; f:boolean;begin read(ch1); if ch1endch then if (1)_then begin match(f); if f then begin read(ch2); answer:=(2)_ end else answer:=false end else (3)_ else (4)_end;begin writeln(enter

14、 string:); match(an); if an then begin (5)_ if (6)_ then writeln(ok.) else writeln(no.) end else writeln(no.)end. 【上海海运学院 1998 七 （15分）】18试利用下列栈和串的基本操作完成下述填空题。initstack(s) 置s为空栈；push(s,x) 元素x入栈;pop(s) 出栈操作;gettop(s) 返回栈顶元素；sempty(s) 判栈空函数；setnull(st) 置串st为空串；length(st) 返回串st的长度；equal(s1,s2) 判串s1和s2是否

15、相等的函数；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)_;

16、(2)_;while (i0），长为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任意个连续的字符组成的子序列455.o(m+n)6011223127010104218(1)模式匹配(2)模式串9(1)其数据元素都是字符(2)顺序存储(3)和链式存储(4)串的长度相等且两

17、串中对应位置的字符也相等10两串的长度相等且两串中对应位置的字符也相等。11xyxyxywwy12*s+=*t+或（*s+=*t+）!=013（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中某字符（si）与t中某字符（tj）相等时，求

18、出局部公共子串。若该子串长度大于已求出的最长公共子串（初始为），则最长公共子串的长度要修改。程序（a）：（1）（i+k=s.len）and(j+k=t.len) and(si+k=tj+k)/如果在s和t的长度内，对应字符相等，则指针k后移（加1）。（2）con:=false/s和t对应字符不等时置标记退出（3）j:=j+k/在t串中，从第j+k字符再与si比较（4）j:=j+1/t串取下一字符（5）i：=i+1/s串指针i后移（加1）。程序（b）：(1) i+k=s.len & j+k=t.len & si+k=tj+k/所有注释同上（a）(2) con=0(3) j+=k(4) j+(5)

19、 i+15（1）0（2）nextk16（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=endch18（1）initstack（s）/栈s初始化为空栈。(2) setnull (exp)/串exp初始化为空串。(3) ch in opset/判取出字符是否是操作符。(

20、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

21、。空格串是由空格组成的串，其长度等于空格的个数。空串是不含任何字符的串，即空串的长度是零。最优的t(m,n)是o（n）。串s2是串s1的子串，且在s1中的位置是1。开始求出最大公共子串的长度恰是串s2的长度，一般情况下，t(m,n) =o(m*n)。朴素的模式匹配（bruteforce）时间复杂度是（mn），kmp算法有一定改进，时间复杂度达到（mn）。本题也可采用从后面匹配的方法，即从右向左扫描，比较次成功。另一种匹配方式是从左往右扫描，但是先比较模式串的最后一个字符，若不等，则模式串后移；若相等，再比较模式串的第一个字符，若第一个字符也相等，则从模式串的第二个字符开始，向右比较，直至相等或

22、失败。若失败，模式串后移，再重复以上过程。按这种方法，本题比较18次成功。kmp算法主要优点是主串指针不回溯。当主串很大不能一次读入内存且经常发生部分匹配时，kmp算法的优点更为突出模式串的next函数定义如下：nextj=根据此定义，可求解模式串t的next和nextval值如下：j12345678910 11 12t串abcaabbabcabnextj011122312345nextvalj0110213011057解法同上题6，其next和nextval值分别为0112123422和0102010422。8解法同题6，t串的next和nextval函数值分别为0111232和011013

23、2。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和0

24、02003。（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,

25、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+

26、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行的pj=pk语句是测试模式串的第j个字符是否等于第k个字符，如是，则指针j和k均增加1，继续比较。第6行的pj=pk语句的意义是，当第j个字符在模式匹配中失配时，若第k个字符和第j个字符不等，则下个与主串匹配的字符是第k个字符；否则，若第k个字符和

27、第j个字符相等，则下个与主串匹配的字符是第k个字符失配时的下一个（即nextvalk）。该算法在最坏情况下的时间复杂度o（m2）。20（1）当模式串中第一个字符与主串中某字符比较不等（失配）时，next1=0表示模式串中已没有字符可与主串中当前字符si比较，主串当前指针应后移至下一字符，再和模式串中第一字符进行比较。（2）当主串第i个字符与模式串中第j个字符失配时，若主串i不回溯，则假定模式串第k个字符与主串第i个字符比较，k值应满足条件1kn-1），返回子串在主串的位置（i-j）。否则，当im-n则为匹配失败。intindex(chars,t,intm,n)/字符串s和t用一维数组存储，其长

28、度分别为m和n。本算法求字符串t在字符串s中的第一次出现，如是，输出子串在s中的位置，否则输出0。inti=0,j=0;while(i=m-n & j=n-1)if(si=tj)i+;j+;/对应字符相等，指针后移。elsei=i-j+1;j=0;/对应字符不相等，i回溯，j仍为0。if(i=m-n & j=n) printf(“t在s串中位置是%d”,i-n+1);return(i-n+1);/匹配成功elsereturn(0); /匹配失败/算法index结束main ()/主函数chars,t;intm,n,i;scanf(“%d%d”,&m,&n);/输入两字符串的长度scanf(“%

29、s”,s);/输入主串scanf(“%s”,t);/输入子串i=index(s,t,m,n);/程序结束程序讨论因用c语言实现，一维数组的下标从0开始，m-1是主串最后一个字符的下标，n-1是t串的最后一个字符的下标。若匹配成功，最佳情况是s串的第0到第n-1个字符与t匹配，时间复杂度为o（n）；匹配成功的最差情况是，每次均在t的最后一个字符才失败，直到s串的第m-n个字符成功，其时间复杂度为o（m-n）*n），即o（m*n）。失败的情况是s串的第m-n个字符比t串某字符比较失败，时间复杂度为o（m*n）。之所以串s的指针i最大到m-n，是因为在m-n之后,所剩子串长度已经小于子串长度n，故不必再去比较。算法中未讨论输入错误（如s串长小于t串长）。另外，根据子串的定义，返回值i-n+1是子串在主串中的位置，子串在主串中的下标是i-n。2.问题分析在一个字符串内，统计含多少整数的问题，核心是如何将数从字符串中分离出来。从左到右扫描字符串，初次碰到数字字符时，作为一个整数