第四章 数组与广义表（作业）

一、判断题

1. 数组是同类型值的集合。 2. 数组是一组相继的内存单元。

3. 数组是一种复杂的数据结构，数组元素之间的关系，既不是线性的，也不是树型的。

4. 插入和删除操作是数据结构中最基本的两种操作，所以这两种操作在数组中也经常使用。

5. 数组的存储方式分为顺序和链式两种。

6. 使用三元组表表示稀疏矩阵的元素，有时并不能节省存储空间。 7. 广义表是由零或多个单元素或子表所组成的有序列，所以广义表可能为空表。

8. 线性表可以看成是广义表的特例，如果广义表中的每个元素都是单元素，则广义表便成为线性表。 二、选择题

1. 一个n*n的对称矩阵，如果以行或列为主序存入内存，则其容量为（ ）。

A.n*n B.n*n/2

C.n(n+1)/2

F.n(n-1)

D.(n+1)*(n+1)/2 E.(n-1)*n/2

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)))

7. 设广义表LS=（a,b,LS）, 其长度是（ ），其深度为（ ）。

A.∞

B.3

C.2

D.5

8. 下列广义表为线性表的是（ ）。

A.E(a,(b,c)) B.E(a,E) C.E(a,b)

D.E(a,L())

三、填空题

1. 求出下列广义表操作的结果： HEAD(((p,h,w)))=（

）,

TAIL(((b,k,p,h)))=（ ）， HEAD(((a,b),(c,d)))= （ TAIL(((a,b),(c,d)))= （

）,

）

）, HEAD(TAIL(((a,b),(c,d))))= （

）,

）,

TAIL(HEAD(((a,b),(c,d))))= （

HEAD(TAIL(HEAD(((a,b),(c,d)))))= （

TAIL(HEAD(TAIL(((a,b),(c,d)))))=（ ）

2. 利用广义表的HEAD和TAIL函数将原子banana分别从下列广义表中分离出来：

1) L1=(apple,pear,banana,orange),则分离式=（

） ） ）

2) L2=((apple,pear),(banana,orange)),则分离式=（

3) L3=(((apple),(pear),(banana),(orange))),则分离式=（

4) L4= (apple,(pear),((banana)),(((orange)))),则分离式=（ ） 5) L5=((((apple))),((pear)),(banana),orange),则分离式=（ 6) L6=((((apple),pear),banana),orange),则分离式=（ 7) L7=(apple,(pear,(banana),orange)),则分离式=（

） ） ）