1、计算机专业基础综合数据结构（数组和广义表）历年真题试卷汇编 4及答案与解析一、综合题1 数组 A18，一 26，06以行为主序存储，设第一个元素的首地址是78，每个元素的长度为 4，试求元素 A4，2，3的存储首地址。 【厦门大学 1998五、1(5 分) 】2 数组 A 中，每个元素 Ai，f的长度均为 32 个二进位，行下标从一 1 到 9，列下标从 1 到 11，从首地址 S 开始连续存放在主存储器中，主存储器字长为 16 位。求：(1)存放该数组所需多少单元?(2)存放数组第 4 列所有元素至少需多少单元?(3)数组按行存放时，元素 A7，4 的起始地址是多少?(4)数组按列存放时，元
2、素 A4，7 的起始地址是多少? 【大连海事大学 1996 四、1(6 分)】3 假设按低下标优先存储整型数组 A(一 3：8，3：5，一 4：0，0：7)时，第一个元素的字节存储地址是 100，每个整数占 4 字节，问 A(0，4，一 2，5)的存储地址是什么? 【清华大学 1996 三】4 设有五对角矩阵 A=(aij)20*20，按特殊矩阵压缩存储的方式将其五条对角线上的元素存于数组 A-10：m中，计算元素 A15，16的存储位置。【东北大学 1999 一、2(4 分)】5 数组 A08，110】的元素是 6 个字符组成的串，则存放 A 至少需要多少字节?A 的第 8 列和第 5 行共
3、占多少字节? 若 A 按行优先方式存储，元素 A8，5的起始地址与当 A 按列优先方式存储时的哪个元素的起始地址一致 ?【厦门大学 2000五、3(14 3 分) 】6 设 mn 阶稀疏矩阵 A 有 t 个非零元素，其三元组表表示为 LTMAt+1)，13，试问：非零元素的个数 t 达到什么程度时用 LTMA 表示 A 才有意义?【北京航空航天大学 1998 一、5(4 分) 】6 设有三对角矩阵(a ij)nn 将其三条对角线上的元素逐行地存于数组 B(1：3n 一 2)中，使得 sk=ai， j，求：7 用 i，j 表示 k 的下标变换公式；8 若 n=103，每个元素占用 L 个单元，则
4、用 BK方式比常规存储节省多少单元?【西安电子科技大学 1996 二、4(5 分)】9 已知 A 为稀疏矩阵，试从空间和时间角度，比较采用两种不同的存储结构 (二维数组和三元组表)完成求 运算的优缺点。【西安电子科技大学 1996 二、6(5分)】10 特殊矩阵和稀疏矩阵哪一种压缩存储后失去随机存取的功能?为什么? 【北京邮电大学 2001 三、1(5 分) 】11 试叙述一维数组与有序表的异同。【西安电子科技大学 1999 计算机应用一、2(5 分)】12 给出数组 A：ARRAY38，26OF INTEGER；当它在内存中按行存放和按列存放时，分别写出数组元素 Af，j地址计算公式(设每个
5、元素占两个存储单元)。【 南开大学 1998 一(8 分)】13 已知 n 阶下三角矩阵 A(即当 ij 时，有 ao=0)，按照压缩存储的思想，可以将其主对角线以下所有元素(包括主对角线上元素)依次存放于一维数组 B 中，请写出从第一列开始采用列序为主序分配方式时在 B 中确定元素 aij 的存放位置的公式。【北京航空航天大学 1999 二(10 分)】【中山大学 1999 三、2(5 分)】13 设有三对角矩阵(a ij)n*n，将其三条对角线上的元素逐行地存于数组 B(1：3n 一2)中，使得 Bk=aij，求：14 用 i、j 表示七的下标变换公式；15 用 k 表示 i，j 的下标变
6、化公式。【东北大学 2002 一(4 分)】【北京工业大学2000 二、1(9 分) 】【南京航空航天大学 2000 四】【山东科技大学 2001 一、6(6 分)】【长沙铁道学院 1997 五、1(10 分)】16 上三角阵 A(N*N)按行主序压缩存放在数组 B 中，其中 Ai，j=Bk 。写出用i、j 表示的 k。【北京工业大学 2001 二、1(5 分)】17 设有上三角矩阵(a ij)n*n 将其上三角中的元素按先行后列的顺序存于数组 B(1：m)中，使得 Bk=aij 且 k=f1(i)+f2(j)+c，请推导出函数 f1、f2 和常数 c，要求 f1 和 f2中不含常数项。【中科
7、院自动化所 1999】【山东科技大学 2002 5 (6 分)17 18 若将 A 视为对称矩阵，画出对其压缩存储的存储表，并讨论如何存取 A 中元素aij(0i，j19 若将 A 视为稀疏矩阵，画出 A 的十字链表结构。【北京科技大学 1997 三(10分)】19 设对角线矩阵20 若将矩阵 A 压缩存储到数组 S 中：试求出 A 中已存储之元素的行列下标(i，j)与 S 中元素的下标 K 之间的关系。21 若将 A 视为稀疏矩阵时，请画出其行逻辑链接顺序表。 【北京科技大学 2000三(10 分 )】22 假定有下列 nn 矩阵(n 为奇数)如果用一维数组 B 按行主次序存储A 的非零元素
8、，问：(1)A 中非零元素的行下标与列下标的关系；(2)给出 A 中非零元素 aij 的下标 (i，j 与 B 中的下标 R 的关系；(3)假定矩阵中每个元素占一个存储单元且 B 的起始地址为 A0，给出利用 aij 的下标(i，j) 定位在 B 中的位置公式。【上海交通大学 1998 三(12 分)】23 对于一个对称矩阵采用压缩存储，只存放它的上三角部分，并按列存放。例如对于一个 n*n 的对称矩阵 A(如右图)，用一个一维数组 B 来存放它的上三角部分：B=A11,A12，A 22，A 13，A 23，A 33，A 14，A 1n，A 2n，A nn同时有两个函数：MAX(i，j) 和
9、MIN(i，j)，分别计算下标 i 和 j 中的大者与小者。试利用它们给出求任意一个 Aij 在 B 中存放位置的公式。 (若式中没有 MAX(i，j) 和 MIN(i，j) 则不给分。)【 清华大学 1997 五(10 分)】24 用三元数组表示稀疏矩阵的转置矩阵，并简要写出解题步骤。【山东工业大学1995 五(10 分) 】二、设计题25 设有大小不等的 n 个数据组(n 个数据组中数据的总数为 m)，顺序存放在空间区D 内，每个数据占一个存储单元，数据组的首地址由数组 S 给出(如右图所示)，试编写将新数据 x 插入第 i 个数据组的末尾且属于第 i 个数据组的算法，插入后，空间区 D
10、和数组 S 的相互关系仍保持正确。【东北大学 2000 六(15 分)】26 以三元组表存储的稀疏矩阵 A、B 非零元个数分别为 m 和 n。试用类 Pascal 语言编写时间复杂度为 O(m+n)的算法将矩阵 B 加到矩阵 A 上去。A 的空间足够大，不另加辅助空间。要求描述所用结构。【北京工业大学 1997 三(10 分)】27 设整数 x1，x 2，x n 已存放在数组 A 中，编写一 Pascal 递归过程，输出从这n 个数中取出所有 k 个数的所有组合(kn)。例：若 A 中存放的数是1，2，3，4，5，k 为 3，则输出结果应为：543，542，541，532，531，52l，43
11、2，431，421， 321。【东南大学 2001 三(10 分)】28 编写一个过程，对一个 nn 矩阵，通过行变换，使其每行元素的平均值按递增顺序排列。【中科院软件所 1996】29 请编写完整的程序。如果矩阵 A 中存在这样的一个元素 Ai，j 满足条件：Ai，j是第 i 行中值最小的元素，且又是第 j 列中值最大的元素，则称之为该矩阵的一个马鞍点。请编程计算出 m*n 的矩阵 a 的所有马鞍点。【上海大学 2000 三(20 分)】【中科院自动化所 1997】30 给定一个整数数组 b0N-1，6 中连续的相等元素构成的子序列称为平台。试设计算法，求出 b 中最长平台的长度。【中科院计
12、算所 1999 五、2(20 分)】31 给定 nm 矩阵 Aab，c 一 d，并设 Ai,jAi，j+1(aib，cjd-1)和 Ai,jAi+1，f (aib 一 1，cjd)。设计一算法判定 x 的值是否在 A 中，要求时间复杂度为 O(m+n)。【东南大学 2005 四(10 分)2001 六(13 分) 1994 三(17 分)】【清华大学 1998 六(10 分) 】32 编写算法，将自然数 1n 2 按“蛇形” 填入 nn 矩阵中。例 (14 2)如图所示(用程序实现)。 【南京航空航天大学 1997 八(12 分)】【中科院计算所1996】33 设二维数组 a1 一 m，1.n
13、 含有 m*n 个整数。(1)写出算法(Pascal 过程或 c 函数)：判断 a 中所有元素是否互不相同，输出相关信息(yesno)；(2)试分析算法的时间复杂度。【华中理工大学 1999 五(10 分)】计算机专业基础综合数据结构（数组和广义表）历年真题试卷汇编 4答案与解析一、综合题1 【正确答案】 元素 A4，2，3的存储首地址为 958。 三维数组以行为主序存储，其元素地址公式为：LOC(A ijk)=LOC(Ac1c2c3)=(3Ac1c2c3)+(i-c1)V2V3+(jc2)V3+(k-c3)*L 其中，c i，d i 是各维的下界和上界， Vi=di 一 ci+1 是各维元素
14、个数，L 是一个元素所占的存储单元数。2 【正确答案】 每个元素 32 个二进制位，主存字长 16 位，故每个元素占 2 个字长，行下标可平移至 1 到 11。(1)242 (2)22 (3)S+182 (4)S+1423 【正确答案】 1784 (公式：Loc(A ijkl)=100(基地址)+(i-c 1)v2v3v4+一 c2)v3v4+(k-c3)v4+(l 一 c4)*4)4 【正确答案】 五对角矩阵按行存储，元素在一维数组中下标(从 1 开始)k 与i，jA15，16 是第 71 个元素，在向量 -10：m中的存储位置是 60。5 【正确答案】 (1)540 (2)108 (3)i
15、=3，j=10 ，即 A3，10求解(3) 用以下等式：Loc(8，5)=Loc(0，1)+(fc1)*(c 一 c2+1)+(j 一 c2)*L=Loc(0，1)+84*LLoc(f， j=Loc(0，1)+(，一 c2)*(d1 一 c1+1)+(fc1)*L即(j-1)+i=84，其中 0i8，1j10。6 【正确答案】 稀疏矩阵 A 有 t 个非零元素，加上行数 mu、列数 nu 和非零元素个数 tu(也算一个三元组)，共占用三元组表 LTMA 的 3(t+1)个存储单元，用二维数组存储时占用 m*n 个单元，只有当 3(t+1)=li=si+1；j一)Dj+1=Dj； 第 i+1 个
16、数据组及以后元素后移Dsi+1=x； 将新数据 x 插入for(j=i+1；jAij)mini=j； 修改第 i 行最小元素的列号for(i=0；ilongest)longest=ij+1；k=j；)局部最长平台i+；j=i； 新平台起点31 【正确答案】 要求查找时间复杂度为 O(m+n)，不能采用常规的二层循环的查找。可以先从右上角(i=a ， j=d)元素与 x 比较，只有三种情况：一是 Aijx，这种情况下向 j 小的方向继续查找；二是 Aijx，下步应向 i 大的方向查找；三是Aij=x，查找成功。否则，若下标已超出范围，则查找失败。核心语句段如下：while(i=C j+;if(i0elsei=i+2；j=n 一 1；最外层 while33 【正确答案】 判断二维数组中元素是否互不相同，只有逐个比较，找到一对相等的元素，就可结论为不是互不相同。如何达到每个元素同其他元素比较一次且只一次?在当前行，每个元素要同本行后面的元素比较一次(下面第一个循环控制变量p 的 for 循环 )，然后同第 i+1 行及以后各行元素比较一次，这就是循环控制变量 k和 P 的二层 for 循环。 for(i=0 ； i 2)。
