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

1、第5章 數(shù)組與廣義表一、 選擇題1. 在以下講述中，正確的是（ B ）。A、線性表的線性存儲結(jié)構(gòu)優(yōu)于鏈表存儲結(jié)構(gòu) B、二維數(shù)組是其數(shù)據(jù)元素為線性表的線性表 C、棧的操作方式是先進先出 D、隊列的操作方式是先進后出2. 若采用三元組壓縮技術(shù)存儲稀疏矩陣，只要把每個元素的行下標(biāo)和列下標(biāo)互換，就完成了對該矩陣的轉(zhuǎn)置運算，這種觀點（ A ）。A、正確 B、錯誤3. 二維數(shù)組SA 中，每個元素的長度為3 個字節(jié)，行下標(biāo)I 從0 到7，列下標(biāo)J 從0 到9，從首地址SA 開始連續(xù)存放在存儲器內(nèi)，該數(shù)組按列存放時，元素A47的起始地址為（ B）。A、SA+141 B、SA+180 C、SA+222 D、SA

2、+2254. 數(shù)組SA 中，每個元素的長度為3 個字節(jié)，行下標(biāo)I 從0 到7，列下標(biāo)J 從0 到9，從首地址SA 開始連續(xù)存放在存儲器內(nèi)，存放該數(shù)組至少需要的字節(jié)數(shù)是（ C ）。A、80 B、100 C、240 D、2705. 常對數(shù)組進行的兩種基本操作是（ B ）。A、建立與刪除 B、索引和修改C、查找和修改 D、查找和索引6. 將一個A1515的下三角矩陣（第一個元素為A00），按行優(yōu)先存入一維數(shù)組B120中，A 中元素A65在B 數(shù)組中的位置K 為（ B ）。A、19 B、26 C、21 D、157. 若廣義表A 滿足Head(A)=Tail(A)，則A 為（ B ）。A、（） B、（）

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

4、,d)13. 下面結(jié)論正確的是（ BC ）。A、一個廣義表的表頭肯定不是一個廣義表 B、一個廣義表的表尾肯定是一個廣義表C、廣義表L=（），（A，B）的表頭為空表 D、廣義表中原子個數(shù)即為廣義表的長度14. 廣義表A=（A,B,(C,D),(E,(F,G)），則head(tail(head(tail(tail(A)=( D )A、(G) B、(D) C、C D、 D15. 已知廣義表L=(x,y,z),a,(u,t,w)，從L 表中取出原子項t 的操作是（ D ）。A 、Head(Head(Tail(Tail(L) B 、Tail(Head(Head(Tail(L) C 、Head(Tail(

5、Head(Tail(L) D 、Head(Tail(Head(Tail(Tail(L)16. 16、設(shè)A=(a,b,(c,d),(e,(f,g)，則Head(Tail(Head(Tail(Tail(A)=( D )A. (g) B.(d) C.c D.d17. 對矩陣壓縮存儲是為了（ B ）A、方便運算 B、節(jié)省空間 C、方便存儲 D、提高運算速度18. 稀疏矩陣一般的壓縮存儲方法有兩種，即（ C ）A、二元數(shù)組和三元數(shù)組 B、三元組和散列C、三元組和十字鏈表 D、散列和十字鏈表二、 判斷題(F/T)1. 數(shù)組是同類型值的集合。(T)2. 數(shù)組的存儲結(jié)構(gòu)是一組連續(xù)的內(nèi)存單元。(T)3. 數(shù)組是

6、一種復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，數(shù)組元素之間的關(guān)系，即不是線性的也不是樹形的。(T)4. 插入和刪除操作是數(shù)據(jù)結(jié)構(gòu)中最基本的兩種操作，所以這兩種操作在數(shù)組中也會經(jīng)常使用。(F)5. 使用三元組表表示稀疏矩陣的元素，有時并不能節(jié)省存儲空間。(F)6. 廣義表是由零個或多個原子或子表所組成的有限序列，所以廣義表可能為空表。(T)7. 線性表可以看成是廣義表的特例，如果廣義表中的每個元素是原子，則廣義表便成為線性表。()8. 廣義表中原子個數(shù)即為廣義表的長度。(F)9. 廣義表中元素的個數(shù)即為廣義表的深度。(F)三、 填空題1. 設(shè)a 是含有N 個分量的整數(shù)數(shù)組，則求該數(shù)組中最大整數(shù)的遞歸定義為（ ），最小整數(shù)

7、的遞歸定義為（ ）。2. 二維數(shù)組A105采用行序為主方式存儲，每個元素占4 個存儲單元，并且A53的存儲地址是1000，則A82的地址是（ 1056 ）。3. 二維數(shù)組Amn采用行序為主方式存儲，每個元素占k 個存儲單元，并且第一個元素的存儲地址是Loc(A00)，則Aij的地址是（Loc(A00+(i*n+m)*k ）。4. 廣義表的（深度 ）定義為廣義表中括弧的重數(shù)。5. 設(shè)廣義表L=（），（），則Head(L)=（ () ）；Tail(L)=（() ）；L 的長度是（ 2 ）；L 的深度是（ 2 ）。6. 廣義表中的元素可以是（ 原子和字表），其描述宜采用程序設(shè)計語言中的（LISP語言

8、 ）表示。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 ）。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,b,c) )11. 下三角矩陣A1.N,1.N的下三角元素已壓縮到一維數(shù)組S1.N*（N+1）/2+1中

9、，若按行序為主序存儲，則AI,j對應(yīng)的S 中的存儲位置是 （ ）。12. 已知一個稀疏矩陣為，則對應(yīng)的三元組表表示為（ （1，3，2） ，（2，1，3），（3，3，-1），（3，4，5） ） 。13. 一個n*n 的對稱矩陣，如果以行或列為主序存入內(nèi)存，則其容量為 （n*（n+1）/2 ）。14. 三維數(shù)組Ac1.d1,c2.d2.,c3.d3共有（ (d1-c1+1)*(d2-c2+1)*(d3-c3+1) ）個元素。15. 數(shù)組A1.10,-2.6,2.8以行優(yōu)先順序存儲，設(shè)基地址為100，每個元素占3 個存儲單元，則元素A5,0,7的存儲地址是（ 913 ）。=100+(4*7*9+2*

10、7+5)*316. 將一個下三角矩陣A1.100,1.100按行優(yōu)先存入一維數(shù)組B1.n中，A 中元素A66,65在B 數(shù)組中的位置為（ 2276 ）。四、 計算題1. 數(shù)組 A869以行主序存儲，設(shè)第一個元素的首地址是54，每個元素的長度為5，求元素A245的存儲地址。答：LOCA245=54+（2*6*9+4*9+5）*5=7992. 假設(shè)二維數(shù)組 A6x8，每個元素用相鄰的6 個字節(jié)存儲，存儲器按字節(jié)編址，已知A 的基地址為1000，計算：（1）數(shù)組A 的體積（存儲量） （2）A 的最后一個元素第一個字節(jié)的地址（3）按行存儲時，a14 的第一個字節(jié)的地址（4）按列存儲時，a47 的第一個

11、字節(jié)的地址。答：（1）數(shù)組A 的體積V=6*8*6=288（2）1000+288-6=1282（3）1000+（4+1*8）*6=1072（4）1000+（4+7*6）*6=12763. 假設(shè)按低下標(biāo)優(yōu)先存儲整數(shù)數(shù)組 A9x3x5x8 時，第一個元素的字節(jié)地址是100，每個整數(shù)占4 個字節(jié)。問下列元素的存儲地址是什么？（1）a0000 =100（2） a1111 =100+（1*3*5*8+1*5*8+1*8+1）*4（3） a3125 =100+（3*3*5*8+1*5*8+2*8+5）*4（4）a8247=100+（8*3*5*8+2*5*8+4*8+7）*44. 按行優(yōu)先順序和按列優(yōu)先順

12、序分別列出四維數(shù)組 A2222所有元素在內(nèi)存中的存儲順序。答：行優(yōu)先順序：A0000, A0100, A1000, A1100, A0010, A0110, A1010, A1110, A0001, A0101, A1001, A1101, A0011, A0111, A1011, A1111列優(yōu)先順序：A0000，A1000，A0100，A1100，A0010，A1010，A0110，A1110，A0001，A1001，A0101，A1101，A0011，A1011，A0111，A11115. 一個 n 階對稱矩陣A 采用一維數(shù)組S 按行序為主序存放其上三角各元素，寫出Sk與Ai,j的關(guān)系公

13、式。設(shè)A1，1存于S1中。6. 寫出下面稀疏矩陣對應(yīng)的三元組表示，并畫出十字鏈表表示法。A=（0，0，2，0），（3，0，0，0），（0，0，-1，5），（0，0，0，0）答：三元組表示：（0,2,2），（1,0,3），（2,2，-1），（2,3,5）十字鏈表表示法：五、 簡答題1. 什么是廣義表，簡述廣義表與線性表的主要區(qū)別？ 廣義表是一種非線性的數(shù)據(jù)結(jié)構(gòu)，顧名思義，它也是線性表的一種推廣 廣義表是線性表的推廣，線性表是廣義表的特例。當(dāng)廣義表中的元素都是原子時，即為線性表2. 利用廣義表的 Head 和Tail 運算把原子student 從下列廣義表中分離出來。（1） L1=（soldier,teacher,student,worker,farmer）（2） L2=（soldier,(teacher,student),(worker,farmer)）3. 畫出下列廣義表的存儲結(jié)構(gòu)圖，并求它的深度。（1）( ),a,(b,c),(d) （2）(a),(b),( ),d),(e,f)4. 已知圖4.4 為廣義表的存儲結(jié)構(gòu)圖，寫出各圖的廣