數(shù)據(jù)結(jié)構(gòu)練習(xí)

1、單元練習(xí)5-判斷題(下列各題，正確的請(qǐng)?jiān)谇懊娴睦ㄌ?hào)內(nèi)打；錯(cuò)誤的打x)(0 ) (1)串是n個(gè)字母的有限序列。(1 ) (2)串的數(shù)據(jù)元素是一個(gè)字符。(0)(3)串的長(zhǎng)度是指串中不同字符的個(gè)數(shù)。(0 ) (4)如果兩個(gè)串含有相同的字符，則說明它們相等。(0)(5)如果一個(gè)串中所有的字母均在另一個(gè)串中出現(xiàn)，則說明前者是后者的子串。(1 ) (6)串的堆分配存儲(chǔ)是一種動(dòng)態(tài)存儲(chǔ)結(jié)構(gòu)。(0 ) (7) “DT”是 “DATA” 的子串。(0 ) (8)串中任意個(gè)字符組成的子序列稱為該串的子串。(1 ) (9)子串的定位運(yùn)算稱為模式匹配。(1 ) (10)在鏈串中為了提高存儲(chǔ)密度，應(yīng)該增大結(jié)點(diǎn)的大小。二.

2、填空題由零個(gè)或多個(gè)字符組成的有限序列稱為 。字符串按存儲(chǔ)方式可以分為：順序存儲(chǔ)、鏈接存儲(chǔ)和 。串的順序存儲(chǔ)結(jié)構(gòu)簡(jiǎn)稱為 順序串。 串順序存儲(chǔ)非緊湊格式的缺點(diǎn)是：浪費(fèi)存儲(chǔ)空間。串順序存儲(chǔ)緊湊格式的缺點(diǎn)是對(duì)串的字符處理。串鏈接存儲(chǔ)的優(yōu)點(diǎn)是插入、刪除方便，缺點(diǎn)的 訪問一組連續(xù)的字符比較困難在C或C+語言中，以字符 表示串值的終結(jié)?？崭翊拈L(zhǎng)度等于 空格字符的個(gè)數(shù)。在空串和空格串中，長(zhǎng)度不為0的是。 兩個(gè)串相等是指兩個(gè)串相長(zhǎng)度等，且對(duì)應(yīng)位置的字符都相等。 設(shè)S=My Music，貝0 LenStr(s)= 8。兩個(gè)字符串分別為:S1=Today is，S2=30 July,2005,ConcatStr(

3、S1,S2)的結(jié)果是： Today is 30 July,2005。求子 串函數(shù) SubStr(Today is 30 July,2005,13,4) 的結(jié) 果是：July 。在子串的定位運(yùn)算中，被匹配的主串稱為目標(biāo)串，子串稱為 模式串。 模式匹配成功的起始位置稱為：子串的起始位置。設(shè)S=abccdcdccbaa ， T=cdcc， 則第 6 次匹配成功。三.選擇題串是一種特殊的線性表A.可以順序存儲(chǔ)C.可以鏈接存儲(chǔ)某串的長(zhǎng)度小于一個(gè)常數(shù)，其特殊性體現(xiàn)在(B )。B數(shù)據(jù)元素是一個(gè)字符D.數(shù)據(jù)元素可以是多個(gè)字符 則采用(B )存儲(chǔ)方式最節(jié)省空間。A .鏈?zhǔn)紹.順序以下論述正確的是( CA.空串與

4、空格串是相同的C.空串是零個(gè)字符的串以下論述正確的是(BA.空串與空格串是相同的C.空格串是有空格的串(5 )以下論斷正確的是(AA.是空串，空格串C. somethingSomethig設(shè)有兩個(gè)串S1和S2，則StrCompareA.串連接C.求子串串的模式匹配是指(D)。C.D.B.D.堆結(jié)構(gòu)tel是Teleptone的子串 空串的長(zhǎng)度等于1ton是Teleptone的子串 空串的長(zhǎng)度等于1B. BEIJING是BEI JING的子串D. BIT=BITE(S1,S2)運(yùn)算稱作(DB.模式匹配D.串比較判斷兩個(gè)串是否相等對(duì)兩個(gè)串比較大小若字符串ABCDEFG采用鏈?zhǔn)酱鎯?chǔ)，假設(shè)每個(gè)指針占用2

5、個(gè)字節(jié)，若希望存儲(chǔ)密度50 %, 則每個(gè)結(jié)點(diǎn)應(yīng)存儲(chǔ)(AA2B設(shè)串 S1=I AM ，)個(gè)字符。C.D.找某字符在主串中第一次出現(xiàn)的位置找某子串在主串中第一次出現(xiàn)的第一個(gè)字符位置A. I AM3C.S2=A SDUDENT,B.4D. 5則 ConcatStr(S1,S2) = ( B )。I AM A SDUDENTC IAMASDUDENT(10 )設(shè) S=,則 LenStr ( S )(AA . 0B. 1(11 )設(shè)目標(biāo)串 T=AABBCCDDEA . 0B. 1(12 )設(shè)目標(biāo)串 T=AABBCCDDEEFFA. 2B . 3(13 )設(shè)目標(biāo)串 T=aabaababaabaa(D )次

6、。A. 1B. 9D.C.A SDUDENT2模式 P=ABCDEC. 2模式 P=CCDC. 4模式 P=abab,D. 3則該模式匹配的有效位移為(A )。D. 3則該模式匹配的有效位移為(D )。D. 5樸素匹配算法的外層循環(huán)進(jìn)行了(14)樸素模式匹配算法在最壞情況下的時(shí)間復(fù)雜度是(D )。A. O( m )S morning(15 )A.moB. O ( n)C. 0 ( m+n ) D. 0 ( m*n )執(zhí)行求子串函數(shù)SubStr(S,2,2)后的結(jié)果為(B )。B . or(16 )(AS1=good)。S2=morning”C. inD . ng執(zhí)行串連接函數(shù)ConcatStr(S1,S2)后的結(jié)果為A goodmorni