第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. 16、設a=(a,b,(c,d),(e,(f,g)))，則head(tail(head(tail(tail(a)))))=( d )
a. (gb.(dc.cd.d
17. 對矩陣壓縮儲存是為了（ b ）
a、方便運算 b、節省空間 c、方便儲存 d、提高運算速度
18. 稀疏矩陣一般的壓縮儲存方法有兩種，即（ c ）
a、二元陣列和三元陣列b、三元組和雜湊
c、三元組和十字鍊錶d、雜湊和十字鍊錶
二、 判斷題
1. 陣列是同型別值的集合。x
2. 陣列的儲存結構是一組連續的記憶體單元。v
3. 陣列是一種複雜的資料結構，陣列元素之間的關係，即不是線性的也不是樹形的。x
4. 插入和刪除操作是資料結構中最基本的兩種操作，所以這兩種操作在陣列中也會經常使用。x
5. 使用三元組表表示稀疏矩陣的元素，有時並不能節省儲存空間。v
6. 廣義表是由零個或多個原子或子表所組成的有限序列，所以廣義表可能為空表。v
7. 線性表可以看成是廣義表的特例，如果廣義表中的每個元素是原子，則廣義表便成為線性表。v
8. 廣義表中原子個數即為廣義表的長度。x
9. 廣義表中元素的個數即為廣義表的深度。x
三、 填空題
1. 設a 是含有n 個分量的整數陣列，則求該陣列中最大整數的遞迴定義為（ ），最小整數的遞迴定義為
（ ）。
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]的位址是（ (i*n+j)*k+loc(a[0][0]) ）。
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)=( a ) （2） tail(b)=( ((c,d
（3）head(head(head(tail(c))))=( a
11. 下三角矩陣a[1..n,1..n]的下三角元素已壓縮到一維陣列s[1..n*（n+1）/2+1]中，若按行序為主序儲存，則a[i,j]對應的s 中的儲存位置是
12. 已知乙個稀疏矩陣為，則對應的三元組表表示為（ a(0,2,2),a(1,0,3),a(2,2,-1),a(2,3,5) ） 。
13. 乙個n*n 的對稱矩陣，如果以行或列為主序存入記憶體，則其容量為 （ (n+1)*n/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=(65+1)*(66)/2+65 ）。
四、 計算題
1. 陣列 a[8][6][9]以行主序儲存，設第乙個元素的首位址是54，每個元素的長度為5，求元素a[2][4][5]的儲存位址。 答:
(2*6*9+4*9+5)*5+54=799
2. 假設二維陣列 a6x8，每個元素用相鄰的6 個位元組儲存，儲存器按位元組編址，已知a 的基位址為1000，計算：
（1）陣列a 的體積（儲存量） 節
（2）a 的最後乙個元素第乙個位元組的位址 1282
（3）按行儲存時，a14 的第乙個位元組的位址 1072
（4）按列儲存時，a47 的第乙個位元組的位址。 1276
3. 假設按低下標優先儲存整數陣列 a9x3x5x8 時，第乙個元素的位元組位址是100，每個整數佔4 個位元組。
問下列元素的儲存位址是什麼？
（1）a0000 100
（2） a1111 (1*3*5*8+1*5*8+1*8+1)*4+100=776
（3） a3125 (3*3*5*8+40+16+5)*4+100=1784
（4）a8247 (8*3*5*8+2*5*8+4*8+7)*4+100=4416
4. 按行優先順序和按列優先順序分別列出四維陣列 a[2][2][2][2]所有元素在記憶體中的儲存順序。
按行:a[0][0][0][0]
a[0][0][0][1]
a[0][0][1][0]
a[0][0][1][1]
a[0][1][0][0]
a[0][1][0][1]
a[0][1][1][0]
a[0][1][1][1]
a[1][0][0][0]
a[1][0][0][1]
a[1][0][1][0]
a[1][0][1][1]
a[1][1][0][0]
a[1][1][0][1]
a[1][1][1][0]
a[1][1][1][1]
按列:a[0][0][0][0]
a[1][0][0][0]
a[0][1][0][0]
a[1][1][0][0]
a[0][0][1][0]
a[1][0][1][0]
a[0][1][1][0]
a[1][1][1][0]
a[0][0][0][1]
a[1][0][0][1]
a[0][1][0][1]
a[1][1][0][1]
a[0][0][1][1]
a[1][0][1][1]
a[0][1][1][1]
a[1][1][1][1]
5. 乙個 n 階對稱矩陣a 採用一維陣列s 按行序為主序存放其上三角各元素，寫出s[k]與a[i,j]的關係公式。設a[1，1]存於s[1]中。
6. 寫出下面稀疏矩陣對應的三元組表示，並畫出十字鍊錶表示法。
a=〔（0，0，2，0），（3，0，0，0），（0，0，-1，5），（0，0，0，0）〕
五、 簡答題
1. 什麼是廣義表，簡述廣義表與線性表的主要區別？
答:廣義表是一種非線性的資料結構，它是線性表的一種推廣
廣義表中的資料元素既可以是單個元素，也可以是子表，因此對於廣義表，我們難以用順序儲存結構來表示它.
2. 利用廣義表的 head 和tail 運算把原子student 從下列廣義表中分離出來。
（1） l1=（soldier,teacher,student,worker,farmer）
《資料結構》第5章陣列和廣義表
第 5 章陣列和廣義表 一 選擇題 1.設有乙個10階的對稱矩陣a，採用壓縮儲存方式，以行序為主儲存，a11為第一元素，其儲存位址為1，每個元素佔乙個位址空間，則a85的位址為 燕山大學 2001 一 2 2分 a.13b.33c.18d.40 2.有乙個二維陣列a 1 6，0 7 每個陣列元素用相...
《資料結構題集》答案第5章陣列和廣義表
第五章陣列和廣義表 5.18 void rsh int a n int k 把陣列a的元素迴圈右移k位,只用乙個輔助儲存空間 print poly descend void get all int a,int m,int i,int seq 遞迴求出所有和為i的m個自然數 print nomial ...
《資料結構》習題集 第1章 緒論
第一章緒論 一 選擇題 1.資料結構被形式定義為 d，s 其中d是 的有限集合，s是d上的 有限集合。a 演算法 b 資料元素 c 資料操作 d 邏輯關係 e 操作 f 映象 g 儲存 h 關係 2.資料結構是一門研究非數值計算的程式設計問題中計算機的 以及它們之間的 和運算 的學科。1 a 操作物...