第5章陣列和廣義表
一、 選擇題
1. 在以下講述中，正確的是（ b ）。【＊】
a、線性表的線性儲存結構優於鍊錶儲存結構
b、二維陣列是其資料元素為線性表的線性表
c、棧的操作方式是先進先出
d、佇列的操作方式是先進後出
2. 若採用三元組壓縮技術儲存稀疏矩陣，只要把每個元素的行下標和列下標互換，就完成了對該矩陣的轉
置運算，這種觀點（ b ）。【＊，★】
a、正確b、錯誤
3. 二維陣列sa 中，每個元素的長度為3 個位元組，行下標i 從0 到7，列下標j 從0 到9，從首位址sa 開始
連續存放在儲存器內，該陣列按列存放時，元素a[4][7]的起始位址為（ b ）。【＊，★】
a、sa+141b、sa+180c、sa+222d、sa+225
4. 陣列sa 中，每個元素的長度為3 個位元組，行下標i 從0 到7，列下標j 從0 到9，從首位址sa 開始連續
存放在儲存器內，存放該陣列至少需要的位元組數是（ c ）。【＊】
a、80b、100c、240d、270
5. 常對陣列進行的兩種基本操作是（ c ）。【＊】
a、建立與刪除 b、索引和修改 c、查詢和修改 d、查詢和索引
6. 將乙個a[15][15]的下三角矩陣（第乙個元素為a[0][0]），按行優先存入一維陣列b[120]中，a 中元素a[6][5]
在b 陣列中的位置k 為（ b
a、19b、26c、21d、15
7. 若廣義表a 滿足head(a)=tail(a)，則a 為（ b ）。【＊】
abcd
8. 廣義表（（a）,a）的表頭是（ c ），表尾是（ c ）。【＊】
a、ab、bc、(ad、((a))
9. 廣義表（（a,b）,c,d）的表頭是（ c ），表尾是（ d ）。【＊】
a、ab、bc、(a,bd、(c,d)
10. 廣義表（（a））的表頭是（ b ），表尾是（ c ）。【＊】
a、ab、(acd、((a))
11. 廣義表（a,b,c,d）的表頭是（ a ），表尾是（ d ）。【＊】
a、ab、(ac、(a,bd、(b,c,d)
12. 廣義表（（a,b,c,d））的表頭是（ c ），表尾是（ b ）。【＊】
a、abc、(a,b,c,dd、((a,b,c,d))
13. 下面結論正確的是（ bc ）。（注：多項選擇）【＊，★】
a、乙個廣義表的表頭肯定不是乙個廣義表
b、乙個廣義表的表尾肯定是乙個廣義表
c、廣義表l=（（），（a，b））的表頭為空表
d、廣義表中原子個數即為廣義表的長度
14. 廣義表a=（a,b,(c,d),(e,(f,g))），則head(tail(head(tail(tail(a)))))=( d ) 【＊，★】
a、(gb、(dc、cd、 d
15. 已知廣義表l=((x,y,z),a,(u,t,w))，從l 表中取出原子項t 的操作是（ d ）。【＊，★】
a 、head(head(tail(tail(lb 、tail(head(head(tail(l))))
c 、head(tail(head(tail(ld 、head(tail(head(tail(tail(l)))))
16. 設a=(a,b,(c,d),(e,(f,g)))，則head(tail(head(tail(tail(a)))))=( d )（注：與14題重複）
a. (gb.(dc.cd.d
17. 對矩陣壓縮儲存是為了（ b ）【＊】
a、方便運算 b、節省空間 c、方便儲存 d、提高運算速度
18. 稀疏矩陣一般的壓縮儲存方法有兩種，即（ c ）【＊】
a、二元陣列和三元陣列b、三元組和雜湊
c、三元組和十字鍊錶d、雜湊和十字鍊錶
二、 判斷題
1. 陣列是同型別值的集合。【×】
2. 陣列的儲存結構是一組連續的記憶體單元。【√】
3. 陣列是一種複雜的資料結構，陣列元素之間的關係，即不是線性的也不是樹形的。【×】
4. 插入和刪除操作是資料結構中最基本的兩種操作，所以這兩種操作在陣列中也會經常使用。【×】
5. 使用三元組表表示稀疏矩陣的元素，有時並不能節省儲存空間。【√】
6. 廣義表是由零個或多個原子或子表所組成的有限序列，所以廣義表可能為空表。【√】
7. 線性表可以看成是廣義表的特例，如果廣義表中的每個元素是原子，則廣義表便成為線性表。【√】
8. 廣義表中原子個數即為廣義表的長度。【×】
9. 廣義表中元素的個數即為廣義表的深度。【×】
三、 填空題
1. 設a 是含有n 個分量的整數陣列，則求該陣列中最大整數的遞迴定義為（f(k)=a[0](k=0時)||f(k)=max(f(k-1),a[k])(k>0時) ），最小整數的遞迴定義為
（f(k)=a[0](k=0時)||f(k)=min(f(k-1),a[k])(k>0時) ）。（注：有函式max(p1,p2)和min(p1,p2)）【＊＊，★】
2. 二維陣列a[10][5]採用行序為主方式儲存，每個元素佔4 個儲存單元，並且a[5][3]的儲存位址是1000，則a[8][2]的位址是（ 1056
3. 二維陣列a[m][n]採用行序為主方式儲存，每個元素佔k 個儲存單元，並且第乙個元素的儲存位址是loc(a[0][0])，則a[i][j]的位址是（ loc(a[0][0])+(n*i+j)*k ）。【＊＊】
4. 廣義表的（ 深度 ）定義為廣義表中括弧的重數。【＊】
5. 設廣義表l=（（），（）），則head(ltail(ll 的長度是（ 2 ）；l 的深度是（ 2 ）。【＊】
6. 廣義表中的元素可以是（ 原子或子表 ），其描述宜採用程式語言中的（ 鍊錶 ）表示。【＊，？】
7. 廣義表(((a)))的表頭是（ ((a)) ），表尾是
8. 廣義表((a),((b),c),(((d))))的表頭是（ (a) ），表尾是（ (((b),c),(((d
9. 設廣義表a=(x,((a,b),c,d))，則head(head(tail(a)))=（ (a,b) ）。【＊】
10. 設廣義表a=(a,b,c),b=(a,(c,d)),c=(a,(b,a),(e,f))，則【＊】
（1）head(a)=( a2） tail(bc,d)) )
（3）head(head(head(tail(ca或(a,b,c
11. 下三角矩陣a[1..n,1..
n]的下三角元素已壓縮到一維陣列s[1..n*（n+1）/2+1]中，若按行序為主序儲存，則a[i,j]對應的s 中的儲存位置是 （ k=i(i-1)/2+j,當i>=j k=n(n+1)/2+1,當i12. 已知乙個稀疏矩陣為，則對應的三元組表表示為（
row col e
1 3 2
2 1 3
3 3 -1
3 4 5
13. 乙個n*n 的對稱矩陣，如果以行或列為主序存入記憶體，則其容量為 （ n(n+1)/2 ）。【＊】
14. 三維陣列a[c1..d1,c2..d2..,c3..d3]共有（ (d1-c1+1)*(d2-c2+1)*(d3-c3+1) ）個元素。【＊】
15. 陣列a[1..10,-2..
6,2..8]以行優先順序儲存，設基位址為100，每個元素佔3 個儲存單元，則元素a[5,0,7]的儲存位址是（ 913 ）。【＊＊，★】
16. 將乙個下三角矩陣a[1..100,1..100]按行優先存入一維陣列b[1..n]中，a 中元素a[66,65]在b 陣列中的位置為（ 2210
四、 計算題
1. 陣列 a[8][6][9]以行主序儲存，設第乙個元素的首位址是54，每個元素的長度為5，求元素a[2][4][5]的儲存位址。【＊＊】
答：a[2][4][5]的儲存位址為loc(2,4,5)=loc(0,0,0)+(2*6*9+4*9+5)*5=54+149*5=799
2. 假設二維陣列 a6x8，每個元素用相鄰的6 個位元組儲存，儲存器按位元組編址，已知a 的基位址為1000，計算：
（1）陣列a 的體積（儲存量）【＊＊，★】
（2）a 的最後乙個元素第乙個位元組的位址
（3）按行儲存時，a14 的第乙個位元組的位址
（4）按列儲存時，a47 的第乙個位元組的位址。
答：（1 ）儲存量= （6*8）*6=288
（2 ）陣列a 的最後乙個元素a57 的位址：1000+288-6=1282
（3 ）按行儲存時，a14 的位址：1000+ （1*8+4 ）*6=1072
（4 ）按列儲存時，a47 的位址：1000+ （7*6+4 ）*6=1276
3. 假設按低下標優先儲存整數陣列 a9x3x5x8 時，第乙個元素的位元組位址是100，每個整數佔4 個位元組。
問下列元素的儲存位址是什麼？【＊＊，★】
（1）a0000
（2）a1111
（3）a3125
（4）a8247
答：（1）100（2 ）776 （3 ）1784 （4 ）4416
4. 按行優先順序和按列優先順序分別列出四維陣列 a[2][2][2][2]所有元素在記憶體中的儲存順序。【＊＊】
答：四維陣列a 的按行優先順序在記憶體中的儲存次序為：a0000 、a0001 、a0010 、a0011、
a0100 、a0101 、a0110、a0111、a1000 、a1001 、a1010 、a1011、a1100、a1101、a1110、
a1111；按列優先儲存順序為：a0000、a1000 、a0100 、a1100、a0010 、a1010 、a0110、
a1110、a0001 、a1001 、a0101 、a1101、a0011、a1011、a0111、a1111
5. 乙個 n 階對稱矩陣a 採用一維陣列s 按行序為主序存放其上三角各元素，寫出s[k]與a[i,j]的關係公式。設a[1，1]存於s[1]中。【＊＊，★】
資料結構習題
前言資料結構是計算機相關專業教學計畫中的一門核心課程，是有志從事計算機與技術工作的人員的一門重要的專業基礎課程。計算機相關學科各領域都要用到各種資料結構，要從事這些領域的工作，尤其是計算機應用領域的開發研製工作，必須具備良好的資料結構基礎。資料結構課程的教學要求是學會分析研究計算機加工的資料物件的特...
資料結構習題
第二章 一選擇題 1 下述哪一條是順序儲存結構的優點？a 儲存密度大 b 插入運算方便 c 刪除運算方便 d 可方便地用於各種邏輯結構的儲存表示 2 下面關於線性表的敘述中，錯誤的是哪乙個？a 線性表採用順序儲存，必須占用一片連續的儲存單元。b 線性表採用順序儲存，便於進行插入和刪除操作。c 線性表...
資料結構習題
一 選擇題 1 下列有關線性表的敘述中，正確的是 a a 乙個線性表是n個資料元素的有限序列 b 線性表中任何乙個元素有且僅有乙個直接前驅 c.線性表中任何乙個元素有且僅有乙個直接後繼 d 以上說法都不正確 2 對線性表進行二分查詢時，要求線性表必須 c a 以順序方式儲存 b 以鏈結方式儲存c 以...