搜索
习题五数组和广义表一、单项选择题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]*k3．稀疏矩阵的压缩存储方法是只存储()A.非零元素B.三元祖（i,j,aij）C.aijD.i,j4.数组A[0..5,0..6]的每个元素占五个字节，将其按列优先次序存储在起始地址为1000的内存单元中，则元素A[5，5]的地址是()。A.1175B.1180C.1205D.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+iC.i（j-i）/2+1D.j（i-1）/2+16.用数组r存储静态链表，结点的next域指向后继，工作指针j指向链中结点，使j沿链移动的操作为()。A.j=r[j].nextB.j=j+1C.j=j-nextD.j=r[j]-next7.对稀疏矩阵进行压缩存储目的是（）。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.广义表的表头总是一个广义表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(SpMatrixTpa,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））。typedefstructglistnode{inttag;structglistnode*next;union{chardata;struct{structglistnode*hp,*tp;}ptr;}val;}*glist,gnode;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;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．C2．C3．A4．A5．B6．A7．C8．C9．C10．C11．A二、填空题1．顺序、列序、行序2.第1行第3列3．i(i-1)/2+j(1=i,j=n)4.非零元很少(tm*n)且分布没有规律5．（1）原子（单元素）是结构上不可再分的，可以是一个数或一个结构；而表带结构，本质就是广义表，因作为广义表的元素故称为子表。（2）大写字母（3）小写字母（4）表中元素的个数（5）表展开后所含括号的层数6．（1）（）（2）（（））（3）2（4）27．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和该元素在向量中的下标有一定规律，可以用简单公式表示，仍具有随机存取功能。而稀疏矩阵是指非零元素和矩阵容量相比很小（tm*n），且分布没有规律。用十字链表作存储结构自然失去了随机存取的功能。即使用三元组表的顺序存储结构，存取下标为i和j的元素时，要扫描三元组表，下标不同的元素，存取时间也不同，最好情况下存取时间为O(1)，最差情况下是O(n)，因此也失去了随机存取的功能。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/35．第一种存储结构第二种存储结构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））））））四、算法设计题1.．[题目分析]矩阵中元素按行和按列都已排序，要求查找时间复杂度为O（m+n），因此不能采用常规的二层循环的查找。可以先从右上角（i=a,j=d）元素与x比较，只有