文档库

最新最全的文档下载
当前位置:文档库 > 第五章数组和广义表习题_数据结构

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

习题五数组和广义表

一、单项选择题

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

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.通常采用___________存储结构来存放数组。对二维数组可有两种存储方法:一种是以___________为主序的存储方式,另一种是以___________为主序的存储方式。

3.设n行n列的下三角矩阵A已压缩到一维数组B[1..n*(n+1)/2]中,若按行为主序存储,则A[i,j]对应的B中存储位置为_______。

4. 所谓稀疏矩阵指的是_ 。

5. 广义表简称表,是由零个或多个原子或子表组成的有限序列,原子与表的差别仅在于____ 。为了区分原子和表,一般用 ____表示表,用 _____表示原子。一个表的长度是指 __,而表的深度是指__ __

6.设广义表L=((),()), 则head(L)是;tail(L)是;L的长度是;深度是 __。

三、应用题

1. 数组A[1..8,-

2..6,0..6]以行为主序存储,设第一个元素的首地址是78,每个元素的长度为4,试求元素A[4,2,3]的存储首地址。

2. 特殊矩阵和稀疏矩阵哪一种压缩存储后失去随机存取的功能?为什么?

3. 数组,广义表与线性表之间有什么样的关系?

4. 设有三对角矩阵(a ij)n*n,将其三条对角线上的元素逐行地存于数组B(1:3n-2)中,使得

B[k]=a ij,求:

(1)用i,j表示k的下标变换公式;

(2)用k表示i,j的下标变化公式。

5.画出下面广义表的头尾链表存储结构图示:

((((a), b)), ((( ), d), (e, f)))

6.求下列广义表运算的结果:

(1)HEAD[((a,b),(c,d))];

(2)TAIL[((a,b),(c,d))];

(3)TAIL[HEAD[((a,b),(c,d))]];

(4)HEAD[TAIL[HEAD[((a,b),(c,d))]]];

(5)TAIL[HEAD[TAIL[((a,b),(c,d))]]];

7. 利用广义表的Head和Tail运算,把原子d分别从下列广义表中分离出来,L1=(((((a),b),d),e));L2=(a,(b,((d)),e))。

第5章数组和广义表

一、单项选择题

1. C

2. C

3. A

4. A

5. B

6. A

7. C

8. C

9. C

10. C

11. A

二、填空题

1.顺序、列序、行序

2. 第1行第3列

3.i(i-1)/2+j (1<=i,j<=n)

4. 非零元很少(t<

5.(1)原子(单元素)是结构上不可再分的,可以是一个数或一个结构;而表带结构,本质就是广义表,因作为广义表的元素故称为子表。

(2)大写字母(3)小写字母(4)表中元素的个数(5)表展开后所含括号的层数6.(1)()(2)(())(3)2 (4)2

7. col<=a.nu, a.data[p].j, q++

8. (1)(p->tag==0) //处理原子

(2)h=reverse(p->val.ptr.hp) //处理表头

(3)(p->val.ptr.tp) //产生表尾的逆置广义表

(4)s->val.ptr.tp=t; //连接

(5)q->val.ptr.hp=h //头结点指向广义表

三、应用题

1. 958 三维数组以行为主序存储,其元素地址公式为:

LOC(A ijk)=LOC(A c1c2c3)+[(i-c1)V2V3+(j-c2)V3+(k-c3)]*L+1

其中c i,d i是各维的下界和上界,V i=d i-c i+1是各维元素个数,L是一个元素所占的存储单元数。

2. 特殊矩阵指值相同的元素或零元素在矩阵中的分布有一定规律,因此可以对非零元素分配单元(对值相同元素只分配一个单元),将非零元素存储在向量中,元素的下标i和j和该元素在向量中的下标有一定规律,可以用简单公式表示,仍具有随机存取功能。而稀疏矩阵是指非零元素和矩阵容量相比很小(t<

3. 数组是具有相同性质的数据元素的集合,同时每个元素又有唯一下标限定,可以说数组

是值和下标偶对的有限集合。n维数组中的每个元素,处于n个关系之中,每个关系都是线性的,且n维数组可以看作其元素是n-1维数组的一个线性表。广义表中的元素,可以是原子,也可以是子表,即广义表是原子或子表的有限序列,满足线性结构的特性:在非空线性结构中,只有一个称为“第一个”的元素,只有一个成为“最后一个”的元素,第一元素有后继而没有前驱,最后一个元素有前驱而没有后继,其余每个元素有唯一前驱和唯一后继。从这个意义上说,广义表属于线性结构。

4. 三对角矩阵第一行和最后一行各有两个非零元素,其余每行均有三个非零元素,所以共有3n-2个元素。

(1)主对角线左下对角线上的元素下标间有i=j+1关系,k与i和j的关系为k=3(i-1);主对角线上元素下标间有关系i=j,k与i和j的关系为k=3(i-1)+1; 主对角线右上那条对角线上元素下标间有关系i=j-1,k与i和j的关系为k=3(i-1)+2。综合以上三等式,有k=2(i-1)+j (1<=i,j<=n, |i-j|<=1)

(2)i=k/3+1;(1≤k≤3n-2) // k/3取小于k/3的最大整数。下同

j=k-2(i-1)=k-2(k/3)=k%3+k/3

5.

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

第一种存储结构

6.

(1)HEAD[((a,b),(c,d))]; (a,b)

(2)TAIL[((a,b),(c,d))]; ((c,d))

(3)TAIL[HEAD[((a,b),(c,d))]]; (b)

(4)HEAD[TAIL[HEAD[((a,b),(c,d))]]]; b

(5)TAIL[HEAD[TAIL[((a,b),(c,d))]]]; (d)

7. Head(Tail(Head(Head(L1))))

Head(Head(Head(Tail(Head(Tail(L2))))))