1、计算机专业基础综合数据结构（数组和广义表）历年真题试卷汇编3 及答案解析(总分：66.00，做题时间：90 分钟)一、综合题(总题数：20，分数：48.00)1.数组 A18，一 26，06以行为主序存储，设第一个元素的首地址是 78，每个元素的长度为 4，试求元素 A4，2，3的存储首地址。 【厦门大学 1998 五、1(5 分)】（分数：2.00）_2.数组 A 中，每个元素 Ai，f的长度均为 32 个二进位，行下标从一 1 到 9，列下标从 1 到 11，从首地址 S 开始连续存放在主存储器中，主存储器字长为 16 位。求：(1)存放该数组所需多少单元?(2)存放数组第 4 列所有元素
2、至少需多少单元?(3)数组按行存放时，元素 A7，4的起始地址是多少?(4)数组按列存放时，元素 A4，7的起始地址是多少?【大连海事大学 1996 四、1(6 分)】（分数：2.00）_3.假设按低下标优先存储整型数组 A(一 3：8，3：5，一 4：0，0：7)时，第一个元素的字节存储地址是100，每个整数占 4 字节，问 A(0，4，一 2，5)的存储地址是什么? 【清华大学 1996 三】（分数：2.00）_4.设有五对角矩阵 A=(a ij ) 20*20 ，按特殊矩阵压缩存储的方式将其五条对角线上的元素存于数组 A-10：m中，计算元素 A15，16的存储位置。【东北大学 1999
3、 一、2(4 分)】（分数：2.00）_5.数组 A08，110】的元素是 6 个字符组成的串，则存放 A 至少需要多少字节?A 的第 8 列和第 5 行共占多少字节?若 A 按行优先方式存储，元素 A8，5的起始地址与当 A 按列优先方式存储时的哪个元素的起始地址一致?【厦门大学 2000 五、3(143 分)】（分数：2.00）_6.设 mn 阶稀疏矩阵 A 有 t 个非零元素，其三元组表表示为 LTMAt+1)，13，试问：非零元素的个数 t 达到什么程度时用 LTMA 表示 A 才有意义?【北京航空航天大学 1998 一、5(4 分)】（分数：2.00）_设有三对角矩阵(a ij )
4、nn 将其三条对角线上的元素逐行地存于数组 B(1：3n 一 2)中，使得 sk=a i ，j，求：（分数：4.00）(1).用 i，j 表示 k 的下标变换公式；（分数：2.00）_(2).若 n=10 3 ，每个元素占用 L 个单元，则用 BK方式比常规存储节省多少单元?【西安电子科技大学1996 二、4(5 分)】（分数：2.00）_7.已知 A 为稀疏矩阵，试从空间和时间角度，比较采用两种不同的存储结构(二维数组和三元组表)完成求（分数：2.00）_8.特殊矩阵和稀疏矩阵哪一种压缩存储后失去随机存取的功能?为什么? 【北京邮电大学 2001 三、1(5 分)】（分数：2.00）_9.试
5、叙述一维数组与有序表的异同。【西安电子科技大学 1999 计算机应用一、2(5 分)】（分数：2.00）_10.给出数组 A：ARRAY38，26OF INTEGER；当它在内存中按行存放和按列存放时，分别写出数组元素 Af，j地址计算公式(设每个元素占两个存储单元)。【南开大学 1998 一(8 分)】（分数：2.00）_11.已知 n 阶下三角矩阵 A(即当 ij 时，有 ao=0)，按照压缩存储的思想，可以将其主对角线以下所有元素(包括主对角线上元素)依次存放于一维数组 B 中，请写出从第一列开始采用列序为主序分配方式时在 B中确定元素 a ij 的存放位置的公式。【北京航空航天大学 1
6、999 二(10 分)】【中山大学 1999 三、2(5 分)】（分数：2.00）_设有三对角矩阵(a ij )n*n，将其三条对角线上的元素逐行地存于数组 B(1：3n 一 2)中，使得 Bk=a ij ，求：（分数：4.00）(1).用 i、j 表示七的下标变换公式；（分数：2.00）_(2).用 k 表示 i，j 的下标变化公式。【东北大学 2002 一(4 分)】【北京工业大学 2000 二、1(9 分)】【南京航空航天大学 2000 四】【山东科技大学 2001 一、6(6 分)】【长沙铁道学院 1997 五、1(10 分)】（分数：2.00）_12.上三角阵 A(N*N)按行主序压
7、缩存放在数组 B 中，其中 Ai，j=Bk。写出用 i、j 表示的 k。【北京工业大学 2001 二、1(5 分)】（分数：2.00）_13.设有上三角矩阵(a ij ) n*n 将其上三角中的元素按先行后列的顺序存于数组 B(1：m)中，使得 Bk=a ij 且 k=f1(i)+f2(j)+c，请推导出函数 f1、f2 和常数 c，要求 f1 和 f2 中不含常数项。【中科院自动化所 1999】【山东科技大学 2002 5 (6 分)（分数：2.00）_（分数：4.00）(1).若将 A 视为对称矩阵，画出对其压缩存储的存储表，并讨论如何存取 A 中元素 a ij (0i，jj，ij，1i,
8、jn2)；在中心元素后，其下标是 k=(f 一 1)(i=li=si+1；j一)Dj+1=Dj； 第 i+1 个数据组及以后元素后移 Dsi+1=x； 将新数据 x 插入 for(j=i+1；jlongest)longest=ij+1；k=j；)局部最长平台 i+；j=i； 新平台起点 )解析：23.给定 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 分)】
9、【清华大学 1998 六(10 分)】（分数：2.00）_正确答案：(正确答案：要求查找时间复杂度为 O(m+n)，不能采用常规的二层循环的查找。可以先从右上角(i=a，j=d)元素与 x 比较，只有三种情况：一是 Aijx，这种情况下向 j 小的方向继续查找；二是 Aijx，下步应向 i 大的方向查找；三是 Aij=x，查找成功。否则，若下标已超出范围，则查找失败。核心语句段如下： while(i=C&!flag) 初始值：i=a； j=d； flag=0； if(Aij=x)flag=l； fla9=1 是成功查到 x 的标志 else if(Aijx)j 一一；else i+；)解析：2
10、4.编写算法，将自然数 1n 2 按“蛇形”填入 nn 矩阵中。例(14 2 )如图所示(用程序实现)。 （分数：2.00）_正确答案：(正确答案：本题的一种算法前面已讨论(请参见本章填空题 32 题)。这里给出另一种解法。分析数的填法，是按“从右上到左下”的”蛇形”，沿平行于副对角线的各条对角线上，将自然数从小到大填写。当从右上到左下时，坐标 i 增加，坐标 j 减小，当 j 减到小于 0 时结束，然后 j 从 0 开始增加，而i 从当前值开始减少，到 in 一 1 时，j=j+2，开始从左下向右上填数；而当 jn 一 1 时，i=i+2，开始从右上向左下填数，直到 n*n 个数填完为止。核
11、心语句段如下： while(i一 1) 从右上向左下填数 (Aij=k+；i+；j 一一；) if(j一 1&J0&J解析：25.设二维数组 a1 一 m，1.n含有 m*n 个整数。(1)写出算法(Pascal 过程或 c 函数)：判断 a 中所有元素是否互不相同，输出相关信息(yesno)；(2)试分析算法的时间复杂度。【华中理工大学 1999 五(10 分)】（分数：2.00）_正确答案：(正确答案：判断二维数组中元素是否互不相同，只有逐个比较，找到一对相等的元素，就可结论为不是互不相同。如何达到每个元素同其他元素比较一次且只一次?在当前行，每个元素要同本行后面的元素比较一次(下面第一个循环控制变量 p 的 for 循环)，然后同第 i+1 行及以后各行元素比较一次，这就是循环控制变量 k 和 P 的二层 for 循环。 for(i=0 ； i 2)。)解析：
