《數(shù)據(jù)結(jié)構(gòu)》習(xí)題集章 數(shù)組與廣義表

本文格式為Word版，下載可任意編輯——《數(shù)據(jù)結(jié)構(gòu)》習(xí)題集章數(shù)組與廣義表第5章數(shù)組與廣義表

一、選擇題

1.在以下陳述中，正確的是（B）。

A、線性表的線性存儲(chǔ)結(jié)構(gòu)優(yōu)于鏈表存儲(chǔ)結(jié)構(gòu)B、二維數(shù)組是其數(shù)據(jù)元素為線性表的線性表C、棧的操作方式是先進(jìn)先出D、隊(duì)列的操作方式是先進(jìn)后出

2.若采用三元組壓縮技術(shù)存儲(chǔ)稀疏矩陣，只要把每個(gè)元素的行下標(biāo)和列下標(biāo)互換，就完成了對(duì)該矩陣的轉(zhuǎn)

置運(yùn)算，這種觀點(diǎn)（B）。A、正確B、錯(cuò)誤

3.二維數(shù)組SA中，每個(gè)元素的長度為3個(gè)字節(jié)，行下標(biāo)I從0到7，列下標(biāo)J從0到9，從首地址SA開始

連續(xù)存放在存儲(chǔ)器內(nèi)，該數(shù)組按列存放時(shí)，元素A[4][7]的起始地址為（B）。A、SA+141B、SA+180C、SA+222D、SA+225

4.數(shù)組SA中，每個(gè)元素的長度為3個(gè)字節(jié)，行下標(biāo)I從0到7，列下標(biāo)J從0到9，從首地址SA開始連續(xù)

存放在存儲(chǔ)器內(nèi)，存放該數(shù)組至少需要的字節(jié)數(shù)是（C）。A、80B、100C、240D、2705.常對(duì)數(shù)組進(jìn)行的兩種基本操作是（C）。

A、建立與刪除B、索引和修改C、查找和修改D、查找和索引

6.將一個(gè)A[15][15]的下三角矩陣（第一個(gè)元素為A[0][0]），按行優(yōu)先存入一維數(shù)組B[120]中，A中元素A[6][5]

在B數(shù)組中的位置K為（B）。A、19B、26C、21D、157.若廣義表A滿足Head(A)=Tail(A)，則A為（B）。

A、（）B、（（））C、（（），（））D、（（），（），（））8.廣義表（（a）,a）的表頭是（C），表尾是（C）。

A、aB、bC、(a)D、((a))9.廣義表（（a,b）,c,d）的表頭是（C），表尾是（D）。

A、aB、bC、(a,b)D、(c,d)10.廣義表（（a））的表頭是（B），表尾是（C）。

A、aB、(a)C、()D、((a))11.廣義表（a,b,c,d）的表頭是（A），表尾是（D）。

A、aB、(a)C、(a,b)D、(b,c,d)12.廣義表（（a,b,c,d））的表頭是（C），表尾是（B）。

A、aB、()C、(a,b,c,d)D、((a,b,c,d))13.下面結(jié)論正確的是（BC）。

A、一個(gè)廣義表的表頭確定不是一個(gè)廣義表B、一個(gè)廣義表的表尾確定是一個(gè)廣義表

C、廣義表L=（（），（A，B））的表頭為空表D、廣義表中原子個(gè)數(shù)即為廣義表的長度

14.廣義表A=（A,B,(C,D),(E,(F,G))），則head(tail(head(tail(tail(A)))))=(D)

A、(G)B、(D)C、CD、D15.已知廣義表L=((x,y,z),a,(u,t,w))，從L表中取出原子項(xiàng)t的操作是（D）。

A、Head(Head(Tail(Tail(L))))B、Tail(Head(Head(Tail(L))))C、Head(Tail(Head(Tail(L))))D、Head(Tail(Head(Tail(Tail(L)))))

1/6

16.16、設(shè)A=(a,b,(c,d),(e,(f,g)))，則Head(Tail(Head(Tail(Tail(A)))))=(D)

A.(g)B.(d)C.cD.d17.對(duì)矩陣壓縮存儲(chǔ)是為了（B）

A、便利運(yùn)算B、節(jié)省空間C、便利存儲(chǔ)D、提高運(yùn)算速度18.稀疏矩陣一般的壓縮存儲(chǔ)方法有兩種，即（C）

A、二元數(shù)組和三元數(shù)組B、三元組和散列C、三元組和十字鏈表D、散列和十字鏈表

二、判斷題

1.2.3.4.5.6.7.8.9.

數(shù)組是同類型值的集合。X

數(shù)組的存儲(chǔ)結(jié)構(gòu)是一組連續(xù)的內(nèi)存單元。V

數(shù)組是一種繁雜的數(shù)據(jù)結(jié)構(gòu)，數(shù)組元素之間的關(guān)系，即不是線性的也不是樹形的。X

插入和刪除操作是數(shù)據(jù)結(jié)構(gòu)中最基本的兩種操作，所以這兩種操作在數(shù)組中也會(huì)經(jīng)常使用。X使用三元組表表示稀疏矩陣的元素，有時(shí)并不能節(jié)省存儲(chǔ)空間。V

廣義表是由零個(gè)或多個(gè)原子或子表所組成的有限序列，所以廣義表可能為空表。V

線性表可以看成是廣義表的特例，假使廣義表中的每個(gè)元素是原子，則廣義表便成為線性表。V廣義表中原子個(gè)數(shù)即為廣義表的長度。X廣義表中元素的個(gè)數(shù)即為廣義表的深度。X

三、填空題

1.設(shè)a是含有N個(gè)分量的整數(shù)數(shù)組，則求該數(shù)組中最大整數(shù)的遞歸定義為（最大整數(shù)的遞歸定義為：f(k)=a[0](k=0

時(shí))||f(k)=max(f(k-1),a[k])(k>0時(shí))），最小整數(shù)的遞歸定義為（最小整數(shù)的遞歸定義為：f(k)=a[0](k=0時(shí))||f(k)=min(f(k-1),a[k])(k>0時(shí))）。2.二維數(shù)組A[10][5]采用行序?yàn)橹鞣绞酱鎯?chǔ)，每個(gè)元素占4個(gè)存儲(chǔ)單元，并且A[5][3]的存儲(chǔ)地址是1000，則A[8][2]

的地址是（1056）。

3.二維數(shù)組A[m][n]采用行序?yàn)橹鞣绞酱鎯?chǔ)，每個(gè)元素占k個(gè)存儲(chǔ)單元，并且第一個(gè)元素的存儲(chǔ)地址是

Loc(A[0][0])，則A[i][j]的地址是（loc(A[0][0])+(n*I+j)*k）。4.廣義表的（深度）定義為廣義表中括弧的重?cái)?shù)。

5.設(shè)廣義表L=（（），（）），則Head(L)=（()）；Tail(L)=（(())）；L的長度是（2）；L的深度是（2）。6.廣義表中的元素可以是（原子或子表），其描述宜采用程序設(shè)計(jì)語言中的（鏈表）表示。7.廣義表(((a)))的表頭是（((a))），表尾是（()）。

8.廣義表((a),((b),c),(((d))))的表頭是（(a)），表尾是（(((b),c),(((d))))）。9.設(shè)廣義表A=(x,((a,b),c,d))，則Head(Head(Tail(A)))=（（a,b））。10.設(shè)廣義表A=(a,b,c),B=(A,(c,d)),C=(a,(B,A),(e,f))，則

（1）Head(A)=(a)（2）Tail(B)=(((c,d)))（3）Head(Head(Head(Tail(C))))=(A)

11.下三角矩陣A[1..N,1..N]的下三角元素已壓縮到一維數(shù)組S[1..N*（N+1）/2+1]中，若按行序?yàn)橹餍虼鎯?chǔ)，則A[I,j]

對(duì)應(yīng)的S中的存儲(chǔ)位置是（）。

2/6

?0?312.已知一個(gè)稀疏矩陣為??0??002000?1000?0??5??0?，則對(duì)應(yīng)的三元組表表示為

（）。

13.一個(gè)n*n的對(duì)稱矩陣，假使以行或列為主序存入內(nèi)存，則其容量為（n(n+1)/2）。14.三維數(shù)組A[c1..d1,c2..d2..,c3..d3]共有（(d1-c1+1)*(d2-c2+1)*(d3-c3+1)）個(gè)元素。

15.數(shù)組A[1..10,-2..6,2..8]以行優(yōu)先順序存儲(chǔ)，設(shè)基地址為100，每個(gè)元素占3個(gè)存儲(chǔ)單元，則元素A[5,0,7]的存儲(chǔ)

地址是（913）。

16.將一個(gè)下三角矩陣A[1..100,1..100]按行優(yōu)先存入一維數(shù)組B[1..n]中，A中元素A[66,65]在B數(shù)組中的位置為

（2210）。

四、計(jì)算題

1.數(shù)組A[8][6][9]以行主序存儲(chǔ)，設(shè)第一個(gè)元素的首地址是54，每個(gè)元素的長度為5，求元素A[2][4][5]的存儲(chǔ)地

址。

A[2][4][5]的存儲(chǔ)地址為loc(2,4,5)=loc(0,0,0)+(2*6*9+4*9+5)*5=54+149*5=799

2.假設(shè)二維數(shù)組A6x8，每個(gè)元素用相鄰的6個(gè)字節(jié)存儲(chǔ)，存儲(chǔ)器按字節(jié)編址，已知A的基地址為1000，計(jì)算：

（1）數(shù)組A的體積（存儲(chǔ)量）

（2）A的最終一個(gè)元素第一個(gè)字節(jié)的地址（3）按行存儲(chǔ)時(shí)，a14的第一個(gè)字節(jié)的地址（4）按列存儲(chǔ)時(shí)，a47的第一個(gè)字節(jié)的地址。答案：（1）存儲(chǔ)量=（6*8）*6=288

（2）數(shù)組A的最終一個(gè)元素a57的地址：1000+288-6=1282（3）按行存儲(chǔ)時(shí)，a14的地址：1000+（1*8+4）*6=1072（4）按列存儲(chǔ)時(shí)，a47的地址：1000+（7*6+4）*6=1276

3.假設(shè)按低下標(biāo)優(yōu)先存儲(chǔ)整數(shù)數(shù)組A9x3x5x8時(shí)，第一個(gè)元素的字節(jié)地址是100，每個(gè)整數(shù)占4個(gè)字節(jié)。

問以下元素的存儲(chǔ)地址是什么？（1）a0000100（2）a1111776（3）a31251784（4）a82474416

4.按行優(yōu)先順序和按列優(yōu)先順序分別列出四維數(shù)組A[2][2][2][2]所有元素在內(nèi)存中的存儲(chǔ)順序。四維數(shù)組A的按行優(yōu)先順序在內(nèi)存中的存儲(chǔ)次序?yàn)椋篈0000、A0001、A0010、A0011、

A0100、A0101、A0110、A0111、A1000、A1001、A1010、A1011、A1100、A1101、A1110、A1111；按列優(yōu)先存儲(chǔ)順序?yàn)椋篈0000、A1000、A0100、A1100、A0010、A1010、A0110、A1110、A0001、A1001、A0101、A1101、A0011、A1011、A0111、A1111

5.一個(gè)n階對(duì)稱矩陣A采用一維數(shù)組S按行序?yàn)橹餍虼娣牌渖先歉髟?，寫出S[k]與A[i,j]的關(guān)系公式。設(shè)

3/6

A[1，1]存于S[1]中。

k=(I-1)(2n-I+2)/2+j-I+1(Ij時(shí))

五、簡(jiǎn)答題

1.什么是廣義表，簡(jiǎn)述廣義表與線性表的主要區(qū)別？

廣義表是線性表的推廣，形式上定義為LS=(a1,a2,…,an)，ai可以是單個(gè)元素，也可以是廣義表，并分別稱為廣義表的原子和子表。

主要區(qū)別是：線性表中元素只能是單個(gè)元素，而廣義表中元素可以是單個(gè)元素，也可以是廣義表；線性表中各元素是獨(dú)立的，而廣義表中元素可以為其他表或子表共享，特別地，廣義表可以是一個(gè)遞歸的表，即廣義表也可以是其本身的一個(gè)子表。

2.利用廣義表的Head和Tail運(yùn)算把原子student從以下廣義表中分開出來。

（1）L1=（soldier,teacher,student,worker,farmer）（2）L2=（soldier,(teacher,student),(worker,farmer)）

Head(Tail(Tail(L1)))=studentHead(Tail(Head(Tail(L2))))=student3.畫出以下廣義表的存儲(chǔ)結(jié)構(gòu)圖，并求它的深度。

（1）((()),a,((b,c)),(((d))))（2）((((a),(b))),(((),d),(e,f)))

4/6

4.已知圖4.4為廣義表的存儲(chǔ)結(jié)構(gòu)圖，寫出各圖的廣義表。

解答：（1）((x,(y)),(((())),(),(z)))（2）(((a,b,()),()),(a,(b)),())

六、設(shè)計(jì)題

1.對(duì)于二維數(shù)組A[m][n]，分別編寫相應(yīng)函