數(shù)據(jù)結構復習題第5章2022616

第5章數(shù)組與廣義表一、選擇題（每題1分，共10分）.一個向量第一個元素的儲存地址是100,每一個元素的長度為2,則第5個元素的地址是（A）o.在數(shù)組A中，每一個數(shù)組元素A用[占]用3個儲存字節(jié)，行下標i從1到8,列下標j從1到10。全部數(shù)組元素接踵存放于一個連續(xù)的儲存空間中，則存放該數(shù)組至少需要的儲存字節(jié)數(shù)是（Oo.假設有60行70列的二維數(shù)組a[l60,1以0列]序為主序次序儲存，其基地址為10000,每一個元素占2個儲存單元，那末第32行第58列的元素a[32,58]的儲存地址為（C）o（無第。行第0列元素）C.14454D.答案A,B,C均不對.將一個A[1..100,1..100]的三對角矩陣，按行優(yōu)先存入一維數(shù)組 B[l??298]中，A中元素A6665（即該元素下標i=66,j=65）,在B數(shù)組中的地點長為（A）。.數(shù)組A[0..5,0..6]的每一個元素占五個字節(jié)，將其按列優(yōu)先次序儲存在初步地址為1000的內(nèi)存單元中，則元素A[5,5]的地址是（A）o.假設以行序為主序儲存二維數(shù)組 A=array[1..100,1..100],設每一個數(shù)據(jù)元素占2個儲存單元，基地址為10,則LOC[5,5]=（B）o.設有數(shù)組A[i,j],數(shù)組的每一個元素長度為3字節(jié)，i的值為1到8,j的值為1到10,數(shù)組從內(nèi)存首地址BA開始次序存放，當用以列為主存放時，元素A[5,8]的存儲首地址為(B)oA.BA+141B.BA+180 C.BA+222D.BA+225.設有一個10階的對稱矩陣A,采用壓縮儲存方式，以行序為主儲存，all為第一元素，其儲存地址為1,每一個元素占一個地址空間，則a85的地址為(B)oA、13B、33C、18D、40.二維數(shù)組A的每一個元素是由6個字符構成的串，其行下標i=0,l,冽，下標>1,2,,10o若A按行先儲存，元素A[8,5]的初步地址與當A按列先儲存時的元素(B)的初步地址相同。設每一個字符占一個字節(jié)。A、A[8,5]B、A[3,10]C>A[5,8]D、A[0,9].若對n階對稱矩陣A以行序為主序方式將其下三角形的元素(包含主對角線上全部元素)挨次存放于一維數(shù)組B[l..(n(n+l))/]2中，則在B中確立aij(ivj)的地點k的關系為(B)oA、i*(i-l)/2+jB、j*(j-l)/2+IC、i*(i+l)/2+jD、j*(j+l)/2+i.對希少矩陣進行壓縮儲存目的是(OoA、便于進行矩陣運算B、便于輸入和輸出C、節(jié)約儲存空間D、降低運算的時間復雜度.數(shù)組r儲存靜態(tài)鏈表，結點的next域指向后繼，工作指針j指向鏈中結點，使j沿鏈挪動的操作為(A)oA、j=r[j].nextB、j=j+lC、j=j->nextD、j=r[j]->next.數(shù)組A[0?.4,-3.?-l,5??7]中含有元素的個數(shù)為(B)o精心整理A、55B、45C、36D、16.有一個100*90的希少矩陣，非0元素有10個，設每一個整型數(shù)占2字節(jié)，則用三元組表示該矩陣時，所需的字節(jié)數(shù)是(B)oA、60B、66C、18000D、33.設二維數(shù)組l..n](即m行n列)按行儲存在數(shù)組中，則二維數(shù)組元素A[i,j]在一維數(shù)組B中的下標為(A)oA、(i-1)*n+jB、(i-1)*n+j-lC、i*(j-1)D、j*m+i-l.A[N,N]是對稱矩陣，將下邊三角(包含對角線)以行序儲存到一維數(shù)組 T[N(N+1)/2]中，則對任一上三角元素對應T[k]的下標k是(B)。A.i(i-1) (j-1) (j-i) (i-1)/2+1.設A是n*n的對稱矩陣，將A的對角線及對角線上方的元素以列為主的次序存放在一維數(shù)組B[l..n(n+l)/2中],對上述任一元素aij(Wli,jWn,且iWj)在B中的地點為(B)oA、i(i-l)/2+jB、j(j-l)/2+IC、j(j-l)/2+i-lD、i(i-l)/2+j-l.對于以行為主序的儲存結構來說.在數(shù)組A[cLdl,c2..d2]中，cl和dl分別為數(shù)組A的第一維下標的下、上界，c2和d2分別為第二維下標的下、上界.每一個數(shù)據(jù)元素占k個儲存單元，二維數(shù)組中任一元素a[i,的]儲存地點可由(B)確立。A、Loc[i,j]=[(d2-c2+l)(i-cl)+(j-c2)]XkB、Loc[i,j]=[Loc[cl,c2]+[(d2-c2+l)(i-cl)+(j-c2)]XkC、Loc[i,j]=A[cl,c2]+[(d2-c2+l)(i-cl)+(j-c2)]XkD、Loc[i,j]=Loc[0,0]+[(d2-c2+l)(i-cl)+(j-c2)]Xk精心整理.設矩陣A是一個對稱矩陣，為了節(jié)約儲存，將其下三角部份 以（以下圖所示）按行序存放在一維數(shù)組B[Lm（n-l）/2]|中，對下三角部份中任一元素 （i〉=j）在一維數(shù)組B的下標地點k值是（B）。A、i（i-l）/2+j-lB>i（i-l）/2+jC、i（i+l）/2+j-lD、i（i+l）/2+j.希少矩陣普通的壓縮儲存方法有（C）兩種。A、二維數(shù)組和三維數(shù)組B、三元組和散列表C、三元組和十字鏈表D、散列表和十字鏈表參照題：.數(shù)組SZ[-3,5010]含有元素數(shù)量為（B）oA、88B、99C、80D、90.二維數(shù)組A的每一個元素是由6個字符構成的串，其行下標i=0、1、 、 8.列下標i=l、2、 、 10o若A按行先儲存，元素A[8,5]的初步地址與當A按列先儲存時的元素（B）的初步地址相同。設每一個字符占一個字節(jié)。A、A[8,5]B、A[3,10]C>A[5,8]D、A[0,9].設有一個10階的對稱矩陣A,采用壓縮破除計方式，以行序為主儲存，al,1為第一個元素，其儲存地址為1,每一個元素占1個地址空間，則a8,5的地址為（B）oA、13B、33C、18D、40.希少矩陣進行壓縮儲存目的是（C）oA、便于進行矩陣運算B、便于輸入和輸出C、節(jié)約儲存空間D、降低運算的時間復雜度25用數(shù)組r儲存靜態(tài)鏈表，結點的next域指向后繼，工作指針j指向鏈中結點，使沿鏈挪動的操作為（A）oA、j=r[j].nextB、j=j+lC、j^j->nextD、j=r[j]->next精心整理.數(shù)組的基本操作主要包含（C）A、建立與刪除B、索引與更正C、接見與更正D、接見與索引.設矩陣A是一個對稱矩陣，為了節(jié)約空間，將其下三角矩陣按行序存放在一維數(shù)組B[l,n（n+1）/2]中，對下三角部份中任一元素 aij（i》j）,在一維數(shù)B中下標k的值是（B）oA、i（i-1）/2+j-lB、i（i-1）/2+jC、i（i+l）/2+j-lD、i（i+1）/2+j8.設有數(shù)組A[i,j],數(shù)組的每一個元素長度為3字節(jié)，i的值為1到8,j的值為1到10,數(shù)組從內(nèi)存首地址BA開始次序存放，當用以列為主存放時，元素A[8,5]的存儲首地址為（B）oA、BA+141B、BA+180C、BA+222D、BA+225數(shù)組A中，每一個元素的長度為3個字節(jié)，行下標i從1到8,列下標j從1到10,從首地址SA開始連續(xù)存放的儲存器內(nèi)，該數(shù)組按行存放，元素A[8][5]的初步地址為CoA.SA+141B.SA+144C.SA+222D.SA+225二、判斷題（每題1分，共10分）.一個希少矩陣Am*n采用三元組形式表示，若把三元組中有關行下標與列下標的值互換，并把m和n的值互換，則就完成為了Am*n的轉置運算。（X）.二維以上的數(shù)組實際上是一種特殊的廣義表。（V）.數(shù)組可看做線性結構的一種推行，所以與線性表相同，可以對它進行插入，刪除等操作。（X）.希少矩陣壓縮儲存后，必會失掉隨機存取功能。（V）.所謂取廣義表的表尾就是返回廣義表中最后一個元素。（X）6廣義表是由零或者多個原予或者子表所構成的有限序列， 所以廣義表可能為空表。（V）.廣義表中的元素也許是一個不行切割的原子，也許是一個非空的廣義表。（X）.線性表可以看做是廣義表的特例，假如廣義表中的每一個元素都是原子，則廣義表便成為線性表。（V）.若一個廣義表的表頭為空表，則此廣義表亦為空表。（X）.數(shù)組元素的下標值越大，存取時間越長。 X（）.數(shù)組是一種復雜的數(shù)據(jù)結構：數(shù)組元素之間的關系既不是線性的，也不是樹形的（J）.從邏輯結構上看，n維數(shù)組的每一個元素均屬于n個向量。（V）.二維數(shù)組是其數(shù)據(jù)元素為線性表的線性表（V）.數(shù)組是同種類值的會集。（X）三、填空題（每空1分，共10分）.已知二維數(shù)組按“行優(yōu)先次序”儲存在內(nèi)存中，a的儲存地址為LOC（a）,則元1111素a.的儲存地址為LOC（a）=o（假設每一個元素占2個儲存單元，ij ijWm）答案：Loc（a）+（（i-l）*m+j-l）*2.二維數(shù)組A[4][4]（即A[O..3][O..3]）的元素初步地址是loc（A[0][0]）=1000,元素的長度為2,則LOC（A[2][2]）的地址為。答案：1020.設有一個二維數(shù)組A[10][20]按行存放于一個連續(xù)的儲存空間中，A[0]⑼的儲存地址是200,每一個數(shù)組元素占1個儲存字，則A⑹⑵的儲存字地址是。答案：322.二維數(shù)組a[4][5][6]（下標從。開始計，a有4*5*6個元素），每一個元素的長度是2,則a⑵⑶[4]的地址是1164o（設a⑼⑼⑼的地址是1000,數(shù)據(jù)以行為主方式儲存精心整理解說:LOC(aijk)=LOC(aOOO)+[v2*v3*(i-cl)+v3*(j-c2)+(k-c3)]*l(l為每一個元素所占單元數(shù)).對矩陣壓縮是為了節(jié)約儲存空間。.所謂希少矩陣指的是非零元極少(t?m*n)且分布沒有規(guī)律。.設有一個10階對稱矩陣A采用壓縮儲存方式(以行為主序儲存： all=l),則a85的地址為33o解說:(k=i(i-l)/2+j)(l<=i,j<=n).己知三對角矩陣A[1..9,L.的]每一個元素占2個單元，現(xiàn)將其三條對角線上的元素逐行儲存在初步地址為1000的連續(xù)的內(nèi)存單元中，則元素A[7,8]的地址為1038。解說：三對角矩陣按行儲存： k=2(i-l)+j(l<=i,j<=n)階對稱矩陣a滿足a[i][j]=a|j][i],i,j=l..n,,用一維數(shù)組t儲存時，t的長度為n(n+l)/2,當i=j,a[i][j]=t[i(i+l)/2(或者j(j+l)/2)],i>j,a[i皿=t[i(i-l)/2+j],i<j,a[i皿=t[j(j-l)/2+i(l<=i,jv=n)]°10.設n行n列的下三角矩陣A已壓縮到一維數(shù)組B"..n*(n+1)⑵中，若按行為主序儲存，則A[i,j]對應的B中儲存地點為i(i-l)/2+j(l<=i,j<=n)。.設數(shù)組數(shù)組中任一元素A[i,j]均占內(nèi)存48個二進制位,從首地址2000開始連續(xù)存放在主內(nèi)存里，主內(nèi)存字長為 16位,那末⑴存放該數(shù)組至少需要的單元數(shù)是 270;(2)存放數(shù)組的第8列的全部元素至少需要的單元數(shù)是 27;(3)數(shù)組按列儲存時，元素A[5,8]的初步地址是2204o.用一維數(shù)組B與列優(yōu)先存放帶狀矩陣A中的非零元素A[i,j](lWiWn,i-2WjWi+2),B中的第8個元素是A中的第1行，第3列的元素。.設數(shù)組a[1..5O,L.8O的]基地址為2000,每