数据结构考研复习题第4章串

第四 【北方交通大学2001一、 C．模式匹配是串的一种重要运算D．串既可以采用顺序，也可以采用链2S1=‘ABCDEFG’,S2=‘9898’,S3=‘###’,S4=‘012345’,concat(re A．ABC###G0123B．ABCD###2345C．ABC###G2345D．ABC###2345E．ABC###G1234F．ABCD###1234G．ABC###01234 求子 D．求串【邮电大学2000二、 西安电子科技大学1996一、1已知串S=‘aaab’,其Next数组值为（ 【西安电子科技大学1996一、7（2 串‘ababaaababaa’的next数组为 【中山大学1999一、7 字符串‘ababaabab’的nextval为 D．(0,1,0,1,0,1,0,1,1【邮电大学1999一、t‘abcabbcabcabdab，nextval值为（11122111234567121112121123456112111001112231123456712110011101100170111021【邮电大学1998二、3 【西安电子科技大学2001应用一、 设S为一个长度为n的字符串，其中的字符各不相同，则S中的互异的非平凡子串（非空且不同于S本身）的个数为（ 【计算所1997】2n- 1F. 【工商大学2001一、6（3 【邮电大学一、4 【长沙铁道学院一、1(1 【大连海事大学20011、L(1分)空格串是指(1)，其长度等于(2)2001 。【中山大学1998一、5 称为该串的子串。【华中理工大学2000一、‘STR）= 19984(2 20004模式串P=‘abaabcac’的next函数值序列为 【西安电子科技大学2001软件 。【邮电大学2001二、4TPTP(1)P(2)19985串是一种特殊的线性表其特殊性表现在(1)串的两种最基本的方式是(2)(3)；两个串相等的充分必要条件是(4)。【中国矿业大学2000一、3（4 。【西安电子科技大学1999软件一、1（2U=‘yxyxyxyxy；t‘xxyASSIGN（S，UASSIGN（m‘ww求RECE（S，V，m）= 。【东学1997一、1(5分)strcpyvoidstrcpy(char*s,char*t)/*copytto{while 199953s10f("abba"1，f("abab")0；int while for(j--;i<j&&s[i]==s[j];i++,j--); 19996(3下列算法实现求采用顺序结构的串s和串t的一个最长公共子串。 str(VARs,t:orderstring;VARindex,length:integer);VARi,j,k,length1:integer;con:boolean;index:=0;length:=0;iWHILE(i<=s.len)DOWHILE(j<=t.len)[IF(s[i]=t[j])[k:=1;length1:=1;con:=true;WHILEconDOIF(1)THEN[length1:=length1+1;k:=k+1;]ELSE(2)_;IF(length1>length)THEN[index:=i;length:=length1;](3);

ELSE 程序 str(orderstring*s,*t;intindex,{inti,j,k,length1,con;while(i<=s.len){if(s[i]={k=1;length1=1;con=1;if(1)_{length1=length1+1;k=k+1;}else(2);if(length1>length){index=i;length=length1;} }else(4)}(5)}}【大学2000一、2PROCget_next(t:string,VARnext:ARRAY[1..t.len]OFinteger);j:=1;k:=(1);WHILEj<t.lenIFk=0ORt.ch[j]=t.ch[k]THENBEGINj:=j+1;k:=k+1;next[j]:=k;ENDELSEk:=(2);19981:s‘abcdefcdekt‘cdesmt,msFUNCindex(s,t,ms,mt);WHILE(i<ms)AND(j<mt)IFs[i]=t[j]THEN[(1);(2)ELSE[(3);(4)_IFj>mtTHENreturn(5) ;ELSEreturn(6)【理工大学1999三、2pascal（）处的字句写在答题纸上。W&M$MWW&和字符$,字符&WM$用作字符串的输入结束符。例如,对输入字符串ab&ba$11&12$ab&dd$&$,程序将分别输出PROGRAMaccept(input,output);CONSTmidch=’&’; PROCEDUREmatch(VARanswer:boolean);VARch1,ch2:char; IFch1<>endchTHENIF(1) read(ch2);answer:=(2)_ENDELSEanswer:=false wrin(‘EnterString:’);IFanTHEN(5) wrin(‘Ok.’)ELSEwri END.【海运学院1998七（15 s 元素x 判串s1和s2是否相等的函数； 返回联接s1和s2之后的串； 返回s中第i个字符； invert(pre:string;VAR“truefalseVARs:stack; ch:char;i:=1; (1);(2)WHILE(i<n)ANDsuccDOBEGINch:=sub（pre,i,l）;IF(3)_THEN(4)ELSEIF(5)THEN(6)_ELSEBEGINexp:=concat((7) exp:=concat((9),(10));(11);IF(12)BEGINexp:=concat(exp,sub(pre,n,1));invert:=trueENDELSEBEGINsetnull(exp);invert:=falseEND注意：每个空格只填一个语句。【1996八199610(1199819962（1）(2杂度为T(m,n)。估算最优的T(m,n)，并简要说明理由。【工业大学1996一、5(6T‘xxyxyTS2001四(819961((2函数值【邮电大学1997三（10三、t=‘abcabaanextnextval1994一已知字符串‘cddcdececdea计算每个字符的next和nextval函数的值【邮电大学2000一2】nextval1999KMPbabababaanextnext（要求写出数组下标起点2000二、2】求模式串T=‘abcaabbac'函数Next(j)值。【西安交通大学1996四、4字符串的模式匹配KMP算法中,失败函数(NEXT)是如何定义的?计算模式串‘aabaabaaabc’中各字符函数值.【石油大学1998一、2(10分)（5【1998八abcaacabac，学2000一（5S=‘acaabbcaababababcaP=‘babab【1997四j1234567taabbaab【邮电大学1992三、TYPESAR=ARRAY[1..m]OFINTEGER;PTY=ARRAY[1..m]OFCHAR;PROCEDUREnext2(P:PTY;VAR IF(K=0)OR THEN[IFTHENELSENEXTVAL[J]:=KELSEUNTIL大学1993二、2（6

|1kjp1pk1pjk1pj1next［j］=

其它情况是什么情况，为什么取next[j]=1?【邮电大学1994二KMPff19933（9）19972（8）2001619961997三、5(31999算，将s转化为t。【北方交通大学1996一、 山东科技大学2002一、6航空航天大学1997九(10)】输入一个字符串，内有数字和非数字字符，如：ak123x45617960?302gef4563，将其中连续的数字作为一个整体，依次存放到一数组ａ中，例如123放入ａ［０］,456放入ａ［１，……。编程统计其共有多少个整数，并输出这些数【大学1998一2000五（15“ab123abc13!“ddddd【华技大学2001假设串的结构如下所示编写算法实现串的置换操作【1995（15TYPEstrtp=RECORDch:ARRAY[1..maxlen]OFchar;【航空航天大学2001六1995PASCAL或Catoi(x).X0--9正负数的‘-’组成，返回值为整型数值。【浙江大学1994二(7S2,S3。【首都经贸大学1998三、8（15CONSTmaxlen=串被确认的最大长度TYPEstrtp=RECORDch:ARRAY[1..maxlen]OFchar; 轻工业大学19