數(shù)據(jù)結(jié)構(gòu)（Java語言版）-習題及答案 第6章數(shù)組和特殊矩陣習題答案

第6章數(shù)組和稀疏矩陣習題參考答案 一、單選題.二維數(shù)組為a[6][10]，每個數(shù)組元素占用4個存儲單元，若按行優(yōu)先順序存放的數(shù)組元素，a[0][0]的存儲地址為860，則a[3][5]的存儲地址是 。AABCD.0.0C.0.0.二維數(shù)組為a[6][10]，每個數(shù)組元素占用4個存儲單元，若按行優(yōu)先順序存放的數(shù)組元素a[3][5]的存儲地址為1000，則a[0][0]的存儲地址是 。AABCD.2.0C.8.4ABCABCDnn2C.nn+/2.nn+/+1一個n階對稱矩陣n，n采用壓縮存儲方式，將其下三角+主對角部分元素按行優(yōu)先存儲到一維數(shù)組中，則（≥）元素在B中的位置k是 。ABCABCD./+i./+1C./+j./+1.一個n階對稱矩陣，采用壓縮存儲方式，將其下三角+主對角部分元素按行優(yōu)先存儲到一維數(shù)組中，則元素在B中的位置k是 。AABCD32374560.一個n階對稱矩陣，采用壓縮存儲方式，將其上三角+主對角部分元素按行優(yōu)先存儲到一維數(shù)組中，則元素在B中的位置k是 。A.0B.7CC.5D.0一個n階（n>）三對角矩陣按行優(yōu)先順序壓縮存放在一維數(shù)組中，則中的元素個數(shù)是 A.nB.n2CC.nD.n2對稀疏矩陣進行壓縮存儲的目的是 A.便于進行矩陣運算B.便于輸入和輸出CC.節(jié)省存儲空間D.降低運算的時間復雜度一個稀疏矩陣采用壓縮后，和直接采用二維數(shù)組存儲相比會失去 特性。A.順序存儲B.隨機存取CC.輸入輸出D.以上都不對行n列的稀疏矩陣采用十字鏈表表示時，其中循環(huán)單鏈表的個數(shù)為 A.+1B.n+1CC.+n+1D.n+1在二維數(shù)組中，每個數(shù)組元素同時處于（）個向量中。A.0B.1CC.2D.n以下屬于數(shù)組的基本運算的是（）。A.插入元素B.刪除元素CC.讀指定位置的元素D.以上都不是有一個三維數(shù)組，其中元素個數(shù)是（）。A.0B.0CC.4D.6ABCD一個二維數(shù)組中，每個元素的長度為個字節(jié)，行下標從到，列下標從到，則連續(xù)存放該數(shù)組至少需要ABCD.0.0C.0.0.設(shè)二維數(shù)組n，每個數(shù)組元素占用k個存儲單元，第一個數(shù)組元素的存儲地址是OC，求按列優(yōu)先順序存放的數(shù)組元素]（≤≤，≤≤n）的存儲地址為（）。AABCD.OC+×n+×k.OC+×n+×kC.OC+×+×k.OC+×+×kABCD設(shè)二維數(shù)組，若按行優(yōu)先的順序存放數(shù)組的元素，則元素的前面有（ABCD6282940ABCD設(shè)二維數(shù)組，若按列優(yōu)先的順序存放數(shù)組的元素，則元素的前面有（ABCD6282940二、編程題OJ—矩陣乘法問題限制時間：，限制空間：。問題描述：SC最近開發(fā)了并行矩陣乘法機器，用于非常大的矩陣乘法運算。給定兩個矩陣和，其中是n×p矩陣，是p×矩陣，可以在Opn+p+時間內(nèi)計算矩陣C=×。然而，的開發(fā)人員很快發(fā)現(xiàn)了一個小問題：可能出錯，而且每當出現(xiàn)錯誤時，結(jié)果矩陣C只包含一個不正確的元素。開發(fā)人員在PM3給出矩陣C之后檢查并糾正它。他們認為這是一項簡單的任務(wù)，因為最多會有一個不正確的元素。所以你要寫一個程序來檢查和糾正PM3計算的結(jié)果。輸入格式：輸入的第一行是3個整數(shù)n，p和m（0<n,p,m≤1000）,它們表示A和B的維數(shù)。然后跟隨n行，每行有p個整數(shù)，以行序優(yōu)先給出A的元素。之后是B和C的元素，以相同的方式給出。和的元素以的絕對值為界，C的界限是。輸出格式：如果C不包含不正確的元素，請打印"Yes"。否則打印"No"后跟另外兩行，第一行上有兩個整數(shù)r和c，第二個上有另一個整數(shù)v，表示C中行r列c的元素應(yīng)該校正為v。答：prtvuScnner;pubccsn{cntN=;cnt]=newnNN;cnt]b=newnNN;cnt]c=newnNN;cnt]c_r=newnN;cnt]b_r=newnN;pubccvdnSrng]rg){Scnnern=newScnnerSyen;ntnp;henhNex){n=nnexIn;=nnexIn;p=nnexIn;rnt=;i<n;++)//輸入arnt=;j<;++)=nnexIn;rnt=;i<;++) //輸入rnt=;j<p;++)b=nnexIn;rnt=;i<n;++) //輸入rnt=;j<p;++)c=nnexIn;rnt=;i<;++) //求出b的每行元素和{b_r=;rnt=;j<p;++)b_r+=b;}rnt=;i<n;++) //求出c的每行元素和{c_r=;rnt=;j<p;++)c_r+=c;}nt;r=;i<n;++) //找出錯行i{ntp=;rnt=;j<;++)p+=*b_r;p=c_r)break;}==n) //Syeuprnn"e";ee{Syeuprnn"N";//第行錯誤rnt=;j<p;++){ntre=;rntk=;kre+=k*bk;re=c){Syeuprn"%d%d\n"++;Syeuprnnre;break;}}}}}}.OJ—矩陣冪序列問題限制時間：，限制空間：。問題描述：給定一個n×n的矩陣A和一個正整數(shù)k，求S=A+A2+A3+…+Ak。輸入格式：輸入只包含一個測試用例。第一行輸入包含三個正整數(shù)n（n≤），k（k≤^）和（<^）。然后跟隨n行，每行包含n個小于的非負整數(shù)，以行序優(yōu)先給出的元素。輸出格式：以A的方式輸出S，每個元素模m。答：prtvuScnner;pubccsn{cntN=;cntnk;pubccntuntntb)//返回矩陣和b相乘的矩陣{ntn=engh;nt]c=newnnn;rnt=;i<n;++)rnt=;j<n;++){rntk=;k<n;k++)c]+=k*bk)%;c]%=;}returnc;}pubccntpntntk)//返回^k的矩陣{ntn=engh;ntn=newnnn;//建立n矩陣rnt=;i<n;++)//置n為單位矩陣n=;nt]be=newnnn;//建立be矩陣rnt=;i<n;++) //置be=arnt=;j<n;++)be=;hek=){fk==) //遇到二進制位n=unbe;be=ubebe;//倍乘k>>=1; //右移一位}returnans;}pubccvdnSrng]rg){Scnnern=newScnnerSyen;n=nnexIn;k=nnexIn;m=nnexIn;nt]=newn*N*N;rnt=;i<n;++){rnt=;j<n;++)=nnexIn;n+=n+n+=;}=pk+; //求出rnt=;i<n;++){rnt=;j<n;++){nte=n+%;f==)e=e+%;//減去If==n)Syeuprn"%d\n"e;eeSyeuprn"%d"e;}}}}三、填空題數(shù)組通常只有兩種基本運算和，因此常采用順序存儲結(jié)構(gòu)來存儲數(shù)組。 答：取元素值;存元素值一個d維數(shù)組中，每個元素最多有個前趨元素和后繼元素。 答：d一個m行n列的矩陣可以看成是長度的線性表，其中每個元素是長度為n的線性表。 答：m數(shù)組具有是因為對數(shù)組任一元素的存取時間是相等的。 答：隨機存取特性二維數(shù)組采用順序存儲方法時。有按行優(yōu)先存儲和兩種方式。 答：按列優(yōu)先存儲三維數(shù)組共含有個元素。 答：315一維數(shù)組采用順序存儲方式，下標從開始，每個元素占個存儲單元，的起始地址為，則的起始地址為。 答：112.數(shù)組以行優(yōu)先順序存儲，設(shè)第一個元素的首地址為，每個元素占個單元的存儲空間，則元素的存儲地址為。答：913.二維數(shù)組M的每個元素占6個字節(jié)，行下標從0到8，列下標從1到10，則存放M至少需要個字節(jié)。M的第8列和第5行共占個字節(jié)。若M按行優(yōu)先方式存儲，元素的起始地址與當按列優(yōu)先方式存儲時的元素的起始地址一致。答：;;]設(shè)數(shù)組,的基地址為，每個元素占個存儲單元，若以行序為主序順序存儲，則元素的存儲地址為。答：6502四、判斷題數(shù)組是同類型元素的集合。 答：錯誤數(shù)組可看成線性表的一種推廣，因此與線性表一樣，其基本運算有插入和刪除等。 答：錯誤數(shù)組只能采用順序存儲結(jié)構(gòu)。 答：錯誤二維數(shù)組中每一行的元素個數(shù)都是相等的。答：錯誤二維數(shù)組的順序存儲方式只能以行優(yōu)先存儲。 答：錯誤二維數(shù)組中共有個元素。 答：錯誤.定義二維數(shù)組，起始地址為OC，每個元素占個存儲單元，在以行序為主序的存儲方式下，某數(shù)據(jù)元素的地址為OC+，則在以列序為主序的存儲方式下，該元素的存儲地址為LOC+36。答：錯誤特殊矩陣是指用途特殊的矩陣。 答：錯誤用一維數(shù)組存儲特殊矩陣，可以簡化對矩陣的存取操作。 答：錯誤五、簡答題簡述數(shù)組的基本運算有哪些？ 答：數(shù)組的基本運算如下：取值運算：給定一組下標，讀取其對應(yīng)的數(shù)據(jù)元素。賦值運算：給定一組下標，存儲或修改與其相對應(yīng)的數(shù)據(jù)元素。從邏輯結(jié)構(gòu)的角度敘述一維數(shù)組與有序表的異同。 答：從邏輯結(jié)構(gòu)的角度看，一維數(shù)組是一種線性表，而有序表是元素有序的線性表，所以兩者都屬于線性表。不同之處于在有序表中元素有序（遞增或遞減）排列，而一維數(shù)組中元素沒有按元素值排列順序的要求。為什么說數(shù)組是線性表的推廣或擴展，而不說數(shù)組就是一種線性表呢？ 答：從邏輯結(jié)構(gòu)的角度看，一維數(shù)組是一種線性表；二維數(shù)組可以看成數(shù)組元素為一維數(shù)組的一維數(shù)組，所以二維數(shù)組是線性結(jié)構(gòu)，可以看成是線性表，但就二維數(shù)組的形狀而言，它又是非線性結(jié)構(gòu)，因此將二維數(shù)組看成是線性表的推廣更準確。三維及以上維的數(shù)組亦如此。說明：有的教材說數(shù)組屬于線性表，這也沒有錯誤。但更準確的說法是數(shù)組是線性表的推廣或擴展。為什么數(shù)組極少使用鏈式結(jié)構(gòu)存儲？ 答：因為數(shù)組使用鏈式結(jié)構(gòu)存儲時需要額外占用更多的存儲空間，而且操