《數(shù)據(jù)結(jié)構(gòu)與算法》第四章-串-考研真題

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

.最優(yōu)的T(m,n)是O(n)。串S2是串SI的子串，且在S1中的位置是I。開始求出最大公共子串的長度恰是串S2的長度，一般情況下，T(m,n)=O(m*n)o.樸素的模式匹配(Brute—Force)時(shí)間復(fù)雜度是。(m*n),KMP算法有一定改進(jìn)，時(shí)間復(fù)雜度達(dá)到。(m+n)。本題也可采用從后面匹配的方法，即從右向左掃描，比較6次成功。另一種匹配方式是從左往右掃描，但是先比較模式串的最后一個(gè)字符，若不等，則模式串后移；若相等，再比較模式串的第一個(gè)字符，若第一個(gè)字符也相等，則從模式串的第二個(gè)字符開始，向右比較，直至相等或失敗。若失敗，模式串后移，再重復(fù)以上過程。按這種方法，本題比較18次成功。.KMP算法主要優(yōu)點(diǎn)是主串指針不回溯。當(dāng)主串很大不能一次讀入內(nèi)存且經(jīng)常發(fā)生部分匹配時(shí)，KMP算法的優(yōu)點(diǎn)更為突出..模式串的next函數(shù)定義如下：next[j]=根據(jù)此定義，可求解模式串I的next和nextval值如下:j123456789101112t串a(chǎn)bcaabbabcabncxt[jj011122312345nextval[jJ011021301105.解法同上題6,其next和nextval值分另IJ為0112123422和0102010422。.解法同題6,i串的next和nextval函數(shù)值分別為0111232和0110132。.解法同題6,其next和nextval值分別為011123⑵231和。.pl的next和nextval值分別為：0112234和0102102；p2的next和nextval值分別為:0121123和0021002。.next數(shù)組值為011234567改進(jìn)后的next數(shù)組信息值為010101017。12.011122312。nexi定義見題上面6和下面題20.串p的next函數(shù)值為：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函數(shù)值為0110132。(p的next函數(shù)值為011函32)。(2)利用KMP(改進(jìn)的nexival)算法，每趟匹配過程如下：第一趟匹配：abcaabbabcabaacbacbaabcab(i=5,j=5)第二趟匹配：abcaabbabcabaacbacbaabc(i=7,j=3)第三趟匹配：abcaa