1、第4XXXX線性表-多維數組和XX表2005-07-14第4章廣義線性表一一多維數組和廣義表課后習題講解1 填空 數組通常只有兩種運算：()和()，這決定了數組通常采用()結構來實現存儲。解答】存取，修改，順序存儲【分析】數組是一個具有固定格式和數量的數據集合，在數組上一般不能做插入、刪除元素的操作。除了初始化和銷毀之外，在數組中通常只有存取和 修改兩種操作$二維數組A中行下標從10到20，列下標從5到10，按行優先存儲，每個元素占4個存儲單元，A105的存儲地址是1000，那么元素A1510的存儲地址是()。解答】1140 【分析】數組A中每行共有6個元素，元素A1510的前面共存儲了 (1

2、5-10)X6+個元素，每個元素占4個存儲單元，所以，其存儲地址是1000+140=1140 -設有一個10階的對稱矩陣A采用壓縮存儲，A00為第一個元素，其存儲地址為每個元素占1個存儲單元，那么元素A85的存儲地址為()。解答】d+41分析】元素A85的前面共存儲了( 1 +2+8) +5=4個元素。稀疏矩陣一般壓縮存儲方法有兩種，分別是()和()。解答三元組順序表，十字鏈表(5)廣義表(a) , ( ( (b) ,c) ) , (d)的長度是()，深度是()，表頭是£) * 探是j -解答】3*4 > (a) > (b),c),(d)廣義表LS= (a (b, c,

3、d) , e)，用Head和Tail函數取出LS中原子b的運算是<老解答】HeadHeadTailLS2選擇題二維數組A的每個元素是由6個字符組成的串，行下標的范圍從08,列下標的范圍 是從09,那么存放A至少需要個字節，A的第8列和第5行共占個字節，假設A按行 優先方式存儲 > 元素A8的起始地址與當A按列優先方式存儲時的©元素的起始地址 一致°A90B180C240D 540 E108F114G54H A85 I A310 J A58 K A49解答】D，列和8個存儲單元，第90X 6=54 至少需要A個元素，所以，存放90列，共有10 rb. 行9為A【分

4、析】數組.第5行共有18個元素注意行列有一個交叉元素，所以，共占108個字節，元素A8按行優先存儲的起始地址為d+8 X 10+5二d+85設元素A曲 按列優先存儲的起始地址與之相同那么d+j X 9+i二d+85解此方程，得i=4, j=9。2將數組稱為隨機存取結構是因為A數組元素是隨機的B對數組任一元素的存取時間是相等的 c隨時可以對數組進行訪問D數組的存儲結構是不虛解答】B下面的說法中，不正確的選項是A數組是一種線性結構B數組是一種定長的線性結構C除了插入與刪除操作外數組的根本操作還有存取、修改檢索和排序等D數組的根本操作有存取修改檢索和排序等，沒有插人與刪除操*>、<* *

5、M解答】c【分析】數組屬于廣義線性表，數組被創立以后，其維數和每維中的元素個數是確定的，所以，數組通常沒有插入和刪除操作。對特殊矩陣采用壓縮存儲的目的主要是為了() * 茗、鼻 p<A表達變得簡單IB對矩陣元素的存取變得簡單C去掉矩陣中的多余元素D減少不必要的存儲空間解答】D【分析】在特殊矩陣中，有很多值相同的元素并且他們的分布有規律，沒有必要為值相同的元素重復存儲(5)下面()不屬于特殊矩陣。A對角矩陣B三角矩陣C稀疏矩陣D對稱矩陣 w<nB 解答】c()(6康廣義表A滿足Head (A)二Tail (A)那么A為A()B( )0 (),() D(),(),()解答】B下面的說法

6、中不正確的選項是A廣義表是一種多層次的結構B廣義表是一種非線性結構c廣義表是一種共享結構D廣義表是一種遞歸解萄B分析】從各層元素各自具有的線性矣系講，廣義表屬于線性結構。(8)下面的說法中、不正確的選項是()對稱矩陣只須存放包括主對角線元素在內的下(或上)三角的元素即對角矩陣只須存放非零元素即可。稀疏矩陣中值為零的元素較多,.a I.此可以采用三元組表方法存儲。 1 D稀疏矩陣中大量值為零的元素分布有規律因此可以采用三元組表方法存儲解答】D如果零元素的分布有規律，因此采用三元組表存儲-稀疏矩陣中大量值為 零的元素分布 沒有規律，【分析】就沒有必要存儲非零元素的行號和列號，而需要按其壓縮規律找出

7、相 應的映象函數43.判斷題(1敷組是一種復雜的數據結構，數組元素之間的矢系既不是線性的 > 也不 是樹形的。解答】錯例如二維數組可以看成是數據元素為線性表的線性表。(2膜用三元組表存儲稀疏矩陣的元素 > 有時并不能節省存儲空間-【解答】對。因為三元組表除了存儲非零元素值外，還需要存儲其行號和列號。(3)稀疏矩陣壓縮存儲后，必會失去隨機存取功能。3【解答】對«因為壓縮存儲后，非零元素的存儲位置和行號列號之間失去了確定的矢線性表可以看成是廣義表的特例如果廣義表中的每個元素都是單元素，那么廣義表便成為線性表。解答對.(5假設廣義表的表頭為空表，那么此廣義表亦為空表0【解答】錯

8、。如廣義表L=(), (a. b)的表頭為空表，但L不是空表。4. 一個稀疏矩陣如圖44所示,寫出對應的三元組順序表和十字鏈表存儲 表示。解答】對應的三元組順序表如圖4-5所示，十字鏈表如圖46所示。 I w 5. A為稀疏矩陣 > 試從空間和時間角度比擬采用二維數組和三元組順序表兩種不同的存儲結構完成求運算的優缺點?！窘獯稹吭O稀疏矩陣為m行n列，如果采用二維數組存儲*其空間復雜度為O (mx n)因為要將所有的矩陣元素累加起來，所以，需要用一個兩層的嵌套循環，其時間復雜度亦 為O (mx n)如果采用三元組順序表進行壓縮存儲、假設矩陣中有t個非零元素，其空間復雜 度為O，將所有的矩陣元

9、素累加起來只需將三元組順序表掃描一遍，其時間復雜度亦為O組順序表存儲可獲得較好的時、空性能。當t«mx時，采用三元6. 設某單位職工工資表ST由工資“扣除和實發金額三項組成，其中工資項包 括一根本工資w 11津貼和44獎金"，扣除項包括 詠戶電"和 弈氣"。請用廣義表形式表示所描述的工資表ST并用表頭和表尾求表中的獎金"項;畫出該工資表ST的存儲結構。 W【解答】ST=(根本工資，津貼，獎金)，(水,電，煤氣),實發金額)Head(Tail(Tail(Head(ST)獎金7.所示。4-7的頭尾表示法如圖ST工資表(2).假設在矩陣A中存在一，該

10、元素是第i行個元素 ai,j(0< i Wn Ow j元素中最小值且又是第j列元索中最大值，那么稱此元索為該矩陣的一個馬鞍點。假設以二維 數組存儲矩陣A,試設計一個求該矩陣所有馬鞍點的算法，并分析最壞情況下的時間復雜度。F、廠3 L F 事 * r LT. P 亍 - I尸 ? r .4 . "【解答】在矩陣中逐行尋找該行中的最小值*然后對其所在的列尋找最大值'如果該列上的最大值與該行上的最小值相等'那么說明該元素是鞍點 > 將它所在行號和列號輸出。具體算法如下：分析算法，夕卜層for循環共執行n次，內層第一個for循環執行m次，第二個for循 環最壞情況

11、下執行n次，所以,最壞情況下的時間復雜度為O(mn+n2)。學習自測及答案1 二維數組M中每個元素的長度是3個字節，行下標從0到乙列下標從O到9，從首 地址d開始存儲。假設按行優先方式存儲，元素M75的起始地址為()，假設按列優先方式存 儲上元素M75的超始地址為()©解答】d+22 > d+141扌W2 .個nxn勺對稱矩陣，按行優先或列優先進行壓縮存儲，那么其存儲容量為(解答】n(n+1)/23設n行n列旳下三角矩陣A (行列下標均從1開始)已壓縮到一*維數組在數組S中的存儲位置是S1Sn(n+1)/2中*假設按行優先存儲 > 貝J4 廣義表LS=(a, (b, c)

12、, (d, e, a)運用Head函數和Tail函數取出LS中原子d的運算是()。解答】Head(Head(Tail(Tail(LS)J T Z5.廣義表佝b, (c, (d)的表尾是()»A (d) B (c,(d) C b,(c,(d) D (b,(c,(d)解答】D6 設有三對角矩陣AnXn (行、列下標均從0開始)> 將其三條對角線上的元素逐行存于數組B3n-2中，使得Bk=aij求:用i,j表示k的下標變換公式;用k表示i, j的下標變換公式【解答】(1淒求i, j表示k的下標變換公式就是要求在k之前已經存儲了多少個非零元素這些非零元素的個數就是k的值。元釁aij求所在的行為i,列為j,那么在其前面的非零元素的個數是；k=2 + 3(i-1 )+(j- i