數(shù)據(jù)結(jié)構(gòu)與算法：第四章 考研真題精選

第三部分考研真題精選串部分一、選擇題1．下面關(guān)于串的的敘述中，哪一個是不正確的？（）A．串是字符的有限序列B．空串是由空格構(gòu)成的串C．模式匹配是串的一種重要運算D．串既可以采用順序存儲，也可以采用鏈?zhǔn)酱鎯?若串S1=‘ABCDEFG’,S2=‘9898’,S3=‘###’,S4=‘012345’concat(replace(S1,substr(S1,length(S2),length(S3)),S3),substr(S4,index(S2,‘8’其結(jié)果為（）A．ABC###G0123B．ABCD###2345C．ABC###G2345D．ABC###2345E．ABC###G1234F．ABCD###1234G．ABC###012343．設(shè)有兩個串p和q，其中q是p的子串，求q在p中首次出現(xiàn)的位置的算法稱為（）A．求子串B．聯(lián)接C．匹配D．求串長4．已知串S=‘a(chǎn)aab’,其Next數(shù)組值為（）。A．0123B．1123C．1231D．12115．串‘a(chǎn)babaaababaa’的next數(shù)組為（）。A．012345678999B．012121111212C．011234223456D．01230123223456．字符串‘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)7．模式串t=‘a(chǎn)bcaabbcabcaabdab’，該模式串的next數(shù)組的值為（），nextval數(shù)組的值為（）。A．01112211123456712B．01112121123456112C．01110013101100701D．01112231123456712E．01100111011001701F．011021310110217018．若串S=’software’,其子串的數(shù)目是（）。A．8B．37C．36D．99．設(shè)S為一個長度為n的字符串，其中的字符各不相同，則S中的互異的非平凡子串（非空且不同于S本身）的個數(shù)為（）。A．2n-1B．n2C．(n2/2)+(n/2)D．(n2/2)+(n/2)-1E.(n2/2)-(n/2)-1F.其他情況10．串的長度是指（）A．串中所含不同字母的個數(shù)B．串中所含字符的個數(shù)C．串中所含不同字符的個數(shù)D．串中所含非空格字符的個數(shù)二、判斷題1．KMP算法的特點是在模式匹配時指示主串的指針不會變小。（）2．設(shè)模式串的長度為m,目標(biāo)串的長度為n，當(dāng)n≈m且處理只匹配一次的模式時，樸素的匹配（即子串定位函數(shù)）算法所花的時間代價可能會更為節(jié)省。（）3．串是一種數(shù)據(jù)對象和操作都特殊的線性表。（）二、填空題1．空格串是指__(1)__，其長度等于___(2)__。2．組成串的數(shù)據(jù)元素只能是________。3．一個字符串中________稱為該串的子串。4．INDEX（‘DATASTRUCTURE’，‘STR’）=________。5．設(shè)正文串長度為n，模式串長度為m，則串匹配的KMP算法的時間復(fù)雜度為________。6．模式串P=‘a(chǎn)baabcac’的next函數(shù)值序列為________。7．字符串’ababaaab’的nextval函數(shù)值為________。8．設(shè)T和P是兩個給定的串，在T中尋找等于P的子串的過程稱為__(1)__，又稱P為__(2)__。9．串是一種特殊的線性表，其特殊性表現(xiàn)在__(1)__；串的兩種最基本的存儲方式是__(2)__、__(3)__；兩個串相等的充分必要條件是__(4)__。10．兩個字符串相等的充分必要條件是_______。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）=________。12．實現(xiàn)字符串拷貝的函數(shù)strcpy為：voidstrcpy(char*s,char*t)/*copyttos*/{while(________)}13．下列程序判斷字符串s是否對稱，對稱則返回1，否則返回0；如f("abba")返回1，f("abab")返回0；intf((1)________){inti=0,j=0;while(s[j])(2)________;for(j--;i<j&&s[i]==s[j];i++,j--);return((3)_______)}=4\*CHINESENUM3四、應(yīng)用題1．名詞解釋：串2．描述以下概念的區(qū)別：空格串與空串。3．兩個字符串S1和S2的長度分別為m和n。求這兩個字符串最大共同子串算法的時間復(fù)雜度為T(m,n)。估算最優(yōu)的T(m,n)，并簡要說明理由。4．設(shè)主串S=‘xxyxxxyxxxxyxyx’，模式串T=‘xxyxy’。請問：如何用最少的比較次數(shù)找到T在S中出現(xiàn)的位置？相應(yīng)的比較次數(shù)是多少？5．KMP算法(字符串匹配算法)較Brute(樸素的字符串匹配)算法有哪些改進?6．已知模式串t=‘a(chǎn)bcaabbabcab’寫出用KMP法求得的每個字符對應(yīng)的next和nextval函數(shù)值。7．給出字符串‘a(chǎn)bacabaaad’在KMP算法中的next和nextval數(shù)組。8．令t=‘a(chǎn)bcabaa’,求其next函數(shù)值和nextval函數(shù)值。9．已知字符串‘cddcdececdea’，計算每個字符的next和nextval函數(shù)的值。10．試利用KMP算法和改進算法分別求p1=‘a(chǎn)baabaa’和p2=‘a(chǎn)abbaab’的next函數(shù)和nextval函數(shù)。11．已知KMP串匹配算法中子串為babababaa,寫出next數(shù)組改進后的next數(shù)組信息值（要求寫出數(shù)組下標(biāo)起點）。12．求模式串T=‘a(chǎn)bcaabbac'的失敗函數(shù)Next(j)值。13．字符串的模式匹配KMP算法中,失敗函數(shù)(NEXT)是如何定義的?計算模式串p=‘a(chǎn)abaabaaabc’中各字符的失敗函數(shù)值.14．設(shè)字符串S=‘a(chǎn)abaabaabaac'，P=‘a(chǎn)abaac'（1）給出S和P的next值和nextval值；（2）若S作主串，P作模式串，試給出利用BF算法和KMP算法的匹配過程。15．設(shè)目標(biāo)為t=‘a(chǎn)bcaabbabcabaacbacba’,模式為p=‘a(chǎn)bcabaa’（1）計算模式p的naxtval函數(shù)值；（5分）（2）不寫出算法,只畫出利用KMP算法進行模式匹配時每一趟的匹配過程。（5分）16．模式匹配算法是在主串中快速尋找模式的一種有效的方法，如果設(shè)主串的長度為m，模式的長度為n，則在主串中尋找模式的KMP算法的時間復(fù)雜性是多少？如果，某一模式P=’abcaacabaca’，請給出它的NEXT函數(shù)值及NEXT函數(shù)的修正值NEXTVAL之值。17．設(shè)目標(biāo)為S=‘a(chǎn)bcaabbcaaabababaabca’，模式為P=‘babab’，（1）手工計算模式P的nextval數(shù)組的值；（2）寫出利用求得的nextval數(shù)組，按KMP算法對目標(biāo)S進行模式匹配的過程。18．用無回溯的模式匹配法（KMP法）及快速的無回溯的模式匹配法求模式串T的next[j]值，添入下面表中：j1