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

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

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

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

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

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

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

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

用i，j表示k的下標變換公式；8.

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

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

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

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

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

已知n階下三角矩陣A(即當i＜j時，有ao=0)，按照壓縮存儲的思想，可以將其主對角線以下所有元素(包括主對角線上元素)依次存放于一維數(shù)組B中，請寫出從第一列開始采用列序為主序分配方式時在B中確定元素aij的存放位置的公式。【北京航空航天大學1999二(10分)】【中山大學1999三、2(5分)】設有三對角矩陣(aij)n*n，將其三條對角線上的元素逐行地存于數(shù)組B(1：3n一2)中，使得B[k]=aij，求：14.

用i、j表示七的下標變換公式；15.

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

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

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

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

若將A視為稀疏矩陣，畫出A的十字鏈表結構?！颈本┛萍即髮W1997三(10分)】設對角線矩陣20.

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

若將A視為稀疏矩陣時，請畫出其行邏輯鏈接順序表。【北京科技大學2000三(10分)】22.

假定有下列n×n矩陣(n為奇數(shù))如果用一維數(shù)組B按行主次序存儲A的非零元素，問：(1)A中非零元素的行下標與列下標的關系；(2)給出A中非零元素aij的下標(i，j與B中的下標R的關系；(3)假定矩陣中每個元素占一個存儲單元且B的起始地址為A0，給出利用aij的下標(i，j)定位在B中的位置公式。【上海交通大學1998三(12分)】23.

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

用三元數(shù)組表示稀疏矩陣的轉置矩陣，并簡要寫出解題步驟?！旧綎|工業(yè)大學1995五(10分)】7.設計題1.

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

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

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

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

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

給定一個整數(shù)數(shù)組b[0．N-1]，6中連續(xù)的相等元素構成的子序列稱為平臺。試設計算法，求出b中最長平臺的長度?！局锌圃河嬎闼?999五、2(20分)】7.

給定n×m矩陣A[a..b，c一d，并設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)。設計一算法判定x的值是否在A中，要求時間復雜度為O(m+n)?！緰|南大學2005四(10分)2001六(13分)1994三(17分)】【清華大學1998六(10分)】8.

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