数据结构单元练习6

1单元练习6一．判断题（下列各题，正确的请在前面的括号内打√；错误的打╳）（√）（1）n维的多维数组可以视为n-1维数组元素组成的线性结构。（√）（2）稀疏矩阵中非零元素的个数远小于矩阵元素的总数。（ㄨ）（3）上三角矩阵主对角线以上（不包括主对角线中的元素），均为常数C。（√）（4）数组元素可以由若干个数据项组成。（√）（5）数组的三元组表存储是对稀疏矩阵的压缩存储。（ㄨ）（6）任何矩阵都可以进行压缩存储。（ㄨ）（7）广义表是线性表的推广，所以广义表也是线性表。（ㄨ）（8）广义表LS=（a0,a1,……an-1），则an-1是其表尾。（√）（9）广义表((a,b),a,b)的表头和表尾是相等的。（√）（10）一个广义表的表尾总是一个广义表。二．填空题（1）多维数组的顺序存储方式有按行优先顺序存储和按列优先顺序存储两种。（2）在多维数组中，数据元素的存放地址可以直接通过地址计算公式算出，所以多维数组是一种随机存取结构。（3）在n维数组中的每一个元素最多可以有n个直接前驱。（4）输出二维数组A[n][m]中所有元素值的时间复杂度为O(n*m)。（5）数组元素a[0..2][0..3]的实际地址上2000，元素长度是4，则LOC[1,2]=2024。LOC[1,2]=2000+（1*4+2）*4（6）稀疏矩阵的三元组有3列。（7）稀疏矩阵的三元组中第1列存储的是数组中非零元素所在的行数。（8）n阶对称矩阵，如果只存储下三角元素，只需要n（n-1）/2个存储单元。（9）稀疏矩阵A如下图所示，其非零元素存于三元组表中，三元组（4，1，5）按列优先顺序存储在三元组表的第4项。8000000110000000600030070050000000090稀疏矩阵AA=2（10）稀疏疏矩阵的压缩存储方法通常有三元组表和十字链表两种。（11）任何一个非空广义表的表尾必定是广义表（或子表）。（12）tail(head((a,b),(c,d))=b。（13）设广义表((a,b,c))，则将c分离出来的运算是head(tail(tail(head(L))))。（14）广义表((a,b),c,d)，表尾是（c,d）。（15）n阶下三角矩阵，因为对角线的上方是同一个常数，需要n（n-1）/2+1个存储单元。（16）稀疏矩阵中有n个非零元素，则三元组有n行。（17）广义表LS=（a,(b),((c,(d)))）的长度是3。（18）广义表LS=（a,(b),((c,(d)))）的深度是4。（19）广义表L=（（），L），则L的深度是∞。（20）广义表LS=（a,(b),((c,(d)))）的表尾是((b),((c,(d))))。三．选择题（1）在一个m维数组中，（D）恰好有m个直接前驱和m个直接界后继。A.开始结点B．总终端结点C.边界结点D．内部结点（2）对下述矩阵进行压缩存储后，失去随机存取功能是（D）。A．对称矩阵B．三角矩阵C．三对角矩阵D．稀疏矩阵（3）在按行优先顺序存储的三元组表中，下述陈述错误的是（D）。A．同一行的非零元，是按列号递增次序存储的B．同一列的非零元，是按行号递增次序存储的C．三元组表中三元组行号递增的D．三元组表中三元组列号递增的（4）对稀疏矩阵进行压缩存储是为了（B）。A．降低运算时间B．节约存储空间C．便于矩阵运算D．便于输入和输出（5）若数组A[0..m][0..n]按列优先顺序存储，则aij的地址为（A）。A．LOC(a00)+[j*m+i]B．LOC(a00)+[j*n+i]C．LOC(a00)+[(j-1)*n+i-1]D．LOC(a00)+[(j-1)*m+i-1]（6）下列矩阵是一个（B）3A．对称矩阵B．三角矩阵C．稀疏矩阵D．带状矩阵（7）在稀疏矩阵的三元组表示法中，每个三元组表示（D）。A．矩阵中非零元素的值B．矩阵中数据元素的行号和列号C．矩阵中数据元素的行号、列号和值D．矩阵中非零数据元素的行号、列号和值（8）已知二维数组A[6][10]，每个数组元素占4个存储单元，若按行优先顺序存放数组元素a[3][5]的存储地址是1000，则a[0][0]的存储地址是（B）。A．872B．860C．868D．8641000=B+(3*10+5)*4B=1000-(3*10+5)*4=1000-140=860（9）广义表是线性表的推广，它们之间的区别在于（A）。A．能否使用子表B．能否使用原子项C．是否能为空D．表的长度（10）下列广义表属于线性表的是（B）。A．E=(a,E)B．E=(a,b,c)C．E=(a,(b,c))D．E=(a,L)；L=()（11）广义表((a,b),c,d)的表尾是(D)。A．aB．dC．(a,b)D．(c,d)（12）广义表A=((x,(a,b)),(x,(a,b),y)),则运算head(head(tail(A)))为（A）。A．xB．（a，b）C．(x,(a,b))D．A（13）tail(head((a,b),c,(c,d)))的结果是（B）。A．bB．（b）C．(a,b)D．(d)（14）若广义表满足head（L）=tail（L），则L的形式是（B）A．空表B．若L=(a1,…,an),则a1=(a2,…an)C．若L=(a1,…,an),则a1=a2=…=an)D．((a1),(a1))（15）数组是一个（B）线性表结构。A．非B．推广了的C．加了限制的D．不加限制的（16）数组A[0:1,0:1,0:1]共有（D）元素。A．4B．5C．6D．8（17）广义表((a,b),c,d)的表头是(C)。A．aB．dC．(a,b)D．(c,d)4（18）广义表A=(a),则表尾为(C)。A．aB．(())C．空表D．(a)（19）以下（C）是稀疏矩阵的压缩存储方法。A．一维数组B．二维数组C．三元组表D．广义表（20）设广义表D=(a,b,c,D),其深度为（D）。A．2B．3C．4D．∞四．算法阅读题1．已知A[]是一个下三角矩阵，下述算法的功能是什么？intf1(intA[],intn){//设B[0..(n+1)n/2-1]存放下三角元素inti,k,s=0;k=0;s=A[0];for(i=0;in-1;i++){k=k+i+2;s=s+A[k];}returns;}算法功能：求矩阵主对角线上元素之和。分析：注意k的变化依次为：0，2，5，9，14，正好是aii在A中的存储位置。在循环中k每次增加i+2。第i行主对角线上的元素aii，其在A中的位置为:i(i+1)/2+i；(1)第i+1行主对角线上的元素ai+1i+1，其在A中的位置为:(i+1)(i+2)/2+(i+1),(2)(2)-(1)得i-2。2．在按行优先顺序存储的三元组表中，求某列非零元素之和的算法如下，填空以完成算法。#defineSMAX100//定义一个足够大的三元组表typedefstruct{inti,j,v;//非零元素的行、列、值}SPNode;//三元组类型5typedefstruct//定义稀疏矩阵{intm,n,t;//矩阵的行、列及非零元素的个数SPNodedata[SMAX];//三元组表}SPMatrix;//三元组表的存储类型iff2(SPNode*a,col){//求第col列非零元素之和intk,sum=0;if(①a-t=0)printf(“a=0”);if(②col0||col=a-n)printf(“列错！”);for(③k=0;ka-t;④k++)if(a-tada[k].j==n)sum=⑤sum+a-data[k].v;returnsum;}五．编程题1．试编写求一个三元组表的稀疏矩阵对角线元素之和的算法。#includestdio.h#defineERROR–99999typedefstruct{introw;intcol;intdata;}Triple;intMDSum(Triple*a){inti;intsum=0;if(a[0].row!=a[0].col)returnERROR;for(i=1;i=a[0].data;i++){if(a[i].row==a[i].col)sum+=a[i].data;}returnsum;}2．试编写求广义表中原子元素个数的算法。6解：设j为原子个数，则求广义表中原子元素个数的算法可递归定义如下：0LS为空表尾原子元素个数+1LS非空且表头为原子元素表头子表原子元素个数+表尾原子元素个数+1LS非空且表头子表intatomnum(Gnode*head){if(head==NULL)return0;if(head-tag==0)return(atomnum(head-next)+1);elsereturn(atomnum(head-next)+atomnum(head-val.sublist));}3．试编写求广义表最大中原子元素个数的算法。intmaxele(Gnode*head){intm=0,a;while(head){if(head-tag==1){a=maxele(head-val.sublist);if(am)m=a;}elseif(head-val.datam)m=head-val.data;head=head-next;}returnm;}j=7【例7】在按行存储的三元组表中，求某列（col）的非零元素之和的算法如下，请填空以完成算法。#defineSMAX100//定义一个足够大的三元组表structSPNode//定义三元组{inti,j,v;//三元组非零元素的行、列和值};structsparmatrix//定义稀疏矩阵{introw,col,terms;//稀疏矩阵行、列和非零元素的个数SPNodedata[SMAX];//三元组表}TTT;intf2(TTT*a,col)//求第col列非零元素之和{inti,sum=0;if(①)Error(“非零元素的个数是不大于0”);if(②)Error(“列号不合法”);for(③;④;k++)if(a-data[k].j==col)sum+=⑤;}returnsum;}分析：本算法首先检查非零元素的个数是否大于0，以及给定的列号是否合法。然后依次扫描三元组表，将列号等于给定列号col的非零元素相加，因此有：①a-terms=0②col0||col=a-terms③k=0④ka-terms⑤a-data[k].v