【安徽大學 數(shù)據(jù)結(jié)構(gòu)】第45章習題.docx

1、習題四4. 1單項選擇題1. 空串與空格串是相同的，這種說法OA. 正確B.不正確2. 串是一中特殊的線性表，其特殊性體現(xiàn)在。A. 可以順序存儲B. 數(shù)據(jù)元素是一個字符C. 可以鏈接存儲D. 數(shù)據(jù)元素可以是多個字符3. 設有兩個串p和q,求q在P中首次出現(xiàn)的位置的運算稱作oA.連接B.模式匹配C.求子串D.求串長4. 設串 si二'ABCDEFG' ,s2二'PQRST'，函數(shù)con (x, y)返回 x和y 串的連接串,subs(s, i, j)返回串s的從序號i的字符開始的j個字符組成的子串,len (s)返回串s的長度，則con (subs (si, 2,

2、 len (s2), subs (si, len (s2), 2)的結(jié)果串是。A. BCDEFB. BCDEFGC. BCPQRSTD. BCDEFEF4.2填空題(將正確的答案填在相應的空中)1. 串的兩種最基本的存儲方式是o2. 兩個串相等的充分必要條件是o3. 空串是，其長度等于o4. 空格串是，其長度等于。5. 設 s='LAM曲TEACHER'，其長度是。4.3算法設計題：1. 編寫算法，從串s中刪除所有和串t相同的子串。2. 編寫算法，實現(xiàn)串的基本操作Replace (&S, T, V) o習題五 數(shù)組5. 1 單項選擇題(其中Ai. j表示下標從i到j)1

3、. 常對數(shù)組進行的兩種基本操作是oA.建立與刪除B.索引和修改C.查找和修改D.查找與索引2. 二維數(shù)組M的成員是6個字符(每個字符占一個存儲單元，即一個字節(jié))組成的串，行下標i的范圍從0到8,列下標j的范圍從1到10,則存放M至少需要個字節(jié)；M 的第8列和第5行共占個字節(jié)。 A. 90B. 180C. 240D. 540 A. 108B. 114C. 54D. 604. 數(shù)組A中，每個元素A的長度為3個字節(jié)，行下標i從1到8,列下標j從1到10,從首地址SA開始連續(xù)存放在存儲器內(nèi)，存放該數(shù)組至少需要的單元數(shù)是oA. 80B. 100C. 240D. 2705. 數(shù)組A中，每個元素A的長度為3

4、個字節(jié)，行下標i從1到8,列下標j從1到10,從首地址SA開始連續(xù)存放在存儲器內(nèi)，該數(shù)組按行存放時，元素A8 5的起始地址為oA. SA+141 B. SA+144 C. SA+222 D. SA+2256. 數(shù)組A中，每個元素A的長度為3個字節(jié)，行下標i從1到8,列下標j從1到10,從 首地址SA開始連續(xù)存放在存儲器內(nèi)，該數(shù)組按列存放時，元素A5 8的起始地址為A. SA+141 B. SA+180 C. SA+222 D. SA+2257若對n階對稱矩陣A以行序為主序方式將其下三角形的元素(包括主對角線上所有元素) 依次存放于一維數(shù)組B (1.(n(n+l)/2)中，則在B中確定aij (

5、i<j)的位置k的關(guān)系為 ()oA. i*(i-l)/2+j B. j*(j-l)/2+iC. i*(i+l)/2+j D. j*(j+l)/2+i8. 設A是n*n的對稱矩陣，將A的對角線及對角線上方的元素以列為主的次序存放在一維 數(shù)組Bl. . n(n+l)/2中，對上述任一元素aij(lWi, jWn,且iWj)在B中的位置為 ()oA. i(i-l)/2+jB. j(j-l)/2+iC. j(j-l)/2+i-lD.i(i-l)/2+j-19. AN, N是對稱矩陣，將下面三角(包括對角線)以行序存儲到一維數(shù)組TN (N+1) /2 中，則對任一上三角元素aij對應Tk的下標k是

6、()oA. i (i-1) /2+jB. j (j-1) /2+iC. i (j-i) /2+1D. j(i-1) /2+110. 設二維數(shù)組Al. . m, 1. . n(即川行n列)按行存儲在數(shù)組Bl. . m*n中，則二維數(shù) 組元素Ai, j在一維數(shù)組B中的下標為()oA. (i-l)*n+jB. (i-l)*n+jTC. i*(j-l)D.j*m+iT設每個整型數(shù)占2字節(jié)，則用三元組表11. 有一個100*90的稀疏矩陣，非0元素有10個,示該矩陣時，所需的字節(jié)數(shù)是()oA. 60B. 66C.12. 數(shù)組A0.4,-l.-3, 5. 7中含有元素的個數(shù)()oC.A. 55B. 453

7、6D. 1613用數(shù)組r存儲靜態(tài)鏈表，結(jié)點的next域指向后繼，工作指針j指向鏈中結(jié)點，使j沿 鏈移動的操作為()。A. j=rj. nextB.j=j+1C.j=j->nextD. j=rj-> next14. 對稀疏矩陣進行壓縮存儲目的是()oA.便于進行矩陣運算B.便于輸入和輸出C.節(jié)省存儲空間D.降低運算的時間復雜度15. 己知廣義表L=(x, y, z), a, (u, t, w),從L表中取出原子項t的運算是()。A. head (tail (tail (L)B. tail (head (head (tail (L)C. head (tail (head (tail (

8、L)D. head (tail (head (tail (tail (L)16. 己知廣義表LS= (a, b, c), (d, e, f),運用head和tail函數(shù)取出LS中原子e的運算是)oB.C.D.A. head(tail (LS) tail(head(LS) head(tail(head(tai 1 (LS) head(tai 1(tai 1(head (LS)o17. 廣義表A二(a, b, (c, d), (e, (f, g),則下面式子的值為(Head(Tail(Head(Tai 1(Tai 1(A)B. (d)D. dA. (g)C. c18.已知廣義表：A= (a, b), tai 1 (head(tai 1(C)二( A.(b)E.B=(A,A), C= (a, (b, A), B),求下列運算的結(jié)果: )oB. AbF.C.(A)D.19.A.(c, d)廣義表運算式Tail (a, b), (c, d)的操作結(jié)果是( (c, d)B.D. d)oc, dC.(L)操作后的結(jié)果為()oC.20.廣義表 L=(a, (b, c),進行 TailA. cB. b5.2填空題(將正確的答案填在相應的空中，其中Ai, j表示下標從i到j)1. 已知二維數(shù)組Am n采用行序為主方式存儲，每個元素占k個存儲單元，并且第一個 元素的存儲地址是LOC(AO 0),則