數(shù)據(jù)結(jié)構(gòu)習(xí)題廣義線性表多維數(shù)組和廣義表

1、第 4 章 廣義線性表多維數(shù)組和廣義表 課后習(xí)題講解 1. 填空 數(shù)組通常只有兩種運(yùn)算：（ ）和（ ），這決定了數(shù)組通常采用（ ）結(jié)構(gòu)來實(shí)現(xiàn)存儲(chǔ)?！窘獯稹看嫒?，修改，順序存儲(chǔ)【分析】數(shù)組是一個(gè)具有固定格式和數(shù)量的數(shù)據(jù)集合，在數(shù)組上一般不能做插入、刪除元素的操作。除了初始化和銷毀之外，在數(shù)組中通常只有存取和修改兩種操作。 二維數(shù)組A中行下標(biāo)從10到20，列下標(biāo)從5到10，按行優(yōu)先存儲(chǔ)，每個(gè)元素占4個(gè)存儲(chǔ)單元，A105的存儲(chǔ)地址是1000，則元素A1510的存儲(chǔ)地址是（ ）?！窘獯稹?140【分析】數(shù)組A中每行共有6個(gè)元素，元素A1510的前面共存儲(chǔ)了(15-10)×6+5個(gè)元素，每個(gè)元

2、素占4個(gè)存儲(chǔ)單元，所以，其存儲(chǔ)地址是1000+140=1140。 設(shè)有一個(gè)10階的對(duì)稱矩陣A采用壓縮存儲(chǔ)，A00為第一個(gè)元素，其存儲(chǔ)地址為d，每個(gè)元素占1個(gè)存儲(chǔ)單元，則元素A85的存儲(chǔ)地址為（ ）?！窘獯稹縟+41【分析】元素A85的前面共存儲(chǔ)了(1+2+8)+5=41個(gè)元素。 稀疏矩陣一般壓縮存儲(chǔ)方法有兩種，分別是（ ）和（ ）?！窘獯稹咳M順序表，十字鏈表 下面的說法中，不正確的是（）A 數(shù)組是一種線性結(jié)構(gòu) B 數(shù)組是一種定長(zhǎng)的線性結(jié)構(gòu) C 除了插入與刪除操作外，數(shù)組的基本操作還有存取、修改、檢索和排序等D 數(shù)組的基本操作有存取、修改、檢索和排序等，沒有插入與刪除操【解答】C【分析】數(shù)組

3、屬于廣義線性表，數(shù)組被創(chuàng)建以后，其維數(shù)和每維中的元素個(gè)數(shù)是確定的，所以，數(shù)組通常沒有插入和刪除操作。 對(duì)特殊矩陣采用壓縮存儲(chǔ)的目的主要是為了（）A 表達(dá)變得簡(jiǎn)單 B 對(duì)矩陣元素的存取變得簡(jiǎn)單C 去掉矩陣中的多余元素 D 減少不必要的存儲(chǔ)空間【解答】D【分析】在特殊矩陣中，有很多值相同的元素并且他們的分布有規(guī)律，沒有必要為值相同的元素重復(fù)存儲(chǔ)。 下面（）不屬于特殊矩陣。A 對(duì)角矩陣 B 三角矩陣 C 稀疏矩陣 D 對(duì)稱矩陣 【解答】C 若廣義表A滿足Head(A)=Tail(A)，則A為（ ）A ( ) B ( ) C ( ),( ) D( ),( ),( )【解答】B 下面的說法中，不正確的是

4、（）A 廣義表是一種多層次的結(jié)構(gòu) B 廣義表是一種非線性結(jié)構(gòu)C 廣義表是一種共享結(jié)構(gòu) D 廣義表是一種遞歸【解答】B【分析】從各層元素各自具有的線性關(guān)系講，廣義表屬于線性結(jié)構(gòu)。 下面的說法中，不正確的是（）A 對(duì)稱矩陣只須存放包括主對(duì)角線元素在內(nèi)的下（或上）三角的元素即可。B 對(duì)角矩陣只須存放非零元素即可。C 稀疏矩陣中值為零的元素較多，因此可以采用三元組表方法存儲(chǔ)。D 稀疏矩陣中大量值為零的元素分布有規(guī)律，因此可以采用三元組表方法存儲(chǔ)【解答】D【分析】稀疏矩陣中大量值為零的元素分布沒有規(guī)律，因此采用三元組表存儲(chǔ)。如果零元素的分布有規(guī)律，就沒有必要存儲(chǔ)非零元素的行號(hào)和列號(hào)，而需要按其壓縮規(guī)律找

5、出相應(yīng)的映象函數(shù)。3. 判斷題 數(shù)組是一種復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，數(shù)組元素之間的關(guān)系既不是線性的，也不是樹形的。【解答】錯(cuò)。例如二維數(shù)組可以看成是數(shù)據(jù)元素為線性表的線性表。 使用三元組表存儲(chǔ)稀疏矩陣的元素，有時(shí)并不能節(jié)省存儲(chǔ)空間。【解答】對(duì)。因?yàn)槿M表除了存儲(chǔ)非零元素值外，還需要存儲(chǔ)其行號(hào)和列號(hào)。 稀疏矩陣壓縮存儲(chǔ)后，必會(huì)失去隨機(jī)存取功能。【解答】對(duì)。因?yàn)閴嚎s存儲(chǔ)后，非零元素的存儲(chǔ)位置和行號(hào)、列號(hào)之間失去了確定的關(guān)系。 線性表可以看成是廣義表的特例，如果廣義表中的每個(gè)元素都是單元素，則廣義表便成為線性表。【解答】對(duì)。 若一個(gè)廣義表的表頭為空表，則此廣義表亦為空表?！窘獯稹垮e(cuò)。如廣義表L=( )，(a

6、，b)的表頭為空表，但L不是空表。4一個(gè)稀疏矩陣如圖4-4所示，寫出對(duì)應(yīng)的三元組順序表和十字鏈表存儲(chǔ)表示?！窘獯稹繉?duì)應(yīng)的三元組順序表如圖4-5所示，十字鏈表如圖4-6所示。5已知A為稀疏矩陣，試從空間和時(shí)間角度比較采用二維數(shù)組和三元組順序表兩種不同的存儲(chǔ)結(jié)構(gòu)完成求 運(yùn)算的優(yōu)缺點(diǎn)?！窘獯稹吭O(shè)稀疏矩陣為m行n列，如果采用二維數(shù)組存儲(chǔ)，其空間復(fù)雜度為(m×n)；因?yàn)橐獙⑺械木仃囋乩奂悠饋恚?，需要用一個(gè)兩層的嵌套循環(huán)， 其時(shí)間復(fù)雜度亦為(m×n)。如果采用三元組順序表進(jìn)行壓縮存儲(chǔ)，假設(shè)矩陣中有t個(gè)非零元素，其空間復(fù)雜度為(t)，將所有的矩陣元素累加起來只需將 三元組順序表掃

7、描一遍，其時(shí)間復(fù)雜度亦為(t)。當(dāng)t << m×n時(shí)，采用三元組順序表存儲(chǔ)可獲得較好的時(shí)、空性能。6設(shè)某單位職工工資表ST由“工資”、“扣除”和“實(shí)發(fā)金額”三項(xiàng)組成，其中工資項(xiàng)包括“基本工資”、“津貼”和“獎(jiǎng)金”，扣除項(xiàng)包括“水”、“電”和“煤氣” 。 請(qǐng)用廣義表形式表示所描述的工資表ST，并用表頭和表尾求表中的“獎(jiǎng)金”項(xiàng)； 畫出該工資表ST的存儲(chǔ)結(jié)構(gòu)。【解答】 ST=(基本工資，津貼，獎(jiǎng)金)，(水，電，煤氣)，實(shí)發(fā)金額)Head(Tail(Tail(Head(ST)=獎(jiǎng)金 工資表ST的頭尾表示法如圖4-7所示。7若在矩陣A中存在一個(gè)元素ai,j（0in-1，0jm-1）

8、，該元素是第i行元素中最小值且又是第j列元素中最大值，則稱此元素為該矩陣的一個(gè)馬鞍點(diǎn)。假設(shè)以二維數(shù)組存儲(chǔ)矩陣A，試設(shè)計(jì)一個(gè)求該矩陣所有馬鞍點(diǎn)的算法，并分析最壞情況下的時(shí)間復(fù)雜度。【解答】在矩陣中逐行尋找該行中的最小值，然后對(duì)其所在的列尋找最大值，如果該列上的最大值與該行上的最小值相等，則說明該元素是鞍點(diǎn)，將它所在行號(hào)和列號(hào)輸出。具體算法如下：分析算法，外層for循環(huán)共執(zhí)行n次，內(nèi)層第一個(gè)for循環(huán)執(zhí)行m次，第二個(gè)for循環(huán)最壞情況下執(zhí)行n次，所以，最壞情況下的時(shí)間復(fù)雜度為(mn+n2)。 學(xué)習(xí)自測(cè)及答案 1二維數(shù)組M中每個(gè)元素的長(zhǎng)度是3個(gè)字節(jié)，行下標(biāo)從0到7，列下標(biāo)從0到9，從首地址d開始存儲(chǔ)

9、。若按行優(yōu)先方式存儲(chǔ)，元素M75的起始地址為（ ），若按列優(yōu)先方式存儲(chǔ)，元素M75的起始地址為（ ）?！窘獯稹縟+22，d+1412一個(gè)n×n的對(duì)稱矩陣，按行優(yōu)先或列優(yōu)先進(jìn)行壓縮存儲(chǔ)，則其存儲(chǔ)容量為（ ）?！窘獯稹縩(n+1)/23設(shè)n行n列的下三角矩陣A（行列下標(biāo)均從1開始）已壓縮到一維數(shù)組S1Sn(n+1)/2中，若按行優(yōu)先存儲(chǔ)，則Aij在數(shù)組S中的存儲(chǔ)位置是（ ）。【解答】i×(i-1)/2+j4已知廣義表LS=(a, (b, c), (d, e, a)，運(yùn)用Head函數(shù)和Tail函數(shù)取出LS中原子d的運(yùn)算是（ ）?！窘獯稹縃ead(Head(Tail(Tail(LS

10、)5廣義表(a, b, (c, (d)的表尾是（ ）。A (d) B (c,(d) C b,(c,(d) D (b,(c,(d)【解答】D6設(shè)有三對(duì)角矩陣An×n（行、列下標(biāo)均從0開始），將其三條對(duì)角線上的元素逐行存于數(shù)組B3n-2中，使得Bk=aij求： 用i, j表示k的下標(biāo)變換公式； 用k表示i, j的下標(biāo)變換公式?！窘獯稹?要求i, j表示k的下標(biāo)變換公式，就是要求在k之前已經(jīng)存儲(chǔ)了多少個(gè)非零元素，這些非零元素的個(gè)數(shù)就是k的值。元素aij求所在的行為i，列為j，則在其前面的非零元素的個(gè)數(shù)是；k=2 + 3(i1)+( ji + 1)= 2i+ j。 因?yàn)閗和i, j之間是一一對(duì)應(yīng)的關(guān)系，k