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

编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

解析：

（分数：4.00）

(1).若将A视为对称矩阵，画出对其压缩存储的存储表，并讨论如何存取A中元素a (0≤i，j<4)；（分ij 数：2.00）

__________________________________________________________________________________________ 正确答案：(正确答案：将对称矩阵对角线及以下元素按行序存入一维数组中，结果如下：维数组中的位置k和其在对称矩阵中的下标(i和j)有确定关系。) 解析：

(2).若将A视为稀疏矩阵，画出A的十字链表结构。【北京科技大学1997三(10分)】（分数：2.00） __________________________________________________________________________________________ 正确答案：(正确答案：因行列表头的“行列域”值用了0和0，下面十字链表中行和列下标均从1开始。

注：上侧列表头胁和左侧行表头Hi是一个(即H1、H2、H3和H4)，为了清楚，画成了两个。) 解析： 设对角线矩阵（分数：4.00）

试求出A中已存储之元素的行列下标(i，j)与S中元素的下

元素在一(1).若将矩阵A压缩存储到数组S中：标K之间的关系。（分数：2.00）

__________________________________________________________________________________________ 正确答案：(正确答案：k=2(f一1)j (1≤i，j≤n，｜i=j｜≤1) i=[k／3]+1 j=k-2(i—1)) 解析：

(2).若将A视为稀疏矩阵时，请画出其行逻辑链接顺序表。【北京科技大学2000三(10分)】（分数：2.00） __________________________________________________________________________________________ 正确答案：(正确答案：行逻辑链接顺序表是稀疏矩阵压缩存储的一种形式。为了随机存取任意一行的非零元，需要知道每一行第一个非零元在三元组表中的位置。为此，除非零元的三元组表外，还需要一个向量，其元素值是每行第一个非零元在三元组表中的位置。其类型定义如下： typedef struct {int mu，nu，tu； ／／稀疏矩阵的行数、列数和非零元素个数 intrpos[maxrow+1]； ／／行向量，元素值是每行第一个非零元在三元组表中的位置 Triple data[maxsize]； }SparsMatrix； 因篇幅所限，不再画出行逻辑链接顺序表。) 解析：

14.假定有下列n×n矩阵(n为奇数) 如果用一维数组B按行主次序存储A的非零元素，问： (1)A

中非零元素的行下标与列下标的关系； (2)给出A中非零元素a 的下标(i，j与B中的下标R的关系； (3)ij 假定矩阵中每个元素占一个存储单元且B的起始地址为A 0 ，给出利用a ij 的下标(i，j)定位在B中的位置公式。【上海交通大学1998三(12分)】 （分数：2.00）

__________________________________________________________________________________________ 正确答案：(正确答案：主对角线上元素的坐标是i=j，副对角线上元素的坐标i和j有i+j=n+1的关系。(1)i=j或i=n+1一j (1≤i，j≤n)(2)非零元素分布在两条主、副对角线上，除对角线相交处一个元素(下称“中心元素”)外，其余每行都有两个元素。主对角线上的元素，在向量B中存储的下标是k=2i一1(i=j，1≤i，j≤n，1≤k≤2n一1)。副对角线上的元素，在中心元素前，在向量B中存储的下标是k=2i(i<>j，i≤j，1≤i,j≤n／2)；在中心元素后，其下标是k=(f一1)(i<>j，n／2+1≤i，j≤n，1≤k≤2n一1)。(3)a ij 在B中的位置 解析：

)