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