第5章 数组和广义表

第五章数组和广义表

讲课提要

【主要内容】

1．多维数组的顺序存储结构

2．特殊矩阵的压缩存储

3．广义表的定义及其与线性表的关系

4．广义表的存储结构

5．广义表运算实现中递归的应用

【教学目标】

1．掌握多维数组的顺序存储结构

2．掌握特殊矩阵的压缩存储方法

3．掌握广义表的定义及其与线性表的关系

4．掌握广义表的存储结构

5．了解广义表运算实现中递归的应用

学习指导

1．多维数组的顺序存储结构

对于多维数组，有两种存储方式：

一是以行为主序（或先行后列）的顺序存放，如BASIC、PASCAL、C等程序设计语言中用的是以行为主的顺序分配，即一行分配完了接着分配下一行。

另一种是以列为主序（先列后行）的顺序存放，如FORTRAN语言中，用的是以列为主序的分配顺序，即一列一列地分配。

以行为主序的分配规律是：最右边的下标先变化，即最右下标从小到大，循环一遍后，右边第二个下标再变，…，从右向左，最后是左下标。以列为主序分配的规律是：最左边的下标先变化，即最左下标从小到大，循环一遍后，左边第二个下标再变，…，从左向右，最后是右下标。

不论按何种方式存储，只要确定了数组的首地址以及每个数组元素所占用的单元数，就可以将数组元素的存储地址表示为其下标的线性函数。设有m×n二维数组A mn，以“以行为主序”的分配为例，按照元素的下标确定其地址的计算方法如下。

设数组的基址为LOC(a11)，每个数组元素占据L个地址单元，计算a ij 的物理地址的函数为：

LOC(a ij) = LOC(a11) + ( (i-1)*n + j-1 ) * L

同理，对于三维数组A mnp，即m×n×p数组，对于数组元素a ijk其物理地址为：LOC(a ijk)=LOC(a111)+( ( i-1) *n*p+ (j-1)*p +k-1) )*L

注意：在C语言中，数组中每一维的下界定义为0，则：

LOC(a ij) = LOC(a00) + ( i*n + j ) * L

【例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 。

2．特殊矩阵压缩存储的意义

在很多科学计算与工程应用中，经常要使用矩阵的概念。矩阵具有与数组相似的性质，

如元素数目固定、元素按下标关系有序地排列，所以在编程时可以利用二维数组来存储矩阵，也可以利用程序设计语言中的各种矩阵运算。

在某些情况下，特别是在数值分析中，经常会出现一些阶数很高的矩阵，其中含有许

多值相同的元素或零元素，如三角矩阵、对称矩阵、稀疏矩阵等，从节约存储空间的角度考虑，此时若用二维数组存储会造成空间的极大浪费。为了节省存储空间，可以对这类矩阵进行压缩存储。即为对多个相同值的元素只分配一个存储空间，而对零元素可以不分配空间。

3．对称矩阵压缩存储的方法

对称矩阵的特点是：在一个n 阶方阵中，有a ij =a ji ，其中1≤i , j ≤n 。

对称矩阵关于主对角线对称，因此只需存储上三角或下三角部分即可。

对于对称矩阵中的任意元素a ij ，若令I=max(i,j)，J=min(i,j)，则将上面两个式子综合起

来得到：k=I*(I-1)/2+J-1。给出对称矩阵A 中任意元素a ij ，依据它的下标i 和j 就可由上述对应关系式确定其在数组M 中的位置K ，因此a ij 的地址可由下式计算。

Loc(a ij )=Loc(M[K])=Loc(M[0])+K*L=Loc(M[0])+[I*(I+1)/2+J]*L

其中：L 为每个数据元素所占的存储单元长度。

I=max(i,j)。

J=min(i,j)。 K=I*(I+1)/2+J 。

【例4-2】若对n 阶对称矩阵A 以行序为主序方式将其下三角形的元素（包括主对角线上所有元素）依次存放于一维数组B[n （n+1）/2]中，则在B 中确定的位置k 的关系为（ ）。

A ．j i i +-2)1(*

B ．i j j +-2)1(*

C ．j i i ++2)1(*

D ．i j j ++2

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

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

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

)1(*。 因此答案为A 。

4．三角矩阵压缩存储的方法

形如图的矩阵称为三角矩阵，其中c 为某个常数。其中下面图(a)为下三角矩阵：主对角

线以上均为同一个常数；(b)为上三角矩阵，主对角线以下均为同一个常数；下面讨论它们的压缩存储方法。

三角矩阵中的重复元素c 可以共享一个存储空间，其余的元素有n(n+1)/2个，因此可压

缩存储到向量sa[0..n(n+1)/2]中，c 存放在向量的最后一个分量中，排列时以行序为主。a ij 和sa[k]的对应关系是：

下三角矩阵： 上三角矩阵：

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

解： 如果a ij 按列存储，那么它的前面有j-1列，共有元素：

n+(n-1)+(n-2)+ …+[n-(j-2)] =(j-1)*n-2

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

的存储顺序为： (j-1)*n-2

)1)(2(--j j +i 5．稀疏矩阵及其压缩存储的特点

设m*n 矩阵中有t 个非零元素且t<

存储采取如下方法：将非零元素所在的行、列以及它的值构成一个三元组（i,j,v ），然后再按某种规律存储这些三元组，这种方法可以节约存储空间。

6．稀疏矩阵压缩存储的顺序存储方式

以顺序方式组织存储时常用的方法是三元组顺序表，方法是：将三元组按行优先的顺序，

同一行中列号从小到大的规律排列成一个线性表，采用顺序存储方法存储该表。

7．稀疏矩阵压缩存储的链式存储方式

稀疏矩阵压缩存储的链式存储方式，即十字链表。当矩阵中非零元素的个数和位置在使

用中经常发生变化时，不宜采用顺序存储结构，可采用十字链表进行存储。其结点结构如图所示。

8．广义表（列表）的定义、术语及它与线性表的关系

广义表（Generalized Lists ）是n （n ≥0）个数据元素a 1, a 2, … a i , … , a n 的有序序列，

一般记作：Ls ＝（a 1, a 2, … a i , … , a n ）。

图4-2 十字链表的结点结构

其中：Ls是广义表的名称，n是它的长度，每个a i（1≤i≤n）是Ls的成员，它可以是单个元素，也可以是一个广义表，分别称为广义表Ls的单元素和子表。当广义表Ls非空时，称第一个元素a1为Ls的表头（head），称其余元素组成的表（a2，…，a i，…，a n）为Ls的表尾（tail）。

?表的深度：表中元素的最深嵌套层数。

?广义表与线性表的关系：当广义表Ls中的元素全部是原子时，广义表即为线性表。因此，可认为线性表是广义表的特例，广义表是线性表的推广。

9．广义表的三个重要性质

（1）广义表是一种多层次的数据结构。广义表的元素可以是单元素，也可以是子表，而子表的元素还可以是子表，…。

（2）广义表可以是递归的表。广义表的定义并没有限制元素的递归，即广义表也可以是其自身的子表。例如表E就是一个递归的表。

（3）广义表可以为其他表所共享。例如，表A、表B、表C是表D的共享子表。在D 中可以不必列出子表的值，而用子表的名称来引用。

10．广义表的存储结构

按结点形式的不同，广义表的链式存储结构可分为两种不同的存储方式。一种称为头尾表示法，另一种称为孩子兄弟表示法。

11．广义表的基本运算

广义表有两个重要的基本操作，即取头操作（Head）和取尾操作（Tail）。

此外，在广义表上可以定义与线性表类似的一些操作，如建立、插入、删除、拆开、连接、复制、遍历等。

【例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个字节，则元素a ij的地址为（）。

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的地址为（）。

A.520

B.522

C.524

D.518

3.若数组A[0…m][0…n]按列优先顺序存储，则a ij地址为（）。

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. 若下三角矩阵A n×n，按列顺序压缩存储在数组Sa[0…(n+1)n/2]中，则非零元素a ij的地址为（）。（设每个元素占d个字节）

A. [(j-1)*n-

2)1

)(

2

(-

-j

j

+i-1]*d

B. [(j-1)*n-

2)1

)(

2

(-

-j

j

+i]*d

C．[(j-1)*n-

2)1

)(

2

(-

-j

j

+i+1]*d

D．[(j-1)*n-

2)1

)(

2

(-

-j

j

+i-2]*d

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

A.无穷大

B.3

C.2

D.5

6. 广义表A=（a），则表尾为（）。

A.a

B.(( ))

C.空表

D.(a)

7. 广义表A=((x,(a,B)),(x,(a,B),y))，则运算head(head(tail(A)))的结果为（）。

A.x

B.(a,B)

C.(x,(a,B))

D.A

8.下列广义表用图来表示时，分支结点最多的是（）。

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.通常对数组进行的两种基本操作是（）。

A.建立与删除

B.索引和修改

C.查找和修改

D.查找与索引

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

A.80

B.100

C.240

D.270

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

A.SA+141

B.SA+144

C.SA+222

D.SA+225

12.稀疏矩阵一般的压缩存储方法有两种，即（）。

A.二维数组和三维数组

B.三元组和散列

C.三元组和十字链表

D.散列和十字链表

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

A.正确

B.不正确

14.一个广义表的表头总是一个（）。

A.广义表

B.元素

C.空表

D.元素或广义表

15.一个广义表的表尾总是一个（）。

A.广义表

B.元素

C.空表

D.元素或广义表

16.数组就是矩阵，矩阵就是数组，这种说法（）。

A.正确

B.错误

C.前句对，后句错

D.后句对

二、填空题

1.一维数组的逻辑结构是_线性结构_，存储结构是_顺序结构_；对于二维或多维数组，分

为_以行为主序_和__以列为主序___两种不同的存储方式。

2. 对于一个二维数组A[m][n]，若按行序为主序存储，则任一元素A[i][j]相对于A[0][0]的地址为__ i ×n+j 个元素位置__。

3. 一个广义表为(a,(a,b),d,e,((i,j),k))，则该广义表的长度为_ 5___，深度为__3__。

4. 一个稀疏矩阵为 ，则对应的三元组线性表为_（（0，2，2），（1，0，3），

(2，2，-1），（2，3，5））

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

6. 已知广义表A=((a,b,c),(d,e,f))，则运算head(tail(tail(A)))=____ e __。

7. 设有一个10阶的对称矩阵A ，采用压缩存储方式以行序为主序存储，a 00为第一个元素，其存储地址为0，每个元素占有1个存储地址空间，则a 85的地址为___41____。

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

9. 三维数组R[c 1…d 1,c 2…d 2,c 3…d 3]共含有__（d 1-c 1+1）×（d 2-c 2+1）×（d 3-c 3+1） __个元素。（其中：c 1≤d 1,c 2≤d 2,c 3≤d 3）

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

三、判断题

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

等操作。（× ）数组是查找和修改

2. 多维数组可以看作数据元素也是基本线性表的基本线性表。（√ ）

3. 以行为主序或以列为主序对于多维数组的存储没有影响。（√ ）

4. 对于不同的特殊矩阵应该采用不同的存储方式。（√ ）

5. 采用压缩存储之后，下三角矩阵的存储空间可以节约一半。（× ）

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

的。（×）

7. 矩阵不仅是表示多维数组，而且是表示图的重要工具。（√ ）

8. 距阵中的数据元素可以是不同的数据类型。（× ）

9. 矩阵中的行列数往往是不相等的。（× ）

10. 广义表的表头可以是广义表，也可以是单个元素。（√ ）

11. 广义表的表尾一定是一个广义表。（√ ）

12. 广义表的元素可以是子表，也可以是单元素。（√ ）

13. 广义表不能递归定义。（× ）广义表可以递归遍历

14. 广义表实际上是基本线性表的推广。（√ ）

15. 广义表的组成元素可以是不同形式的元素。（√ ）

????????????-0000510000030200

1、设广义表L=((a，b，c))，则L的长度和深度分别为（ C ）。

A. 1和1

B. 1和3

C. 1和2

D. 2和3

2、广义表((a),a)的表尾是（ B ）。

A. a

B. (a)

C. ()

D. ((a))

3、稀疏矩阵的常见压缩存储方法有（ C ）两种。

A. 二维数组和三维数组

B. 三元组和散列表

C. 三元组和十字链表

D. 散列表和十字链表

4、一个非空广义表的表头（ D ）。

A. 不可能是子表

B. 只能是子表

C. 只能是原子

D.可以是子表或原子

5、数组A[0..5,0..6]的每个元素占5个字节，将其按列优先次序存储在起始地址为1000的内存单元中，则元素A[5][5]的地址是（A ）。

A. 1175

B. 1180

C. 1205

D. 1210

6、广义表G=(a,b(c,d,(e,f)),g)的长度是（ A ）。

A. 3

B. 4

C. 7

D. 8

7、采用稀疏矩阵的三元组表形式进行压缩存储，若要完成对三元组表进行转置，只要将行和列对换，这种说法（ B ）。

A. 正确

B. 错误

C. 无法确定

D. 以上均不对

8、广义表(a,b,c)的表尾是（ B ）。

A. b,c

B. (b,c)

C. c

D. (c)

9、常对数组进行两种基本操作是（ C ）。

A. 建立和删除

B. 索引和修改

C.查找和修改

D. 查找与索引

10、对一些特殊矩阵采用压缩存储的目的主要是为了（ D ）。

A. 表达变得简单

B. 对矩阵元素的存取变得简单

C. 去掉矩阵中的多余元素

D. 减少不必要的存储空间的开销

11、设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第一个元素，其存储地址为1，每元素占1个地址空间，则a85的地址为（ B ）。

A. 13

B. 33

C. 18

D. 40

12、设矩阵A是一个对称矩阵，为了节省存储，将其下三角部分按行序存放在一维数组B[1,n(n-1)/2]中，对下三角部分中任一元素ai,j(i>=j)，在一维数组B 的下标位置k的值是（ B ）。

A. i(i-1)/2+j-1

B. i(i-1)/2+j

C.

i(i+1)/2+j-1 D. i(i+1)/2+j

13、广义表A=((a),a)的表头是（ B ）。

A. a

B. (a)

C. b

D. ((a))

14、稀疏矩阵一般的压缩存储方法有两种，即（ C ）。

A. 二维数组和三维数组

B. 三元组和散列

C. 三元组和十字链表

D. 散列和十字链表

15、假设以三元组表表示稀疏矩阵，则与如图所示三元组表对应的4×5的稀疏矩阵是（注：矩阵的行列下标均从1开始）（ B ）。

A. ??????? ?

?--00405000000000706080 B. ??????? ??--00000004053000706080 C. ??????? ??--00405000073000006080 D. ??????? ?

?--00000304050000706080 16、以下有关广义表的表述中，正确的是（ A ）。

A. 由0个或多个原子或子表构成的有限序列

B. 至少有一个元素是子表

C. 不能递归定义

D. 不能为空表

17、对广义表L=((a,b),((c,d),(e,f)))执行head(tail(head(tail(L))))操作的结果是（D ）。 A. 的 B. e C. (e) D. （e,f ）

二、判断题

（× ）1、广义表中原子个数即为广义表的长度。

（ ×）2、一个稀疏矩阵采用三元组表示，若把三元组中有关行下标与列下标的值互换，并把mu 和nu 的值进行互换，则完成了矩阵转置。

（√ ）3、稀疏矩阵压缩存储后，必会失去随机存取功能。

（× ）4、广义表的长度是指广义表中括号嵌套的层数。

（√ ）5、广义表是一种多层次的数据结构，其元素可以是单原子也可以是子表。

三、填空题

1、已知二维数组A[m][n]采用行序为主方式存储，每个元素占k 个存储单元，并且第一个元素的存储地址是LOC(A[0][0])，则A[i][j]的地址是___ Loc(A[0][0])+(i*N+j)*k ____。

2、广义表运算式HEAD(TAIL((a,b,c),(x,y,z)))的结果是： (x,y,z) 。

3、二维数组，可以按照 列序为主和行序为主 两种不同的存储方式。

4、稀疏矩阵的压缩存储方式有： 三元组 和 十字链表 。

四、综合题

1、现有一个稀疏矩阵，请给出它的三元组表。

?????

???????-02000

12000010130 答案：

i

2

1

1

v j 43

3

132332113-212

一、基本概念

1、数组地址的计算（一维数组，二维数组）

2、稀疏矩阵的压缩存储方法：三元组表和十字链表（要求会稀疏矩阵的三元组表示）

3、广义表的概念

4、求广义表的深度和长度、求广义表的表头和表尾

二、练习题

3. 二维数组A[10][20]采用列序为主方式存储，每个元素占一个存储单元并且A[0][0]的存储地址是200，则A[6][12]的地址是____。

4. 二维数组A[10..20][

5..10]采用行序为主方式存储，每个元素占4个存储单元，并且A[10][5]的存储地址是1000，则A[18][9]的地址是____。

6．求下列广义表操作的结果：

(1) GetTail[GetHead[((a,b),(c,d))]];

(2) GetTail[GetHead[GetTail[((a,b),(c,d))]]]

第五章 数组和广义表

第五章数组和广义表 一．选择题 1．在二维数组A 中引用A[i,j]的时间_________。 A．与i、j的大小有关 B．与i、j的大小无关 C．与i的大小有关，与j的大小无关 D．与i的大小无关，与j的大小有关 2．在稀疏矩阵的带行指针向量的链接存储中，每一行单链表中的结点都具有相同的________。 A．行号 B．列号 C．元素值 D.地址 3．二维数组A 按行顺序存储，其中每个元素占1个存储单元。若 A[1][1]的存储地址为420， A[3][3]的存储地址为446，则A[5][5]的存储地址为_______。A．470 B．471 C．472 D. 473 4．在稀疏矩阵的十字链接存储中，每个列单链表中的结点都具有相同的_____。A．行号 B．列号 C．元素值 D.地址 5．下面的说法中，不正确的是________。 A．对称矩阵中只须存放包括主对角线元素在内的下(或上)三角部分的元素即可B．对角矩阵中只须存放的非零元素即可 C．稀疏矩阵中值为零的元素较多，因此可以采用三元组表方法存储 D．稀疏矩阵中大量值为零的元素分布有规律，因此可以采用三元组表方法存储6．对一些特殊矩阵采用压缩存储的目的主要是为了________。 A．表达变得简单 B．对矩阵元素的存取变得简单 C．去掉矩阵中的多余元素 D．减少不必要的存储空间的开销 7．若将n 阶对称矩阵 A 按照行序为主序方式将包括主对角线元素在内的下三角形的所有元素依次存放在一个一维数组 B 中，则该对称矩阵在 B 中占用了________个数组元素。 A．n2 B．n*(n-1) C．n*(n+1)／2 D．n*(n-1) 8. 稀疏矩阵的三元组顺序表表示的一个三元组中不包括________。 A. 行号 B.列号 C.元素值 D.元素总数 9．稀疏矩阵一般的压缩存储方法有两种，即________。 A．二维数组和三维数组 B．三元组和散列 C. 三元组和十字链表 D．散列和十字链表 10．有一个 10 阶对称矩阵 A，采用压缩存储方式(以行序为主存储，且A[0 Ⅱ0]=1)，则A[8][5]的地址是________。 A．52 B．48 C．54 D．53 11.数组通常具有的两种基本操作是________。 A．建立与删除 B．索引和修改 C．查找和修改 D．查找与索引12．二维数组M 的成员是 6 个字符(每个字符占一个存储单元)组成的串，行下标 i 的范围从0 到 8，列下标j 的范围从1到10，则存放M 至少需要________个字节。 A．90 B．180 C．240 D．540 13．二维数组M 的元素是4 个字符(每个字符占一个存储单元)组成的串，行下标 i 的范围从0 到 4 ，列下标j 的范围从0 到 5,M 按行存储时元素M[3 Ⅱ5]的起始地址与M 按列存储时元素________的起始地址相同。

数据结构 第五章数组和广义表

第五章数组和广义表：习题 习题 一、选择题 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 (2) A. 108 B. 114 C. 54 D. 60 (3)[8][5] B. A[3][10] [5][8] [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.零元素个数较多的矩阵 B.零元素个数占矩阵元素中总个数一半的矩阵 C.零元素个数远远多于非零元素个数且分布没有规律的矩阵 D.包含有零元素的矩阵 7．对稀疏矩阵进行压缩存储的目的是( )。 A.便于进行矩阵运算 B.便于输入和输出 C.节省存储空间 D. 降低运算的时间复杂度 8．稀疏矩阵一般的压缩存储方法有两种，即( )。 A.二维数组和三维数组 B.三元组和散列 C.三元组和十字链表 D.散列和十字链表 9．有一个100×90的稀疏矩阵，非0元素有10个，设每个整型数占两字节，则用三元组表示该矩阵时，所需的字节数是( )。 A. 60 B. 66 C．18000 D．33 10. A[N，N]是对称矩阵，将下面三角（包括对角线）以行序存储到一维数组T[N(N+I)/2] 中，则对任一上三角元素a[i][j]对应T[k]的下标k是( )。 A. i(i-l)/2+j B. j(j-l)/2+i C. i(j-i)/2+1 D. j(i-l)/2+1 11．已知广义表L=((x，y,z)，a，(u，t，w))，从L表中取出原子项t的运算是( ) A. head(tail(tail(L))) B. tail(head(head(taiI(L)))) C. head(tail(head(taiI(L)))) D. head(tail(head(tail(tail(L)))))

(完整word版)数据结构第五章数组和广义表习题及答案

习题五数组和广义表 一、单项选择题 1．常对数组进行的两种基本操作是（） A.建立与删除 B. 索引与修改 C. 查找与修改 D. 查找与索引2．对于C语言的二维数组DataType A[m][n],每个数据元素占K个存储单元，二维数组中任意元素a[i,j] 的存储位置可由( )式确定. A.Loc[i,j]=A[m,n]+[(n+1)*i+j]*k B.Loc[i,j]=loc[0,0]+[(m+n)*i+j]*k C.Loc[i,j]=loc[0,0]+[(n+1)*i+j]*k D.Loc[i,j]=[(n+1)*i+j]*k 3．稀疏矩阵的压缩存储方法是只存储 ( ) A.非零元素 B. 三元祖（i,j, aij） C. aij D. i,j 4. 数组A[0..5,0..6]的每个元素占五个字节，将其按列优先次序存储在起始地址为1000的内存单元中，则元素A[5，5]的地址是( )。 A. 1175 B. 1180 C. 1205 D. 1210 5. A[N，N]是对称矩阵，将下面三角（包括对角线）以行序存储到一维数组T[N（N+1）/2]中，则对任一上三角元素a[i][j]对应T[k]的下标k是（）。 A. i（i-1）/2+j B. j（j-1）/2+i C. i（j-i）/2+1 D. j（i-1）/2+1 6. 用数组r存储静态链表，结点的next域指向后继，工作指针j指向链中结点，使j 沿链移动的操作为( )。 A. j=r[j].next B. j=j+1 C. j=j->next D. j=r[j]-> next 7. 对稀疏矩阵进行压缩存储目的是（）。 A．便于进行矩阵运算 B．便于输入和输出 C．节省存储空间 D．降低运算的时间复杂度 8. 已知广义表LS＝((a,b,c),(d,e,f)),运用head和tail函数取出LS中原子e的运算是( )。 A. head(tail(LS)) B. tail(head(LS)) C. head(tail(head(tail(LS))) D. head(tail(tail(head(LS)))) 9. 广义表（（a,b,c,d））的表头是（），表尾是（）。 A. a B.（） C.（a,b,c,d） D.（b,c,d） 10. 设广义表L=（（a,b,c）），则L的长度和深度分别为（）。 A. 1和1 B. 1和3 C. 1和2 D. 2和3 11. 下面说法不正确的是( )。 A. 广义表的表头总是一个广义表 B. 广义表的表尾总是一个广义表 C. 广义表难以用顺序存储结构 D. 广义表可以是一个多层次的结构 二、填空题 1．通常采用___________存储结构来存放数组。对二维数组可有两种存储方法：一种是以___________为主序的存储方式，另一种是以___________为主序的存储方式。 2. 用一维数组B与列优先存放带状矩阵A中的非零元素A[i,j] (1≤i≤n,i-2≤j≤i+2),B 中的第8个元素是A 中的第_ _行，第_ _列的元素。

第5章 数组和广义表 自测题含答案

第5章 数组和广义表 自测题含答案 一、单选题 1. 假设有二维数组A 6×8，每个元素用相邻的6个字节存储，存储器按字节编址。已知A 的起始存储位置（基地址）为1000，则数组A 的体积（存储量）为 288 B ；末尾元素A 57的第一个字节地址为 1282 ；若按行存储时，元素A 14的第一个字节地址为 (8+4)×6+1000=1072 ；若按列存储时，元素A 47的第一个字节地址为 (6×7＋4)×6＋1000）＝1276 。 2. 〖00年计算机系考研题〗设数组a[1…60, 1…70]的基地址为2048，每个元素占2个存储单元，若以列序为主序顺序存储，则元素a[32,58]的存储地址为 8950 。 答：不考虑0行0列，利用列优先公式： LOC(a ij )=LOC(a c 1， c 2)+[(j-c 2)*( d 1-c 1+1)+i-c 1)]*L 得：LOC(a 32,58)=2048+[(58-1)*(60-1+1)+32-1]]*2＝8950 3. 三元素组表中的每个结点对应于稀疏矩阵的一个非零元素，它包含有三个数据项，分别表示该元素的 行下标 、 列下标 和 元素值 。 4. 求下列广义表操作的结果： （1） GetHead 【((a,b),(c,d))】=== (a, b) ; //头元素不必加括号 （2） GetHead 【GetTail 【((a,b),(c,d))】】=== (c,d) ; （3） GetHead 【GetTail 【GetHead 【((a,b),(c,d))】】】=== b ; （4） GetTail 【GetHead 【GetTail 【((a,b),(c,d))】】】=== （d ） ; 二、单选题（ A ）1. 〖01年计算机系考研题〗假设有60行70列的二维数组a[1…60, 1…70]以列序为主序顺序存储，其基地址为10000，每个元素占2个存储单元，那么第32行第58列的元素a[32,58]的存储地址为 。（无第0行第0列元素） Ａ．16902 Ｂ．16904 Ｃ．14454 Ｄ．答案A, B, C 均不对 答：此题与填空题第8小题相似。（57列×60行＋31行）×2字节＋10000=16902 ( B )2. 设矩阵A 是一个对称矩阵，为了节省存储，将其下三角部分（如下图所示）按行序存放在一维数组B[ 1, n(n-1)/2 ]中，对下三角部分中任一元素a i,j (i ≤j), 在一维数组B 中下标k 的值是： Ａ．i(i-1)/2+j-1 Ｂ．i(i-1)/2+j Ｃ．i(i+1)/2+j-1 Ｄ．i(i+1)/2+j ??????????????=n n n n a a a a a a A ,2 ,1,2 ,21,21 ,1

第五章 数组和广义表

第5章数组和广义表习题 一、选择题 1.设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第一元素，其存储地址为1，每个元素占一个地址空间，则a85的地址为（B）。 i×（i-1）/2+j-1~~~~（i>=j） 8×7÷2+5=33因为a11从1开始所以要加1 A. 13 B. 33 C. 18 D. 40 2. 数组A[0..5,0..6]的每个元素占五个字节，将其按列优先次序存储在起始地址为1000的内存单元中，则元素A[5，5]的地址是( A)。 所求=a+(j*n+j)*l A. 1175 B. 1180 C. 1205 D. 1210 3. 若对n阶对称矩阵A以行序为主序方式将其下三角形的元素(包括主对角线上所有元素)依次存放于一维数组B［1..(n(n+1))/2］中，则在B中确定aij（i

数据库系统l试题库及答案 第5章数组和广义表

第5章 数组和广义表 5.1数组 一、填空题 1. 假设有二维数组A 6×8，每个元素用相邻的6个字节存储，存储器按字节编址。已知A 的起始存储位置 （基地址）为1000，则数组A 的体积（存储量）为 ；末尾元素A 57的第一个字节地址为 。 2. 三元组表中的每个结点对应于稀疏矩阵的一个非零元素，它包含有三个数据项，分别表示该元素 的 、 和 。 3. 设数组a[1…60, 1…70]的基地址为2048，每个元素占2个存储单元，若以列序为主序顺序存储，则 元素a[32,58]的存储地址为 。 4. 设n 行n 列的下三角矩阵A 已压缩到一维数组B[1..n*（n+1）/2]中，若按行为主序存储，则A[i,j] 对应的B 中存储位置为 。 5. 设有一个10阶对称矩阵A 采用压缩存储方式（以行为主序存储：a 11=1），则a 85 的地址为 。 6. 设下三角矩阵A 如果按行序为主序将下三角元素A i j (i ≤j)存储在一个一维数组B[1..n(n+1)/2]中， 对任一个三角矩阵元素A ij ,它在数组B 中的下标为 。 二、选择题 1. （ ）假设有60行70列的二维数组a[1…60, 1…70]以列序为主序顺序存储，其基地址为10000， 每个元素占2个存储单元，那么第32行第58列的元素a[32,58]的存储地址为 。 A ．16902 B ．16904 C ．14454 D ．答案A, B, C 均不对 2. （ ）对特殊矩阵采用压缩存储的目的主要是为了 。 A ．表达变得简单 B ．对矩阵元素的存取变得简单 C ．去掉矩阵中多余元素 D ．减少不必要的存储空间 3. （ ）对于n 阶对称矩阵，如果以行序或列序放入内存中，则需要 个存储单元。 A ．n(n+1)/2 B ．n(n-1)/2 C ． n 2 D ．n 2 /2 4. 有一个100*90的稀疏矩阵，非0元素有10个，设每个整型数占2字节，则用三元组表示该矩阵时， 所需的字节数是 。 A. 60 B. 66 C. 18000 D. 33 5. 对稀疏矩阵进行压缩存储目的是（ ）。 A ．便于进行矩阵运算 B ．便于输入和输出 C ．节省存储空间 D ．降低运算的时间复杂度 6. （ ）设矩阵A 是一个对称矩阵，为了节省存储，将其下三角部分（如下图所示）按行序存放在一 维数组B[1, n(n-1)/2 ]中，对下三角部分中任一元素a i,j (i ≤j), 在一维数组B 中下标k 的值是 。 A ．i(i-1)/2+j-1 B ．i(i-1)/2+j C ．i(i+1)/2+j-1 D ．i(i+1)/2+j 三、判断题： 1．（ ）一个稀疏矩阵Am*n 采用三元组形式表示，若把三元组中有关行下标与列下标的值互换，并把 ?????? ? ???????=n n n n a a a a a a A ,2,1 ,2,21,21,1Λ Λ

第5章 数组和广义表答案

第五章答案 5.2设有三对角矩阵A n×n,将其三条对角线上的元素逐行的存于数组B[1..3n-2]中，使得 B[k]=a ij，求：（1）用i,j表示k的下标变换公式；（2）用k表示i、j的下标变换公式。【解答】（1）k=2(i-1)+j (2) i=[k/3]+1, j=[k/3]+k%3 （[ ]取整，%取余） 5.4在稀疏矩阵的快速转置算法5.2中，将计算position[col]的方法稍加改动，使算法只占用一个辅助向量空间。 【解答】算法（一） FastTransposeTSMatrix(TSMartrix A, TSMatrix *B) {/*把矩阵A转置到B所指向的矩阵中去，矩阵用三元组表表示*/ int col,t,p,q; int position[MAXSIZE]; B->len=A.len; B->n=A.m; B->m=A.n; if(B->len>0) { position[1]=1; for(t=1;t<=A.len;t++) position[A.data[t].col+1]++; /*position[col]存放第col-1列非零元素的个数, 即利用pos[col]来记录第col-1列中非零元素的个数*/ /*求col列中第一个非零元素在B.data[ ]的位置，存放在position[col]中*/ for(col=2;col<=A.n;col++) position[col]=position[col]+position[col-1]; for(p=1;pdata[q].row=A.data[p].col; B->data[q].col=A.data[p].row; B->data[q].e=A.data[p].e; Position[col]++; } } } 算法(二) FastTransposeTSMatrix(TSMartrix A, TSMatrix *B) { int col,t,p,q; int position[MAXSIZE]; B->len=A.len; B->n=A.m; B->m=A.n; if(B->len>0) { for(col=1;col<=A.n;col++) position[col]=0; for(t=1;t<=A.len;t++) position[A.data[t].col]++; /*计算每一列的非零元素的个数*/ /*从最后一列起求每一列中第一个非零元素在B.data[]中的位置，存放在position[col]中*/ for(col=A.n,t=A.len;col>0;col--) { t=t-position[col]; position[col]=t+1; } for(p=1;p

第五章数组和广义表

第五章数组与广义表 一．选择题 1．下面的说法不正确的是____________。 A．数组是一种线性结构B．数组是一种定长的线性表结构 C．除了插入与删除操作外，数组的基本操作还有存取、修改、检索和 排序等 D．数组的基本操作有存取、修改、检索和排序等，没有插入和删除操 作 分析：数组的主要操作是存取、修改、检索和排序。数组没有插入和修改 错误。答案应选择C。 2．一维数组A 采用顺序存储结构，每个元素占用6 个字节，第6 个元素的起始地址为100，则该数组的首地址是 。 A．64 B．28 C．70 D．90 分析：设数组元素的首地址为x，则存在关系x+5*6=100，因此x 为70，答案应选择C。 3．稀疏矩阵采用压缩存储的目的主要是______________ 。 A．表达变得简单B．对矩阵元素的存取变得简单 C．去掉矩阵中的多余元素D．减少不必要的存储空间的开销 分析：答案应选择D。 4．若对n 阶对称矩阵A 以行序为主序方式将其下三角形的元素(包括主对角线上所有元素)依次存放于一维数组B［1..(n(n+1))/2］中，则在B 中确 定aij(i

第五章数组和广义表

第五章数组和广义表 一、单项选择题 1．一维数组A采用顺序存储结构，每个元素占用6个字节，第6个元素的存储地址为100，则该数组的首地址是（）。 A．64 B．28 C．70 D．90 2．稀疏矩阵采用压缩存储的目的主要是（）。 A．表达变得简单B．对矩阵元素的存取变得简单 C．去掉矩阵中的多余元素D．减少不必要的存储空间的开销 3．一个非空广义表的表头（）。 A．不可能是原子B．只能是子表 C．只能是原子D．可以是子表或原子 4．常对数组进行的两种基本操作是（）。 A．建立与删除B．索引与修改 C．查找和修改D．查找与索引 5. 设二维数组A[5][6]按行优先顺序存储在内存中，已知A[0][0] 起始地址为1000，每个数组元素占用5个存储单元，则元素A[4][4]的地址为（）。 A．1140 B．1145 C．1120 D．1125 6．设有一个20阶的对称矩阵A，采用压缩存储的方式，将其下三角部分以行序为主序存储到一维数组B中（数组下标从1开始），则矩阵中元素a9,2在一维数组B中的下标是（）。 A．41 B．32 C．18 D．38 7．稀疏矩阵的压缩存储方式通常有两种，即（）。 A．二元组和三元组B．三元组和散列 C．三元组和十字链表D．散列和十字链表 8．广义表（a，（a，b），d，e，（（I，j），k））的长度和深度分别是（）。

A．5，3 B．5，5 C．6，4 D．6，6 9．广义表（（a），a）的表头是（）。 A．a B．（a）C．（）D．（（a）） 10．二维数组A[20][10]采用行序为主序方式存储，每个数据元素占4个存储单元，且A[10][5]的存储地址是1000，则A[18][9]的存储地址是（）。 A．1208 B．1212 C．1368 D．1336 11．二维数组A中，每个数据元素占4个字节，行下标从0到4，列下标从0到5，按行优先存储时元素A[3][5]的地址域同按列优先存储时元素（）的地址相同。 A．A[2][4] B．A[3][4] C．A[3][5] D．A[4][4] 二、问答题 1、简述广义表和线性表的区别与联系。 2、设广义表L=((),())，试问head(L)、tail(L)、L的长度、深度各为多少？

第五章数组与广义表(作业)

第四章数组与广义表（作业） 一、判断题 1.数组是同类型值的集合。 2.数组是一组相继的内存单元。 3.数组是一种复杂的数据结构，数组元素之间的关系，既不是线 性的，也不是树型的。 4.插入和删除操作是数据结构中最基本的两种操作，所以这两种 操作在数组中也经常使用。 5.数组的存储方式分为顺序和链式两种。 6.使用三元组表表示稀疏矩阵的元素，有时并不能节省存储空间。 7.广义表是由零或多个单元素或子表所组成的有序列，所以广义 表可能为空表。 8.线性表可以看成是广义表的特例，如果广义表中的每个元素都 是单元素，则广义表便成为线性表。 二、选择题 1.一个n*n的对称矩阵，如果以行或列为主序存入内存，则其容 量为（）。 A.n*n B.n*n/2 C.n(n+1)/2 D.(n+1)*(n+1)/2 E.(n-1)*n/2 F.n(n-1) 2.在二维数组A[7][9]中，假定每个数据元素占4个存储单元，A00 的存储位置（基地址）为100，则A56的存储位置为（）。 A.232 B.151 C.204 D.304

3.设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主 存储，a11为第一个元素，其存储地址为1，每个元素占1个地址空间，则a85的地址为（）。 A.13 B.33 C.18 D.40 4.二维数组a的每个元素是由6个字符组成的串，行下标i的范 围从0-8，列下标j的范围是从1-10。 （1）存放a至少需要( ）个字节。 A.90 B.180 C.240 D.270 E.540 （2）A的第8列和第5行共占（）字节。 A.108 B.114 C.54 D.60 E.150 （3）若a按行存放，元素a[8,5]的起始地址与当a按列存放的元素( ）的起始地址一致。 A.a[8,5] B. a[3,10] C.a[5,8] D. a[0,9] 5.已知广义表LS=（a,(b,c,c),e）,运用HEAD和TAIL函数取出LS中 的单元素b的运算是（）。 A.HEAD(HEAD(LS)) B.TAIL(HEAD(LS)) C.HEAD(HEAD(TAIL(LS))) D.HEAD(TAIL(LS)) 6.已知广义表A=((a,b,c),(d,e,f)),从A中取出单元素e的运算是 （）。 A.TAIL(HEAD(A)) B.HEAD(TAIL(A)) C.HEAD(TAIL(TAIL(HEAD(A)))) D.HEAD(TAIL(HEAD(TAIL(A)))) E.HEAD(TAIL(TAIL(A)))

第5章 数组和广义表

1．广义表(((a)))的表头是(((a)))，表尾是( ) 。 2．假设一个10阶的下三角矩阵A按列优先顺序压缩存储在一维数组B中，则B数组的大小应为55。(1+10)*10／2 3．假设三维数组A[10][9][8]按行优先顺序存储，若每个元素占3个存储单元，且首地址为100，则元素A[9][8][7]的存储地址是2257 。 4．对矩阵采用压缩存储是为了节省空间。 5．广义表（a,(a,b),d,e,((i,j),k)）的长度为5。 ？？？1．二维数组A[12][18]采用列优先的存储方法，若每个元素各占3个存储单元，且第1个元素的地址为150，则元素A[9][7]的地址为（ A ） A．429 B．432 C．435 D．438 ？？？2．二维数组A[8][9]按行优先顺序存储，若数组元素A[2][3]的存储地址为1087，A[4][7]的存储地址为1153，则数组元素A[6][7]的存储地址为（A）A．1207 B．1209 C．1211 D．1213 3．对广义表L=（（a,b）,(c,d), (e,f)）执行操作tail(tail(L))的结果是（B）A．(e,f) B．((e,f)) C．(f) D．() 1．已知稀疏矩阵采用带行表的三元组表表示，其形式说明如下： #define MaxRow 100 //稀疏矩阵的最大行数 typedef struct { int i,j,v; //行号、列号、元素值 }TriTupleNode; typedef struct{ TriTupleNode data[MaxSize]; int RowTab[MaxRow+1]; //行表 int m,n,t; //矩阵的行数、列数和非零元个数 }RTriTupleTable; 下列算法f的功能是，以行优先的顺序输入稀疏矩阵的非零元（行号、列号、元素值），建立稀疏矩阵的带行表的三元组表存储结构。请在空缺处填入合适内容，使其成为一个完整的算法。（注：矩阵的行、列下标均从1起计） void f (RTriTupleTable *R)

第5章 数组和广义表

第五章数组和广义表 讲课提要 【主要内容】 1．多维数组的顺序存储结构 2．特殊矩阵的压缩存储 3．广义表的定义及其与线性表的关系 4．广义表的存储结构 5．广义表运算实现中递归的应用 【教学目标】 1．掌握多维数组的顺序存储结构 2．掌握特殊矩阵的压缩存储方法 3．掌握广义表的定义及其与线性表的关系 4．掌握广义表的存储结构 5．了解广义表运算实现中递归的应用 学习指导 1．多维数组的顺序存储结构 对于多维数组，有两种存储方式： 一是以行为主序（或先行后列）的顺序存放，如BASIC、PASCAL、C等程序设计语言中用的是以行为主的顺序分配，即一行分配完了接着分配下一行。 另一种是以列为主序（先列后行）的顺序存放，如FORTRAN语言中，用的是以列为主序的分配顺序，即一列一列地分配。 以行为主序的分配规律是：最右边的下标先变化，即最右下标从小到大，循环一遍后，右边第二个下标再变，…，从右向左，最后是左下标。以列为主序分配的规律是：最左边的下标先变化，即最左下标从小到大，循环一遍后，左边第二个下标再变，…，从左向右，最后是右下标。 不论按何种方式存储，只要确定了数组的首地址以及每个数组元素所占用的单元数，就可以将数组元素的存储地址表示为其下标的线性函数。设有m×n二维数组A mn，以“以行为主序”的分配为例，按照元素的下标确定其地址的计算方法如下。 设数组的基址为LOC(a11)，每个数组元素占据L个地址单元，计算a ij 的物理地址的函数为： LOC(a ij) = LOC(a11) + ( (i-1)*n + j-1 ) * L 同理，对于三维数组A mnp，即m×n×p数组，对于数组元素a ijk其物理地址为：LOC(a ijk)=LOC(a111)+( ( i-1) *n*p+ (j-1)*p +k-1) )*L 注意：在C语言中，数组中每一维的下界定义为0，则： LOC(a ij) = LOC(a00) + ( i*n + j ) * L 【例4-1】二维数组A的每一个元素是由6个字符组成的串，其行下标i=0，1，…，8，列下标j=1，2，…，10。若A以行为主序存储元素，A[8][5]的物理地址与当A按列为主序存

第五章数组和广义表习题_数据结构

习题五数组和广义表一、单项选择题）1．常对数组进行的两种基本操作是（ D.查找与索引C.B.索引与修改建立与删除A. 查找与修改 K 个存储单元，二维数组中DataType A[m][n],2．对于 C 语言的二维数组每个数据元素占.( )a[i,j]的存储位置可由任意元素式确定 A.Loc[i,j]=A[m,n]+[(n+1)*i+j]*k B.Loc[i,j]=loc[0,0]+[(m+n)*i+j]*k C.Loc[i,j]=loc[0,0]+[(n+1)*i+j]*k D.Loc[i,j]=[(n+1)*i+j]*k 3．稀疏矩阵的压缩存储方法是只存储( ) A. 非零元素三元祖（i,j, aij）D. i,jC. aij B. 数组A[0..5,0..6]的每个元素占五个字节，将其按列优先次序存储在起始地址为10004. ( )的地址是A[5 ，5]的内存单元中，则元素。 A. 1175 B. 1180 C. 1205 D. 1210 A[N，N] 是对称矩阵，将下面三角（包括对角线）以行序存储到一维数组T[N （N+1）/2]5. 对应T[k] 的下标k是（中，则对任一上三角元素）。a[i][j] （i-1）/2+j（j-i）/2+1（（j-1）/2+i i-1 ）/2+1D. jB. jA. iC. i j 沿用数组r 存储静态链表，结点的next 域指向后继，工

作指针j 指向链中结点，使6. ( )链移动的操作为。 A. j=r[j].next B. j=j+1D. j=r[j]-> next C. j=j->next 对稀疏矩阵进行压缩存储目的是（）。7. A．便于进行矩阵运算．便于输入和输出B ．节省存储空间C．降低运算的时间复杂度D LS＝((a,b,c),(d,e,f)),函数取出LS 中原子运用head 和tail e 的运算是已知广义表8. 。)( A. head(tail(LS)) B. tail(head(LS)) C. head(tail(head(tail(LS))) D. head(tail(tail(head(LS)))) 广义表（（a,b,c,d），表尾是（））的表头是（）。9. （a,b,c,d（b,c,d）（））D.C.A. aB. L=（（a,b,c）），则L 的长度和深度分别为（设广义表）。10.和 3 1和和和3 2B. 1C. 1A. 1D. 211.下面说法不正确的是( )。 A. 广义表的表头总是一个广义表 B. 广义表的表尾总是一个广义表 C. 广义表难以用顺序存储结构 D.广义表可以是一个多层次的结构二、填空题 存储结构来存放数组___________1．通常采用。对二维数组可有两种存储方法：一种是以

数据结构课后习题答案第五章数组与广义表

第五章数组与广义表 一、假设有二维数组A6*8，每个元素用相邻的6个字节存储，存储器按字节 编址。已知A的起始存储位置（基地址）为1000。计算： 1、数组A的体积（即存储量）； 2、数组A的最后一个元素a57的第一个字节的地址； 3、按行存储时，元素a14的第一个字节的地址； 4、按列存储时，元素a47的第一个字节的地址； 答案： 1、（6*8）*6=288 2、loc(a57)=1000+(5*8+7)*6=1282或=1000+（288-6）=1282 3、loc(a14)=1000+(1*8+4)*6=1072 4、loc(a47)=1000+(7*6+4)*6=1276 二、假设按低下标(行优先)优先存储整数数组A9*3*5*8时第一个元素的字节地址是100，每个整数占四个字节。问下列元素的存储地址是什么？ （1）a0000(2)a1111(3)a3125 (4)a8247 答案：（1）100 （2）loc(a1111)=100+(1*3*5*8+1*5*8+1*8+1)*4=776 (3) loc(a3125)=100+(3*3*5*8+1*5*8+2*8+5)*4=1784 (4) loc(a8247)=100+(8*3*5*8+2*5*8+4*8+7)*4=4416 五、设有一个上三角矩阵（aij）n*n,将其上三角元素逐行存于数组B[m]中，（m 充分大），使得B[k]=aij且k=f1(i)+f2(j)+c。试推导出函数f1,f2和常数C（要求f1和f2中不含常数项）。 答： K=n+(n-1)+(n-2)+…..+(n-(i-1)+1)+j-i =(i-1)(n+(n-i+2))/2+j-i 所以f1(i)=(n+1/2)i-1/2i2 f2(j)=j c=-(n+1) 九、已知A为稀疏矩阵，试从空间和时间角度比较采用两种不同的存储结构（二

第5章 数组和广义表(习题)

第5章数组和广义表 习题 一. 选择题 1、数组A[0..5,0..6]的每个元素占五个字节，将其按列优先次序存储在起始地址为1000的内存单元中，则元素A[5，5]的地址是( )。 A. 1175 B. 1180 C. 1205 D. 1210 2、若对n阶对称矩阵A以行序为主序方式将其下三角形的元素(包括主对角线上所有元素)依次存放于一维数组B［1..(n(n+1))/2］中，则在B中确定a ij（i

《数据结构》习题集：第5章 数组与广义表

第5章数组与广义表 一、选择题 1.在以下讲述中，正确的是（B ）。 A、线性表的线性存储结构优于链表存储结构 B、二维数组是其数据元素为线性表的线性表 C、栈的操作方式是先进先出 D、队列的操作方式是先进后出 2.若采用三元组压缩技术存储稀疏矩阵，只要把每个元素的行下标和列下标互换，就完成了对该矩阵的转 置运算，这种观点（B ）。 A、正确 B、错误 3.二维数组SA 中，每个元素的长度为3 个字节，行下标I 从0 到7，列下标J 从0 到9，从首地址SA 开始 连续存放在存储器内，该数组按列存放时，元素A[4][7]的起始地址为（ B ）。 A、SA+141 B、SA+180 C、SA+222 D、SA+225 4.数组SA 中，每个元素的长度为3 个字节，行下标I 从0 到7，列下标J 从0 到9，从首地址SA 开始连续 存放在存储器内，存放该数组至少需要的字节数是（ C ）。 A、80 B、100 C、240 D、270 5.常对数组进行的两种基本操作是（C ）。 A、建立与删除 B、索引和修改 C、查找和修改 D、查找和索引 6.将一个A[15][15]的下三角矩阵（第一个元素为A[0][0]），按行优先存入一维数组B[120]中，A 中元素A[6][5] 在B 数组中的位置K 为（B ）。 A、19 B、26 C、21 D、15 7.若广义表A 满足Head(A)=Tail(A)，则A 为（B ）。 A、（） B、（（）） C、（（），（）） D、（（），（），（）） 8.广义表（（a）,a）的表头是（C ），表尾是（C ）。 A、a B、b C、(a) D、((a)) 9.广义表（（a,b）,c,d）的表头是（C ），表尾是（D ）。 A、a B、b C、(a,b) D、(c,d) 10.广义表（（a））的表头是（B ），表尾是（C ）。 A、a B、(a) C、() D、((a)) 11.广义表（a,b,c,d）的表头是（A ），表尾是（D ）。 A、a B、(a) C、(a,b) D、(b,c,d) 12.广义表（（a,b,c,d））的表头是（C ），表尾是（B ）。 A、a B、() C、(a,b,c,d) D、((a,b,c,d)) 13.下面结论正确的是（BC ）。 A、一个广义表的表头肯定不是一个广义表 B、一个广义表的表尾肯定是一个广义表 C、广义表L=（（），（A，B））的表头为空表 D、广义表中原子个数即为广义表的长度 14.广义表A=（A,B,(C,D),(E,(F,G))），则head(tail(head(tail(tail(A)))))=( D ) A、(G) B、(D) C、C D、D