數(shù)據(jù)結(jié)構(gòu)答案第4章

數(shù)據(jù)結(jié)構(gòu)答案第4章數(shù)據(jù)結(jié)構(gòu)答案第4章數(shù)據(jù)結(jié)構(gòu)答案第4章數(shù)據(jù)結(jié)構(gòu)答案第4章編制僅供參考審核批準(zhǔn)生效日期地址：電話：傳真:郵編:第4章廣義線性表——多維數(shù)組和廣義表2005-07-14第4章廣義線性表——多維數(shù)組和廣義表課后習(xí)題講解1.填空⑴數(shù)組通常只有兩種運算：（）和（），這決定了數(shù)組通常采用（）結(jié)構(gòu)來實現(xiàn)存儲。

【解答】存取，修改，順序存儲

【分析】數(shù)組是一個具有固定格式和數(shù)量的數(shù)據(jù)集合，在數(shù)組上一般不能做插入、刪除元素的操作。除了初始化和銷毀之外，在數(shù)組中通常只有存取和修改兩種操作。⑵二維數(shù)組A中行下標(biāo)從10到20，列下標(biāo)從5到10，按行優(yōu)先存儲，每個元素占4個存儲單元，A[10][5]的存儲地址是1000，則元素A[15][10]的存儲地址是（）。

【解答】1140

【分析】數(shù)組A中每行共有6個元素，元素A[15][10]的前面共存儲了(15-10)×6+5個元素，每個元素占4個存儲單元，所以，其存儲地址是1000+140=1140。⑶設(shè)有一個10階的對稱矩陣A采用壓縮存儲，A[0][0]為第一個元素，其存儲地址為d，每個元素占1個存儲單元，則元素A[8][5]的存儲地址為（）。

【解答】d+41

【分析】元素A[8][5]的前面共存儲了(1+2+…+8)+5=41個元素。⑷稀疏矩陣一般壓縮存儲方法有兩種，分別是（）和（）。

【解答】三元組順序表，十字鏈表⑸廣義表((a),(((b),c)),(d))的長度是（），深度是（），表頭是（），表尾是（）。

【解答】3，4，(a)，((((b),c)),(d))⑹已知廣義表LS=(a，(b，c，d)，e)，用Head和Tail函數(shù)取出LS中原子b的運算是（）。

【解答】Head(Head(Tail(LS)))2.選擇題⑴二維數(shù)組A的每個元素是由6個字符組成的串，行下標(biāo)的范圍從0~8，列下標(biāo)的范圍是從0~9，則存放A至少需要（）個字節(jié)，A的第8列和第5行共占（）個字節(jié)，若A按行優(yōu)先方式存儲，元素A[8][5]的起始地址與當(dāng)A按列優(yōu)先方式存儲時的（）元素的起始地址一致。

A90B180C240D540E108F114G54

HA[8][5]IA[3][10]JA[5][8]KA[4][9]

【解答】D，E，K

【分析】數(shù)組A為9行10列，共有90個元素，所以，存放A至少需要90×6=540個存儲單元，第8列和第5行共有18個元素（注意行列有一個交叉元素），所以，共占108個字節(jié)，元素A[8][5]按行優(yōu)先存儲的起始地址為d+8×10+5=d+85，設(shè)元素A[i][j]按列優(yōu)先存儲的起始地址與之相同，則d+j×9+i=d+85，解此方程，得i=4，j=9。⑵將數(shù)組稱為隨機存取結(jié)構(gòu)是因為（）

A數(shù)組元素是隨機的B對數(shù)組任一元素的存取時間是相等的

C隨時可以對數(shù)組進行訪問D數(shù)組的存儲結(jié)構(gòu)是不定

【解答】B⑶下面的說法中，不正確的是（）

A數(shù)組是一種線性結(jié)構(gòu)B數(shù)組是一種定長的線性結(jié)構(gòu)

C除了插入與刪除操作外，數(shù)組的基本操作還有存取、修改、檢索和排序等

D數(shù)組的基本操作有存取、修改、檢索和排序等，沒有插入與刪除操

【解答】C

【分析】數(shù)組屬于廣義線性表，數(shù)組被創(chuàng)建以后，其維數(shù)和每維中的元素個數(shù)是確定的，所以，數(shù)組通常沒有插入和刪除操作。⑷對特殊矩陣采用壓縮存儲的目的主要是為了（）

A表達(dá)變得簡單B對矩陣元素的存取變得簡單

C去掉矩陣中的多余元素D減少不必要的存儲空間

【解答】D

【分析】在特殊矩陣中，有很多值相同的元素并且他們的分布有規(guī)律，沒有必要為值相同的元素重復(fù)存儲。⑸下面（）不屬于特殊矩陣。

A對角矩陣B三角矩陣C稀疏矩陣D對稱矩陣

【解答】C⑹若廣義表A滿足Head(A)=Tail(A)，則A為（）

A()B(())C((),())D((),(),())

【解答】B⑺下面的說法中，不正確的是（）

A廣義表是一種多層次的結(jié)構(gòu)B廣義表是一種非線性結(jié)構(gòu)

C廣義表是一種共享結(jié)構(gòu)D廣義表是一種遞歸

【解答】B

【分析】從各層元素各自具有的線性關(guān)系講，廣義表屬于線性結(jié)構(gòu)。⑻下面的說法中，不正確的是（）

A對稱矩陣只須存放包括主對角線元素在內(nèi)的下（或上）三角的元素即可。

B對角矩陣只須存放非零元素即可。

C稀疏矩陣中值為零的元素較多，因此可以采用三元組表方法存儲。

D稀疏矩陣中大量值為零的元素分布有規(guī)律，因此可以采用三元組表方法存儲

【解答】D

【分析】稀疏矩陣中大量值為零的元素分布沒有規(guī)律，因此采用三元組表存儲。如果零元素的分布有規(guī)律，就沒有必要存儲非零元素的行號和列號，而需要按其壓縮規(guī)律找出相應(yīng)的映象函數(shù)。3.判斷題⑴數(shù)組是一種復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，數(shù)組元素之間的關(guān)系既不是線性的，也不是樹形的。

【解答】錯。例如二維數(shù)組可以看成是數(shù)據(jù)元素為線性表的線性表。⑵使用三元組表存儲稀疏矩陣的元素，有時并不能節(jié)省存儲空間。

【解答】對。因為三元組表除了存儲非零元素值外，還需要存儲其行號和列號。⑶稀疏矩陣壓縮存儲后，必會失去隨機存取功能。

【解答】對。因為壓縮存儲后，非零元素的存儲位置和行號、列號之間失去了確定的關(guān)系。⑷線性表可以看成是廣義表的特例，如果廣義表中的每個元素都是單元素，則廣義表便成為線性表。

【解答】對。⑸若一個廣義表的表頭為空表，則此廣義表亦為空表。

【解答】錯。如廣義表L=(()，(a，b))的表頭為空表，但L不是空表。4．一個稀疏矩陣如圖4-4所示，寫出對應(yīng)的三元組順序表和十字鏈表存儲表示。

【解答】對應(yīng)的三元組順序表如圖4-5所示，十字鏈表如圖4-6所示。5．已知A為稀疏矩陣，試從空間和時間角度比較采用二維數(shù)組和三元組順序表兩種不同的存儲結(jié)構(gòu)完成求運算的優(yōu)缺點。

【解答】設(shè)稀疏矩陣為m行n列，如果采用二維數(shù)組存儲，其空間復(fù)雜度為Ｏ(m×n)；因為要將所有的矩陣元素累加起來，所以，需要用一個兩層的嵌套循環(huán)，其時間復(fù)雜度亦為Ｏ(m×n)。如果采用三元組順序表進行壓縮存儲，假設(shè)矩陣中有t個非零元素，其空間復(fù)雜度為Ｏ(t)，將所有的矩陣元素累加起來只需將三元組順序表掃描一遍，其時間復(fù)雜度亦為Ｏ(t)。當(dāng)t<<m×n時，采用三元組順序表存儲可獲得較好的時、空性能。6．設(shè)某單位職工工資表ST由“工資”、“扣除”和“實發(fā)金額”三項組成，其中工資項包括“基本工資”、“津貼”和“獎金”，扣除項包括“水”、“電”和“煤氣”。⑴請用廣義表形式表示所描述的工資表ST，并用表頭和表尾求表中的“獎金”項；

⑵畫出該工資表ST的存儲結(jié)構(gòu)。

【解答】⑴ST=((基本工資，津貼，獎金)，(水，電，煤氣)，實發(fā)金額)

Head(Tail(Tail(Head(ST))))=獎金

⑵工資表ST的頭尾表示法如圖4-7所示。7．若在矩陣A中存在一個元素ai,j（0≤i≤n-1，0≤j≤m-1），該元素是第i行元素中最小值且又是第j列元素中最大值，則稱此元素為該矩陣的一個馬鞍點。假設(shè)以二維數(shù)組存儲矩陣A，試設(shè)計一個求該矩陣所有馬鞍點的算法，并分析最壞情況下的時間復(fù)雜度。

【解答】在矩陣中逐行尋找該行中的最小值，然后對其所在的列尋找最大值，如果該列上的最大值與該行上的最小值相等，則說明該元素是鞍點，將它所在行號和列號輸出。具體算法如下：分析算法，外層for循環(huán)共執(zhí)行n次，內(nèi)層第一個for循環(huán)執(zhí)行m次，第二個for循環(huán)最壞情況下執(zhí)行n次，所以，最壞情況下的時間復(fù)雜度為Ｏ(mn+n2)。學(xué)習(xí)自測及答案1．二維數(shù)組M中每個元素的長度是3個字節(jié)，行下標(biāo)從0到7，列下標(biāo)從0到9，從首地址d開始存儲。若按行優(yōu)先方式存儲，元素M[7][5]的起始地址為（），若按列優(yōu)先方式存儲，元素M[7][5]的起始地址為（）。

【解答】d+22，d+1412．一個n×n的對稱矩陣，按行優(yōu)先或列優(yōu)先進行壓縮存儲，則其存儲容量為（）。

【解答】n(n+1)/23．設(shè)n行n列的下三角矩陣A（行列下標(biāo)均從1開始）已壓縮到一維數(shù)組S[1]~S[n(n+1)/2]中，若按行優(yōu)先存儲，則A[i][j]在數(shù)組S中的存儲位置是（）。

【解答】i×(i-1)/2+j4．已知廣義表LS=(a,(b,c),(d,e,a))，運用Head函數(shù)和Tail函數(shù)取出LS中原子d的運算是（）。

【解答】Head(Head(Tail(Tail(LS))))5．廣義表(a,b,(c,(d)))的表尾是（）。

A(d)B(c,(d))Cb,(c,(d))D(b,(c,(d)))

【解答】D6．設(shè)有三對角矩陣An×n（行、列下標(biāo)均從0開始），將其三條對角線上的元素逐行存于數(shù)組B[3n-2]中，使得B[k]=aij求：

⑴用i,j表示k的下標(biāo)變換公式；

⑵用k表示i,j的下標(biāo)變換公式。

【解答】⑴要求i,j表示k的下標(biāo)變換公式，就是要求在k之前已經(jīng)存儲了多少個非零元素，這些非零元素的個數(shù)就是k的值。元素aij求所在的行為i，列為j，則在其前面的非零元素的