您現(xiàn)在的位置: 跨考網(wǎng)考研專業(yè)課正文

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

最后更新時間:2010-11-02 04:47:17
輔導(dǎo)課程:暑期集訓(xùn) 在線咨詢
復(fù)習緊張,焦頭爛額?逆風輕襲,來跨考秋季集訓(xùn)營,幫你尋方法,定方案! 了解一下>>

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分)】

跨考考研課程

班型 定向班型 開班時間 高定班 標準班 課程介紹 咨詢
秋季集訓(xùn) 沖刺班 9.10-12.20 168000 24800起 小班面授+專業(yè)課1對1+專業(yè)課定向輔導(dǎo)+協(xié)議加強課程(高定班)+專屬規(guī)劃答疑(高定班)+精細化答疑+復(fù)試資源(高定班)+復(fù)試課包(高定班)+復(fù)試指導(dǎo)(高定班)+復(fù)試班主任1v1服務(wù)(高定班)+復(fù)試面授密訓(xùn)(高定班)+復(fù)試1v1(高定班)
2023集訓(xùn)暢學 非定向(政英班/數(shù)政英班) 每月20日 22800起(協(xié)議班) 13800起 先行階在線課程+基礎(chǔ)階在線課程+強化階在線課程+真題階在線課程+沖刺階在線課程+專業(yè)課針對性一對一課程+班主任全程督學服務(wù)+全程規(guī)劃體系+全程測試體系+全程精細化答疑+擇校擇專業(yè)能力定位體系+全年關(guān)鍵環(huán)節(jié)指導(dǎo)體系+初試加強課+初試專屬服務(wù)+復(fù)試全科標準班服務(wù)

①凡本網(wǎng)注明“稿件來源:跨考網(wǎng)”的所有文字、圖片和音視頻稿件,版權(quán)均屬北京尚學碩博教育咨詢有限公司(含本網(wǎng)和跨考網(wǎng))所有,任何媒體、網(wǎng)站或個人未經(jīng)本網(wǎng)協(xié)議授權(quán)不得轉(zhuǎn)載、鏈接、轉(zhuǎn)帖或以其他任何方式復(fù)制、發(fā)表。已經(jīng)本網(wǎng)協(xié)議授權(quán)的媒體、網(wǎng)站,在下載使用時必須注明“稿件來源,跨考網(wǎng)”,違者本網(wǎng)將依法追究法律責任。

②本網(wǎng)未注明“稿件來源:跨考網(wǎng)”的文/圖等稿件均為轉(zhuǎn)載稿,本網(wǎng)轉(zhuǎn)載僅基于傳遞更多信息之目的,并不意味著再通轉(zhuǎn)載稿的觀點或證實其內(nèi)容的真實性。如其他媒體、網(wǎng)站或個人從本網(wǎng)下載使用,必須保留本網(wǎng)注明的“稿件來源”,并自負版權(quán)等法律責任。如擅自篡改為“稿件來源:跨考網(wǎng)”,本網(wǎng)將依法追究法律責任。

③如本網(wǎng)轉(zhuǎn)載稿涉及版權(quán)等問題,請作者見稿后在兩周內(nèi)速來電與跨考網(wǎng)聯(lián)系,電話:400-883-2220