第4章 数组和广义表
【例4-1】二维数组A的每一个元素是由6个字符组成的串，其行下标i=0，1，…，8，列下标j=1，2，…，10。若A以行为主序存储元素，A[8][5]的物理地址与当A按列为主序存储时的元素（ ）的物理地址相同。设每个字符占一个字节。
A．A[8][5] B．A[3][10] C．A[5][8] D．A[0][9]
解： 二维数A是一个9行10列的矩阵，即A[9][10]。按行存储时，A[8][5]是第85个元素存储的元素。而按列存储时，第85个存储的元素是A[3][10]。即正确答案为B。
【例4-2】若对n阶对称矩阵A以行序为主序方式将其下三角形的元素（包括主对角线上所有元素）依次存放于一维数组B[n（n+1）/2]中，则在B中确定的位置k的关系为（ ）。
A．jii2)1(* B．ijj2)1(* C．jii2)1(* D．ijj2)1(*
解： 如果aij按行存储，那么它的前面有i-1行，其有元素个数为：
1+2+3+…+（i-1）=i（i-1）/2。同时它又是所在行的第j列，因此它排列的顺序还得加上j，一维数组B[n(n+1)/2]中的位置k与其下标的关系是：jii2)1(*。
因此答案为A。
【例4-3】已知n阶下三角矩阵A，按照压缩存储的思想，可以将其主对角线以下所有元素（包括主对角线上元素）依次存放于一维数组B中。请写出从第一列开始以列序为主序分配方式时在B中确定元素aij的存放位置的公式。
解： 如果aij按列存储，那么它的前面有j-1列，共有元素：
n+(n-1)+(n-2)+ …+[n-(j-2)]
=(j-1)*n-2)1)(2(jj
而它又是所在列的第i行，因此在它前的元素个数还得加上i。因此它在一维数组B中的存储顺序为：
(j-1)*n-2)1)(2(jj+i
【例4-4】已知广义表L=((x,y,z),a,(u,t,w))，从L表中取出的原子项ASCII码最大的运算是（ ）。
计算机专业基础综合数据结构（数组和广义表）历年真题试卷汇编5
(总分：60.00，做题时间：90分钟)
一、 单项选择题(总题数：15，分数：30.00)
1.对n阶对称矩阵作压缩存储时，需要表长为( )的顺序表。【华中科技大学2006一、2(2分)】
（分数：2.00）
A.n／2
B.n 2 ／2
C.n(n+1)／2 √
D.n(n-1)／2
解析：
2.有一个100*90的稀疏矩阵，非0元素有10个，设每个整型数占2字节，则用三元组表示该矩阵时，所需的字节数是( )。【南京理工大学1999二、8(2分)】
（分数：2.00）
A.60
B.66 √
C.18000
D.33
解析：解析：三元组的每个元素包括行值、列值和元素值，10个非零元素占60字节。加上三元组表中行．数、列数和总的非零元素个数所占的6字节，故选B。
3.数组A[0．．4，一1．-3，5．．7]中含有元素的个数( )。【中山大学1998二、5(2分)】
（分数：2.00）
A.55
B.45 √
C.36
D.16
解析：
4.用数组r存储静态链表，结点的next域指向后继，工作指针j指向链中结点，使j沿链移动的操作为( )。【南京理工大学2001一、1 6(1．5分)】
（分数：2.00）
A.j=r[f]．next √
B.j=1+1
C.j=f一>next
D.j=r[j]一>next
解析：
5.一个非空广义表的表尾( )。【北京交通大学2004一、2(2分)】
（分数：2.00）
A.不能是子表
B.只能是子表 √
C.只能是原子
D.是原子或子表
解析：
6.广义表(((a))，((b，(c)，(e(e，f)))，o)的深度是( )。【华中科技大学2007一、7(2分)】
（分数：2.00）
A.2 B.3
C.4 √
D.5
解析：
7.广义表(a，((b，(c，d(e，f)))，g)的深度为( )。【北京邮电大学2005一、4(2分)】
* *
第五章数组和广义表：习题
习 题
一、选择题
1．假设以行序为主序存储二维数组A[1．．100,1．．100]，设每个数据元素占两个存储单元，基地址为10，则LOC(A[5，5])=( )。
A. 808 B. 818 C. 1010 D. 1020
2．同一数组中的元素( )。
A. 长度可以不同 B．不限 C．类型相同 D. 长度不限
3．二维数组A的元素都是6个字符组成的串，行下标i的范围从0到8，列下标j的范
圈从1到10。从供选择的答案中选出应填入下列关于数组存储叙述中( )内的正确答案。
(1)存放A至少需要( )个字节。
(2)A的第8列和第5行共占( )个字节。
(3)若A按行存放，元素A[8]【5]的起始地址与A按列存放时的元素( )的起始地址
一致。
供选择的答案：
(1)A. 90 B. 180 C. 240 D. 270 E.540
(2) A. 108 B. 114 C. 54 D. 60 E.150
(3)A.A[8][5] B. A[3][10] c.A[5][8] D.A[O][9]
4.数组与一般线性表的区别主要是( )。
A.存储方面 B.元素类型方面
C.逻辑结构方面 D.不能进行插入和删除运算
5．设二维数组A[1．．m，1．．n]按行存储在数组B[1．．m×n]中，则二维数组元素A[i，j]在一维数组B中的下标为( )。
A. (i-l)×n+j B. (i-l)×n+j-l
C．i×(j-l) D. j×m+i-l
6．所谓稀疏矩阵指的是( )。
A.零元素个数较多的矩阵
1 第五章 数组与广义表
一．单项选择题
1．在以下的叙述中，正确的是 。
A. 线性表的线性存储结构优于链表存储结构
B. 二维数组是数据元素为线性表的线性表
C. 栈的操作方式是先进先出
D. 队列的操作方式是先进后出
2．常对数组进行的两种操作是 。
A. 建立与删除 B. 索引和修改 C. 查找和修改 D. 查找与索引
3．在数组A中，每个数组元素A[i,j]占用3个存储字，行下标i从1到8，列下标j从1到10。所有数组元素相继存放在一个连续的存储空间，则存放该数组至少需要的存储字数是 。
A. 80 B. 100 C. 240 D. 270
4．假设8行10列的二维数组a[1..8, 1..10]分别以行序为主序和以列序为主序顺序存储时，其首地址相同，那么以行序为主序时元素a[3][5]的地址与以列序为主序时元素 _______的地址相同。
A. a[5][3] B. a[8][3] C. a[1][4] D. 答案A、B、C均不对
5．如果只保存一个n阶对称矩阵a的下三角元素（含对角线元素），并采用行主序存储在一维数组b中，a[i][j]（或a[i,j]）存于b[k]，则对i
A. B. C. D.
6．将一个A[1..100,1..100]的三对角矩阵以行序为主序存入一维数组B[1..298]中，元素A[66，65]在B数组中的位置k等于_______。
A. 198 B. 197 C. 196 D. 195
7．稀疏矩阵一般的压缩存储方法有两种，即 。
A. 二维数组和三维数组 B. 三元组和散列
