精品文檔第四章 串一、選擇題1下面關(guān)于串的的敘述中，哪一個(gè)是不正確的？（ ）【北方交通大學(xué) 2001 一、5（2分）】A串是字符的有限序列 B空串是由空格構(gòu)成的串C模式匹配是串的一種重要運(yùn)算 D串既可以采用順序存儲(chǔ)，也可以采用鏈?zhǔn)酱鎯?chǔ)2 若串S1=ABCDEFG, S2=9898 ,S3=#,S4=012345,執(zhí)行concat(replace(S1,substr(S1,length(S2),length(S3),S3),substr(S4,index(S2,8),length(S2)其結(jié)果為（ ）【北方交通大學(xué) 1999 一、5 （25/7分）】AABC#G0123 BABCD#2345 CABC#G2345 DABC#2345EABC#G1234 FABCD#1234 GABC#012343設(shè)有兩個(gè)串p和q，其中q是p的子串，求q在p中首次出現(xiàn)的位置的算法稱(chēng)為（ ）A求子串 B聯(lián)接 C匹配 D求串長(zhǎng)【北京郵電大學(xué) 2000 二、4（20/8分）】【西安電子科技大學(xué) 1996 一、1 （2分）】4已知串S=aaab,其N(xiāo)ext數(shù)組值為（ ）。【西安電子科技大學(xué) 1996 一、7 （2分）】A0123 B1123 C1231 D12115串 ababaaababaa 的next數(shù)組為（ ）。【中山大學(xué) 1999 一、7】A012345678999 B012121111212 C011234223456 D01230123223456字符串a(chǎn)babaabab 的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 )【北京郵電大學(xué) 1999 一、1（2分）】7模式串t=abcaabbcabcaabdab，該模式串的next數(shù)組的值為（ ），nextval數(shù)組的值為 （ ）。 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【北京郵電大學(xué) 1998 二、3 （2分）】8若串S=software,其子串的數(shù)目是（ ）。【西安電子科技大學(xué) 2001應(yīng)用 一、2（2分）】A8 B37 C36 D99設(shè)S為一個(gè)長(zhǎng)度為n的字符串，其中的字符各不相同，則S中的互異的非平凡子串（非空且不同于S本身）的個(gè)數(shù)為（ ）。【中科院計(jì)算所 1997 】A2n-1 Bn2 C(n2/2)+(n/2) D(n2/2)+(n/2)-1 E. (n2/2)-(n/2)-1 F.其他情況10串的長(zhǎng)度是指（ ）【北京工商大學(xué) 2001 一、6 （3分）】A串中所含不同字母的個(gè)數(shù) B串中所含字符的個(gè)數(shù)C串中所含不同字符的個(gè)數(shù) D串中所含非空格字符的個(gè)數(shù)二、判斷題1KMP算法的特點(diǎn)是在模式匹配時(shí)指示主串的指針不會(huì)變小。（ ）【北京郵電大學(xué) 2002 一、4 （1分）】2設(shè)模式串的長(zhǎng)度為m,目標(biāo)串的長(zhǎng)度為n，當(dāng)nm且處理只匹配一次的模式時(shí)，樸素的匹配（即子串定位函數(shù)）算法所花的時(shí)間代價(jià)可能會(huì)更為節(jié)省。（ ）【長(zhǎng)沙鐵道學(xué)院 1998 一、1 (1分)】3串是一種數(shù)據(jù)對(duì)象和操作都特殊的線(xiàn)性表。（ ）【大連海事大學(xué) 2001 1、L (1分)】二、填空題1空格串是指_(1)_，其長(zhǎng)度等于_(2)_。 【西安電子科技大學(xué) 2001軟件 一、4（2分）】2組成串的數(shù)據(jù)元素只能是_。 【中山大學(xué) 1998 一、5 （1分）】3一個(gè)字符串中_稱(chēng)為該串的子串 。 【華中理工大學(xué) 2000 一、3（1分）】4INDEX（DATASTRUCTURE， STR）=_。【福州大學(xué) 1998 二、4 (2分)】5設(shè)正文串長(zhǎng)度為n，模式串長(zhǎng)度為m，則串匹配的KMP算法的時(shí)間復(fù)雜度為_(kāi)。 【重慶大學(xué) 2000 一、4】6模式串P=abaabcac的next函數(shù)值序列為_(kāi)。【西安電子科技大學(xué) 2001軟件 一、6（2分）】7字符串a(chǎn)babaaab的nextval函數(shù)值為_(kāi)。 【北京郵電大學(xué) 2001 二、4 （2分）】8設(shè)T和P是兩個(gè)給定的串，在T中尋找等于P的子串的過(guò)程稱(chēng)為_(kāi)(1)_，又稱(chēng)P為_(kāi)(2)_。【西安電子科技大學(xué) 1998 二、5 （16/6分）】9串是一種特殊的線(xiàn)性表，其特殊性表現(xiàn)在_(1)_；串的兩種最基本的存儲(chǔ)方式是_(2)_、_(3)_；兩個(gè)串相等的充分必要條件是_(4)_。 【中國(guó)礦業(yè)大學(xué) 2000 一、3 （4分）】10兩個(gè)字符串相等的充分必要條件是_。 【西安電子科技大學(xué) 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）= _。 【東北大學(xué) 1997 一、1 (5分)】12實(shí)現(xiàn)字符串拷貝的函數(shù) strcpy為： void strcpy(char *s , char *t) /*copy t to s*/ while (_) 【浙江大學(xué) 1999 一、5 (3分)】13下列程序判斷字符串s 是否對(duì)稱(chēng)，對(duì)稱(chēng)則返回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+,j-); return(3)_) 【浙江大學(xué) 1999 一、6 (3分)】14下列算法實(shí)現(xiàn)求采用順序結(jié)構(gòu)存儲(chǔ)的串s和串t的一個(gè)最長(zhǎng)公共子串。程序（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)_; 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 (i=s.len) j=1;while(jlength) index=i; length=length1; (3)_; else (4) _; (5) _ 【上海大學(xué) 2000 一、2 （10分）】15完善算法：求KMP算法中next數(shù)組。PROC get _next(t:string,VAR next:ARRAY1.t.len OF integer);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;【中山大學(xué) 1998 四、1 （4分）】16下面函數(shù)index用于求t是否為s的子串，若是返回t第一次出現(xiàn)在s中的序號(hào)(從1開(kāi)始計(jì))，否則返回0。例如:s=abcdefcdek，t=cde,則indse(s,t)=3, index(s,aaa)=0 。已知t，s的串長(zhǎng)分別是mt,ms FUNC index(s,t,ms,mt);i:=1;j:=1;WHILE (ims) AND (jmt THEN return (5)_; ELSE return (6)_ENDF;【南京理工大學(xué) 1999 三、2 （6分）】17閱讀下列程序說(shuō)明和pascal程序,把應(yīng)填入其中的（ ）處的字句寫(xiě)在答題紙上。程序說(shuō)明：本程序用于判別輸入的字符串是否為如下形式的字符串:W&M$ 其中,子字符串M是子字符串W的字符反向排列,在此假定W不含有字符&和字符$,字符&用作W與M的分隔符,字符$用作字符串的輸入結(jié)束符。例如,對(duì)輸入字符串a(chǎn)b&ba$、11&12$、ab&dd$、&$,程序?qū)⒎謩e輸出Ok.(是),No.(不是)。程序PROGRAM accept(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 String:); match(an); IF an THEN BEGIN (5)_ IF (6)_ THEN writeln(Ok.) ELSE writeln(No.) END ELSE writeln(No.)END. 【上海海運(yùn)學(xué)院 1998 七 （15分）】18試?yán)孟铝袟：痛幕静僮魍瓿上率鎏羁疹}。initstack(s) 置s為空棧；push(s,x) 元素x入棧;pop(s) 出棧操作;gettop(s) 返回棧頂元素；sempty(s) 判棧空函數(shù)；setnull(st) 置串st為空串；length(st) 返回串st的長(zhǎng)度；equal(s1,s2) 判串s1和s2是否相等的函數(shù)；concat(s1,s2) 返回聯(lián)接s1和s2之后的串；sub(s,i,1) 返回s中第i個(gè)字符；empty(st) 判串空函數(shù)FUNC invert(pre:string; VAR exp:string):boolean;若給定的表達(dá)式的前綴式pre正確，本過(guò)程求得和它相應(yīng)的表達(dá)式exp并返回“true”，否則exp為空串，并返回“false”。已知原表達(dá)式中不包含括弧，opset為運(yùn)算符的集合。VAR s:stack; i,n:integer; succ:boolean; ch: char;BEGINi:=1; n:=length(pre); succ:=true;(1)_; (2)_;WHILE (i0），長(zhǎng)為n的子串有1個(gè)，長(zhǎng)為n-1的子串有2個(gè)，長(zhǎng)為n-2的子串有3個(gè)，長(zhǎng)為1的子串有n個(gè)。由于空串是任何串的子串，所以本題的答案為：8*（8+1）/2+1=37。故選B。但某些教科書(shū)上認(rèn)為“空串是任意串的子串”無(wú)意義，所以認(rèn)為選C。為避免考試中的二意性，編者認(rèn)為第9題出得好。二、判斷題1.2.3.三填空題1(1)由空格字符（ASCII值32）所組成的字符串(2)空格個(gè)數(shù)2字符3任意個(gè)連續(xù)的字符組成的子序列455.O(m+n)6011223127010104218(1)模式匹配(2)模式串9(1)其數(shù)據(jù)元素都是字符(2)順序存儲(chǔ)(3)和鏈?zhǔn)酱鎯?chǔ)(4)串的長(zhǎng)度相等且兩串中對(duì)應(yīng)位置的字符也相等10兩串的長(zhǎng)度相等且兩串中對(duì)應(yīng)位置的字符也相等。11xyxyxywwy12*s+=*t+或（*s+=*t+）!=013（1）chars (2) j+(3) i = j14題目分析本題算法采用順序存儲(chǔ)結(jié)構(gòu)求串s和串t的最大公共子串。串s用i指針（1=i=s.len）。t串用j指針（1=j=t.len）。算法思想是對(duì)每個(gè)i（1=i=s.len，即程序中第一個(gè)WHILE循環(huán)），來(lái)求從i開(kāi)始的連續(xù)字符串與從j（1=j=t.len，即程序中第二個(gè)HILE循環(huán)）開(kāi)始的連續(xù)字符串的最大匹配。程序中第三個(gè)（即最內(nèi)層）的WHILE循環(huán)，是當(dāng)s中某字符（si）與t中某字符（tj）相等時(shí)，求出局部公共子串。若該子串長(zhǎng)度大于已求出的最長(zhǎng)公共子串（初始為），則最長(zhǎng)公共子串的長(zhǎng)度要修改。程序（a）：（1）（i+k=s.len）AND(j+k=t.len) AND(si+k=tj+k)/如果在s和t的長(zhǎng)度內(nèi)，對(duì)應(yīng)字符相等，則指針k后移（加1）。（2）con:=false/s和t對(duì)應(yīng)字符不等時(shí)置標(biāo)記退出（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) 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.程序中遞歸調(diào)用（1）ch1midch/當(dāng)讀入不是分隔符&和輸入結(jié)束符$時(shí)，繼續(xù)讀入字符（2）ch1=ch2/讀入分隔符&后，判ch1是否等于ch2，得出真假結(jié)論。（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是運(yùn)算符，則入運(yùn)算符棧s。(5) sempty (s)/判棧s是否為空。(6) succ := false/若讀出ch是操作數(shù)且棧為空，則按出錯(cuò)處理。(7) exp(8)ch/若ch是操作數(shù)且棧非空，則形成部分中綴表達(dá)式。(9) exp(10) gettop(s) /取棧頂操作符。(11) pop(s)/操作符取出后，退棧。(12) sempty(s)/將pre的最后一個(gè)字符（操作數(shù)）加入到中綴式exp的最后。四應(yīng)用題串是零個(gè)至多個(gè)字符組成的有限序列。從數(shù)據(jù)結(jié)構(gòu)角度講，串屬于線(xiàn)性結(jié)構(gòu)。與線(xiàn)性表的特殊性在于串的元素是字符。空格是一個(gè)字符，其ASCII碼值是32。空格串是由空格組成的串，其長(zhǎng)度等于空格的個(gè)數(shù)。空串是不含任何字符的串，即空串的長(zhǎng)度是零。最優(yōu)的T(m,n)是O（n）。串S2是串S1的子串，且在S1中的位置是1。開(kāi)始求出最大公共子串的長(zhǎng)度恰是串S2的長(zhǎng)度，一般情況下，T(m,n) =O(m*n)。樸素的模式匹配（BruteForce）時(shí)間復(fù)雜度是（mn），KMP算法有一定改進(jìn)，時(shí)間復(fù)雜度達(dá)到（mn）。本題也可采用從后面匹配的方法，即從右向左掃描，比較次成功。另一種匹配方式是從左往右掃描，但是先比較模式串的最后一個(gè)字符，若不等，則模式串后移；若相等，再比較模式串的第一個(gè)字符，若第一個(gè)字符也相等，則從模式串的第二個(gè)字符開(kāi)始，向右比較，直至相等或失敗。若失敗，模式串后移，再重復(fù)以上過(guò)程。按這種方法，本題比較18次成功。KMP算法主要優(yōu)點(diǎn)是主串指針不回溯。當(dāng)主串很大不能一次讀入內(nèi)存且經(jīng)常發(fā)生部分匹配時(shí)，KMP算法的優(yōu)點(diǎn)更為突出模式串的next函數(shù)定義如下：nextj=根據(jù)此定義，可求解模式串t的next和nextval值如下：j12345678910 11 12t串a(chǎn)bcaabbabcabnextj011122312345nextvalj0110213011057解法同上題6，其next和nextval值分別為0112123422和0102010422。8解法同題6，t串的next和nextval函數(shù)值分別為0111232和0110132。9解法同題6，其next和nextval值分別為011123121231和011013020131。10p1的next和nextval值分別為：0112234和0102102；p2的next和nextval值分別為：0121123和0021002。11next數(shù)組值為011234567改進(jìn)后的next數(shù)組信息值為010101017。12011122312。13next定義見(jiàn)題上面6和下面題20。串p的next函數(shù)值為：01212345634。14（1）S的next與nextval值分別為012123456789和002002002009，p的next與nextval值分別為012123和002003。（2）利用BF算法的匹配過(guò)程：利用KMP算法的匹配過(guò)程：第一趟匹配：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函數(shù)值為0110132。（p的next函數(shù)值為0111232）。（2）利用KMP(改進(jìn)的nextval)算法，每趟匹配過(guò)程如下：第一趟匹配：abcaabbabcabaacbacbaabcab(i=5,j=5)第二趟匹配：abcaabbabcabaacbacbaabc(i=7,j=3)第三趟匹配：abcaabbabcabaacbacbaa(i=7,j=1)第四趟匹配：abcaabbabcabaac bacba(成功)abcabaa(i=15,j=8)16KMP算法的時(shí)間復(fù)雜性是O（m+n）。p的next和nextval值分別為01112212321和01102201320。17（1）p的nextval函數(shù)值為01010。（next函數(shù)值為01123）（2）利用所得nextval數(shù)值，手工模擬對(duì)s的匹配過(guò)程，與上面16題類(lèi)似，為節(jié)省篇幅，故略去。18模式串T的next和nextval值分別為0121123和0021002。19第4行的pJ=pK語(yǔ)句是測(cè)試模式串的第J個(gè)字符是否等于第K個(gè)字符，如是，則指針J和K均增加1，繼續(xù)比較。第6行的pJ=pK語(yǔ)句的意義是，當(dāng)?shù)贘個(gè)字符在模式匹配中失配時(shí)，若第K個(gè)字符和第J個(gè)字符不等，則下個(gè)與主串匹配的字符是第K個(gè)字符；否則，若第K個(gè)字符和第J個(gè)字符相等，則下個(gè)與主串匹配的字符是第K個(gè)字符失配時(shí)的下一個(gè)（即NEXTVALK）。該算法在最壞情況下的時(shí)間復(fù)雜度O（m2）。20（1）當(dāng)模式串中第一個(gè)字符與主串中某字符比較不等（失配）時(shí)，next1=0表示模式串中已沒(méi)有字符可與主串中當(dāng)前字符si比較，主串當(dāng)前指針應(yīng)后移至下一字符，再和模式串中第一字符進(jìn)行比較。（2）當(dāng)主串第i個(gè)字符與模式串中第j個(gè)字符失配時(shí)，若主串i不回溯，則假定模式串第k個(gè)字符與主串第i個(gè)字符比較，k值應(yīng)滿(mǎn)足條件1kn-1），返回子串在主串的位置（i-j）。否則，當(dāng)im-n則為匹配失敗。intindex(chars,t,intm,n)/字符串s和t用一維數(shù)組存儲(chǔ)，其長(zhǎng)度分別為m和n。本算法求字符串t在字符串s中的第一次出現(xiàn)，如是，輸出子串在s中的位置，否則輸出0。inti=0,j=0;while(i=m-n & j=n-1)if(si=tj)i+;j+;/對(duì)應(yīng)字符相等，指針后移。elsei=i-j+1;j=0;/對(duì)應(yīng)字符不相等，I回溯，j仍為0。if(i=m-n & j=n) printf(“t在s串中位置是%d”,i-n+1);return(i-n+1);/匹配成功elsereturn(0); /匹配失敗/算法index結(jié)束main ()/主函數(shù)chars,t;intm,n,i;scanf(“%d%d”,&m,&n);/輸入兩字符串的長(zhǎng)度scanf(“%s”,s);/輸入主串scanf(“%s”,t);/輸入子串i=index(s,t,m,n);/程序結(jié)束程序討論因用C語(yǔ)言實(shí)現(xiàn)，一維數(shù)組的下標(biāo)從0開(kāi)始，m-1是主串最后一個(gè)字符的下標(biāo)，n-1是t串的最后一個(gè)字符的下標(biāo)。若匹配成功，最佳情況是s串的第0到第n-1個(gè)字符與t匹配，時(shí)間復(fù)雜度為o（n）；匹配成功的最差情況是，每次均在t的最后一個(gè)字符才失敗，直到s串的第m-n個(gè)字符成功，其時(shí)間復(fù)雜度為o（m-n）*n），即o（m*n）。失敗的情況是s串的第m-n個(gè)字符比t串某字符比較失敗，時(shí)間復(fù)雜度為o（m*n）。之所以串s的指針i最大到m-n，是因?yàn)樵趍-n之后,所剩子串長(zhǎng)度已經(jīng)小于子串長(zhǎng)度n，故不必再去比較。算法中未討論輸入錯(cuò)誤（如s串長(zhǎng)小于t串長(zhǎng)）。另外，根據(jù)子串的定義，返回值i-n+1是子串在主串中的位置，子串在主串中的下標(biāo)是i-n。2.問(wèn)題分析在一個(gè)字符串內(nèi)，統(tǒng)計(jì)含多少整數(shù)的問(wèn)題，核心是如何將數(shù)從字符串中分離出來(lái)。從左到右掃描字符串，初次碰到數(shù)字字符時(shí)，作