習題5 陣列和廣義表
一、基本內容
陣列定義及表示方式；特殊矩陣和稀疏矩陣的壓縮儲存方法及運算的實現；廣義表的邏輯結構和儲存結構。
二、學習要點
1.了解陣列的兩種儲存表示方法，並掌握陣列在以行為主的儲存結構中的位址計算方法。
2．掌握對特殊矩陣進行壓縮儲存時的下標變換公式。
3．了解稀疏矩陣的兩種壓縮儲存方法的特點和適用範圍，領會以三元組表示稀疏矩陣時進行矩陣運算採用的處理方法。
4．掌握廣義表的結構特點及其儲存表示方法，讀者可根據自己的習慣掌握任意一種結構的鍊錶
5.1 單項選擇題
1. 常對陣列進行的兩種基本操作是____。
a. 建立與刪除 b. 索引和修改 [, ] d. 查詢與索引
2. 二維陣列m的成員是6個字元（每個字元佔乙個儲存單元，即乙個位元組）組成的串，行下標i的範圍從0到8，列下標j的範圍從0到9，則存放m 至少需要①_ _個位元組；m陣列的第8列和第5行共佔②____個位元組。
① a. 90 b. 180 c. 240
b. 114 c. 54 d. 60
3. 二維陣列a中，每個元素的長度為3個位元組，行下標i從0到7，列下標j從0到9，從首位址sa開始連續存放在儲存器內，存放該陣列至少需要的位元組數是____。
a. 80 b. 100t': 'span', 'c': ' c'}, , ] d. sa+225
5. 二維陣列a中，每個元素a的長度為3個位元組，行下標i從0到7，列下標j從0到9，從首位址sa開始連續存放在儲存器內，該陣列按列存放時，元素a[4][7]的起始位址為____。
a. sa+141 [, ] c. sa+222 d. sa+225
5.2 填空題（將正確的答案填在相應的空中）
1. 已知二維陣列a[m][n]採用行序為主方式儲存，每個元素佔k個儲存單元，並且第乙個元素的儲存位址是loc(a[0][0])，則a[i][j]的位址是__ loc (a[0][0])+(n*i+j)*k __。
2. 二維陣列a[10][20]採用列序為主方式儲存，每個元素佔乙個儲存單元並且a[0][0]的儲存位址是200，則a[6][12]的位址是__ 200+（12*10+6）= 326_。
3. 二維陣列a[10..20][5..
10]採用行序為主方式儲存，每個元素佔4個儲存單元，並且a[10][5]的儲存位址是1000，則a[18][9]的位址是_1000+((18-10)*6 +(9-5))*4 = 1208_。
4.設aij是矩陣a的第i行第j列非零元素，則b[k]與矩陣a[i,j]的一一對應關係：k=j*(j-1)/2+i且i＜=j； k的取值範圍為1，2…．，n*(n+1)/2
5．求下列廣義表操作的結果：
(1) gettail[gethead[((a,b),(c,dt': 'span', 'c': ' (b)'}]
(2) gettail[gethead[gettail[((a,b),(c,dt': 'span', 'c': ' (d)'}]
6.利用廣義表的gethead和gettail操作寫出如上題的函式表示式,把原子banana分別從下列廣義表中分離出來.
(1) l1=(((apple)),((pear)),(banana),orange);
[, , , , , , , ]
7. 對如圖所示的稀疏陣列，分別畫出採用三元組表和帶行指標向量的單鏈表表示。
5.3 演算法設計題:
1. 假設稀疏矩陣a和b均以三元組順序表作為儲存結構。試寫出矩陣相加的演算法，另設三元組表c存放結果矩陣。
2. 假設係數矩陣a和b均以三元組順序表作為儲存結構。試寫出滿足以下條件的矩陣相加的演算法：
假設三元組順序表a的空間足夠大，將矩陣b加到矩陣a上，不增加a，b之外的附加空間，你的演算法能否達到o（m+n）的時間複雜度？其中m和n分別為a，b矩陣中非零元的數目。
3．試編寫乙個以三元組形式輸出用十字鍊錶表示的稀疏矩陣中非零元素及其下標的演算法。
習題答案
資料結構練習題
習題3 棧和佇列 一 基本內容 棧和佇列的結構特點 在兩種儲存結構上如何實現棧和佇列的基本操作以及棧和佇列在程式設計中的應用。二 學習要點 1.掌握棧和佇列的特點。2 熟練掌握棧型別的兩種實現方法，即兩種儲存結構表示時的基本操作實現演算法，特別應注意棧滿和棧空的條件以及它們的描述方法。3 熟練掌握迴...
資料結構練習題
a.n b.n 1 2 c.n 1 9 對於乙個具有n個頂點和e條邊的無向圖，若採用鄰接表表示，則表頭向量的大小為 所有鄰接表中的接點總數是 b.n 1 c.n 1 d.n e a.e 2 b.e d.n e 10 已知乙個圖如圖7.1所示，若從頂點a出發按深度搜尋法進行遍歷，則可能得到的一種頂點序...
資料結構練習題
1 3個結點可構成棵不同形態的樹。2 利用直接選擇排序演算法對n個記錄進行排序，最壞的情況下，記錄交換的次數為 3 乙個圖的 表示法是唯一的，而 表示法是不唯一的。4 一棵深度為h的滿二叉樹上的結點總數為 一棵深度為h的完全二叉樹上的結點總數的最小值為 最大值為 5 在一棵完全二叉樹中有n個結點，對...