數(shù)組及其他線性結(jié)構(gòu)

1、數(shù)組及其他線性結(jié)構(gòu)一、單項選擇題（共 24題）1. 數(shù)組A中，每個元素 A的長度為3字節(jié)，行下標(biāo)i從1到8,列下標(biāo)j從1到10,從首 地址SA開始連續(xù)存放在存儲器內(nèi)，存放該數(shù)組至少需要的單元數(shù)是（）。A. 80B.100C.240D.270 答案：C2. 稀疏矩陣一般的壓縮存儲方式有兩種，即（）。A. 三元組和十字鏈表B.三元組和散列C.二維數(shù)組和三維數(shù)組D.散列和十字鏈表答案：A3. 串是一種特殊的線性表，其特殊性體現(xiàn)在串的（）。A. 數(shù)據(jù)元素可以順序存儲B.數(shù)據(jù)元素是一個字符C.數(shù)據(jù)元素可以連接存儲D.數(shù)據(jù)元素可以是多個字符答案：B4. 一個數(shù)組元素ai與（）的表示等價。D. a + i4

2、個存儲單元，該數(shù)組的首地）D. 1460A. &a + iB. *（a + i）C. *a + i答案：B5. 二維數(shù)組A1210采用行優(yōu)先存儲，每個數(shù)據(jù)元素占用址（即A00的地址）為1200，則A65的地址為（A.1400B.1404C.1372 答案：D6. 有一個 M N的矩陣A，若采用行優(yōu)先進行順序存儲，每個元素占用8個字節(jié)，則Aj （1乞i咗M ,1咗j N）元素的相對字節(jié)地址（相對首元素地址而言）為（）A.（i -1）N j） 8B. （i -1）Nj -1）8C.（i Nj -1）8D. （i -1）Nj 1）8答案：B7. 二維數(shù)組M的元素是4個字符（每個字符占一個存儲單元）組

3、成的串，行下標(biāo) i的范圍 從0到4，行下標(biāo)j的范圍從0到5，皿按行存儲時元素 M35的起始地址與 M按列存儲時元素（）的起始地址相同。A. M24B. M34C. M3 5D. M44答案：B8. 有一個N N的下三角矩陣A,若采用行優(yōu)先進行順序存儲，每個元素占用k個字節(jié)，則N, j i）元素的相對字節(jié)地址（相對首元素地址而言）為（）A. （i （i 1）/2 j -1） 4B. （i i/2 j） 4C. (i (i -1)/2 j -1) 4D. (i (i _1)/2 j) 4答案：C9. 下列敘述中正確的是（）。A. 數(shù)據(jù)的邏輯結(jié)構(gòu)與存儲結(jié)構(gòu)必定是一一對應(yīng)的B. 由于計算機存儲空間是向

4、量式的存儲結(jié)構(gòu)，因此，數(shù)據(jù)的存儲結(jié)構(gòu)一定是線性結(jié)構(gòu)C. 程序設(shè)計語言中的數(shù)組一般是順序存儲結(jié)構(gòu)，因此，利用數(shù)組只能處理線性結(jié)構(gòu)D. 以上3種說法都不對答案：CA.建立與刪除B.索引與修改C.查找和修改答案：C11.以下（）是C語言中abcd321ABCD的子串。A.abedB.321ABC.abcABC答案：D12.右串 S-software，其子串的數(shù)目是（）。A. 8B.37C.3610.對數(shù)組常進行的兩種基本操作是（）。D.查找與索引D. 21ABD. 9答案：C13.將一個A1:100,1:100的三對角矩陣，按行優(yōu)先存入一維數(shù)組A66,65（即該元素的下標(biāo)）在B數(shù)組中位置k為（）。A

5、. 198B.195C.197B1:298中，A中元素D. 196答案：B14.二維數(shù)組Amn按行序為主順序存放在內(nèi)存中，每個數(shù)組元素占 的地址計算公式是（）。1個存儲單元，則元素 ajA. LOC(a ij) = LOC(a 11) + (i - 1)*m+(j - 1)B. LOC(aij) = LOC(a11) + (j -1)*m+(i - 1)C. LOC(aij) = LOC(a11) + (i -1)*n+(j - 1)D. LOC(aij) = LOC(a11) + (j -1)*n+(i - 1)答案：C15. 串是一種特殊的線性表，其特殊性體現(xiàn)在()。A.可以順序存儲B.數(shù)

6、據(jù)元素是一個字符C.可以鏈接存儲D.數(shù)據(jù)元素可以是多個字符答案：B16. 設(shè)有兩個串p和q,求q在p中首次出現(xiàn)的位置的運算稱作()。A.連接B.模式匹配C.求子串D.求串長答案：B17. 設(shè)串 s仁ABCDEFG s2=PQRST,函數(shù) con(x,y)返回 x 和 y 串的連接串，subs(s,l,j)返回串s的從序號i的字符開始的j個字符組成的子串，len(s)返回串s的長度，則con (sub(s1,2,le n( s2),sub(s1,le n(s2),2)的結(jié)果是()OA. BCDEFB. BCDEFGC.BCPQRSTD.BCDEFEF答案：D18.常對數(shù)組進行的兩種基本操作是()

7、A.建立和刪除B.索引和修改C.查找和修改D.索引和查找答案：C19.稀疏矩陣一般的壓縮存儲方法有兩種，即()A.二維數(shù)組和三維數(shù)組B.三元組和散列C.三兀組和十字鏈表D.散列和十字鏈表答案：C20. 設(shè)串 s仁ABCDEFG s2=PQRST,函數(shù) con(x,y)返回 x 和 y 串的連接串，subs(s, i, j)返回串s的從序號i開始的j個字符組成的子串，len(s)返回串s的長度，則con(subs(s1,2, le n(s2), subs(s1, le n( s2), 2)的結(jié)果串是：()A. BCDEFB. BCDEFGC. BCPQRSTD. BCDEFEF答案：D21. 假

8、設(shè)有60行70列的二維數(shù)組a160, 170以列序為主序順序存儲，其基地址為10000,每個元素占 2個存儲單元，那么第 32行第58列的元素a32,58的存儲地址為（）。（無第0行第0列元素）A. 16902B. 16904C. 14454D.答案 A,B,C 均不對答案：A22. 設(shè)矩陣A是一個對稱矩陣，為了節(jié)省存儲，將其下三角部分（如右圖所示）按行序存放在一維數(shù)組B 1, n（n-1）/2 中，對下三角部分中任一元素am （i wj）,在一維數(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+j答案：B2

9、3. 從供選擇的答案中，選出應(yīng)填入下面敘述?內(nèi)的最確切的解答,把相應(yīng)編號寫在答卷的對應(yīng)欄內(nèi)。有一個二維數(shù)組A,行下標(biāo)的范圍是 0到8，列下標(biāo)的范圍是1到5,每個數(shù)組元素用相鄰的4個字節(jié)存儲。存儲器按字節(jié)編址。假設(shè)存儲數(shù)組元素A0,1的第一個字節(jié)的地址是0。存儲數(shù)組A的最后一個元素的第一個字節(jié)的地址是（）。若按行存儲，則A3,5和A5,3的第一個字節(jié)的地址分別是（）和（ ）。若按列存儲，則 A7,1和A2,4的第一個字節(jié)的地址分別是（ ）和（ ）。A. 28B. 44C. 76D. 92E. 108F. 116G.132H. 176I. 184J. 188答案：HCEAF24.從供選擇的答案中，

10、選出應(yīng)填入下面敘述?內(nèi)的最確切的解答，把相應(yīng)編號寫在答卷的對應(yīng)欄內(nèi)。有一個二維數(shù)組A，行下標(biāo)的范圍是1到6，列下標(biāo)的范圍是 0到乙每個數(shù)組兀素用相鄰的6個字節(jié)存儲，存儲器按字節(jié)編址。那么，這個數(shù)組的體積是(1)）個字節(jié)。假設(shè)存儲數(shù)組兀素A1,0的第一個字節(jié)的地址是0，則存儲數(shù)組A的最后一個兀素的第一個字節(jié)的地址是（辺）。若按行存儲，則A2,4的第一個字節(jié)的地址是（3）。若按列存儲，則A5,7的第一個字節(jié)的地址是(4)）。A. 12B. 66C. 72D. 96E. 114F. 120G. 156H. 234I. 276J. 282K. 283L. 288答案：LJBI二、填空題（共10題）1.

11、 空串是（），其長度等于（）?？崭翊牵ǎ溟L度（）。答案：零個字符的串0僅由空格組成的串大于02. 在二維數(shù)組a10，20中，每個元素占用 8個存儲單元，假定該數(shù)組的首地址為2000，則數(shù)組元素a6 ,15的字節(jié)地址為（）。答案：30803. 有一個 10 10的下三角矩陣A，若將其進行順序存儲于一維數(shù)組aN中，則Aj（1 G乞10,1乞j j）對應(yīng)的S的存儲位置是（）。答案：i x（ i + 1 ） /2+j7. 有一個10階對稱矩陣A,采用壓縮存儲方式（以行序為主存儲，且A00=1），則A85的地址是（）.答案：428. 兩個串相等的充分必要條件是（）。答案：兩個串的長度相等且對應(yīng)位置

12、的字符相同9. 數(shù)組Qn用來表示一個循環(huán)隊列，f為隊首指針，r為隊尾指針。假設(shè)隊列中元素的個數(shù)小于n,則計算隊列中元素個數(shù)的公式為（）。答案：（n + r - f）%n）、10. 數(shù)據(jù)的存儲結(jié)構(gòu)可用 4種基本的存儲方法表示，它們分別是（）和（）。答案：順序 鏈?zhǔn)?索引 散列三、簡答題（共7題）1.假定用一維數(shù)組 a7順序存儲一個循環(huán)隊列，隊首和隊尾指針分別用front和rear表示，當(dāng)前隊列中已有 5個元素；23, 45, 67, 80, 34,其中23為隊首元素，front的值為3, 請畫出對應(yīng)的存儲狀態(tài)，當(dāng)連續(xù)進行4次出隊運算后，再讓 15, 36, 48元素依次進隊，請再次畫出對應(yīng)的存儲

13、狀態(tài)。答案：兩次對應(yīng)的存儲狀態(tài)分別為：0 I 23456so342345；rear T front2.用三元組線性表表示如下稀疏矩陣：0 0 0 2 0 01 0 0 0 0 00 0 4 0 0 00 0 0 0 0 00 0 0 0 3 0 0 0 0 0 0 0 一答案：三元組線性表中的每個結(jié)點對應(yīng)于稀疏矩陣的一個非零元素，它包含3個數(shù)據(jù)項，分別表示該元素的行下標(biāo)、列下標(biāo)和元素值。另外，三元組線性表的表頭存儲矩陣中的行數(shù)、列數(shù)和非零元素個數(shù)。6640321012244433設(shè)Ann為一個上三角矩陣，將A中所有非零元素按列序順次存入一維數(shù)組B中，則A與B元素的對應(yīng)關(guān)系是什么？【解答】上三角

14、矩陣如下所示anai2ai3ain0a22 a a23a2n1 030a a a33a+a3n000 ann其數(shù)據(jù)元素滿足Aij=0，對所有的ij上三角矩陣正好是一個下三角矩陣的轉(zhuǎn)秩，我們知道，一個下三角矩陣按行壓縮存儲時,矩陣元素與一維數(shù)組的對應(yīng)關(guān)系為AijBi*(i+1)/2+j ，對所有的 ij ；因此，下三角矩陣按列序存儲在一維數(shù)組中的元素對應(yīng)關(guān)系為AijBj*(j+1)/2+i，對所有的 ij.4.用三元組表表示下面稀疏矩陣：0 0 0 00 0 0 0|0 3 0 00 0 0 00 0 0 60 0 00 0 0 02 0 0 00 0 0 00 0 0 00 8 0 00 0

15、0 00 0 0 00 0 0 00 0 0 50 0 0 0答案:5.用三元組表表示下面稀疏矩陣:-323368546785812 一00000 -200009 000000 000500 000000 0.000030 一答案:-122 21123134445366116 _答案：-02000000012000000003000000000004000000060000000000000001 6 -2259435.653 一6.下面三元組表表示一個稀疏矩陣，試寫出其對應(yīng)的稀疏矩陣。7.下面三元組表表示一個稀疏矩陣，試寫出其對應(yīng)的稀疏矩陣。0 00 00 00 00 00 61112 49

16、 283 5643?j答案：100000009008006.00700四、應(yīng)用題（共2題）1. 設(shè)有數(shù)組a44，按行存儲數(shù)組中元素，編寫函數(shù)求兩條對角線元素和的乘積。因此用循環(huán)答案：數(shù)組a44中一條對角線是aii，另一條對角線則是a4-ii，將兩條對角線的元素分別相加，再計算乘積。算法源代碼如下：int fun_Mult(int a44)int i, s = 1, sum1 = 0, sum2 = 0;for(i = 0; i 4; i+)suml = suml + aii;sum2 = sum2 * a4-ii;s = suml * sum2;return(s);2. 若x和y是兩個采用順序結(jié)構(gòu)存儲的串，