第4~5章和數(shù)組自測卷

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

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

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

4、序號i開始的j個字符組成的子串,len(s)返回串s的長度,則con(subs(s1,2, len(s2), subs(s1, len(s2), 2)的結(jié)果串是：A. BCDEFB . BCDEFG C . BCPQRSTD . BCDEFEF()4.假設(shè)有60行70列的二維數(shù)組 a160, 170以列序為主序順序存儲，其基地址為10000,每個元素占2個存儲單元，那么第32行第58列的元素a32,58的存儲地址為 。(無第0行第0列元 素)A. 16902B. 16904C. 14454D.答案A, B, C均不對()5.設(shè)矩陣A是一個對稱矩陣，為了節(jié)省存儲，將其下三角部分(如右圖所示)按行

5、序存放在一維數(shù)組B 1, n(n-1)/2 中，對下三角部分中任一元素aij(iwj),在一維數(shù)組B中下標(biāo)k的值是：A. i(i-1)/2+j-1B . i(i-1)/2+jC. i(i+1)/2+j-1D. i(i+1)/2+ja1,1a2,1a2,2Aan,1an ,2an,n6 .從供選擇的答案中，選出應(yīng)填入下面敘述?內(nèi)的最確切的解答,把相應(yīng)編號寫在答卷的對應(yīng)欄I有一個二維數(shù)組 A,行下標(biāo)的范圍是 0到8,列下標(biāo)的范圍是 1到5,每個數(shù)組元素用相鄰的4個字節(jié)存儲。存儲器按字節(jié)編址。假設(shè)存儲數(shù)組元素A0,1的第一個字節(jié)的地址是0。存儲數(shù)組A的最后一個元素的第一個字節(jié)的地址是A 。若按行存儲

6、，則 A3,5和A5,3的第一個字節(jié)的地址分別是 B 和 C 。若按列存儲，則 A7,1和A2,4的第一個字節(jié)的地址分別是 D 和E。供選擇的答案AE:2844 76 92108116132176184188答案：A= B = C = D = E=7 .從供選擇的答案中，選出應(yīng)填入下面敘述?內(nèi)的最確切的解答,把相應(yīng)編號寫在答卷的對應(yīng)欄I有一個二維數(shù)組 A,行下標(biāo)的范圍是 1到6,列下標(biāo)的范圍是 0到7,每個數(shù)組元素用相鄰的6個字節(jié)存儲，存儲器按字節(jié)編址。那么，這個數(shù)組的體積是A個字節(jié)。假設(shè)存儲數(shù)組元素A1,0的第一個字節(jié)的地址是0,則存儲數(shù)組A的最后一個元素的第一個字節(jié)的地址是B 。若按行存儲

7、,則A2,4的第一個字節(jié)的地址是C 。若按列存儲，則 A5,7的第一個字節(jié)的地址是D q供選擇的答案AD: 12 66 72 96 114 120 156 234 276282(11)283(12) 288答案：A= B = C = D = E=三、簡答題(每小題5分，共15分)1 .已知二維數(shù)組Am,m采用按行優(yōu)先順序存放，每個元素占K個存儲單元，并且第一個元素的存儲地址 為Loc(a11),請寫出求Loc(aij)的計算公式。如果采用列優(yōu)先順序存放呢？2 .遞歸算法比非遞歸算法花費更多的時間，對嗎？為什么?四、計算題(每題 5分，共20分)1 .【嚴(yán)題集 4.3】設(shè) s=' I A

8、M ASTUDENT , t= ' GOOD , q= ' WORKER , 求 Replace(s, ' STUDENT,q)和 Concat(SubString(s,6,2), Concat(t,SubString(s,7,8)2 .用三元組表表示下列稀疏矩陣:00000000000000000000020300080000009000000000(1)0006000000000(2)00500000000000000000000000005000030200000003 .下列各三元組表分別表示一個稀疏矩陣，試寫出它們的稀疏矩陣。6 4 61 2 22 1 12(

9、1) 3 1 344 45 3 66 1164551 1 124 9328356437五、算法設(shè)計題（每題1.【嚴(yán)題集4.12】10分，共30分）編寫一個實現(xiàn)串的置換操作Replace(&S, T, V)的算法。2.【嚴(yán)題集5.18】試設(shè)計一個算法，將數(shù)組 An中的元素A0至An-1循環(huán)右移k位，并要求只用一 個元素大小的附加存儲，元素移動或交換次數(shù)為O(n)附加題：利用 C 的庫函數(shù)strlen, strcpy (或 strncpy )寫一個算法void StrDelete(char *S,int t,int m) ，刪除串S中從位置i開始的連續(xù)的m個字符。若iRstrlen(S),則沒有字符被刪除；若 i+m > strlen(S),則將S 中從位置i 開始直至末尾的字符均被刪去。提示：