《數據結構與算法》第四章?串考研真題精選一、選擇題.下面關于串的的敘述中，哪一個是不正確的？（）A.串是字符的有限序列B.空串是由空格構成的串C.模式匹配是串的一種重要運算D.串既可以采用順序存儲，也可以采用鏈式存儲2若串S尸'ABCDEFG',S2='9898',S3='###',S4='012345',執行concat（replace（S1,substr（S1,length（S2）,length（S3））,S3）,substr（S4,index（S2,'8'）,length（S2）））其結果為（）A.ABC###G0123B.ABCD###2345C.ABC###G2345D.ABC###2345E.ABC###G1234F.ABCD###1234G.ABC###01234TOC\o"1-5"\h\z.設有兩個串p和q,其中q是p的子串，求q在p中首次出現的位置的算法稱為()A.求子串B.聯接C.匹配D.求串長.已知串S='aaab',其next數組值為()。A.0123B.1123C.1231D.1211.串*ababaaababaa*的next數組為()。A.B.C.D..字符串4ababaababJ的nextval為()A.(0,1,0』,04,1,0/)B.(0,1,0J,0,2,1,0,1)C.(0,101,0,0,0,1,1)D.(0,1,0J,OJA1,1).模式串t=4abcaabbcabcaabdab5,該模式串的next數組的值為(7nextval數組的值為()。A.C.()11100131011007018.A.C.()11100131011007018.若串S='software',其子串的數目是（D.01I12231123456712F.01102131011021701)oA.8B.37C.36A.8B.37C.36A.8B.37C.36D.9.設S為一個長度為n的字符串，其中的字符各不相同，則S中的互異的非平凡子用（非TOC\o"1-5"\h\z空且不同于S本身）的個數為（）。A.2n-lB.n2C.(n2/2)+(n/2)D.(n2/2)+(n/2)-lE.（n2/2）-（n/2）-lF.其他情況10.串的長度是指（）B.串中所含字符的個數D.B.串中所含字符的個數D.串中所含非空格字符的個數C.串中所含不同字符的個數二、判斷題1.KMP算法的特點是在模式匹配時指示主串的指針不會變小。（）.設模式串的長度為明目標串的長度為n,當且處理只匹配一次的模式時，樸素的匹配（即子串定位函數）算法所花的時間代價可能會更為節省。（）.串是一種數據對象和操作都特殊的線性表。（）二、填空題.空格串是指（1）,其長度等于（2）..組成串的數據元素只能是,.一個字符串中稱為該串的子串o.INDEX('DATASTRUCTURE','STR')=。.設正文串長度為n,模式串長度為m,則串匹配的KMP算法的時間復雜度為。.模式串P=4abaabcacJ的next函數值序列為。.字符串'ababaaab'的nextval函數值為。.設T和P是兩個給定的串，在T中尋找等于P的子串的過程稱為(1)，又稱P為(2)。.串是一種特殊的線性表，其特殊性表現在(1):串的兩種最基本的存儲方式是q_、(3)：兩個串相等的充分必要條件是一(4)。.兩個字符串相等的充分必要條件是。.知U='xyxyxyxxyxy'；t='xxy'；ASSIGN(S,U)；ASSIGN(V,SUBSTR(S,INDEX(s,t),LEN(t)+1))；ASSIGN(m,'ww')求REPLACE(S,V,m)=。.實現字符串拷貝的函數strcpy為：voidstrcpy(char*s,char*t)/*copyttos*/{while()).下列程序判斷字符串s是否對稱，對稱則返回1,否則返回0；如f(“abba")返回1,f("abab")返回0；intf(￡D){inti=0,j=0;while(s[j])(2);for。--;i<j&&s[i]==s[j];i++,j-)；return((3))I四、應用題.名詞解釋：串.描述以下概念的區別：空格串與空串。.兩個字符串S1和S2的長度分別為m和n0求這兩個字符串最大共同子串算法的時間復雜度為T(m,n)。估算最優的T(m,n),并簡要說明理由。.設主串S='xxyxxxyxxxxyxyx',模式串T二'xxyxy'。請問：如何用最少的比較次數找到T在S中出現的位置？相應的比較次數是多少？.KMP算法(字符串匹配算法)較Brute(樸素的字符串匹配)算法有哪些改進？.己知模式串t=4abcaabbabcab,寫出用KMP法求得的每個字符對應的next和nextval函數值。.給出字符串1abacabaaad,在KMP算法中的next和nextval數組。.令1='abcabaa',求其next函數值和nextval函數值。.已知字符串<cddcdccecdea，,計算每個字符的next和nextval函數的值。.試利用KMP算法和改進算法分別求pl=4abaabaa?和p2=*aabbaab,的next函數和nextval函數。.已知KMP串匹配算法中子串為babababaa,寫出next數組改進后的next數組信息值(要求寫出數組下標起點)。.求模式串T='abcaabbac'的失敗函數Nexi(j)值。.字符串的模式匹配KMP算法中，失敗函數(NEXT)是如何定義的？計算模式串p=1aabaabaaabc'中各字符的失敗函數值..設字符串S=4aabaabaabaac'?P=*aabaac'(1)給出S和P的next值和nextval值：(2)若S作主串，P作模式串，試給出利用BF算法和KMP算法的匹配過程。.設目標為t='abcaabbabcabaacbacba',模式為p='abcabaa'(1)計算模式p的naxtval函數值；(5分)(2)不寫出算法，只畫出利用KMP算法進行模式匹配時每一趟的匹配過程。(5分)16.模式匹配算法是在主串中快速尋找模式的一種有效的方法，如果設主串的長度為m,模式的長度為n,則在主串中尋找模式的KMP算法的時間復雜性是多少？如果，某一模式P='abcaacabaca,,請給出它的NEXT函數值及NEXT函數的修正值NEXTVAL之值。.設目標為$=*abcaabbcaaabababaabca*,模式為P='babab',(1)手工計算模式P的nextval數組的值;(2)寫出利用求得的nextval數組，按KMP算法對目標S進行模式匹配的過程。.用無回溯的模式匹配法(KMP法)及快速的無回溯的模式匹配法求模式串T的next[j]值，添入下面表中：j1234567taabbaabkmp法求得的next[j]值快速無回溯法求得的ncxt[j]值串答案一、選擇題I.B2.E3.C4.A5.C6.A7.ID7.2F8.B9.D10.B二、判斷題三.填空題1.(1)由空格字符(ASCII值32)所組成的字符串(2)空格個數2.字符3.任意個連續的字符組成的子序列4.55.0(m+n)6.011223127.010104218.⑴模式匹配(2)模式串.(1)其數據元素都是字符(2)順序存儲(3)和鏈式存儲(4)串的長度相等且兩串中對應位置的字符也相等.兩串的長度相等且兩串中對應位置的字符也相等。.'xyxyxywwy'12.*s++=*t++或(*s++=*t++)!='\0'(1)charsfl(2)j++(3)i>=j四.應用題.串是零個至多個字符組成的有限序列。從數據結構角度講，串屬于線性結構。與線性表的特殊性在于串的元素是字符。.空格是一個字符，其ASCII碼值是32。空格串是由空格組成的串，其長度等于空格的個數?？沾遣缓魏巫址拇?，即空串的長度是零。

.最優的T(m,n)是O(n)。串S2是串SI的子串，且在S1中的位置是I。開始求出最大公共子串的長度恰是串S2的長度，一般情況下，T(m,n)=O(m*n)o.樸素的模式匹配(Brute—Force)時間復雜度是。(m*n),KMP算法有一定改進，時間復雜度達到。(m+n)。本題也可采用從后面匹配的方法，即從右向左掃描，比較6次成功。另一種匹配方式是從左往右掃描，但是先比較模式串的最后一個字符，若不等，則模式串后移；若相等，再比較模式串的第一個字符，若第一個字符也相等，則從模式串的第二個字符開始，向右比較，直至相等或失敗。若失敗，模式串后移，再重復以上過程。按這種方法，本題比較18次成功。.KMP算法主要優點是主串指針不回溯。當主串很大不能一次讀入內存且經常發生部分匹配時，KMP算法的優點更為突出..模式串的next函數定義如下：next[j]=根據此定義，可求解模式串I的next和nextval值如下:j123456789101112t串abcaabbabcabncxt[jj011122312345nextval[jJ011021301105.解法同上題6,其next和nextval值分另IJ為0112123422和0102010422。.解法同題6,i串的next和nextval函數值分別為0111232和0110132。.解法同題6,其next和nextval值分別為011123⑵231和。.pl的next和nextval值分別為：0112234和0102102；p2的next和nextval值分別為:0121123和0021002。.next數組值為011234567改進后的next數組信息值為010101017。12.011122312。nexi定義見題上面6和下面題20.串p的next函數值為：01212345634?⑴S的next與nextval值分別為和002002002009,p的next與nextval值分別為012123和002003值分別為012123和002003。(2)利用BF算法的匹配過程:第一趟匹配:aabaabaabaac利用KMP算法的匹配過程：第一趟匹配：aabaabaabaacaabaac(i=6,j=6)aabaac(i=6,j=6)第：趟匹配：aabaabaabaac(aa)baac第三趟匹配：aabaabaabaac(成功)(aa)baacaabaac(i=6.j=6)第—.趟匹配：aabaabaabaacaa(i=3j=2)第三趟匹配：aabaabaabaaca(i=3,j=I)第四趟匹配：aabaabaabaacaabaac(i=9,j=6)第五趟匹配：aabaabaabaacaa(i=6j=2)第六趟匹配：aabaabaabaaca(i=6,j=l)第七趟匹配：aabaabaabaac(成功)aabaac(i=13,j=7)(1)p的nextval函數值為0110132。(p的next函數值為011函32)。(2)利用KMP(改進的nexival)算法，每趟匹配過程如下：第一趟匹配：abcaabbabcabaacbacbaabcab(i=5,j=5)第二趟匹配：abcaabbabcabaacbacbaabc(i=7,j=3)第三趟匹配：abcaa