1、完整word版第五章数组和广义表习题数据结构习题五 数组和广义表一、单项选择题1常对数组进行的两种基本操作是（ ）A.建立与删除 B. 索引与修改 C. 查找与修改 D. 查找与索引2对于C语言的二维数组DataType Amn,每个数据元素占K个存储单元，二维数组中任意元素ai,j 的存储位置可由( )式确定.A.Loci,j=Am,n+(n+1)*i+j*kB.Loci,j=loc0,0+(m+n)*i+j*kC.Loci,j=loc0,0+(n+1)*i+j*kD.Loci,j=(n+1)*i+j*k3稀疏矩阵的压缩存储方法是只存储 ( )A.非零元素 B. 三元祖（i,j, aij）
2、C. aij D. i,j4. 数组A0.5,0.6的每个元素占五个字节，将其按列优先次序存储在起始地址为1000的内存单元中，则元素A5，5的地址是( )。A. 1175 B. 1180 C. 1205 D. 12105. AN，N是对称矩阵，将下面三角（包括对角线）以行序存储到一维数组TN（N+1）/2中，则对任一上三角元素aij对应Tk的下标k是（ ）。A. i（i-1）/2+j B. j（j-1）/2+i C. i（j-i）/2+1 D. j（i-1）/2+16. 用数组r存储静态链表，结点的next域指向后继，工作指针j指向链中结点，使j 沿链移动的操作为( )。 A. j=rj.n
3、ext B. j=j+1 C. j=j-next D. j=rj- 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. a B.（） C.（a,b,c,d） D.（b,c,d）
4、10. 设广义表L=（a,b,c），则L的长度和深度分别为（ ）。 A. 1和1 B. 1和3 C. 1和2 D. 2和311. 下面说法不正确的是( )。 A. 广义表的表头总是一个广义表 B. 广义表的表尾总是一个广义表C. 广义表难以用顺序存储结构 D. 广义表可以是一个多层次的结构二、填空题1通常采用_存储结构来存放数组 。对二维数组可有两种存储方法：一种是以_为主序的存储方式，另一种是以_为主序的存储方式。2. 用一维数组B与列优先存放带状矩阵A中的非零元素Ai,j (1in,i-2ji+2),B中的第8个元素是A 中的第_ _行，第_ _列的元素。3设n行n列的下三角矩阵A已压缩到
5、一维数组B1.n*（n+1）/2中，若按行为主序存储，则Ai,j对应的B中存储位置为_。4. 所谓稀疏矩阵指的是_ 。5. 广义表简称表，是由零个或多个原子或子表组成的有限序列，原子与表的差别仅在于_ 。为了区分原子和表，一般用 _表示表，用 _表示原子。一个表的长度是指 _，而表的深度是指_ _6设广义表L=(),(), 则head(L)是 ；tail(L)是 ；L的长度是 ；深度是 _。7基于三元组的稀疏矩阵转置的处理方法有两种，以下运算按照矩阵A的列序来进行转置，请在_处用适当的句子用以填充。Trans_Sparmat(SpMatrixTp a,SpMatrixTp *b) (*b).m
6、u=a.nu;(*b).nu=a.mu;(*b).tu=a.tu; if(a.tu) q=1; for(col=1; _;col+) for(p=1;ptag=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) _ e
7、lse q=(glist)malloc(sizeof(gnode);q-tag=1; q-val.ptr.tp=NULL; (5) ; return(q);三、应用题1. 数组A1.8，-2.6，0.6以行为主序存储，设第一个元素的首地址是78，每个元素的长度为4，试求元素A4,2,3的存储首地址。2. 特殊矩阵和稀疏矩阵哪一种压缩存储后失去随机存取的功能？为什么？3. 数组，广义表与线性表之间有什么样的关系？ 4. 设有三对角矩阵(aij)n*n，将其三条对角线上的元素逐行地存于数组B(1:3n-2)中，使得Bk=aij，求：（1）用i,j表示k的下标变换公式；（2）用k表示i,j的下标变化
8、公式。5画出下面广义表的两种存储结构图示： (a), b), ( ), d), (e, f)6求下列广义表运算的结果：（1） HEAD(a,b),(c,d); （2） TAIL(a,b),(c,d); （3） TAILHEAD(a,b),(c,d); （4） HEADTAILHEAD(a,b),(c,d); （5） TAILHEADTAIL(a,b),(c,d); 7. 利用广义表的Head和ail运算，把原子d分别从下列广义表中分离出来，L1(a),b),d),e)；L2（a,(b,(d),e)）。 四、算法设计题1. 给定nxm矩阵Aa.b,c.d,并设Ai,jAi,j+1(aib,cjd
9、-1)和Ai,jAi+1,j(aib-1,cjd).设计一算法判定X的值是否在A中,要求时间复杂度为O(m+n)。2. 设二维数组a1.m, 1.n 含有m*n 个整数。(1) 写出算法：判断a中所有元素是否互不相同?输出相关信息(yes/no)；(2) 试分析算法的时间复杂度。3. 设A1.100是一个记录构成的数组，B1.100是一个整数数组，其值介于1至100之间，现要求按B1.100的内容调整A中记录的次序，比如当B1=ll时，则要求将A1的内容调整到A11中去。规定可使用的附加空间为O(1)。4稀疏矩阵用三元组的表示形式，试写一算法实现两个稀疏矩阵相加，结果仍用三元组表示。5. 试编
10、写建立广义表存储结构的算法，要求在输入广义表的同时实现判断、建立。设广义表按如下形式输入（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列3i(i-1)/2+j (1=i,j=n)4. 非零元很少(tm*n)且分布没有规律5 （1） 原子（单元素）是结构上不可再分的，可以是一个数或一个结构；而表带结构，本质就是广义表，因作为广义表的元素故称为子表。 （2）大写字母 （3）小写字母 （4）表
11、中元素的个数（5）表展开后所含括号的层数6（1）（） （2）（） （3）2 （4）27 coltag=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是一个元素所占的存
12、储单元数。2. 特殊矩阵指值相同的元素或零元素在矩阵中的分布有一定规律，因此可以对非零元素分配单元（对值相同元素只分配一个单元），将非零元素存储在向量中，元素的下标i和j和该元素在向量中的下标有一定规律，可以用简单公式表示，仍具有随机存取功能。而稀疏矩阵是指非零元素和矩阵容量相比很小（tm*n），且分布没有规律。用十字链表作存储结构自然失去了随机存取的功能。即使用三元组表的顺序存储结构，存取下标为i和j的元素时，要扫描三元组表，下标不同的元素，存取时间也不同，最好情况下存取时间为O(1)，最差情况下是O(n)，因此也失去了随机存取的功能。3. 数组是具有相同性质的数据元素的集合，同时每个元素又
13、有唯一下标限定，可以说数组是值和下标偶对的有限集合。n维数组中的每个元素，处于n个关系之中，每个关系都是线性的，且n维数组可以看作其元素是n-1维数组的一个线性表。广义表中的元素，可以是原子，也可以是子表，即广义表是原子或子表的有限序列，满足线性结构的特性：在非空线性结构中，只有一个称为“第一个”的元素，只有一个成为“最后一个”的元素，第一元素有后继而没有前驱，最后一个元素有前驱而没有后继，其余每个元素有唯一前驱和唯一后继。从这个意义上说，广义表属于线性结构。 4. 三对角矩阵第一行和最后一行各有两个非零元素，其余每行均有三个非零元素，所以共有3n-2个元素。（1）主对角线左下对角线上的元素下
14、标间有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|x， 这情况下向j 小的方向继续查找；二是Ai,jx，下步应向i大的方向查找；三是Ai,j=x，查找成功。否则，若下标已超出范围，则查找失败。void search(datatype A , int a,b,c,d, datatype x) /n*m矩阵A,行下标从a到b,列下标从c到d,本算法查找x是
15、否在矩阵A中. i=a; j=d; flag=0; /flag是成功查到x的标志 while(i=c) if(Aij=x) flag=1;break; else if (Aijx) j-; else i+; if(flag) printf(“A%d%d=%d”,i,j,x); /假定x为整型. else printf(“矩阵A中无%d 元素”，x)； 算法search结束。算法讨论算法中查找x的路线从右上角开始，向下（当xAi,j）或向左（当xAi,j）。向下最多是m，向左最多是n。最佳情况是在右上角比较一次成功，最差是在左下角（Ab,c），比较m+n次，故算法最差时间复杂度是O(m+n)。2
16、.题目分析判断二维数组中元素是否互不相同，只有逐个比较,找到一对相等的元素，就可结论为不是互不相同。如何达到每个元素同其它元素比较一次且只一次？在当前行，每个元素要同本行后面的元素比较一次（下面第一个循环控制变量p的for循环），然后同第i+1行及以后各行元素比较一次，这就是循环控制变量k和p的二层for循环。int JudgEqual(ing amn,int m,n) /判断二维数组中所有元素是否互不相同，如是，返回1；否则，返回0。for(i=0;im;i+) for(j=0;jn-1;j+) for(p=j+1;pn;p+) /和同行其它元素比较 if(aij=aip) printf(“
17、no”); return(0); /只要有一个相同的，就结论不是互不相同 for(k=i+1;km;k+) /和第i+1行及以后元素比较 for(p=0;pn;p+) if(aij=akp) printf(“no”); return(0); / for(j=0;jn-1;j+)printf(yes”); return(1); /元素互不相同/算法JudgEqual结束（2）二维数组中的每一个元素同其它元素都比较一次，数组中共m*n个元素，第1个元素同其它m*n-1个元素比较，第2个元素同其它m*n-2 个元素比较，第m*n-1个元素同最后一个元素(m*n)比较一次,所以在元素互不相等时总的比较
18、次数为 (m*n-1)+(m*n-2)+2+1=（m*n）(m*n-1)/2。在有相同元素时,可能第一次比较就相同,也可能最后一次比较时相同,设在(m*n-1)个位置上均可能相同,这时的平均比较次数约为（m*n）(m*n-1)/4，总的时间复杂度是O(n4)。3. 题目分析题目要求按B数组内容调整A数组中记录的次序，可以从i=1开始，检查是否Bi=i。如是，则Ai恰为正确位置，不需再调；否则，Bi=ki，则将Ai和Ak对调，Bi和Bk对调，直到Bi=i为止。void CountSort (rectype A,int B)/A是100个记录的数组，B是整型数组，本算法利用数组B对A进行计数排序i
19、nt i,j,n=100;i=1;while(in) if(Bi!=i) /若Bi=i则Ai正好在自己的位置上，则不需要调整 j=i; while (Bj!=i) k=Bj; Bj=Bk; Bk=k; / Bj和Bk交换 r0=Aj;Aj=Ak; Ak=r0; /r0是数组A的元素类型,Aj和Ak交换i+; /完成了一个小循环，第i个已经安排好/算法结束4解答：本题首先判断三元组A，B表示的矩阵是否行列相同，若相同才能进行矩阵的加法运算。若三元组表示的矩阵能进行相加运算，其思路如下： 若a,b表的指针均没有到表尾，重复下列步骤：（1） 若a表元素的i 域值小于b表元素的i域值，将a表当前元素插
20、入到c表表尾， a表指针后移。（2） 若a表元素的i 域值大于b表元素的i域值，将b表当前元素插入到c表表尾， b表指针后移。（3） 若a表元素的i域值等于b表元素的i域值，又分以下几种情况讨论：若a表元素的j域值小于b表元素的j域值，将a表当前元素插入到c表表尾，a表指针后移。若a表元素的j域值大于b表元素的j域值，将b表当前元素插入到c表表尾，b表指针后移。若a表元素的j域值等于b表元素的j域值，若a,b表当前元素的v域值和非零，则在c表表尾播入元素的Ij域值等于a表当前元素的Ij域 的值，域v的值等于a,b表的域值的和，将a,b表当前指针后移。(4) 若a表的指针没到表尾，b表的指针到表
21、尾，将a表剩余元素依次插入到c表表尾，否则，将b表剩余元素依次插入到c表表尾.SpMaterixTp trsxsum(SpMaterixTp a, SpMaterixTp b , SpMaterixTp c)if ( (a .mu=b. mu)&(a.nu=b.mu) /*a，b为同行同列矩阵*/ c.mu=a.mu ;c.nu=a.nu; I=1; j=1; p=0;if (a.tu&b.tu) /*a，b为非空矩阵*/ cola=a.dataI.i; rowa = a.dataI .j; /*取三元组a的元素的行、列下标*/ colb= b.dataj.i; rowb =b.dataj .
22、j; /*取三元组b的元素的行、列下标*/ while (I=a.tu)&(j=b.tu) switch cola colb: /*在c中，插入三元组b的元素*/ P+;c.datap .i=b.data j .i; c.data p.j= b.data j.j; c.data p .v= b.dataj.v; j+; break; /*b元素后移*/ Cola =colb : P+; /*三元组 a，b的元素I域相等*/ If (rowarowb) /*在c中插入三元组b的元素*/ c.datap.i=b.dataj.i; c.datap.j=b.dataj.j; c.datap.v= b.
23、dataj.v; j+; else if (a.dataI.v +b.dataj.v) /*a中的元素和b中的元素I，j的域都相等且v域的和非零*/ c.data p.i =a.dataI.i ;/*在c中元素*/ c.datap.j=a.dataj.j; c.datap.v=a.dataI.v+b.dataj.v; I+; j+; else p-;I+;j+; /*a中元素和b中元素的I，j域都相等且v 域的和为零*/ break; /*swith结束*/if (Itag=1; /子表 gh-element.slink=creat(); /递归构造子表else gh-tag=0;gh-element.data=ch; /原子结点
