數(shù)據(jù)結(jié)構(gòu)試題精選（4）-應(yīng)用題[1]_跨考網(wǎng)

1．名詞解釋：串 【大連海事 1996 一、10? (1分) 】【河海大學 1998 二、5（3分）】

　　2．描述以下概念的區(qū)別：空格串與空串?！?a target="_blank">大連海事大學 1996 三、2、（1） (2分)】

　　3．兩個字符串S1和S2的長度分別為m和n。求這兩個字符串最大共同子串算法的時間復(fù)雜度為T(m,n)。估算最優(yōu)的T(m,n)，并簡要說明理由。 【北京工業(yè)大學 1996 一、5 (6分)】

　　4．設(shè)主串S=‘xxyxxxyxxxxyxyx’，模式串T=‘xxyxy’。請問：如何用最少的比較次數(shù)找到T在S中出現(xiàn)的位置？相應(yīng)的比較次數(shù)是多少？ 【大連海事大學 2001 四? (8分)】

　　5．KMP算法(字符串匹配算法)較Brute(樸素的字符串匹配)算法有哪些改進?【大連海事大學1996三、1((2分)】

　　6．已知模式串t=‘a(chǎn)bcaabbabcab’寫出用KMP法求得的每個字符對應(yīng)的next和nextval函數(shù)值。

　　【北京郵電大學 1997? 三 （10分）】

　　7．給出字符串‘a(chǎn)bacabaaad’在KMP算法中的next和nextval數(shù)組?！颈本┼]電大學 2000 三、1（5分）】

　　8．令t=‘a(chǎn)bcabaa’,求其next 函數(shù)值和nextval函數(shù)值。 【北方交通大學 1994? 一 （6分）】

　　9．已知字符串‘cddcdececdea’，計算每個字符的next和nextval函數(shù)的值。【南京郵電大學 2000 一 2】

　　10．試利用KMP算法和改進算法分別求p1=‘a(chǎn)baabaa’和p2=‘a(chǎn)abbaab’的next函數(shù)和nextval函數(shù)。

　　【東南大學 1999 一、6（8分）】

　　11．已知KMP串匹配算法中子串為babababaa,寫出next數(shù)組改進后的next數(shù)組信息值（要求寫出數(shù)組下標起點）?！?a target="_blank">西南交通大學 2000 二、2】

　　12．求模式串T=‘a(chǎn)bcaabbac'? 的失敗函數(shù)Next(j)值。【西安交通大學 1996 四、4 (5分)】

　　13．字符串的模式匹配KMP算法中,失敗函數(shù)(NEXT)是如何定義的?計算模式串p=‘a(chǎn)abaabaaabc’中各字符的失敗函數(shù)值.【石油大學 1998? 一、2 (10分)】

???? 14．設(shè)字符串S=‘a(chǎn)abaabaabaac'，P=‘a(chǎn)abaac'

　?。?）給出S和P的next值和nextval值；

　?。?）若S作主串，P作模式串，試給出利用BF算法和KMP算法的匹配過程。

　　【北方交通大學1998二（15分）】

　　15．設(shè)目標為t=‘a(chǎn)bcaabbabcabaacbacba’,模式為p=‘a(chǎn)bcabaa’

　?。?）計算模式p的naxtval函數(shù)值；（5分）

　?。?）不寫出算法,只畫出利用KMP算法進行模式匹配時每一趟的匹配過程。（5分）

　　【清華大學 1998 八（10分）】

　　16．模式匹配算法是在主串中快速尋找模式的一種有效的方法，如果設(shè)主串的長度為m，模式的長度為n，則在主串中尋找模式的KMP算法的時間復(fù)雜性是多少？如果，某一模式???? P=’abcaacabaca’，請給出它的NEXT函數(shù)值及NEXT函數(shù)的修正值NEXTVAL之值?！?a target="_blank">上海交通大學 2000? 一 （5分）】

　　17．設(shè)目標為S=‘a(chǎn)bcaabbcaaabababaabca’，模式為P=‘babab’，

　?。?）手工計算模式P的nextval數(shù)組的值；(5分)

　?。?）寫出利用求得的nextval數(shù)組，按KMP算法對目標S進行模式匹配的過程。 (5分)

　　【清華大學 1997 四（10分）】