數(shù)據(jù)結(jié)構(gòu)考研復(fù)習(xí)題第4章串

第四 【北方交通大學(xué)2001一、 C．模式匹配是串的一種重要運(yùn)算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．求串【郵電大學(xué)2000二、 西安電子科技大學(xué)1996一、1已知串S=‘a(chǎn)aab’,其N(xiāo)ext數(shù)組值為（ 【西安電子科技大學(xué)1996一、7（2 串‘a(chǎn)babaaababaa’的next數(shù)組為 【中山大學(xué)1999一、7 字符串‘a(chǎn)babaabab’的nextval為 D．(0,1,0,1,0,1,0,1,1【郵電大學(xué)1999一、t‘a(chǎn)bcabbcabcabdab，nextval值為（11122111234567121112121123456112111001112231123456712110011101100170111021【郵電大學(xué)1998二、3 【西安電子科技大學(xué)2001應(yīng)用一、 設(shè)S為一個(gè)長(zhǎng)度為n的字符串，其中的字符各不相同，則S中的互異的非平凡子串（非空且不同于S本身）的個(gè)數(shù)為（ 【計(jì)算所1997】2n- 1F. 【工商大學(xué)2001一、6（3 【郵電大學(xué)一、4 【長(zhǎng)沙鐵道學(xué)院一、1(1 【大連海事大學(xué)20011、L(1分)空格串是指(1)，其長(zhǎng)度等于(2)2001 ?！局猩酱髮W(xué)1998一、5 稱(chēng)為該串的子串?！救A中理工大學(xué)2000一、‘STR）= 19984(2 20004模式串P=‘a(chǎn)baabcac’的next函數(shù)值序列為 【西安電子科技大學(xué)2001軟件 ?！距]電大學(xué)2001二、4TPTP(1)P(2)19985串是一種特殊的線性表其特殊性表現(xiàn)在(1)串的兩種最基本的方式是(2)(3)；兩個(gè)串相等的充分必要條件是(4)?！局袊?guó)礦業(yè)大學(xué)2000一、3（4 ?！疚靼搽娮涌萍即髮W(xué)1999軟件一、1（2U=‘yxyxyxyxy；t‘xxyASSIGN（S，UASSIGN（m‘ww求RECE（S，V，m）= ?！緰|學(xué)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下列算法實(shí)現(xiàn)求采用順序結(jié)構(gòu)的串s和串t的一個(gè)最長(zhǎng)公共子串。 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)}}【大學(xué)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‘a(chǎn)bcdefcdekt‘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)【理工大學(xué)1999三、2pascal（）處的字句寫(xiě)在答題紙上。W&M$MWW&和字符$,字符&WM$用作字符串的輸入結(jié)束符。例如,對(duì)輸入字符串a(chǎn)b&ba$11&12$ab&dd$&$,程序?qū)⒎謩e輸出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.【海運(yùn)學(xué)院1998七（15 s 元素x 判串s1和s2是否相等的函數(shù)； 返回聯(lián)接s1和s2之后的串； 返回s中第i個(gè)字符； 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注意：每個(gè)空格只填一個(gè)語(yǔ)句?！?996八199610(1199819962（1）(2雜度為T(mén)(m,n)。估算最優(yōu)的T(m,n)，并簡(jiǎn)要說(shuō)明理由?！竟I(yè)大學(xué)1996一、5(6T‘xxyxyTS2001四(819961((2函數(shù)值【郵電大學(xué)1997三（10三、t=‘a(chǎn)bcabaanextnextval1994一已知字符串‘cddcdececdea計(jì)算每個(gè)字符的next和nextval函數(shù)的值【郵電大學(xué)2000一2】nextval1999KMPbabababaanextnext（要求寫(xiě)出數(shù)組下標(biāo)起點(diǎn)2000二、2】求模式串T=‘a(chǎn)bcaabbac'函數(shù)Next(j)值?！疚靼步煌ù髮W(xué)1996四、4字符串的模式匹配KMP算法中,失敗函數(shù)(NEXT)是如何定義的?計(jì)算模式串‘a(chǎn)abaabaaabc’中各字符函數(shù)值.【石油大學(xué)1998一、2(10分)（5【1998八abcaacabac，學(xué)2000一（5S=‘a(chǎn)caabbcaababababcaP=‘babab【1997四j1234567taabbaab【郵電大學(xué)1992三、TYPESAR=ARRAY[1..m]OFINTEGER;PTY=ARRAY[1..m]OFCHAR;PROCEDUREnext2(P:PTY;VAR IF(K=0)OR THEN[IFTHENELSENEXTVAL[J]:=KELSEUNTIL大學(xué)1993二、2（6

|1kjp1pk1pjk1pj1next［j］=

其它情況是什么情況，為什么取next[j]=1?【郵電大學(xué)1994二KMPff19933（9）19972（8）2001619961997三、5(31999算，將s轉(zhuǎn)化為t?！颈狈浇煌ù髮W(xué)1996一、 山東科技大學(xué)2002一、6航空航天大學(xué)1997九(10)】輸入一個(gè)字符串，內(nèi)有數(shù)字和非數(shù)字字符，如：ak123x45617960?302gef4563，將其中連續(xù)的數(shù)字作為一個(gè)整體，依次存放到一數(shù)組ａ中，例如123放入ａ［０］,456放入ａ［１，……。編程統(tǒng)計(jì)其共有多少個(gè)整數(shù)，并輸出這些數(shù)【大學(xué)1998一2000五（15“ab123abc13!“ddddd【華技大學(xué)2001假設(shè)串的結(jié)構(gòu)如下所示編寫(xiě)算法實(shí)現(xiàn)串的置換操作【1995（15TYPEstrtp=RECORDch:ARRAY[1..maxlen]OFchar;【航空航天大學(xué)2001六1995PASCAL或Catoi(x).X0--9正負(fù)數(shù)的‘-’組成，返回值為整型數(shù)值?！菊憬髮W(xué)1994二(7S2,S3?！臼锥冀?jīng)貿(mào)大學(xué)1998三、8（15CONSTmaxlen=串被確認(rèn)的最大長(zhǎng)度TYPEstrtp=RECORDch:ARRAY[1..maxlen]OFchar; 輕工業(yè)大學(xué)19