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