计算机专业基础综合数据结构（数组和广义表）历年真题试卷汇
编1
(总分：64.00，做题时间：90分钟)
一、 单项选择题(总题数：15，分数：34.00)
1.数组A[0．．5，0．．6]的每个元素占5个字节，将其按列优先次序存储在起始地址为1000的内存单元中，则元素A[5，5]的地址是( )。【南京理工大学2001一、13(1．5分)】 A.1 175 √ B.1 180 C.1205 D.1210
2.设7行6列的数组a以列序为主序顺序存储，基地址为1024，每个元素占2个存储单元，第4行第5列的元素(假定无第0行第0列)的存储地址是( )。【华中科技大学2006一、3(2分)】 A.1068 B.1086 √ C.1084 D.1066
3.若6行5列的数组以列序为主序顺序存储，基地址为1000，每个元素占2个存储单元，则第3行第4列的元素(假定无第0行第0列)的地址是( )。【华中科技大学2004一、4(1分)】 A.1040 √ B.1042 C.1026
D.备选答案A，B，C都不对
二维数组A的元素都是6个字符组成的串，行下标i的范围从0到8，列下标j的范围从1到10。从供选择的答案中选出应填入下列关于数组存储叙述中( )内的正确答案。(1)存放A至少需要( )个字节；(2)A的第8 N一和第5行共占( )个字节；(3)若A按行存放，元素A[8，5]的起始地址与A按列存放时的元素( )的起始地址一致。【山东工业大学2000三、1(4分)】【山东大学1998三、1(4分)】（分数：6.00） (1).(1) A.90 B.180 C.240 D.270 E.540 √ (2).(2) A.108 √ B.1 14 C.54 D.60 E.150 (3).(3) A.A[8，5] B.A[3，10] √ C.A[5，8] D.A[0，9]
4.设二维数组A[1．．m，1,n](即m行n列)按行存储在数组研1一m*n]中，则二维数组元素A[i，j]在一维数组B中的下标为( )。【南京理工大学1998一、2(2分)】
A.(i-1) n+j B.(i—1) n+j-1 C.t (f一1) D.f m+i-1 √
5.将一个A[1—100，1．．100]的三对角矩阵，按行优先存入一维数组B[1—298]中，A中元素A 6665 (即该元素下标i=66，j=65)，在B数组中的位置K为( )。【北京邮电大学1998二、5(2分)】 A.198 B.195 √ C.197
6.数组通常具有的两种基本操作是( )。【中南大学2005一、10(2分)】 A.查找和修改 √ B.查找和索引 C.索引和修改 D.建立和删除
7.对矩阵压缩存储是为了( )。【中南大学2005一、9(2分)】 A.方便运算 B.方便储存 C.提高运算速度 D.减少储存空间 √
8.稀疏矩阵一般的压缩存储方法有( )。【南京理工大学2005一、12(1分)】 A.三元组和二维数组 B.散列和十字链表 C.三元组和散列
D.三元组和十字链表 √
9.稀疏矩阵一般的压缩存储方法有两种，即( )。【华南理工大学2005一、1(2分)】【暨南大学2010一、12(2分)】【江苏大学2005一、9(2分)】 A.二维数组和三维数组 B.三元组和散列
C.三元组和十字链表 √ D.散列和十字链表
10.稀疏矩阵的三元组存储方法( )。【华南理工大学2006一、4(2分)】 A.实现转置运算很简单，只需将每个三元组的行标和列标交换 B.是一种链式存储方法
C.矩阵的非零元个数和位置在操作过程中变化不大时较有效 √ D.比十字链表法更高效
11.在稀疏矩阵的快速转置算法中，num[col]表示源矩阵M中( )。【北京理工大学2007一、7(1分)】 A.第col行中非零元的个数 B.第col行中零元的个数 C.第col列中非零元的个数 √ D.第col列中零元的个数
12.设有一个n行n列的对称矩阵A，将其下三角部分按行存放在一个一维数组B中，A[0][0]存放于B[0]中，那第i行的对角元素A[i][j]存放于B中( )处。【哈尔滨工业大学2005二、5(1分)】 A.(i+3)*i／2 √ B.(i+1)*/2 C.(2n-i+1)*i／2 D.(2n一i－1)*i／2
**
*
*
n阶对称矩阵的对称元素a ij 可以用向量B[k](0≤k≤n*(n+1)／2)表示。i和j与k之间的关系式如下：
三角矩阵元素存储时公式类似，只是增加一个常量元素。下标从0开始和从1开始，只要平移1个单元。以行序存储上三角的公式是： 13.若对n阶对称矩阵A以行序为主序方式将其下三角形的元素(包括主对角线上所有元素)依次存放于一维数组B[1．．(n(n+1))／2]中，则在B中确定a (i＜j)的位置k的关系为( )。【北京航空航天大学2000ij 一、2(2分)】【烟台大学2007一、9(2分)】 A.i*(f一1)／2+j B.j*(j－1)／2+i √ C.f*(i+1)／2+j D.j*(j+1)／2+i
14.设A是n*n的对称矩阵，将A的对角线及对角线上方的元素以列为主的次序存放在一维数组B[1.n(n+1)／2]中，对上述任一元素a ij ，(1≤i，i≤j，且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
二、 填空题(总题数：5，分数：10.00)
15.数组的存储结构采用__________存储方式。【中山大学1998一、6(1分)】【北京邮电大学2006一、6(2分)】
__________________________________________________________________________________________ 正确答案：(正确答案：顺序存储结构)
16.二维数组A[10．．20，5．．1]采用行序为主序方式存储，每个数据元素占4个存储单元，且A[10，5]的存储地址是1000，则A[18，9]的存储地址是__________。【北京交通大学2006二、2(2分)】 __________________________________________________________________________________________ 正确答案：(正确答案：1208)
17.对于数组A m*n 其元素a ij 按行优先与按列优先存储时地址之差为__________。【东南大学2005数据结构部分二、3(1分)】
__________________________________________________________________________________________ 正确答案：(正确答案：(i-j)*(n一1)。按上面选择题1～5解释给的公式，元素a ij 按行优先与按列优先存储时地址差为(i-j)*(n一1)。)
18.设数组a[1．．50，1．．80]的基地址为2000，每个元素占2个存储单元，若以行序为主序顺序存储，则元素a[45，68]的存储地址为(1)；若以列序为主序顺序存储，则元素a[45，68]的存储地址为(2)。【华中理工大学2000一、5(2分)】
__________________________________________________________________________________________ 正确答案：(正确答案：(1)9174(2)8788)
19.三维数组a[4][5][6](下标从0开始计，a有4*5*6个元素)，每个元素的长度是2，则a[2][3][4]的地址是__________。(设a[0][0][0]的地址是1000，数据以行为主方式存储。)【南京理工大学2000二、11(1．5分)】
__________________________________________________________________________________________ 正确答案：(正确答案：1164 公式：LOC(a )=LOC(a000)+[v2*v3*(j—c )+v3*+(j一c )+(k-c )]*l(其ij 1 2 3 中，I为每个元素所占单元数，vi是第i维的元素个数=(di一cl+1)，ci和di分别是第i维的界偶。))
三、 判断题(总题数：10，分数：20.00)
20.数组是一种线性结构，因此只能用来存储线性表。( )【北京邮电大学2005二、6(1-分)】 A.正确 B.错误 √
21.数组不适合作为任何二叉树的存储结构。( )【南京航空航天大学1995五、2(1分)】