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

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

2、填空題由零個或多個字符組成的有限序列稱為 。字符串按存儲方式可以分為：順序存儲、鏈接存儲和 。串的順序存儲結(jié)構(gòu)簡稱為 順序串。 串順序存儲非緊湊格式的缺點是：浪費存儲空間。串順序存儲緊湊格式的缺點是對串的字符處理。串鏈接存儲的優(yōu)點是插入、刪除方便，缺點的 訪問一組連續(xù)的字符比較困難在C或C+語言中，以字符 表示串值的終結(jié)?？崭翊拈L度等于 空格字符的個數(shù)。在空串和空格串中，長度不為0的是。 兩個串相等是指兩個串相長度等，且對應(yīng)位置的字符都相等。 設(shè)S=My Music，貝0 LenStr(s)= 8。兩個字符串分別為: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 。在子串的定位運算中，被匹配的主串稱為目標串，子串稱為 模式串。 模式匹配成功的起始位置稱為：子串的起始位置。設(shè)S=abccdcdccbaa ， T=cdcc， 則第 6 次匹配成功。三.選擇題串是一種特殊的線性表A.可以順序存儲C.可以鏈接存儲某串的長度小于一個常數(shù)，其特殊性體現(xiàn)在(B )。B數(shù)據(jù)元素是一個字符D.數(shù)據(jù)元素可以是多個字符 則采用(B )存儲方式最節(jié)省空間。A .鏈式B.順序以下論述正確的是( CA.空串與

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

5、個字節(jié)，若希望存儲密度50 %, 則每個結(jié)點應(yīng)存儲(AA2B設(shè)串 S1=I AM ，)個字符。C.D.找某字符在主串中第一次出現(xiàn)的位置找某子串在主串中第一次出現(xiàn)的第一個字符位置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è)目標串 T=AABBCCDDEA . 0B. 1(12 )設(shè)目標串 T=AABBCCDDEEFFA. 2B . 3(13 )設(shè)目標串 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)進行了(14)樸素模式匹配算法在最壞情況下的時間復(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