第四章串答案-展示頁
2025-07-04 03:50本頁面
【正文】 ac 第一趟匹配：aabaabaabaac aabaac(i=6,j=6) aabaac(i=6,j=6) 第二趟匹配： aabaabaabaac 第二趟匹配：aabaabaabaac aa(i=3,j=2) (aa)baac 第三趟匹配： aabaabaabaac 第三趟匹配：aabaabaabaac a(i=3,j=1) (成功) (aa)baac第四趟匹配： aabaabaabaac aabaac(i=9,j=6)第五趟匹配： aabaabaabaac aa(i=6,j=2)第六趟匹配： aabaabaabaac a(i=6,j=1)第七趟匹配： aabaabaabaac(成功) aabaac(i=13,j=7) 15．（1）p的nextval函數(shù)值為0110132。串p的next函數(shù)值為：01212345634。12．011122312。10．p1的next和nextval值分別為：0112234和0102102；p2的next和nextval值分別為：0121123和0021002。8．解法同題6，t串的next和nextval函數(shù)值分別為0111232和0110132?！。担甂MP算法主要優(yōu)點是主串指針不回溯。若失敗，模式串后移，再重復(fù)以上過程。本題也可采用從后面匹配的方法，即從右向左掃描，比較６次成功。開始求出最大公共子串的長度恰是串S2的長度，一般情況下，T(m,n) =O(m*n)。?。常顑?yōu)的T(m,n)是O（n）。空格串是由空格組成的串，其長度等于空格的個數(shù)。與線性表的特殊性在于串的元素是字符。四．應(yīng)用題?。保橇銈€至多個字符組成的有限序列。 (12 ) sempty(s) //將pre的最后一個字符（操作數(shù)）加入到中綴式exp的最后。 (9) exp (10) gettop(s) //取棧頂操作符。 (6) succ := false //若讀出ch是操作數(shù)且棧為空，則按出錯處理。 (4) push (s,ch) //如ch是運算符，則入運算符棧s?！? (2) setnull (exp) //串exp初始化為空串。 （3）answer：=true （4）answer：=false （5）read（ch） （6）ch=endch18．（1）initstack（s） /／棧s初始化為空棧。和輸入結(jié)束符$時，繼續(xù)讀入字符 （2）ch1=ch2 //讀入分隔符amp。 s[i+k]==t[j+k] //所有注釋同上（a） (2) con=0 (3) j+=k (4) j++ (5) i++15．（1）0 （2）next[k]16．（1）i：=i+1 （2）j:=j+1 (3)i:=ij+2 (4)j:=1。 j+k= amp?！〕绦颍╞）：(1) i+k= amp。程序（a）：（1）（i+k=）AND(j+k=) AND(s[i+k]=t[j+k]) //如果在s和t的長度內(nèi)，對應(yīng)字符相等，則指針k 后移（加1）。程序中第三個（即最內(nèi)層）的WHILE循環(huán)，是當(dāng)s中某字符（s［i］）與t中某字符（t［j］）相等時，求出局部公共子串。t串用j指針（1=j=）。11．’xyxyxywwy’ 12．*s++=*t++ 或（*s++=*t++）!=‘\0’13．（1）char s[ ] (2) j++ (3) i = j14．[題目分析]本題算法采用順序存儲結(jié)構(gòu)求串s和串t的最大公共子串。為避免考試中的二意性，編者認為第9題出得好。故選B。若字符串長度為n（n0），長為n的子串有1個，長為n1的子串有2個，長為n2的子串有3個，……，長為1的子串有n個。第四章 串 一、選擇題 注：子串的定義是：串中任意個連續(xù)的字符組成的子序列，并規(guī)定空串是任意串的子串，任意串是其自身的子串。由于空串是任何串的子串，所以本題的答案為：8*（8+1）/2+1=37。但某些教科書上認為“空串是任意串的子串”無意義，所以認為選C。二、判斷題1.√2.√3.√三．填空題1．(1) 由空格字符（ASCII值32）所組成的字符串 (2)空格個數(shù) 2．字符3．任意個連續(xù)的字符組成的子序列 4．5 (m+n)6．01122312 7．01010421 8．(1)模式匹配 (2)模式串9．(1)其數(shù)據(jù)元素都是字符(2)順序存儲(3)和鏈式存儲(4)串的長度相等且兩串中對應(yīng)位置的字符也相等10．兩串的長度相等且兩串中對應(yīng)位置的字符也相等。串s用i指針（1=i=）。算法思想是對每個i（1=i=，即程序中第一個WHILE循環(huán)），來求從i開始的連續(xù)字符串與從j（1=j=，即程序中第二個ＷHILE循環(huán)）開始的連續(xù)字符串的最大匹配。若該子串長度大于已求出的最長公共子串（初始為０），則最長公共子串的長度要修改。 （2）con:=false //s和t對應(yīng)字符不等時置標記退出 （3）j:=j+k //在t串中，從第j+k字符再與s[i]比較 （4）j:=j+1 //t串取下一字符（5）i：=i+1 //s串指針i后移（加1）。amp。amp。 (5)imt（或i:=ij+1） (6)0 （1）ch1midch //當(dāng)讀入不是分隔符amp。后，判ch1是否等于ch2，得出真假結(jié)論。 (3) ch in opset //判取出字符是否是操作符。 (5) sempty (s) //判棧s是否為空。 (7) exp (8)ch //若ch是操作數(shù)且棧非空，則形成部分中綴表達式。 (11) pop(s) //操作符取出后，退棧。從數(shù)據(jù)結(jié)構(gòu)角度講，串屬于線性結(jié)構(gòu)?！。玻崭袷且粋€字符，其ASCII碼值是32。空串是不含任何字符的串，即空串的長度是零。串S2是串S1的子串，且在S1中的位置是1?！。矗畼闼氐哪Ｊ狡ヅ洌˙rute－Force）時間復(fù)雜度是Ｏ（m＊n），KMP算法有一定改進，時間復(fù)雜度達到Ｏ（m＋n）。另一種匹配方式是從左往右掃描，但是先比較模式串的最后一個字符，若不等，則模式串后移；若相等，再比較模式串的第一個字符，若第一個字符也相等，則從模式串的第二個字符開始，向右比較，直至相等或失敗。按這種方法，本題比較18次成功。當(dāng)主串很大不能一次讀入內(nèi)存且經(jīng)常發(fā)生部分匹配時，KMP算法的優(yōu)點更為突出． ６．模式串的next函數(shù)定義如下： next［j］= 根據(jù)此定義，可求解模式串t的next和nextval值如下：j1 2 3 4 5 6 7 8 9 10 11 12 t串a(chǎn) b c a a b b a b c a b
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1