第四章串與數(shù)組測(cè)試題答案

1、第4章 串和數(shù)組 自測(cè)卷答案 姓名 班級(jí) 一、填空題（每空1分，共20分）1. 不包含任何字符（長(zhǎng)度為0）的串 稱為空串； 由一個(gè)或多個(gè)空格（僅由空格符）組成的串 稱為空白串。（對(duì)應(yīng)嚴(yán)題集4.1，簡(jiǎn)答題：簡(jiǎn)述空串和空格串的區(qū)別）2. 設(shè)S=“A;/document/Mary.doc”，則strlen(s= 20 , “/”的字符定位的位置為 3 。4. 子串的定位運(yùn)算稱為串的模式匹配； 被匹配的主串 稱為目標(biāo)串， 子串 稱為模式。5. 設(shè)目標(biāo)T=”abccdcdccbaa”，模式P=“cdcc”，則第 6 次匹配成功。6. 若n為主串長(zhǎng)，m為子串長(zhǎng)，則串的古典（樸素）匹配算法最壞的情況下需要比

2、較字符的總次數(shù)為 (n-m+1*m 。7. 假設(shè)有二維數(shù)組A6×8，每個(gè)元素用相鄰的6個(gè)字節(jié)存儲(chǔ)，存儲(chǔ)器按字節(jié)編址。已知A的起始存儲(chǔ)位置（基地址）為1000，則數(shù)組A的體積（存儲(chǔ)量）為 288 B ；末尾元素A57的第一個(gè)字節(jié)地址為 1282 ；若按行存儲(chǔ)時(shí)，元素A14的第一個(gè)字節(jié)地址為 (8+4×6+1000=1072 ；若按列存儲(chǔ)時(shí)，元素A47的第一個(gè)字節(jié)地址為 (6×74×61000）1276 。(注：數(shù)組是從0行0列還是從1行1列計(jì)算起呢？由末單元為A57可知，是從0行0列開(kāi)始！8. 設(shè)數(shù)組a160, 170的基地址為2048，每個(gè)元素占2個(gè)存儲(chǔ)

3、單元，若以列序?yàn)橹餍蝽樞虼鎯?chǔ)，則元素a32,58的存儲(chǔ)地址為 8950。答：不考慮0行0列，利用列優(yōu)先公式： LOC(aij=LOC(ac1，c2+(j-c2*(d1-c1+1+i-c1*L得：LOC(a32,58=2048+(58-1*(60-1+1+32-1*289509. 三元素組表中的每個(gè)結(jié)點(diǎn)對(duì)應(yīng)于稀疏矩陣的一個(gè)非零元素，它包含有三個(gè)數(shù)據(jù)項(xiàng)，分別表示該元素的 行下標(biāo) 、 列下標(biāo) 和 元素值 。10.求下列廣義表操作的結(jié)果：（1） GetHead【(a,b,(c,d】= (a, b ; /頭元素不必加括號(hào)（2） GetHead【GetTail【(a,b,(c,d】= (c,d ;（3）

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

5、(s返回串s的長(zhǎng)度，則con(subs(s1, 2, len(s2, subs(s1, len(s2, 2的結(jié)果串是：BCDEF BCDEFG BCPQRST BCDEFEF解：con(x,y返回x和y串的連接串，即 con(x,yABCDEFGPQRST；subs(s, i, j返回串s的從序號(hào)i開(kāi)始的j個(gè)字符組成的子串，則subs(s1, 2, len(s2subs(s1, 2, 5= BCDEF; subs(s1, len(s2, 2subs(s1, 5, 2= EF;所以con(subs(s1, 2, len(s2, subs(s1, len(s2, 2con( BCDEF, EF之連

6、接，即BCDEFEF（ A ）4.假設(shè)有60行70列的二維數(shù)組a160, 170以列序?yàn)橹餍蝽樞虼鎯?chǔ)，其基地址為10000，每個(gè)元素占2個(gè)存儲(chǔ)單元，那么第32行第58列的元素a32,58的存儲(chǔ)地址為 。（無(wú)第0行第0列元素）16902 16904 14454 答案A, B, C均不對(duì)答：此題與填空題第8小題相似。（57列×60行31行）×2字節(jié)10000=16902解：注意B的下標(biāo)要求從1開(kāi)始。先用第一個(gè)元素去套用，可能有B和C；再用第二個(gè)元素去套用B和C，B=2而C3（不符）；所以選B( B 5. 設(shè)矩陣 A 是一個(gè)對(duì)稱矩陣，為了節(jié)省存儲(chǔ)，將其下三角部分（如下圖所示）按行

7、序存放在一維數(shù)組 B 1, n(n-1/2 中，對(duì)下三角部分中任一元素 a i,j (i j, 在一維數(shù)組 B 中下標(biāo) k 的值是： i(i-1/2+j-1 i(i-1/2+j i(i+1/2+j-1 i(i+1/2+j6. 從供選擇的答案中，選出應(yīng)填入下面敘述 ？ 內(nèi)的最確切的解答，把相應(yīng)編號(hào)寫在答卷的對(duì)應(yīng)欄內(nèi)。有一個(gè)二維數(shù)組A，行下標(biāo)的范圍是0到8，列下標(biāo)的范圍是1到5，每個(gè)數(shù)組元素用相鄰的4個(gè)字節(jié)存儲(chǔ)。存儲(chǔ)器按字節(jié)編址。假設(shè)存儲(chǔ)數(shù)組元素A0,1的第一個(gè)字節(jié)的地址是0。存儲(chǔ)數(shù)組A的最后一個(gè)元素的第一個(gè)字節(jié)的地址是 A 。若按行存儲(chǔ)，則A3,5和A5,3的第一個(gè)字節(jié)的地址分別是 B 和 C

8、。若按列存儲(chǔ)，則A7,1和A2,4的第一個(gè)字節(jié)的地址分別是 D 和 E 。供選擇的答案：AE：28 44 76 92 108 116 132 176 184 188答案：ABCDE=8, 3, 5, 1, 67.有一個(gè)二維數(shù)組A，行下標(biāo)的范圍是1到6，列下標(biāo)的范圍是0到7，每個(gè)數(shù)組元素用相鄰的6個(gè)字節(jié)存儲(chǔ)，存儲(chǔ)器按字節(jié)編址。那么，這個(gè)數(shù)組的體積是 A 個(gè)字節(jié)。假設(shè)存儲(chǔ)數(shù)組元素A1,0的第一個(gè)字節(jié)的地址是0，則存儲(chǔ)數(shù)組A的最后一個(gè)元素的第一個(gè)字節(jié)的地址是 B 。若按行存儲(chǔ)，則A2,4的第一個(gè)字節(jié)的地址是 C 。若按列存儲(chǔ)，則A5,7的第一個(gè)字節(jié)的地址是 D 。供選擇的答案AD：12 66 72

9、96 114 120 156 234 276 282 （11）283 （12）288答案：ABCD=12, 10, 3, 9三、簡(jiǎn)答題（每小題5分，共15分）1. 【其他教材】KMP算法的設(shè)計(jì)思想是什么？它有什么優(yōu)點(diǎn)？答：其設(shè)計(jì)思想是，利用已經(jīng)部分匹配的結(jié)果來(lái)加快模式串的滑動(dòng)速度。主要優(yōu)點(diǎn)有二：一是在模式與主串已經(jīng)部分匹配的情況下，可以大大加快匹配速度；二是主串指針不回溯，可以使外設(shè)文件邊讀入邊匹配。2. 已知二維數(shù)組Am,m采用按行優(yōu)先順序存放，每個(gè)元素占K個(gè)存儲(chǔ)單元，并且第一個(gè)元素的存儲(chǔ)地址為L(zhǎng)oc(a11，請(qǐng)寫出求Loc(aij的計(jì)算公式。如果采用列優(yōu)先順序存放呢？解：公式教材已給出，此

10、處雖是方陣，但行列公式仍不相同；按行存儲(chǔ)的元素地址公式是： Loc(aij= Loc(a11 + (i-1*m+(j-1 * K按列存儲(chǔ)的元素地址公式是： Loc(aij= Loc(a11 + (j-1*m+(i-1 * K3.遞歸算法比非遞歸算法花費(fèi)更多的時(shí)間，對(duì)嗎？為什么？答：不一定。時(shí)間復(fù)雜度與樣本個(gè)數(shù)n有關(guān)，是指最深層的執(zhí)行語(yǔ)句耗費(fèi)時(shí)間，而遞歸算法與非遞歸算法在最深層的語(yǔ)句執(zhí)行上是沒(méi)有區(qū)別的，循環(huán)的次數(shù)也沒(méi)有太大差異。僅僅是確定循環(huán)是否繼續(xù)的方式不同，遞歸用棧隱含循環(huán)次數(shù)，非遞歸用循環(huán)變量來(lái)顯示循環(huán)次數(shù)而已。四、計(jì)算題（每題5分，共20分）1. 設(shè)s=I AM A STUDENT, t

11、=GOOD, q=WORKER, 求Replace(s,STUDENT,q 和Concat(SubString(s,6,2, Concat(t,SubString(s,7,8。解： Replace(s,STUDENT,qI AM A WORKER 因?yàn)?SubString(s,6,2A ；SubString(s,7,8 STUDENTConcat(t,SubString(s,7,8GOOD STUDENT所以Concat(SubString(s,6,2, Concat(t,SubString(s,7,8A GOOD STUDENT2. （P60 4-18）用三元組表表示下列稀疏矩陣： 解：參見(jiàn)填空題4. 三元素組表中的每個(gè)結(jié)點(diǎn)對(duì)應(yīng)于稀疏矩陣的一個(gè)非零元素，它包含有三個(gè)數(shù)據(jù)項(xiàng)，分別表示該元素的 行下標(biāo) 、 列下標(biāo) 和 元素值 。所以（1）可列表為： （2）可列表為：8866416-225943565353233685467858