數(shù)據(jù)結(jié)構(gòu)答案第4章_第1頁(yè)
數(shù)據(jù)結(jié)構(gòu)答案第4章_第2頁(yè)
數(shù)據(jù)結(jié)構(gòu)答案第4章_第3頁(yè)
已閱讀5頁(yè),還剩6頁(yè)未讀 繼續(xù)免費(fèi)閱讀

下載本文檔

版權(quán)說(shuō)明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡(jiǎn)介

1、第4XXXX線性表-多維數(shù)組和XX表2005-07-14第4章廣義線性表一一多維數(shù)組和廣義表課后習(xí)題講解1 填空 數(shù)組通常只有兩種運(yùn)算:()和(),這決定了數(shù)組通常采用()結(jié)構(gòu)來(lái)實(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ǔ)地址是()。解答】1140 【分析】數(shù)組A中每行共有6個(gè)元素,元素A1510的前面共存儲(chǔ)了 (1

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

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

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

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

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

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

8、。如廣義表L=(), (a. b)的表頭為空表,但L不是空表。4. 一個(gè)稀疏矩陣如圖44所示,寫出對(duì)應(yīng)的三元組順序表和十字鏈表存儲(chǔ) 表示。解答】對(duì)應(yīng)的三元組順序表如圖4-5所示,十字鏈表如圖46所示。 I w 5. A為稀疏矩陣 > 試從空間和時(shí)間角度比擬采用二維數(shù)組和三元組順序表兩種不同的存儲(chǔ)結(jié)構(gòu)完成求運(yùn)算的優(yōu)缺點(diǎn)?!窘獯稹吭O(shè)稀疏矩陣為m行n列,如果采用二維數(shù)組存儲(chǔ)*其空間復(fù)雜度為O (mx n)因?yàn)橐獙⑺械木仃囋乩奂悠饋?lái),所以,需要用一個(gè)兩層的嵌套循環(huán),其時(shí)間復(fù)雜度亦 為O (mx n)如果采用三元組順序表進(jìn)行壓縮存儲(chǔ)、假設(shè)矩陣中有t個(gè)非零元素,其空間復(fù)雜 度為O,將所有的矩陣元

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

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

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

12、, (d, e, a)運(yùn)用Head函數(shù)和Tail函數(shù)取出LS中原子d的運(yùn)算是()。解答】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 設(shè)有三對(duì)角矩陣AnXn (行、列下標(biāo)均從0開(kāi)始)> 將其三條對(duì)角線上的元素逐行存于數(shù)組B3n-2中,使得Bk=aij求:用i,j表示k的下標(biāo)變換公式;用k表示i, j的下標(biāo)變換公式【解答】(1淒求i, j表示k的下標(biāo)變換公式就是要求在k之前已經(jīng)存儲(chǔ)了多少個(gè)非零元素這些非零元素的個(gè)數(shù)就是k的值。元釁aij求所在的行為i,列為j,那么在其前面的非零元素的個(gè)數(shù)是;k=2 + 3(i-1 )+(j- i

溫馨提示

  • 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。

評(píng)論

0/150

提交評(píng)論