内容发布更新时间 : 2024/11/16 1:16:44星期一 下面是文章的全部内容请认真阅读。

计算机专业基础综合数据结构（数组和广义表）历年真题试卷汇

编3

(总分：66.00，做题时间：90分钟)

一、 综合题(总题数：20，分数：48.00)

1.数组A[1．．8，一2．．6，0．．6]以行为主序存储，设第一个元素的首地址是78，每个元素的长度为4，试求元素A[4，2，3]的存储首地址。 【厦门大学1998五、1(5分)】 （分数：2.00）

__________________________________________________________________________________________ 正确答案：(正确答案：元素A[4，2，3]的存储首地址为958。 三维数组以行为主序存储，其元素地址公式为：LOC(A ijk )=LOC(A c1c2c3 )=(3A c1c2c3 )+[(i-c 1 )V 2 V 3 +(j—c 2 )V 3 +(k-c 3 )]*L其中，c i ，d i 是各维的下界和上界，V i =d i 一c i +1是各维元素个数，L是一个元素所占的存储单元数。) 解析：

2.数组A中，每个元素A[i，f]的长度均为32个二进位，行下标从一1到9，列下标从1到11，从首地址S开始连续存放在主存储器中，主存储器字长为16位。求：(1)存放该数组所需多少单元?(2)存放数组第4列所有元素至少需多少单元?(3)数组按行存放时，元素A[7，4]的起始地址是多少?(4)数组按列存放时，元素A[4，7]的起始地址是多少?【大连海事大学1996四、1(6分)】 （分数：2.00）

__________________________________________________________________________________________ 正确答案：(正确答案：每个元素32个二进制位，主存字长16位，故每个元素占2个字长，行下标可平移至1到11。(1)242 (2)22 (3)S+182 (4)S+142) 解析：

3.假设按低下标优先存储整型数组A(一3：8，3：5，一4：0，0：7)时，第一个元素的字节存储地址是100，每个整数占4字节，问A(0，4，一2，5)的存储地址是什么? 【清华大学1996三】 （分数：2.00）

__________________________________________________________________________________________ 正确答案：(正确答案：1784 (公式：Loc(A ijkl )=100(基地址)+[(i-c 1 )v 2 v 3 v 4 +一c 2 )v 3 v 4 +(k-c

3

)v 4 +(l一c 4 )]*4))

解析：

4.设有五对角矩阵A=(a ij ) 20*20 ，按特殊矩阵压缩存储的方式将其五条对角线上的元素存于数组A[-10：m]中，计算元素A[15，16]的存储位置。【东北大学1999一、2(4分)】 （分数：2.00）

__________________________________________________________________________________________ 正确答案：(正确答案：五对角矩阵按行存储，元素在一维数组中下标(从1开始)k与i，jA[15，16]是第71个元素，在向量[-10：m]中的存储位置是60。) 解析：

5.数组A[0．8，1．．10】的元素是6个字符组成的串，则存放A至少需要多少字节?A的第8列和第5行共占多少字节?若A按行优先方式存储，元素A[8，5]的起始地址与当A按列优先方式存储时的哪个元素的起始地址一致?【厦门大学2000五、3(14％／3分)】 （分数：2.00）

__________________________________________________________________________________________ 正确答案：(正确答案：(1)540 (2)108 (3)i=3，j=10，即A[3，10]求解(3)用以下等式： Loc(8，5)=Loc(0，1)+{(f—c1)*(c一c2+1)+(j一c2))*L=Loc(0，1)+[84]*L Loc(f，j]=Loc(0，1)+{(，一c2)*(d1一c1+1)+(f—c1))*L 即(j-1)+i=84，其中0≤i≤8，1≤j≤10。) 解析：

6.设m×n阶稀疏矩阵A有t个非零元素，其三元组表表示为LTMA[t+1)，1．．3]，试问：非零元素的个数t达到什么程度时用LTMA表示A才有意义?【北京航空航天大学1998一、5(4分)】 （分数：2.00）

__________________________________________________________________________________________ 正确答案：(正确答案：稀疏矩阵A有t个非零元素，加上行数mu、列数nu和非零元素个数tu(也算一个三元组)，共占用三元组表LTMA的3(t+1)个存储单元，用二维数组存储时占用m*n个单元，只有当3(t+1)

设有三对角矩阵(a ij ) n×n 将其三条对角线上的元素逐行地存于数组B(1：3n一2)中，使得s[k]=a i ，j，求：（分数：4.00）

(1).用i，j表示k的下标变换公式；（分数：2.00）

__________________________________________________________________________________________ 正确答案：(正确答案：k=3(i一1) ／／主对角线左下角，即i=j+1 k=3(i-1)+1 ／／主对角线上，即i=j k=3(f一1)+2 ／／主对角线右上角，即i=j一1 由以上三式，得k=2(f一1)+j (1≤i，j≤n；1≤k≤3n一2)) 解析：

(2).若n=10 ，每个元素占用L个单元，则用B[K]方式比常规存储节省多少单元?【西安电子科技大学1996二、4(5分)】（分数：2.00）

__________________________________________________________________________________________ 正确答案：(正确答案：(10 ,10 一(3*10 一2))*L) 解析：

7.已知A为稀疏矩阵，试从空间和时间角度，比较采用两种不同的存储结构(二维数组和三元组表)完成求

运算的优缺点。【西安电子科技大学1996二、6(5分)】 （分数：2.00）

__________________________________________________________________________________________ 正确答案：(正确答案：稀疏矩阵A采用二维数组存储时，需要n*n个存储单元，完成求∑a ij (1≤i≤n)时，由于a[i][i]随机存取，速度快。但采用三元组表时，若非零元素个数为t，需3(t+1)个存储单元(第一个分量中存储稀疏矩阵A的行数、列数和非零元素个数，以后t个分量存储各非零元素的行值、列值、元素值)，比二维数组节省存储单元；但在求∑a ij (1≤i≤n)时，要扫描整个三元组表，才能找到行列值相等的非零元素，其时间性能比采用二维数组时差。) 解析：

8.特殊矩阵和稀疏矩阵哪一种压缩存储后失去随机存取的功能?为什么? 【北京邮电大学2001三、1(5分)】 （分数：2.00）

__________________________________________________________________________________________ 正确答案：(正确答案：特殊矩阵指值相同的元素或零元素在矩阵中的分布有一定规律，因此可以对非零元素分配单元(对值相同元素只分配一个单元)，将非零元素存储在向量中，元素的下标i和j和该元素在向量中的下标有一定规律，可以用简单公式表示，仍具有随机存取功能。而稀疏矩阵是指非零元素和矩阵容量相比很小(t＜＜m*n，且分布没有规律。用十字链表作存储结构自然失去了随机存取的功能。即使用三元组表的顺序存储结构，存取下标为i和j的元素时，要扫描三元组表，下标不同的元素，存取时间也不同，最好情况下存取时间为O(1)，最差情况下是O(n)，因此也失去了随机存取的功能。) 解析：

9.试叙述一维数组与有序表的异同。【西安电子科技大学1999计算机应用一、2(5分)】 （分数：2.00）

__________________________________________________________________________________________ 正确答案：(正确答案：一维数组属于特殊的顺序表，和有序表的差别主要在于有序表中元素按值排序(非递增或非递减)，而一维数组中元素没有按元素值排列顺序的要求。) 解析：

3

3

3

3

10.给出数组A：ARRAY[3．．8，2．．6]OF INTEGER；当它在内存中按行存放和按列存放时，分别写出数组元素A[f，j]地址计算公式(设每个元素占两个存储单元)。【南开大学1998一(8分)】 （分数：2.00）

__________________________________________________________________________________________ 正确答案：(正确答案：LOCA[i，j)=LOC(A[3，2])+[(f一3)*5+(，一2)]×2 (按行存放)LOCA[i，j)=LOC(A[3，2])+[(j-2)*6+(i一3)]×2 (按列存放)) 解析：

11.已知n阶下三角矩阵A(即当i＜j时，有ao=0)，按照压缩存储的思想，可以将其主对角线以下所有元素(包括主对角线上元素)依次存放于一维数组B中，请写出从第一列开始采用列序为主序分配方式时在B中确定元素a 的存放位置的公式。【北京航空航天大学1999二(10分)】【中山大学1999三、2(5分)】 ij （分数：2.00）

__________________________________________________________________________________________ 正确答案：(正确答案：刀阶下三角矩阵元素A[i][j](1≤i，j≤i≥j)。第1列有n个元素，第j列有n-j+1个元素，第1列到第j-1列是梯形，元素数为(n+(n-j+2))(j-1)／2，而a ij 在第j列上的位置是i-j+1。所以n阶下三角矩阵A按列存储，其元素a 在一维数组B中的存储位置k与i和j的关系为：k=(n+(n—(jij 一1)+1))(j-1)／2+(i—j+1)=(2n-f)(j-1)／2+i) 解析：

设有三对角矩阵(a ij )n*n，将其三条对角线上的元素逐行地存于数组B(1：3n一2)中，使得B[k]=a ij ，求：（分数：4.00）

(1).用i、j表示七的下标变换公式；（分数：2.00）

__________________________________________________________________________________________ 正确答案：(正确答案：三对角矩阵第一行和最后一行各有两个非零元素，其余每行均有三个非零元素，所以共有3n一2个元素。(1)主对角线左下对角线上的元素下标间有i=j+1关系，k与i和j的关系为k=3(i-1)；主对角线上元素下标间有关系i=j，k与i和j的关系为k=-3(i—1)+1；主对角线右上那条对角线上元素下标间有关系i=j一1，k与i和j的关系为k=3(i-1)+2。综合以上三等式，有k=2(i一1)+j (1≤i，j≤n，｜i-j｜≤1)。) 解析：

(2).用k表示i，j的下标变化公式。【东北大学2002一(4分)】【北京工业大学2000二、1(9分)】【南京航空航天大学2000四】【山东科技大学2001一、6(6分)】【长沙铁道学院1997五、1(10分)】（分数：2.00）

__________________________________________________________________________________________ 正确答案：(正确答案：i=k／3+1；(1≤k≤3n一2) ／／k／3取小于k／3的最大整数。下同j=k-2(i一1)=k-2(k／3)=k％3+k／3) 解析：

12.上三角阵A(N*N)按行主序压缩存放在数组B中，其中A[i，j]=B[k]。写出用i、j表示的k。【北京工业大学2001二、1(5分)】 （分数：2.00）

__________________________________________________________________________________________ 正确答案：(正确答案：上三角矩阵第一行有n个元素，第i—1行有n一(i一1)+1个元素，第一行到第i一1行是梯形，而第i行上第j个元素(即a ij )是第i行上第j-i+个元素，故元素A ij 在一维数组中的存储位置(下标k)为：k=(n+(n+(i一1)+1))(i—1)／2+(j一i+1)=(2n一i+2)(i一1)／2+j一i+1) 解析：

13.设有上三角矩阵(a ij ) n*n 将其上三角中的元素按先行后列的顺序存于数组B(1：m)中，使得B[k]=a ij 且k=f1(i)+f2(j)+c，请推导出函数f1、f2和常数c，要求f1和f2中不含常数项。【中科院自动化所1999】【山东科技大学2002— 5 (6分) （分数：2.00）

__________________________________________________________________________________________ 正确答案：(正确答案：将上面14题的等式进一步整理为：k=(n+1／2)i—i ／2+j-n则得f 1 (i)=(n+1／2)i—i ／2，f 2 (j)=j，c=一n。)

2

2