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

第五章数组和广义表习题数据结构习题五数组和广义表一、单项选择题1．常对数组进行的两种基本操作是（A.建立与删除B.索引与更正

C.

）

查找与更正

D.

查找与索引2．对于C语言的二维数组DataTypeA[m][n],每个数据元素占K个储藏单元，二维数组中任意元素a[i,j]的储藏地址可由( )式确立.A.Loc[i,j]=A[m,n]+[(n+1)_i+j]_kB.Loc[i,j]=loc[0,0]+[(m+n)_i+j]_kC.Loc[i,j]=loc[0,0]+[(n+1)_i+j]_kD.Loc[i,j]=[(n+1)_i+j]_k．稀罕矩阵的压缩储藏方法是只储藏( )A.非零元素B.三元祖（i,j,aij）C.aijD.i,j数组A[0..5,0..6]的每个元素占五个字节，将其按列优先次序储藏在初步地址为1000的内存单元中，则元素

A[5，5]的地址是

(

)

。A.1175

B.1180

C.1205

D.12105.A[N

，N]是对称矩阵，将下边三角（包含对角线）以行序储藏到一维数组T[N（N+1）/2]中，则对任一上三角元素

a[i][j]

对应

T[k]

的下标

k是（

）。A.i（i-1

）/2+jB.j（j-1）/2+i

C.i

（j-i）/2+1D.j

（i-1）/2+16.

用数组r储藏静态链表，结点的

ne_t

域指向后继，工作指针

j指向链中结点，使

j沿链搬动的操作为(

)

。A.j=r[j].ne_t

B.j=j+1

C.j=j->ne_t

D.j=r[j]->ne_t7.

对稀罕矩阵进行压缩储藏目的是（

）。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.aB.（）C.（a,b,c,d）D.（b,c,d）10.设广义表L=（（a,b,c）），则L的长度和深度分别为（）。A.1和1B.1和3C.1和2D.2和311.下边说法不正确的选项是( )。A.广义表的表头总是一个广义表C.广义表难以用次序储藏结构

B.广义表的表尾总是一个广义表D.广义表可以是一个多层次的结构二、填空题1．平时采纳___________储藏结构来存放数组。对二维数组可有两种储藏方法：一种是以___________为主序的储藏方式，另一种是以___________为主序的储藏方式。用一维数组B与列优先存放带状矩阵A中的非零元素A[i,j](1≤i≤n,i-2≤j≤i+2),B中的第8个元素是A中的第__列的元素。

_

行，第_．设n行n列的下三角矩阵A已压缩到一维数组B[1..n_（n+1）/2]中，若按行为主序储藏，则A[i,j]对应的B中储藏地址为_______。4.所谓稀罕矩阵指的是_。广义表简称表，是由零个或多个原子或子表组成的有限序列，原子与表的差别仅在于____。为了区分原子和表，一般用____表，用_____表示原子。一个表的长度是指__，而表的深度是指

表示____6．设广义表

L=(( ),( )),

则head(L)

是

；tail(L)是；L的长度是；深度是__。7．基于三元组的稀罕矩阵转置的办理方法有两种，以下运算依据矩阵

A的列序来进行转置，请在

___________处用适合的句子用以填补。Trans_Sparmat(SpMatri_Tpa,SpMatri_Tp_b){(_b).mu=a.nu;(_b).nu=a.mu;(_b).tu=a.tu;{q=1;

if(a.tu)for(col=1;___________;col++)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;___________;}}

for(p=1;p完美以下程序。下边是一个将广义表逆置的过程。比方本来广义表为（（a,b）,c,（d,e）），经逆置后为：（（e,d）,c,（b,a））。typedefstructglistnode{inttag;structglistnode_ne_t;union{chardata;struct{structglistnode_hp,_tp;}ptr;}val;glistreverse(p)glistp;{glistq,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;

}_glist,gnode;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]的储藏首地址。特别矩阵和稀罕矩阵哪一种压缩储藏后失掉随机存取的功能？为何？数组，广义表与线性表之间有什么样的关系？设有三对角矩阵(aij)n_n，将其三条对角线上的元素逐行地存于数组B(1:3n-2)中，使得B[k]=aij，求：（1）用i,j表示k的下标变换公式；（2）用k表示i,j的下标变化公式。5．画出下边广义表的两种储藏结构图示：((((a),b)),((( ),d),(e,f)))．求以下广义表运算的结果：（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))]]];利用广义表的Head和Ｔail运算，把原子d分别从以下广义表中分别出来，L1＝(((((a),b),d),e))；L2＝（a,(b,((d)),e)）。四、算法设计题1.给定n_m矩阵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).设计一算法判断_的值可否在A中,要求时间复杂度为O(m+n)。2.设二维数组a[1..m,1..n]含有m_n个整数。写出算法：判断a中全部元素可否互不同样?输出相关信息(yes/no)；(2)试解析算法的时间复杂度。设A[1..100]是一个记录组成的数组，B[1..100]是一个整数数组，其值介于1至100之间，现要求按B[1..100]的内容调整A中记录的次序，比方当B[1]=ll时，则要求将A[1]的内容调整到A[11]中去。规定可使用的附带空间为O(1)。．稀罕矩阵用三元组的表示形式，试写一算法实现两个稀罕矩阵相加，结果仍用三元组表示。试编写建立广义表储藏结构的算法，要求在输入广义表的同时实现判断、建立。设广义表按以下形式输入（a1,a2,a3,?,an）n>=0，此中ai或为单字母表示的原子或为广义表，n=0时为只含空格字符的空表。第5章数组和广义表一、单项选择题1．C2．C3．A4．A5．B6．A7．C8．C9．C10．C11．A二、填空题1．次序、列序、行序2.第1行第3列3．i(i-1)/2+j(14.非零元极少(t5．（1）原子（单元素）是结构上不行再分的，可以是一个数或一个结构；而表带结构，实质就是广义表，因作为广义表的元素故称为子表。（2）大写字母（3）小写字母（4）表中元素的个数（5）表睁开后所含括号的层数

6．（1）（）（2）（（））

（3）2

（4）27．

col8.

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