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

习题五 数组和广义表

一、单项选择题

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 中的第_ _行，第_ _列的元素。

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

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

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

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

7．基于三元组的稀疏矩阵转置的处理方法有两种，以下运算按照矩阵A的列序来进行转置，请在___________处用适当的句子用以填充。

Trans_Sparmat(SpMatrixTp a,SpMatrixTp *b)

{ (*b).mu=a.nu;(*b).nu=a.mu;(*b).tu=a.tu; if(a.tu) { q=1;

for(col=1; ___________;col++) for(p=1;p<=a.tu;p++)

if(___________==col)

{(*b).data[q].i=a.data[p].j; (*b).data[q].j=a.data[p].i; (*b).data[q].v=a.data[p].v; ___________; }

}

8. 完善下列程序。下面是一个将广义表逆置的过程。例如原来广义表为（（a,b）,c,（d,e）），经逆置后为：（（e,d）,c,（b,a））。

typedef struct glistnode

{int tag;

struct glistnode *next;

union{char data;

struct{struct glistnode *hp,*tp;}ptr; }val; }*glist,gnode; glist reverse(p) glist p;

{glist q,h,t,s;

if(p==NULL) q=NULL; else

{if(1) { q=(glist)malloc(sizeof(gnode)); q->tag=0;

q->val.data=p->val.data; }

else {(2)

if (3)

{t=reverse(p->val.ptr.tp); s=t;

while(s->val.ptr.tp!=NULL) s=s->val.ptr.tp; s->val.ptr.tp=(glist)malloc(sizeof(gnode));

s=s->val.ptr.tp;s->tag=1;s->val.ptr.tp=NULL; s->val.ptr.hp=h; (4) __ }

else {q=(glist)malloc(sizeof(gnode));q->tag=1; q->val.ptr.tp=NULL; (5) ; }

}

} return(q); }

三、应用题

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

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

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

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

B[k]=aij，求：

（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和Ｔail运算，把原子d分别从下列广义表中分离出来，L1＝(((((a),b),d),e))；L2＝（a,(b,((d)),e)）。

四、算法设计题

1. 给定nxm矩阵A[a..b,c..d],并设A[i,j]≤A[i,j+1](a≤i≤b,c≤j≤d-1)和A[i,j]≤A[i+1,j](a≤i≤b-1,c≤j≤d).设计一算法判定X的值是否在A中,要求时间复杂度为O(m+n)。

2. 设二维数组a[1..m, 1..n] 含有m*n 个整数。

(1) 写出算法：判断a中所有元素是否互不相同?输出相关信息(yes/no)； (2) 试分析算法的时间复杂度。

3. 设A[1..100]是一个记录构成的数组，B[1..100]是一个整数数组，其值介于1至100之间，现要求按B[1..100]的内容调整A中记录的次序，比如当B[1]=ll时，则要求将A[1]的内容调整到A[11]中去。规定可使用的附加空间为O(1)。

4．稀疏矩阵用三元组的表示形式，试写一算法实现两个稀疏矩阵相加，结果仍用三元组表示。

5. 试编写建立广义表存储结构的算法，要求在输入广义表的同时实现判断、建立。设广义表按如下形式输入（a1,a2,a3,?,an） n>=0，其中ai或为单字母表示的原子或为广义表，n=0时为只含空格字符的空表。

第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(Aijk)=LOC(Ac1c2c3)+[(i-c1)V2V3+(j-c2)V3+(k-c3)]*L+1

其中ci,di是各维的下界和上界，Vi=di-ci+1是各维元素个数，L是一个元素所占的存储单元数。

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

本文来源：https://www.bwwdw.com/article/z12h.html