數(shù)據(jù)結構串與數(shù)組廣義表自測題

1、第45章 串和數(shù)組 自測卷 姓名 班級 題號一二三四五總分題分2015201530100得分一、填空題（每空1分，共20分）1. 稱為空串； 稱為空白串。2. 設S=“A;/document/Mary.doc”，則strlen(s)= , “/”的字符定位的位置為 。4. 子串的定位運算稱為串的模式匹配； 稱為目標串， 稱為模式。5. 設目標T=”abccdcdccbaa”，模式P=“cdcc”，則第 次匹配成功。6. 若n為主串長，m為子串長，則串的古典匹配算法最壞的情況下需要比較字符的總次數(shù)為 。7. 假設有二維數(shù)組A68，每個元素用相鄰的6個字節(jié)存儲，存儲器按字節(jié)編址。已知A的起始存儲位

2、置（基地址）為1000，則數(shù)組A的體積（存儲量）為 ；末尾元素A57的第一個字節(jié)地址為 ；若按行存儲時，元素A14的第一個字節(jié)地址為 ；若按列存儲時，元素A47的第一個字節(jié)地址為 。8. 設數(shù)組a160, 170的基地址為2048，每個元素占2個存儲單元，若以列序為主序順序存儲，則元素a32,58的存儲地址為 。9. 三元素組表中的每個結點對應于稀疏矩陣的一個非零元素，它包含有三個數(shù)據(jù)項，分別表示該元素的 、 和 。10.求下列廣義表操作的結果：（1） GetHead【(a,b),(c,d)】= ; （2） GetHead【GetTail【(a,b),(c,d)】= ;（3） GetHead【

3、GetTail【GetHead【(a,b),(c,d)】= ;（4） GetTail【GetHead【GetTail【(a,b),(c,d)】= ;二、單選題（每小題1分，共15分）（ ）1. 串是一種特殊的線性表，其特殊性體現(xiàn)在： 可以順序存儲 數(shù)據(jù)元素是一個字符 可以鏈式存儲 數(shù)據(jù)元素可以是多個字符（ ）2. 設有兩個串p和q，求q在p中首次出現(xiàn)的位置的運算稱作： 連接 模式匹配 求子串 求串長（ ）3. 設串s1=ABCDEFG，s2=PQRST，函數(shù)con(x,y)返回x和y串的連接串，subs(s, i, j)返回串s的從序號i開始的j個字符組成的子串，len(s)返回串s的長度，則

4、con(subs(s1, 2, len(s2), subs(s1, len(s2), 2)的結果串是： BCDEF BCDEFG BCPQRST BCDEFEF（ ）4. 假設有60行70列的二維數(shù)組a160, 170以列序為主序順序存儲，其基地址為10000，每個元素占2個存儲單元，那么第32行第58列的元素a32,58的存儲地址為 。（無第0行第0列元素） 16902 16904 14454 答案A, B, C均不對( ) 5. 設矩陣A是一個對稱矩陣，為了節(jié)省存儲，將其下三角部分（如右圖所示）按行序存放在一維數(shù)組B 1, n(n-1)/2 中，對下三角部分中任一元素ai,j(ij), 在

5、一維數(shù)組B中下標k的值是：i(i-1)/2+j-1 i(i-1)/2+j i(i+1)/2+j-1 i(i+1)/2+j6. 從供選擇的答案中，選出應填入下面敘述 ？ 內的最確切的解答，把相應編號寫在答卷的對應欄內。有一個二維數(shù)組A，行下標的范圍是0到8，列下標的范圍是1到5，每個數(shù)組元素用相鄰的4個字節(jié)存儲。存儲器按字節(jié)編址。假設存儲數(shù)組元素A0,1的第一個字節(jié)的地址是0。存儲數(shù)組A的最后一個元素的第一個字節(jié)的地址是 A 。若按行存儲，則A3,5和A5,3的第一個字節(jié)的地址分別是 B 和 C 。若按列存儲，則A7,1和A2,4的第一個字節(jié)的地址分別是 D 和 E 。供選擇的答案AE：28 4

6、4 76 92 108 116 132 176 184 188答案：A B C D E= 7. 從供選擇的答案中，選出應填入下面敘述 ？ 內的最確切的解答，把相應編號寫在答卷的對應欄內。有一個二維數(shù)組A，行下標的范圍是1到6，列下標的范圍是0到7，每個數(shù)組元素用相鄰的6個字節(jié)存儲，存儲器按字節(jié)編址。那么，這個數(shù)組的體積是 A 個字節(jié)。假設存儲數(shù)組元素A1,0的第一個字節(jié)的地址是0，則存儲數(shù)組A的最后一個元素的第一個字節(jié)的地址是 B 。若按行存儲，則A2,4的第一個字節(jié)的地址是 C 。若按列存儲，則A5,7的第一個字節(jié)的地址是 D 。供選擇的答案AD：12 66 72 96 114 120 15

7、6 234 276 282 (11)283 （12）288答案：A B C D E= 三、簡答題（每小題5分，共15分）1. KMP算法的設計思想是什么？它有什么優(yōu)點？2. 已知二維數(shù)組Am,m采用按行優(yōu)先順序存放，每個元素占K個存儲單元，并且第一個元素的存儲地址為Loc(a11)，請寫出求Loc(aij)的計算公式。如果采用列優(yōu)先順序存放呢？ 3. 遞歸算法比非遞歸算法花費更多的時間，對嗎？為什么？四、計算題（每題5分，共20分）1. 【嚴題集4.3】設s=I AM A STUDENT, t=GOOD, q=WORKER, 求Replace(s,STUDENT,q) 和Concat(SubString(s,6,2), Concat(t,SubString(s,7,8)。2. 【嚴題集4.8】 已知主串s=ADBADABBAABADABBADADA,模式串pat=ADABBADADA。寫出模式串的nextval函數(shù)值，并由此畫出KMP算法匹配的全過程。3. 用三元組表表示下列稀疏矩陣： 4. 下列各三元組表分別表示一個稀疏矩陣，試寫出它們的稀疏矩陣。 五、算法設計題（每題10分，共30分）1. 【嚴題集4.12】 編寫一個實現(xiàn)串的置換操作Replace(&S, T, V)的算法。2. 【嚴題集