计算机专业基础综合数据结构（数组和广义表）历年真题试卷汇编3
(总分66, 做题时间90分钟)
6. 综合题
1. 
数组A[1．．8，一2．．6，0．．6]以行为主序存储，设第一个元素的首地址是78，每个元素的长度为4，试求元素A[4，2，3]的存储首地址。  【厦门大学1998五、1(5分)】
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分)】
3. 
假设按低下标优先存储整型数组A(一3：8，3：5，一4：0，0：7)时，第一个元素的字节存储地址是100，每个整数占4字节，问A(0，4，一2，5)的存储地址是什么?  【清华大学1996三】
4. 
设有五对角矩阵A=(a ij ) 20*20 ，按特殊矩阵压缩存储的方式将其五条对角线上的元素存于数组A[-10：m]中，计算元素A[15，16]的存储位置。【东北大学1999一、2(4分)】
5. 
数组A[0．8，1．．10】的元素是6个字符组成的串，则存放A至少需要多少字节?A的第8列和第5行共占多少字节?若A按行优先方式存储，元素A[8，5]的起始地址与当A按列优先方式存储时的哪个元素的起始地址一致?【厦门大学2000五、3(14％／3分)】
6. 
设m×n阶稀疏矩阵A有t个非零元素，其三元组表表示为LTMA[t+1)，1．．3]，试问：非零元素的个数t达到什么程度时用LTMA表示A才有意义?【北京航空航天大学1998一、5(4分)】
设有三对角矩阵(a ij ) n×n 将其三条对角线上的元素逐行地存于数组B(1：3n一2)中，使得s[k]=a i ，j，求：
7. 
用i，j表示k的下标变换公式；
8. 
若n=10 3 ，每个元素占用L个单元，则用B[K]方式比常规存储节省多少单元?【西安电子科技
大学1996二、4(5分)】
9. 
已知A为稀疏矩阵，试从空间和时间角度，比较采用两种不同的存储结构(二维数组和三元组表)完成求运算的优缺点。【西安电子科技大学1996二、6(5分)】
10. 
特殊矩阵和稀疏矩阵哪一种压缩存储后失去随机存取的功能?为什么?  【北京邮电大学2001三、1(5分)】
11. 
试叙述一维数组与有序表的异同。【西安电子科技大学1999计算机应用一、2(5分)】
数组和链表12. 
给出数组A：ARRAY[3．．8，2．．6]OF INTEGER；当它在内存中按行存放和按列存放时，分别写出数组元素A[f，j]地址计算公式(设每个元素占两个存储单元)。【南开大学1998一(8分)】
13. 
已知n阶下三角矩阵A(即当i＜j时，有ao=0)，按照压缩存储的思想，可以将其主对角线以下
所有元素(包括主对角线上元素)依次存放于一维数组B中，请写出从第一列开始采用列序为主序分配方式时在B中确定元素a ij 的存放位置的公式。【北京航空航天大学1999二(10分)】【中山大学1999三、2(5分)】
设有三对角矩阵(a ij )n*n，将其三条对角线上的元素逐行地存于数组B(1：3n一2)中，使得B[k]=a ij ，求：
14. 
用i、j表示七的下标变换公式；
15. 
用k表示i，j的下标变化公式。【东北大学2002一(4分)】【北京工业大学2000二、1(9分)】【南京航空航天大学2000四】【山东科技大学2001一、6(6分)】【长沙铁道学院1997五、1(10分)】
16. 
上三角阵A(N*N)按行主序压缩存放在数组B中，其中A[i，j]=B[k]。写出用i、j表示的k。【北京工业大学2001二、1(5分)】
17. 
设有上三角矩阵(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分)
18. 
若将A视为对称矩阵，画出对其压缩存储的存储表，并讨论如何存取A中元素a ij (0≤i，j<4)；
19. 
若将A视为稀疏矩阵，画出A的十字链表结构。【北京科技大学1997三(10分)】
设对角线矩阵
20. 
若将矩阵A压缩存储到数组S中：试求出A中已存储之元素的行列下标(i，j)与S中元素的下标K之间的关系。
21. 
若将A视为稀疏矩阵时，请画出其行逻辑链接顺序表。【北京科技大学2000三(10分)】
22. 
假定有下列n×n矩阵(n为奇数) 如果用一维数组B按行主次序存储A的非零元素，问： (1)A中非零元素的行下标与列下标的关系； (2)给出A中非零元素a ij 的下标(i，j与B中的下标R的关系； (3)假定矩阵中每个元素占一个存储单元且B的起始地址为A 0 ，给出利用a ij 的下标(i，j)定位在B中的位置公式。【上海交通大学1998三(12分)】
23. 
对于一个对称矩阵采用压缩存储，只存放它的上三角部分，并按列存放。例如对于一个n*n的对称矩阵A(如右图)，用一个一维数组B来存放它的上三角部分：B=[A 11 ,A 12 ，A 22 ，A
13 ，A 23 ，A 33 ，A 14 ，…，A 1n ，A 2n ，…，A nn ]同时有两个函数：MAX(i，j)和MIN(i，j)，分别计算下标i和j中的大者与小者。试利用它们给出求任意一个A ij 在B中存放位置的公式。(若式中没有MAX(i，j)和MIN(i，j)则不给分。)【清华大学1997五(10分)】
24. 
用三元数组表示稀疏矩阵的转置矩阵，并简要写出解题步骤。【山东工业大学1995五(10分)】
7. 设计题
1. 
设有大小不等的n个数据组(n个数据组中数据的总数为m)，顺序存放在空间区D内，每个数据占一个存储单元，数据组的首地址由数组S给出(如右图所示)，试编写将新数据x插入第i个数据组的末尾且属于第i个数据组的算法，插入后，空间区D和数组S的相互关系仍保持正确。【东北大学2000六(15分)】
2. 
以三元组表存储的稀疏矩阵A、B非零元个数分别为m和n。试用类Pascal语言编写时间复杂度为O(m+n)的算法将矩阵B加到矩阵A上去。A的空间足够大，不另加辅助空间。要求描述所用结构。【北京工业大学1997三(10分)】
3. 
设整数x 1 ，x 2 ，…，x n 已存放在数组A中，编写一Pascal递归过程，输出从这n个数中取出所有k个数的所有组合(k≤n)。例：若A中存放的数是1，2，3，4，5，k为3，则输出结果应为：543，542，541，532，531，52l，432，431，421，321。【东南大学2001三(10分)】
4. 
编写一个过程，对一个n×n矩阵，通过行变换，使其每行元素的平均值按递增顺序排列。【中科院软件所1996】
5. 
请编写完整的程序。如果矩阵A中存在这样的一个元素A[i，j]满足条件：A[i，j]是第i行中值最小的元素，且又是第j列中值最大的元素，则称之为该矩阵的一个马鞍点。请编程计算出m*n
的矩阵a的所有马鞍点。【上海大学2000三(20分)】【中科院自动化所1997】
6. 
给定一个整数数组b[0．N-1]，6中连续的相等元素构成的子序列称为平台。试设计算法，求出b中最长平台的长度。【中科院计算所1999五、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. 
编写算法，将自然数1～n 2 按“蛇形”填入n×n矩阵中。例(1～4 2 )如图所示(用程序实现)。 【南京航空航天大学1997八(12分)】【中科院计算所1996】
9. 
设二维数组a[1一m，1.n]含有m*n个整数。(1)写出算法(Pascal过程或c函数)：判断a中所有元素是否互不相同，输出相关信息(yes／no)；(2)试分析算法的时间复杂度。【华中理工大学1999五(10分)】

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。