數(shù)據(jù)結(jié)構(gòu)串試題及答案

單項選擇題(每題2分,共10題)1.串是一種特殊的線性表,其特殊性體現(xiàn)在（）A.可以順序存儲B.數(shù)據(jù)元素是一個字符C.可以鏈式存儲D.數(shù)據(jù)元素可以是多個字符答案：B2.空串與空格串的區(qū)別是()A.沒有區(qū)別B.長度不同C.空串有長度D.空格串無長度答案：B3.串的長度是指()A.串中所含不同字母的個數(shù)B.串中所含字符的個數(shù)C.串中所含不同字符的個數(shù)D.串中所含非空格字符的個數(shù)答案：B4.串"ababaaab"的next數(shù)組值為()A.01234567B.01123422C.01212111D.01230123答案：B5.設串s1='ABCDEFG',s2='PQRST',函數(shù)CONCAT(x,y)返回x和y串的連接串,SUBSTR(s,i,j)返回串s的從序號i的字符開始的j個字符組成的子串,LEN(s)返回串s的長度,則CONCAT(SUBSTR(s1,2,LEN(s2)),SUBSTR(s1,LEN(s2),2))的結(jié)果串是()A.BCDEFGB.BCDEFEFC.BCPQRSTD.BCDEFE答案：B6.串的模式匹配是指()A.找兩個串是否相等B.找子串位置C.找串的長度D.找串中字符種類答案：B7.在串的順序存儲結(jié)構(gòu)中,其存儲密度()A.大于1B.小于1C.等于1D.小于等于1答案：C8.若串S='software',其子串的數(shù)目是()A.8B.37C.36D.9答案：B9.采用鏈存儲結(jié)構(gòu)的串稱為鏈串,若每個結(jié)點存放k個字符,那么存儲密度為()A.k/(k+1)B.k/(k+sizeof(指針))C.1D.0答案：B10.設有兩個串p和q,求q在p中首次出現(xiàn)的位置的運算稱作()A.連接B.模式匹配C.求子串D.求串長答案：B多項選擇題(每題2分,共10題)1.以下關(guān)于串的敘述正確的是(）A.串是字符的有限序列B.串可以采用順序存儲C.串可以采用鏈式存儲D.空串是長度為0的串答案:ABCD2.串的基本操作包括()A.賦值B.求長度C.串連接D.模式匹配答案:ABCD3.順序串的優(yōu)點有()A.存儲密度高B.操作簡單C.插入和刪除方便D.訪問速度快答案:ABD4.鏈串的特點有()A.存儲靈活B.插入和刪除操作效率高C.存儲密度可能較低D.訪問速度比順序串快答案:ABC5.以下哪些是求串長的函數(shù)(不同語言中)()A.strlenB.lengthC.sizeD.len答案:ABCD6.串模式匹配算法有()A.簡單匹配算法B.KMP算法C.BM算法D.Dijkstra算法答案:ABC7.若串s1和s2相等,則()A.長度相等B.對應位置字符相同C.所含字符種類相同D.都是空串答案:AB8.串的連接操作會改變()A.參與連接的串B.連接結(jié)果串的長度C.連接結(jié)果串的內(nèi)容D.原串的存儲結(jié)構(gòu)答案:BC9.空串和空格串在以下哪些方面有區(qū)別()A.定義B.長度C.存儲D.操作結(jié)果答案:ABCD10.對于串的操作,以下說法正確的是()A.可以對串進行遍歷B.可以從串中提取子串C.可以比較兩個串的大小D.串的操作與線性表操作完全相同答案:ABC判斷題(每題2分,共10題)1.空串和空格串是相同的概念。(）答案：錯2.串只能采用順序存儲結(jié)構(gòu)。()答案：錯3.兩個串相等的充要條件是長度相等且對應字符相同。()答案：對4.串的模式匹配就是比較兩個串是否相等。()答案：錯5.在順序串中,插入和刪除操作效率較高。()答案：錯6.鏈串的存儲密度一定小于順序串。()答案：對7.求串長操作的時間復雜度為O(n)。()答案：錯8.串連接操作會生成一個新的串。()答案：對9.模式匹配算法中,KMP算法效率一定高于簡單匹配算法。()答案：對10.可以對串進行排序操作。()答案：對簡答題(每題5分,共4題)1.簡述空串和空格串的區(qū)別。答案:空串長度為0,不含任何字符;空格串長度不為0,由一個或多個空格字符組成,存儲和含義上都有明顯不同。2.簡單說明串的模式匹配概念。答案:在主串中查找子串首次出現(xiàn)的位置。通過特定算法對比主串和子串字符序列,確定子串在主串中的起始位置。3.順序串和鏈串各有什么優(yōu)缺點?答案：順序串優(yōu)點是存儲密度高、訪問快；缺點是插入刪除效率低。鏈串優(yōu)點是插入刪除靈活；缺點是存儲密度低,可能需額外指針空間。4.簡述KMP算法相較于簡單匹配算法的優(yōu)勢。答案:簡單匹配算法每次匹配失敗需回溯主串指針,KMP算法利用部分匹配信息,不回溯主串指針,減少字符比較次數(shù),提高匹配效率。討論題(每題5分,共4題)1.在實際應用中,如何根據(jù)需求選擇順序串或鏈串?答案：若頻繁訪問元素且插入刪除操作少,選順序串,因其存儲密度高、訪問快。若插入刪除操作頻繁,選鏈串,雖存儲密度低,但插入刪除靈活。2.討論串模式匹配算法在文本編輯中的應用。答案:在文本編輯中,可用于查找特定文本內(nèi)容,如查找關(guān)鍵詞;替換操作也依賴模式匹配找到目標串位置后進行替換;還能實現(xiàn)文本定位,方便用戶快速跳轉(zhuǎn)。3.當處理超長字符串時,順序串和鏈串會面臨哪些問題?答案：順序串可能因內(nèi)存連續(xù)分配困難導致存儲問題,