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

1、數(shù)據(jù)結(jié)構(gòu)習(xí)題集：章數(shù)組與廣義表數(shù)據(jù)結(jié)構(gòu)習(xí)題集：章數(shù)組與廣義表 編輯整理：尊敬的讀者朋友們：這里是精品文檔編輯中心，本文檔內(nèi)容是由我和我的同事精心編輯整理后發(fā)布的，發(fā)布之前我們對(duì)文中內(nèi)容進(jìn)行仔細(xì)校對(duì)，但是難免會(huì)有疏漏的地方，但是任然希望（數(shù)據(jù)結(jié)構(gòu)習(xí)題集：章數(shù)組與廣義表）的內(nèi)容能夠給您的工作和學(xué)習(xí)帶來(lái)便利。同時(shí)也真誠(chéng)的希望收到您的建議和反饋，這將是我們進(jìn)步的源泉，前進(jìn)的動(dòng)力。本文可編輯可修改，如果覺得對(duì)您有幫助請(qǐng)收藏以便隨時(shí)查閱，最后祝您生活愉快 業(yè)績(jī)進(jìn)步，以下為數(shù)據(jù)結(jié)構(gòu)習(xí)題集：章數(shù)組與廣義表的全部?jī)?nèi)容。10 / 11第5章 數(shù)組與廣義表一、 選擇題1. 在以下講述中,正確的是( b ）。a、線性

2、表的線性存儲(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è)元素的長(zhǎng)度為3 個(gè)字節(jié)，行下標(biāo)i 從0 到7,列下標(biāo)j 從0 到9，從首地址sa 開始連續(xù)存放在存儲(chǔ)器內(nèi),該數(shù)組按列存放時(shí)，元素a47的起始地址為（ b ）。a、sa+141 b、sa+180 c、sa+222 d、sa+2254. 數(shù)組sa 中,每個(gè)元素的長(zhǎng)度為3 個(gè)字節(jié)，行下標(biāo)i 從0 到7，

3、列下標(biāo)j 從0 到9,從首地址sa 開始連續(xù)存放在存儲(chǔ)器內(nèi)，存放該數(shù)組至少需要的字節(jié)數(shù)是（ c ）.a、80 b、100 c、240 d、2705. 常對(duì)數(shù)組進(jìn)行的兩種基本操作是（ c ）。a、建立與刪除 b、索引和修改c、查找和修改 d、查找和索引6. 將一個(gè)a1515的下三角矩陣（第一個(gè)元素為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、（） c、（(），（） d、（),()，（）8. 廣義表（a），a）的表頭是（ c

4、 ），表尾是( 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,d）13. 下面結(jié)論正確的是( bc ）。a、一個(gè)廣義表的表頭

5、肯定不是一個(gè)廣義表 b、一個(gè)廣義表的表尾肯定是一個(gè)廣義表c、廣義表l=（)，（a,b）的表頭為空表 d、廣義表中原子個(gè)數(shù)即為廣義表的長(zhǎng)度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 表中取出原子項(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（

6、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. 對(duì)矩陣壓縮存儲(chǔ)是為了（ b ）a、方便運(yùn)算 b、節(jié)省空間 c、方便存儲(chǔ) d、提高運(yùn)算速度18. 稀疏矩陣一般的壓縮存儲(chǔ)方法有兩種，即（ c ）a、二元數(shù)組和三元數(shù)組 b、三元組和散列c、三元組和十字鏈表 d、散列和十字鏈表二、 判斷題1. 數(shù)組是同類型值的集合。x2. 數(shù)組的存儲(chǔ)結(jié)構(gòu)是一組連續(xù)的內(nèi)存單元。v3. 數(shù)組是一種復(fù)雜的數(shù)據(jù)結(jié)構(gòu),數(shù)組元素之間的關(guān)系，即不是線性的也不是樹

7、形的。x4. 插入和刪除操作是數(shù)據(jù)結(jié)構(gòu)中最基本的兩種操作，所以這兩種操作在數(shù)組中也會(huì)經(jīng)常使用。x5. 使用三元組表表示稀疏矩陣的元素，有時(shí)并不能節(jié)省存儲(chǔ)空間。v6. 廣義表是由零個(gè)或多個(gè)原子或子表所組成的有限序列，所以廣義表可能為空表。v7. 線性表可以看成是廣義表的特例，如果廣義表中的每個(gè)元素是原子，則廣義表便成為線性表.v8. 廣義表中原子個(gè)數(shù)即為廣義表的長(zhǎng)度。x9. 廣義表中元素的個(gè)數(shù)即為廣義表的深度。x三、 填空題1. 設(shè)a 是含有n 個(gè)分量的整數(shù)數(shù)組，則求該數(shù)組中最大整數(shù)的遞歸定義為（最大整數(shù)的遞歸定義為：f（k）=a0（k=0 時(shí)）|f（k)=max(f(k1）,ak)（k0 時(shí)）

8、 ),最小整數(shù)的遞歸定義為（最小整數(shù)的遞歸定義為：f(k)=a0(k=0 時(shí)）|f（k)=min（f(k1)，ak）（k0 時(shí)) ）。2. 二維數(shù)組a105采用行序?yàn)橹鞣绞酱鎯?chǔ)，每個(gè)元素占4 個(gè)存儲(chǔ)單元,并且a53的存儲(chǔ)地址是1000,則a82的地址是（ 1056 )。3. 二維數(shù)組amn采用行序?yàn)橹鞣绞酱鎯?chǔ)，每個(gè)元素占k 個(gè)存儲(chǔ)單元,并且第一個(gè)元素的存儲(chǔ)地址是loc（a00），則aij的地址是（loc(a00)+(ni+j)*k ）。4. 廣義表的( 深度 )定義為廣義表中括弧的重?cái)?shù)。5. 設(shè)廣義表l=（），（），則head(l）=（ (） )；tail(l)=（ （）) )；l 的長(zhǎng)度是(

9、 2 )；l 的深度是（ 2 ）。6. 廣義表中的元素可以是（ 原子或子表 ），其描述宜采用程序設(shè)計(jì)語(yǔ)言中的（ 鏈表 ）表示。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(hea

10、d（head（tail(c)）)=( a )11. 下三角矩陣a1。n，1.。n的下三角元素已壓縮到一維數(shù)組s1.。n*（n+1）/2+1中,若按行序?yàn)橹餍虼鎯?chǔ),則ai,j對(duì)應(yīng)的s 中的存儲(chǔ)位置是 （ ）.12. 已知一個(gè)稀疏矩陣為，則對(duì)應(yīng)的三元組表表示為（ ） .13. 一個(gè)nn 的對(duì)稱矩陣,如果以行或列為主序存入內(nèi)存，則其容量為 （ n(n+1）/2 )。14. 三維數(shù)組ac1.。d1,c2.。d2。.，c3.d3共有( （d1c1+1）*（d2-c2+1)（d3-c3+1) ）個(gè)元素。15. 數(shù)組a1。.10,-2.6,2.8以行優(yōu)先順序存儲(chǔ),設(shè)基地址為100，每個(gè)元素占3 個(gè)存儲(chǔ)單元,

11、則元素a5，0,7的存儲(chǔ)地址是( 913 ）.16. 將一個(gè)下三角矩陣a1。.100，1.100按行優(yōu)先存入一維數(shù)組b1.。n中,a 中元素a66，65在b 數(shù)組中的位置為（ 2210 ）。四、 計(jì)算題1. 數(shù)組 a869以行主序存儲(chǔ)，設(shè)第一個(gè)元素的首地址是54，每個(gè)元素的長(zhǎng)度為5，求元素a245的存儲(chǔ)地址。 a245的存儲(chǔ)地址為loc(2,4,5）=loc（0，0，0)+(2*69+49+5)*5=54+149*5=7992. 假設(shè)二維數(shù)組 a6x8，每個(gè)元素用相鄰的6 個(gè)字節(jié)存儲(chǔ)，存儲(chǔ)器按字節(jié)編址，已知a 的基地址為1000，計(jì)算：（1）數(shù)組a 的體積（存儲(chǔ)量) （2)a 的最后一個(gè)元素第

12、一個(gè)字節(jié)的地址(3）按行存儲(chǔ)時(shí)，a14 的第一個(gè)字節(jié)的地址（4)按列存儲(chǔ)時(shí),a47 的第一個(gè)字節(jié)的地址。答案:（1）存儲(chǔ)量=（68)*6=288（2)數(shù)組a 的最后一個(gè)元素a57 的地址：1000+2886=1282（3）按行存儲(chǔ)時(shí)，a14 的地址:1000+（1*8+4）6=1072(4)按列存儲(chǔ)時(shí)，a47 的地址:1000+(7*6+4)6=12763. 假設(shè)按低下標(biāo)優(yōu)先存儲(chǔ)整數(shù)數(shù)組 a9x3x5x8 時(shí)，第一個(gè)元素的字節(jié)地址是100，每個(gè)整數(shù)占4 個(gè)字節(jié)。問下列元素的存儲(chǔ)地址是什么?（1）a0000 100（2） a1111 776（3） a3125 1784（4）a8247 4416

13、4. 按行優(yōu)先順序和按列優(yōu)先順序分別列出四維數(shù)組 a2222所有元素在內(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、a11115. 一個(gè) n 階對(duì)稱矩陣a 采用一維數(shù)組s 按行序?yàn)橹餍虼?/p>

14、放其上三角各元素,寫出sk與ai,j的關(guān)系公式。設(shè)a1，1存于s1中. k=（i1）（2n-i+2）/2+ji+1 （i=j 時(shí)) 和k=（j-1）(2nj+2）/2+i-j+1 (ij 時(shí)）五、 簡(jiǎn)答題1. 什么是廣義表，簡(jiǎn)述廣義表與線性表的主要區(qū)別？廣義表是線性表的推廣，形式上定義為ls=(a1,a2，,an)，ai 可以是單個(gè)元素，也可以是廣義表，并分別稱為廣義表的原子和子表。主要區(qū)別是：線性表中元素只能是單個(gè)元素，而廣義表中元素可以是單個(gè)元素，也可以是廣義表；線性表中各元素是獨(dú)立的，而廣義表中元素可以為其他表或子表共享，特別地，廣義表可以是一個(gè)遞歸的表,即廣義表也可以是其本身的一個(gè)子表

15、。2. 利用廣義表的 head 和tail 運(yùn)算把原子student 從下列廣義表中分離出來(lái)。(1） l1=（soldier，teacher，student,worker，farmer）（2) l2=（soldier，(teacher，student)，（worker，farmer）head（tail（tail（l1）=student head(tail（head（tail（l2)）)）=student3. 畫出下列廣義表的存儲(chǔ)結(jié)構(gòu)圖,并求它的深度。（1）( ）)，a，(（b,c），(d)）) （2）(（a），(b）),(（ ),d),（e，f）4. 已知圖4.4 為廣義表的存儲(chǔ)結(jié)構(gòu)圖，寫出各圖的廣義表.解答：（1）(x,(y），（( ）)，（ )，（z)）（2