計(jì)算機(jī)專業(yè)基礎(chǔ)綜合數(shù)據(jù)結(jié)構(gòu)數(shù)組和廣義表歷年真題試卷匯編3-真題無答案

計(jì)算機(jī)專業(yè)基礎(chǔ)綜合數(shù)據(jù)結(jié)構(gòu)（數(shù)組和廣義表）歷年真題試卷匯編3(總分66,做題時(shí)間90分鐘)6.綜合題1.

數(shù)組A[1．．8，一2．．6，0．．6]以行為主序存儲(chǔ)，設(shè)第一個(gè)元素的首地址是78，每個(gè)元素的長(zhǎng)度為4，試求元素A[4，2，3]的存儲(chǔ)首地址?！緩B門大學(xué)1998五、1(5分)】2.

數(shù)組A中，每個(gè)元素A[i，f]的長(zhǎng)度均為32個(gè)二進(jìn)位，行下標(biāo)從一1到9，列下標(biāo)從1到11，從首地址S開始連續(xù)存放在主存儲(chǔ)器中，主存儲(chǔ)器字長(zhǎng)為16位。求：(1)存放該數(shù)組所需多少單元?(2)存放數(shù)組第4列所有元素至少需多少單元?(3)數(shù)組按行存放時(shí)，元素A[7，4]的起始地址是多少?(4)數(shù)組按列存放時(shí)，元素A[4，7]的起始地址是多少?【大連海事大學(xué)1996四、1(6分)】3.

假設(shè)按低下標(biāo)優(yōu)先存儲(chǔ)整型數(shù)組A(一3：8，3：5，一4：0，0：7)時(shí)，第一個(gè)元素的字節(jié)存儲(chǔ)地址是100，每個(gè)整數(shù)占4字節(jié)，問A(0，4，一2，5)的存儲(chǔ)地址是什么?【清華大學(xué)1996三】4.

設(shè)有五對(duì)角矩陣A=(aij)20*20，按特殊矩陣壓縮存儲(chǔ)的方式將其五條對(duì)角線上的元素存于數(shù)組A[-10：m]中，計(jì)算元素A[15，16]的存儲(chǔ)位置?！緰|北大學(xué)1999一、2(4分)】5.

數(shù)組A[0．8，1．．10】的元素是6個(gè)字符組成的串，則存放A至少需要多少字節(jié)?A的第8列和第5行共占多少字節(jié)?若A按行優(yōu)先方式存儲(chǔ)，元素A[8，5]的起始地址與當(dāng)A按列優(yōu)先方式存儲(chǔ)時(shí)的哪個(gè)元素的起始地址一致?【廈門大學(xué)2000五、3(14％／3分)】6.

設(shè)m×n階稀疏矩陣A有t個(gè)非零元素，其三元組表表示為L(zhǎng)TMA[t+1)，1．．3]，試問：非零元素的個(gè)數(shù)t達(dá)到什么程度時(shí)用LTMA表示A才有意義?【北京航空航天大學(xué)1998一、5(4分)】設(shè)有三對(duì)角矩陣(aij)n×n將其三條對(duì)角線上的元素逐行地存于數(shù)組B(1：3n一2)中，使得s[k]=ai，j，求：7.

用i，j表示k的下標(biāo)變換公式；8.

若n=103，每個(gè)元素占用L個(gè)單元，則用B[K]方式比常規(guī)存儲(chǔ)節(jié)省多少單元?【西安電子科技大學(xué)1996二、4(5分)】9.

已知A為稀疏矩陣，試從空間和時(shí)間角度，比較采用兩種不同的存儲(chǔ)結(jié)構(gòu)(二維數(shù)組和三元組表)完成求運(yùn)算的優(yōu)缺點(diǎn)?！疚靼搽娮涌萍即髮W(xué)1996二、6(5分)】10.

特殊矩陣和稀疏矩陣哪一種壓縮存儲(chǔ)后失去隨機(jī)存取的功能?為什么?【北京郵電大學(xué)2001三、1(5分)】11.

試敘述一維數(shù)組與有序表的異同?！疚靼搽娮涌萍即髮W(xué)1999計(jì)算機(jī)應(yīng)用一、2(5分)】12.

給出數(shù)組A：ARRAY[3．．8，2．．6]OFINTEGER；當(dāng)它在內(nèi)存中按行存放和按列存放時(shí)，分別寫出數(shù)組元素A[f，j]地址計(jì)算公式(設(shè)每個(gè)元素占兩個(gè)存儲(chǔ)單元)。【南開大學(xué)1998一(8分)】13.

已知n階下三角矩陣A(即當(dāng)i＜j時(shí)，有ao=0)，按照壓縮存儲(chǔ)的思想，可以將其主對(duì)角線以下所有元素(包括主對(duì)角線上元素)依次存放于一維數(shù)組B中，請(qǐng)寫出從第一列開始采用列序?yàn)橹餍蚍峙浞绞綍r(shí)在B中確定元素aij的存放位置的公式?！颈本┖娇蘸教齑髮W(xué)1999二(10分)】【中山大學(xué)1999三、2(5分)】設(shè)有三對(duì)角矩陣(aij)n*n，將其三條對(duì)角線上的元素逐行地存于數(shù)組B(1：3n一2)中，使得B[k]=aij，求：14.

用i、j表示七的下標(biāo)變換公式；15.

用k表示i，j的下標(biāo)變化公式?！緰|北大學(xué)2002一(4分)】【北京工業(yè)大學(xué)2000二、1(9分)】【南京航空航天大學(xué)2000四】【山東科技大學(xué)2001一、6(6分)】【長(zhǎng)沙鐵道學(xué)院1997五、1(10分)】16.

上三角陣A(N*N)按行主序壓縮存放在數(shù)組B中，其中A[i，j]=B[k]。寫出用i、j表示的k。【北京工業(yè)大學(xué)2001二、1(5分)】17.

設(shè)有上三角矩陣(aij)n*n將其上三角中的元素按先行后列的順序存于數(shù)組B(1：m)中，使得B[k]=aij且k=f1(i)+f2(j)+c，請(qǐng)推導(dǎo)出函數(shù)f1、f2和常數(shù)c，要求f1和f2中不含常數(shù)項(xiàng)?！局锌圃鹤詣?dòng)化所1999】【山東科技大學(xué)2002—5(6分)18.

若將A視為對(duì)稱矩陣，畫出對(duì)其壓縮存儲(chǔ)的存儲(chǔ)表，并討論如何存取A中元素aij(0≤i，j<4)；19.

若將A視為稀疏矩陣，畫出A的十字鏈表結(jié)構(gòu)?！颈本┛萍即髮W(xué)1997三(10分)】設(shè)對(duì)角線矩陣20.

若將矩陣A壓縮存儲(chǔ)到數(shù)組S中：試求出A中已存儲(chǔ)之元素的行列下標(biāo)(i，j)與S中元素的下標(biāo)K之間的關(guān)系。21.

若將A視為稀疏矩陣時(shí)，請(qǐng)畫出其行邏輯鏈接順序表?！颈本┛萍即髮W(xué)2000三(10分)】22.

假定有下列n×n矩陣(n為奇數(shù))如果用一維數(shù)組B按行主次序存儲(chǔ)A的非零元素，問：(1)A中非零元素的行下標(biāo)與列下標(biāo)的關(guān)系；(2)給出A中非零元素aij的下標(biāo)(i，j與B中的下標(biāo)R的關(guān)系；(3)假定矩陣中每個(gè)元素占一個(gè)存儲(chǔ)單元且B的起始地址為A0，給出利用aij的下標(biāo)(i，j)定位在B中的位置公式?！旧虾＝煌ù髮W(xué)1998三(12分)】23.

對(duì)于一個(gè)對(duì)稱矩陣采用壓縮存儲(chǔ)，只存放它的上三角部分，并按列存放。例如對(duì)于一個(gè)n*n的對(duì)稱矩陣A(如右圖)，用一個(gè)一維數(shù)組B來存放它的上三角部分：B=[A11,A12，A22，A13，A23，A33，A14，…，A1n，A2n，…，Ann]同時(shí)有兩個(gè)函數(shù)：MAX(i，j)和MIN(i，j)，分別計(jì)算下標(biāo)i和j中的大者與小者。試?yán)盟鼈兘o出求任意一個(gè)Aij在B中存放位置的公式。(若式中沒有MAX(i，j)和MIN(i，j)則不給分。)【清華大學(xué)1997五(10分)】24.

用三元數(shù)組表示稀疏矩陣的轉(zhuǎn)置矩陣，并簡(jiǎn)要寫出解題步驟。【山東工業(yè)大學(xué)1995五(10分)】7.設(shè)計(jì)題1.

設(shè)有大小不等的n個(gè)數(shù)據(jù)組(n個(gè)數(shù)據(jù)組中數(shù)據(jù)的總數(shù)為m)，順序存放在空間區(qū)D內(nèi)，每個(gè)數(shù)據(jù)占一個(gè)存儲(chǔ)單元，數(shù)據(jù)組的首地址由數(shù)組S給出(如右圖所示)，試編寫將新數(shù)據(jù)x插入第i個(gè)數(shù)據(jù)組的末尾且屬于第i個(gè)數(shù)據(jù)組的算法，插入后，空間區(qū)D和數(shù)組S的相互關(guān)系仍保持正確。【東北大學(xué)2000六(15分)】2.

以三元組表存儲(chǔ)的稀疏矩陣A、B非零元個(gè)數(shù)分別為m和n。試用類Pascal語言編寫時(shí)間復(fù)雜度為O(m+n)的算法將矩陣B加到矩陣A上去。A的空間足夠大，不另加輔助空間。要求描述所用結(jié)構(gòu)?！颈本┕I(yè)大學(xué)1997三(10分)】3.

設(shè)整數(shù)x1，x2，…，xn已存放在數(shù)組A中，編寫一Pascal遞歸過程，輸出從這n個(gè)數(shù)中取出所有k個(gè)數(shù)的所有組合(k≤n)。例：若A中存放的數(shù)是1，2，3，4，5，k為3，則輸出結(jié)果應(yīng)為：543，542，541，532，531，52l，432，431，421，321?！緰|南大學(xué)2001三(10分)】4.

編寫一個(gè)過程，對(duì)一個(gè)n×n矩陣，通過行變換，使其每行元素的平均值按遞增順序排列?！局锌圃很浖?996】5.

請(qǐng)編寫完整的程序。如果矩陣A中存在這樣的一個(gè)元素A[i，j]滿足條件：A[i，j]是第i行中值最小的元素，且又是第j列中值最大的元素，則稱之為該矩陣的一個(gè)馬鞍點(diǎn)。請(qǐng)編程計(jì)算出m*n的矩陣a的所有馬鞍點(diǎn)?！旧虾４髮W(xué)2000三(20分)】【中科院自動(dòng)化所1997】6.

給定一個(gè)整數(shù)數(shù)組b[0．N-1]，6中連續(xù)的相等元素構(gòu)成的子序列稱為平臺(tái)。試設(shè)計(jì)算法，求出b中最長(zhǎng)平臺(tái)的長(zhǎng)度?！局锌圃河?jì)算所1999五、2(20分)】7.

給定n×m矩陣A[a..b，c一d，并設(shè)A[i,j]≤A[i，j+1](a≤i≤b，c≤j≤d-1)和A[i,j]≤A[i+1，f](a≤i≤b一1，c≤j≤d)。設(shè)計(jì)一算法判定x的值是否在A中，要求時(shí)間復(fù)雜度為O(m+n)?！緰|南大學(xué)2005四(10分)2001六(13分)1994三(17分)】【清華大學(xué)1998六(10分)】8.

編寫算法，將自然數(shù)1～n2按“蛇形”填入