第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的关系为（ ）。

i*(i?1)j*(j?1)i*(i?1)j*(j?1)?j?i?j?i2222A． B． C． D．

解： 如果aij按行存储，那么它的前面有i-1行，其有元素个数为：

1+2+3+…+（i-1）=i（i-1）/2。同时它又是所在行的第j列，因此它排列的顺序还得加

i*(i?1)?j2上j，一维数组B[n(n+1)/2]中的位置k与其下标的关系是：。

因此答案为A。

【例4-3】已知n阶下三角矩阵A，按照压缩存储的思想，可以将其主对角线以下所有元素（包括主对角线上元素）依次存放于一维数组B中。请写出从第一列开始以列序为主序分配方式时在B中确定元素aij的存放位置的公式。

解： 如果aij按列存储，那么它的前面有j-1列，共有元素： n+(n-1)+(n-2)+ ?+[n-(j-2)]

(j?2)(j?1)2=(j-1)*n-

而它又是所在列的第i行，因此在它前的元素个数还得加上i。因此它在一维数组B中

的存储顺序为：

(j?2)(j?1)2(j-1)*n-+i

【例4-4】已知广义表L=((x,y,z),a,(u,t,w))，从L表中取出的原子项ASCII码最大的运算是

（ ）。

A．head(tail(tail(L)))

B．tail(head(head(tail(L)))) C．head(tail(tail(head(L)))) D．head(tail(tail(tail(L))))

解：选项A的结果是字符串“u”；选项B的结果是空表，无字符；选项C的结果是字符“z”；选项D的结果是字符“t”。从所有选项的结果可以看出，ASCII码最大的是字符“z”。因此正确答案是C。

习题4

一、单项选择题

1. 设二维数组A[0?m-1][0?n-1]按行优先顺序存储在内存中，第一个元素的地址为p，每个元素占k个字节，则元素aij的地址为（ 1. A）。

A.p +[i*n+j-1]*k B.p+[(i-1)*n+j-1]*k C.p+[(j-1)*n+i-1]*k D.p+[j*n+i-1]*k

2. 已知二维数组A10×10中，元素a20的地址为560，每个元素占4个字节，则元素a10

的地址为（ 2. A）。

A.520 B.522 C.524 D.518

3. 若数组A[0?m][0?n]按列优先顺序存储，则aij地址为（3. A ）。 A.LOC(a00)+[j*m+i] B. LOC(a00)+[j*n+i]

C.LOC(a00)+[(j-1)*n+i-1] D. LOC(a00)+[(j-1)*m+i-1]

4. 若下三角矩阵An×n，按列顺序压缩存储在数组Sa[0?(n+1)n/2]中，则非零元素aij的地址为（4. B）。（设每个元素占d个字节）

(j?2)(j?1)2A. [(j-1)*n-+i-1]*d (j?2)(j?1)2B. [(j-1)*n-+i]*d (j?2)(j?1)2C．[(j-1)*n-+i+1]*d (j?2)(j?1)2D．[(j-1)*n-+i-2]*d

5. 设有广义表D=(a,b,D)，其长度为（B ），深度为（A ）。

A.无穷大 B.3 C.2 D.5 6. 广义表A=（a），则表尾为（6. C ）。

A.a B.(( )) C.空表 D.(a)

7. 广义表A=((x,(a,B)),(x,(a,B),y))，则运算head(head(tail(A)))的结果为（7. A ）。 A.x B.(a,B) C.(x,(a,B)) D.A 8. 下列广义表用图来表示时，分支结点最多的是（ 8. A）。 A.L=((x,(a,B)),(x,(a,B),y)) B.A=(s,(a,B))

C.B=((x,(a,B),y)) D.D=((a,B),(c,(a,B),D) 9. 通常对数组进行的两种基本操作是（9. C）。

A.建立与删除 B.索引和修改 C.查找和修改 D.查找与索引

10. 假定在数组A中，每个元素的长度为3个字节，行下标i从1到8，列下标j从1到10，从首地址SA开始连续存放在存储器内，存放该数组至少需要的单元数为（10. C）。

A.80 B.100 C.240 D.270

11. 数组A中，每个元素的长度为3个字节，行下标i从1到8，列下标j从1到10，从首地址SA开始连续存放在存储器内，该数组按行存放时，元素A[8][5]的起始地址为（11. C ）。

A.SA+141 B.SA+144 C.SA+222 D.SA+225 12. 稀疏矩阵一般的压缩存储方法有两种，即（12. C ）。 A.二维数组和三维数组 B.三元组和散列 C.三元组和十字链表 D.散列和十字链表

13. 若采用三元组压缩技术存储稀疏矩阵，只要把每个元素的行下标和列下标互换，就完成了对该矩阵的转置运算，这种观点（13. B ）。

A.正确 B.不正确 14. 一个广义表的表头总是一个（14. D）。

A.广义表 B.元素 C.空表 D.元素或广义表 15. 一个广义表的表尾总是一个（ 15.A）。

A.广义表 B.元素 C.空表 D.元素或广义表 16. 数组就是矩阵，矩阵就是数组，这种说法（16.B ）。 A.正确 B.错误 C.前句对，后句错 D.后句对 二、填空题

1. 一维数组的逻辑结构是______________，存储结构是______________；对于二维或多维数组，分为______________和______________两种不同的存储方式。1. 线性结构，顺序结构，以行为主序，以列为主序 2. 对于一个二维数组A[m][n]，若按行序为主序存储，则任一元素A[i][j]相对于A[0][0]的地址为______________。2. i×n+j个元素位置

3. 一个广义表为(a,(a,b),d,e,((i,j),k))，则该广义表的长度为_____，深度为_____。3. 5，3 4. 一个稀疏矩阵为 ，则对应的三元组线性表为_____________。4.（（0，2，2），（1，0，3），（2，2，-1），（2，3，5））

?0020? ?3000???

?00?15? ??

?0000?

5. 一个n×n的对称矩阵，如果以行为主序或以列为主序存入内存，则其容量为______________。5. n×(n+1)/2

6. 已知广义表A=((a,b,c),(d,e,f))，则运算head(tail(tail(A)))=____________。6. e 7. 设有一个10阶的对称矩阵A，采用压缩存储方式以行序为主序存储，a00为第一个元素，其存储地址为0，每个元素占有1个存储地址空间，则a85的地址为______________。7. 41

8. 已知广义表Ls=(a,(b,c,d),e)，运用head和tail函数取出Ls中的原子b的运算是______________。8. head(head(tail(Ls)))

9. 三维数组R[c1?d1,c2?d2,c3?d3]共含有______________个元素。（其中：c1≤d1,c2≤d2,c3≤d3）9.（d1-c1+1）×（d2-c2+1）×（d3-c3+1）

10. 数组A[1?10，-2?6，2?8]以行优先的顺序存储，设第一个元素的首地址是100，每个元素占3个存储长度的存储空间，则元素A[5，0，7]的存储地址为______________。10. 913

三、判断题

1. 数组可看作基本线性表的一种推广，因此与线性表一样，可以对它进行插入、删除等操作。（ 1.×

）

2. 多维数组可以看作数据元素也是基本线性表的基本线性表。（2.√） 3. 以行为主序或以列为主序对于多维数组的存储没有影响。（3.√） 4. 对于不同的特殊矩阵应该采用不同的存储方式。（4.√ ） 5. 采用压缩存储之后，下三角矩阵的存储空间可以节约一半。（5.×）

6. 在一般情况下，采用压缩存储之后，对称矩阵是所有特殊矩阵中存储空间节约最多的。（6.×）

7. 矩阵不仅是表示多维数组，而且是表示图的重要工具。（7.√） 8. 距阵中的数据元素可以是不同的数据类型。（8.×） 9. 矩阵中的行列数往往是不相等的。（9.×）

10. 广义表的表头可以是广义表，也可以是单个元素。（10.√） 11. 广义表的表尾一定是一个广义表。（11.√） 12. 广义表的元素可以是子表，也可以是单元素。（12.√） 13. 广义表不能递归定义。（13.× ） 14. 广义表实际上是基本线性表的推广。（14.√） 15. 广义表的组成元素可以是不同形式的元素。（ 15.√ ）