數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)題-第5章答案2014-6-16

第5章數(shù)組與廣義表一、選擇題〔每題1分，共10分〕一個向量第一個元素的存儲地點(diǎn)是100，每個元素的長度為2，那么第5個元素的地點(diǎn)是〔A〕。A.110B.108C.100D.1202.在數(shù)組A中，每一個數(shù)組元素A[i][j]占用3個存儲字節(jié)，行下標(biāo)i從1到8，列下標(biāo)j從1到10。所有數(shù)組元素相繼寄存于一個連續(xù)的存儲空間中，那么寄存該數(shù)組起碼需要的存儲字節(jié)數(shù)是〔C〕。A.80B.100C.240D.270假定有60行70列的二維數(shù)組a[160,170]以列序?yàn)橹餍虼涡虼鎯?，其基地點(diǎn)為10000，每個元素占2個存儲單元，那么第32行第58列的元素a[32,58]的存儲地點(diǎn)為〔C〕?！矡o第0行第0列元素〕A.16902B.16904C.14454D.答案A,B,C均不對4.將一個A[1..100，1..100]的三對角矩陣，按行優(yōu)先存入一維數(shù)組B[1‥298]中，A中元素A6665〔即該元素下標(biāo)i=66，j=65〕，在B數(shù)組中的地點(diǎn)K為〔A〕。A.198B.195C.197D.1965.數(shù)組A[0..5,0..6]的每個元素占五個字節(jié)，將其按列優(yōu)先序次存儲在開端地點(diǎn)為1000的內(nèi)存單元中，那么元素A[5，5]的地點(diǎn)是〔A〕。A.1175B.1180C.1205D.12106.假定以行序?yàn)橹餍虼鎯ΧS數(shù)組A=array[1..100，1..100]，設(shè)每個數(shù)據(jù)元素占2個存儲單元，基地點(diǎn)為10，那么LOC[5，5]=〔B〕。A.808B.818C.1010D.10207.設(shè)有數(shù)組A[i,j]，數(shù)組的每個元素長度為3字節(jié)，i的值為1到8，j的值為1到10，數(shù)組從內(nèi)存首地點(diǎn)BA開始次序寄存，當(dāng)用以列為主寄存時，元素A[5，8]的存儲首地點(diǎn)為〔B〕。A.BA+141B.BA+180C.BA+222D.BA+2258.設(shè)有一個10階的對稱矩陣A，采用壓縮存儲方式，以行序?yàn)橹鞔鎯?，a11為第一元素，其存儲地點(diǎn)為1，每個元素占一個地點(diǎn)空間，那么a85的地點(diǎn)為〔B〕。A、13B、33C、18D、409.二維數(shù)組A的每個元素是由6個字符組成的串，其行下標(biāo)i=0,1,,8,列下標(biāo)j=1,2,,10。假定A按行先存儲，元素A[8,5]的開端地點(diǎn)與當(dāng)A按列先存儲時的元素〔B〕的開端地點(diǎn)相同。設(shè)每個字符占一個字節(jié)。A、A[8,5]B、A[3,10]C、A[5,8]D、A[0,9]10.假定對n階對稱矩陣A以行序?yàn)橹餍蚍绞綄⑵湎氯切蔚脑?包括主對角線上所有元素)依次寄存于一維數(shù)組B［1..(n(n+1))/2］中，那么在B中確定aij〔i<j〕的地點(diǎn)k的關(guān)系為〔B〕。A、i*(i-1)/2+jB、j*(j-1)/2+IC、i*(i+1)/2+jD、j*(j+1)/2+i11.對稀疏矩陣進(jìn)行壓縮存儲目的是〔C〕。A、便于進(jìn)行矩陣運(yùn)算B、便于輸入和輸出C、節(jié)儉存儲空間D、降低運(yùn)算的時間復(fù)雜度數(shù)組r存儲靜態(tài)鏈表，結(jié)點(diǎn)的next域指向后繼，工作指針j指向鏈中結(jié)點(diǎn)，使j沿鏈移動的操作為〔A〕。A、j=r[j].nextB、j=j+1C、j=j->nextD、j=r[j]->next13.數(shù)組A[0..4,-3..-1,5..7]中含有元素的個數(shù)為〔B〕。精選A、55B、45C、36D、1614.有一個100*90的稀疏矩陣，非0元素有10個，設(shè)每個整型數(shù)占2字節(jié)，那么用三元組表示該矩陣時，所需的字節(jié)數(shù)是〔B〕。A、60B、66C、18000D、3315.設(shè)二維數(shù)組A[1..m，1..n]〔即m行n列〕按行存儲在數(shù)組B[1..m*n]中，那么二維數(shù)組元素A[i，j]在一維數(shù)組B中的下標(biāo)為〔A〕。A、〔i-1〕*n+jB、〔i-1〕*n+j-1C、i*〔j-1〕D、j*m+i-116.A[N，N]是對稱矩陣，將下面三角〔包括對角線〕以行序存儲到一維數(shù)組T[N〔N+1〕/2]中，那么對任一上三角元素a[i][j]對應(yīng)T[k]的下標(biāo)k是〔B〕。A.i〔i-1〕/2+jB.j〔j-1〕/2+IC.i〔j-i〕/2+1D.j〔i-1〕/2+1設(shè)A是n*n的對稱矩陣，將A的對角線及對角線上方的元素以列為主的序次寄存在一維數(shù)組B[1..n(n+1)/2]中，對上述任一元素aij(1≤i，j≤n，且i≤j)在B中的地點(diǎn)為〔B〕。A、i(i-l)/2+jB、j(j-l)/2+IC、j(j-l)/2+i-1D、i(i-l)/2+j-118.關(guān)于以行為主序的存儲構(gòu)造來說．在數(shù)組A[c1..d1,c2..d2]中，c1和d1分別為數(shù)組A的第一維下標(biāo)的下、上界，c2和d2分別為第二維下標(biāo)的下、上界．每個數(shù)據(jù)元素占k個存儲單元，二維數(shù)組中任一元素a[i,j]的存儲地點(diǎn)可由〔B〕確定。A、Loc[i,j]=[(d2-c2+1)(i-c1)+(j-c2)]×kB、Loc[i,j]=[Loc[c1,c2]+[(d2-c2+1)(i-c1)+(j-c2)]×kC、Loc[i,j]=A[c1,c2]+[(d2-c2+1)(i-c1)+(j-c2)]×kD、Loc[i,j]=Loc[0,0]+[(d2-c2+1)(i-c1)+(j-c2)]×k設(shè)矩陣A是一個對稱矩陣，為了節(jié)儉存儲，將其下三角局部(如下列圖所示)按行序寄存在一維數(shù)組B[1..n(n-1)/2]|中，對下三角局部中任一元素〔i〉=j〕在一維數(shù)組B的下標(biāo)地點(diǎn)k值是〔B〕。A、i(i-1)/2+j-lB、i(i-1)／2+jC、i(i+1)/2+j-1D、i(i+1)／2+j20.稀疏矩陣一般的壓縮存儲方法有(C)兩種。A、二維數(shù)組和三維數(shù)組B、三元組和散列表C、三元組和十字鏈表D、散列表和十字鏈表參照題：21.數(shù)組SZ[-35，O10]含有元素數(shù)目為〔B〕。A、88B、99C、80D、9022.二維數(shù)組A的每個元素是由6個字符組成的串，其行下標(biāo)i=0、1、、8．列下標(biāo)i=1、2、、10。假定A按行先存儲，元素A[8，5]的開端地點(diǎn)與當(dāng)A按列先存儲時的元素〔B〕的開端地點(diǎn)相同。設(shè)每個字符占一個字節(jié)。A、A[8，5]B、A[3，10]C、A[5，8]D、A[0，9]23.設(shè)有一個10階的對稱矩陣A，采用壓縮破除計方式，以行序?yàn)橹鞔鎯Γ琣1,1為第一個元素，其存儲地點(diǎn)為1，每個元素占1個地點(diǎn)空間，那么a8,5的地點(diǎn)為〔B〕。精選A、13B、33C、18D、4024.稀疏矩陣進(jìn)行壓縮存儲目的是〔C〕。A、便于進(jìn)行矩陣運(yùn)算B、便于輸入和輸出C、節(jié)儉存儲空間D、降低運(yùn)算的時間復(fù)雜度25.用數(shù)組r存儲靜態(tài)鏈表，結(jié)點(diǎn)的next域指向后繼，工作指針j指向鏈中結(jié)點(diǎn)，使沿鏈移動的操作為〔A〕。A、j=r[j].nextB、j=j+1C、j=j->nextD、j=r[j]->next26.數(shù)組的根本操作主要包括〔C〕A、成立與刪除B、索引與改正C、接見與改正D、接見與索引27.設(shè)矩陣A是一個對稱矩陣，為了節(jié)儉空間，將其下三角矩陣按行序寄存在一維數(shù)組B[1，n〔n+1〕/2]中，對下三角局部中任一元素aij〔i≥j〕，在一維數(shù)B中下標(biāo)k的值是〔B〕。A、i〔i-1〕/2+j-1B、i〔i-1〕/2+jC、i〔i+1〕/2+j-1D、i〔i+1〕/2+j8.設(shè)有數(shù)組A[i,j]，數(shù)組的每個元素長度為3字節(jié)，i的值為1到8，j的值為1到10，數(shù)組從內(nèi)存首地點(diǎn)BA開始次序寄存，當(dāng)用以列為主寄存時，元素A[8，5]的存儲首地點(diǎn)為〔B〕。A、BA+141B、BA+180C、BA+222D、BA+225數(shù)組A中，每個元素的長度為3個字節(jié)，行下標(biāo)i從1到8，列下標(biāo)j從1到10，從首地點(diǎn)SA開始連續(xù)寄存的存儲器內(nèi)，該數(shù)組按行寄存，元素A[8][5]的開端地點(diǎn)為C。A．SA＋141B．SA＋144C．SA＋222D．SA＋225二、判斷題〔每題1分，共10分〕一個稀疏矩陣Am*n采用三元組形式表示，假定把三元組中相關(guān)行下標(biāo)與列下標(biāo)的值交換，并把m和n的值交換，那么就達(dá)成了Am*n的轉(zhuǎn)置運(yùn)算?！病痢扯S以上的數(shù)組其實(shí)是一種特殊的廣義表。〔√〕數(shù)組可當(dāng)作線性構(gòu)造的一種推廣，因此與線性表同樣，能夠?qū)λM(jìn)行插入，刪除等操作。×〕稀疏矩陣壓縮存儲后，必會失去隨機(jī)存取功能?！病獭?.所謂取廣義表的表尾就是返回廣義表中最后一個元素?！病痢?.廣義表是由零或多個原予或子表所組成的有限序列，所以廣義表可能為空表。(√)7.廣義表中的元素或許是一個不可切割的原子，或許是一個非空的廣義表?！病痢?.線性表能夠當(dāng)作是廣義表的特例，如果廣義表中的每個元素都是原子，那么廣義表便成為線性表。(√)9.假定一個廣義表的表頭為空表，那么此廣義表亦為空表。〔×〕10.數(shù)組元素的下標(biāo)值越大，存取時間越長。(×)數(shù)組是一種復(fù)雜的數(shù)據(jù)構(gòu)造：數(shù)組元素之間的關(guān)系既不是線性的，也不是樹形的(√)12.從邏輯構(gòu)造上看，n維數(shù)組的每個元素均屬于n個向量?！病獭?3.二維數(shù)組是其數(shù)據(jù)元素為線性表的線性表〔√〕數(shù)組是同種類值的會合?！病痢橙?、填空題〔每空1分，共10分〕1.二維數(shù)組按“行優(yōu)先次序〞存儲在內(nèi)存中，a11的存儲地點(diǎn)為LOC〔a11〕，那么元素aij的存儲地點(diǎn)為LOC〔aij〕=?！布俣恳粋€元素占2個存儲單元，1≤i≤n,1≤j≤m〕答案：Loc(a11)+((i-1)*m+j-1)*2精選2.二維數(shù)組A[4][4](即A[0..3][0..3])的元素開端地點(diǎn)是loc(A[0][0])=1000,元素的長度為2,那么LOC(A[2][2])的地點(diǎn)為。答案：10203.設(shè)有一個二維數(shù)組A[10][20]，按行寄存于一個連續(xù)的存儲空間中，A[0][0]的存儲地點(diǎn)是200，每個數(shù)組元素占1個存儲字，那么A[6][2]的存儲字地點(diǎn)是____________。答案：3224.二維數(shù)組a[4][5][6]〔下標(biāo)從0開始計，a有4*5*6個元素〕，每個元素的長度是2，那么a[2][3][4]的地點(diǎn)是1164。(設(shè)a[0][0][0]的地點(diǎn)是1000,數(shù)據(jù)以行為主方式存儲)解釋:LOC(aijk)=LOC(a000)+[v2*v3*(i-c1)+v3*(j-c2)+(k-c3)]*l(l為每個元素所占單元數(shù))5.對矩陣壓縮是為了節(jié)儉存儲空間。6.所謂稀疏矩陣指的是非零元很少(t<<m*n)且散布沒有規(guī)律。7.設(shè)有一個10階對稱矩陣A采用壓縮存儲方式〔以行為主序存儲：a11=1〕，那么a85的地點(diǎn)為33。解釋:(k=i(i-1)/2+j)(1<=i,j<=n)8.己知三對角矩陣A[1..9,1..9]的每個元素占2個單元，現(xiàn)將其三條對角線上的元素逐行存儲在開端地點(diǎn)為1000的連續(xù)的內(nèi)存單元中，那么元素A[7,8]的地點(diǎn)為1038。解釋:三對角矩陣按行存儲：k=2(i-1)+j(1<=i,j<=n)9.n階對稱矩陣a知足a[i][j]=a[j][i],i,j=1..n,，用一維數(shù)組t存儲時，t的長度為n(n+1)/2，當(dāng)i=j，a[i][j]=t[i(i+1)/2(或j(j+1)/2)],i>j,a[i][j]=t[i(i-1)/2+j],i<j,a[i][j]=t[j(j-1)/2+i(1<=i,j<=n)]。10.設(shè)n行n列的下三角矩陣A已壓縮到一維數(shù)組B[1..n*〔n+1〕/2]中，假定按行為主序存儲，那么A[i,j]對應(yīng)的B中存儲地點(diǎn)為i(i-1)/2+j(1<=i,j<=n)。10.設(shè)數(shù)組A[0..8,1..10],數(shù)組中任一元素A[i,j]均占內(nèi)存48個二進(jìn)制位，從首地點(diǎn)2000開始連續(xù)寄存在主內(nèi)存里，主內(nèi)存字長為16位，那么〔l〕寄存該數(shù)組起碼需要的單元數(shù)是270;〔2〕寄存數(shù)組的第8列的所有元素起碼需要的單元數(shù)是27;〔3〕數(shù)組按列存儲時，元素A[5,8]的開端地點(diǎn)是2204。11.用一維數(shù)組B與列優(yōu)先寄存帶狀矩陣A中的非零元素A[i,j](1≤i≤n,i-2≤j≤i+2),B中的第8個元素是A中的第1行，第3列的元素。設(shè)數(shù)組a[1..50,1..80]的基地點(diǎn)為2