1、计算机专业基础综合数据结构（数组和广义表）历年真题试卷汇编 1及答案与解析一、单项选择题1 数组 A05，06的每个元素占 5 个字节，将其按列优先次序存储在起始地址为 1000 的内存单元中，则元素 A5，5的地址是 ( )。【南京理工大学 2001一、13(1 5 分) 】（A）1 175（B） 1 180（C） 1205 （D）12102 设 7 行 6 列的数组 a 以列序为主序顺序存储，基地址为 1024，每个元素占 2 个存储单元，第 4 行第 5 列的元素(假定无第 0 行第 0 列)的存储地址是( )。【华中科技大学 2006 一、3(2 分)】（A）1068（B） 1086（
2、C） 1084 （D）10663 若 6 行 5 列的数组以列序为主序顺序存储，基地址为 1000，每个元素占 2 个存储单元，则第 3 行第 4 列的元素(假定无第 0 行第 0 列)的地址是( )。【华中科技大学 2004 一、4(1 分) 】（A）1040（B） 1042（C） 1026 （D）备选答案 A，B，C 都不对3 二维数组 A 的元素都是 6 个字符组成的串，行下标 i 的范围从 0 到 8，列下标 j的范围从 1 到 10。从供选择的答案中选出应填入下列关于数组存储叙述中( )内的正确答案。(1)存放 A 至少需要 ( )个字节；(2)A 的第 8 N 一和第 5 行共占(
3、 ) 个字节；(3)若 A 按行存放，元素 A8，5 的起始地址与 A 按列存放时的元素( )的起始地址一致。【山东工业大学 2000 三、1(4 分)】【山东大学 1998 三、1(4 分)】4 (1)（A）90（B） 180（C） 240 （D）270（E）5405 (2)（A）108（B） 1 14（C） 54 （D）60 （E）1506 (3)（A）A8 ，5（B） A3，10（C） A5，8（D）A0 ，97 设二维数组 A1m，1,n(即 m 行 n 列) 按行存储在数组研 1 一 m*n中，则二维数组元素 Ai，j 在一维数组 B 中的下标为( )。 【南京理工大学 1998 一
4、、2(2分)】（A）(i-1) *n+j（B） (i1)*n+j-1 （C） t*(f 一 1)（D）f *m+i-18 将一个 A1100，1100的三对角矩阵，按行优先存入一维数组 B1298中，A 中元素 A6665 (即该元素下标 i=66，j=65) ，在 B 数组中的位置 K 为( )。【北京邮电大学 1998 二、5(2 分) 】（A）198（B） 195（C） 1979 数组通常具有的两种基本操作是( )。【中南大学 2005 一、10(2 分)】（A）查找和修改（B）查找和索引（C）索引和修改（D）建立和删除10 对矩阵压缩存储是为了( )。【中南大学 2005 一、9(2
5、分)】（A）方便运算（B）方便储存（C）提高运算速度（D）减少储存空间11 稀疏矩阵一般的压缩存储方法有( )。【南京理工大学 2005 一、12(1 分)】（A）三元组和二维数组（B）散列和十字链表（C）三元组和散列（D）三元组和十字链表12 稀疏矩阵一般的压缩存储方法有两种，即( )。【华南理工大学 2005 一、1(2分)】【 暨南大学 2010 一、12(2 分)】【江苏大学 2005 一、9(2 分)】（A）二维数组和三维数组（B）三元组和散列（C）三元组和十字链表（D）散列和十字链表13 稀疏矩阵的三元组存储方法( )。【华南理工大学 2006 一、4(2 分)】（A）实现转置运算
6、很简单，只需将每个三元组的行标和列标交换（B）是一种链式存储方法（C）矩阵的非零元个数和位置在操作过程中变化不大时较有效（D）比十字链表法更高效14 在稀疏矩阵的快速转置算法中，numcol表示源矩阵 M 中( )。【北京理工大学 2007 一、7(1 分) 】（A）第 col 行中非零元的个数（B）第 col 行中零元的个数（C）第 col 列中非零元的个数（D）第 col 列中零元的个数15 设有一个 n 行 n 列的对称矩阵 A，将其下三角部分按行存放在一个一维数组 B中，A00存放于 B0中，那第 i 行的对角元素 Aij存放于 B 中( )处。【哈尔滨工业大学 2005 二、5(1
7、分)】（A）(i+3)*i2（B） (i+1)*/2（C） (2n-i+1)*i2 （D）(2n 一 i1)*i 216 若对 n 阶对称矩阵 A 以行序为主序方式将其下三角形的元素 (包括主对角线上所有元素)依次存放于一维数组 B1(n(n+1)2中，则在 B 中确定 aij(ij)的位置k 的关系为( )。【北京航空航天大学 2000 一、2(2 分)】【烟台大学 2007 一、9(2分)】（A）i*(f 一 1)2+j（B） j*(j1)2+i（C） f*(i+1)2+j（D）j*(j+1)2+i17 设 A 是 n*n 的对称矩阵，将 A 的对角线及对角线上方的元素以列为主的次序存放在
8、一维数组 B1.n(n+1)2中，对上述任一元素 aij，(1i，ij，且 i（A）i(i-1)2+j（B） j(j 一 1)2+i（C） j(j-1)2+i-1 （D）f(i-1)2+j-1二、填空题18 数组的存储结构采用_存储方式。【中山大学 1998 一、6(1 分)】【北京邮电大学 2006 一、6(2 分)】19 二维数组 A1020，51采用行序为主序方式存储，每个数据元素占 4个存储单元，且 A10，5的存储地址是 1000，则 A18，9的存储地址是_。【北京交通大学 2006 二、2(2 分)】20 对于数组 Am*n 其元素 aij 按行优先与按列优先存储时地址之差为_。
9、【东南大学 2005 数据结构部分二、3(1 分)】21 设数组 a150，1 80的基地址为 2000，每个元素占 2 个存储单元，若以行序为主序顺序存储，则元素 a45，68 的存储地址为(1)；若以列序为主序顺序存储，则元素 a45，68的存储地址为(2)。【华中理工大学 2000 一、5(2 分)】22 三维数组 a456(下标从 0 开始计，a 有 4*5*6 个元素)，每个元素的长度是2，则 a234的地址是 _。(设 a000的地址是 1000，数据以行为主方式存储。)【南京理工大学 2000 二、11(15 分)】三、判断题23 数组是一种线性结构，因此只能用来存储线性表。(
10、)【北京邮电大学 2005 二、6(1-分)】（A）正确（B）错误24 数组不适合作为任何二叉树的存储结构。( )【南京航空航天大学 1995 五、2(1分)】（A）正确（B）错误25 从逻辑结构上看 n 维数组的每个元素均属于 n 个向量。( )【东南大学 2001 一、2(1 分)】【中山大学 1994 一、2(2 分) 】（A）正确（B）错误26 稀疏矩阵压缩存储后，必会失去随机存取功能。( )【中科院软件所 1997 一、1(1 分)】【烟台大学 2007 二、5(1 分) 】（A）正确（B）错误27 稀疏矩阵压缩存储后，还可以进行随机存取。( )【哈尔滨工业大学 2005 三、7(1
11、 分)】（A）正确（B）错误28 一个稀疏矩阵 Am*n 采用三元组形式表示，若把三元组中有关行下标与列下标的值互换，并把 m 和 n 的值互换，则就完成了 Am*n 的转置运算。( )【西安交通大学1996 二、8(3 分) 】（A）正确（B）错误29 数组可看成线性结构的一种推广，因此与线性表一样，可以对它进行插入、删除等操作( ) 。 【上海交通大学 1998 一、5(1 分) 】（A）正确（B）错误30 二维以上的数组其实是一种特殊的广义表。( )【北京邮电大学 2002 一、5(1分)】（A）正确（B）错误31 线性表可以看成是广义表的特例，如果广义表中的每个元素都是原子，则广义表便
12、成为线性表。( ) 【中国海洋大学 2007 二、5(1 分)】（A）正确（B）错误32 广义表是线性表的推广，是一类线性数据结构。( )【中国海洋大学 2007 二、4(1 分)】（A）正确（B）错误计算机专业基础综合数据结构（数组和广义表）历年真题试卷汇编 1答案与解析一、单项选择题1 【正确答案】 A2 【正确答案】 B3 【正确答案】 A4 【正确答案】 E5 【正确答案】 A6 【正确答案】 B7 【正确答案】 D8 【正确答案】 B9 【正确答案】 A10 【正确答案】 D11 【正确答案】 D12 【正确答案】 C13 【正确答案】 C14 【正确答案】 C15 【正确答案】 A
13、【试题解析】 n 阶对称矩阵的对称元素 aij 可以用向量 Bk(0kn*(n+1)2)表示。i 和 j 与 k 之间的关系式如下：三角矩阵元素存储时公式类似，只是增加一个常量元素。下标从 0 开始和从 1 开始，只要平移 1 个单元。以行序存储上三角的公式是：16 【正确答案】 B17 【正确答案】 B二、填空题18 【正确答案】 顺序存储结构19 【正确答案】 120820 【正确答案】 (i-j)*(n 一 1)。按上面选择题 15 解释给的公式，元素 aij 按行优先与按列优先存储时地址差为(i-j)*(n 一 1)。21 【正确答案】 (1)9174(2)878822 【正确答案】
14、1164 公式：LOC(a ij)=LOC(a000)+v2*v3*(jc1)+v3*+(j 一 c2)+(k-c3)*l(其中，I 为每个元素所占单元数，vi 是第 i 维的元素个数=(di 一 cl+1)，ci 和di 分别是第 i 维的界偶。)三、判断题23 【正确答案】 B24 【正确答案】 B【试题解析】 对于完全二叉树，用一维数组作存储结构是效率高的(存储密度大)。25 【正确答案】 A26 【正确答案】 A27 【正确答案】 B28 【正确答案】 B【试题解析】 稀疏矩阵转置后，除行列下标及行列数互换外，还必须确定该元素转置后在新三元组中的位置。29 【正确答案】 B【试题解析】 数组在维数和界偶确定后，其元素个数已经确定，不能进行插入和删除运算。30 【正确答案】 A【试题解析】 该广义表的元素具有相同性质，属于同一数据对象。例如，n(n1)维数组可以看成其元素是(n 一 1)维数组的广义表，广义表的元素都是 (n 一 1)维数组。31 【正确答案】 A32 【正确答案】 B【试题解析】 线性表中的元素具有相同性质，属于同一数据对象。广义表中的元素有原子，有子表，不具有同一性质，因此严格说，广义表不是线性结构。但是，当广义表中的元素都是原子时，广义表蜕变成线性表。
