数据结构-第5章--数组和广义表-练习题.docx

第5章数组和广义表一、选择题1.设有一个10阶的对称矩阵A,采用压缩存储方式，以行序为主存储，却为第一元素，其存储地址为1,每个元素占一个地址空间，那么硼的地址为（）。A. 13B. 33C. 18D. 402 .有一个二维数组Al:6,0:7每个数组元素用相邻的6个字节存储，存储器按字节编址，那么这个数组的体积是（）个字节。假设存储数组元素Al,0的第一个字节的地址是0,那么存储数组A的最后一个元素的第一个字节的地址是（假设按行存储，那么A2,4的第一个字节的地址是（假设按列存储，那么A5,7的第一个字节的地址是（）。就般情况而言，当（）时，按行存储的AI,J地址与按列存储的AJ,I地址相等。供选择的答案:-：A. 12B. 66C. 72G. 156H. 234I. 276：A.行与列的上界相同C.行与列的上、下界都相同D.96E.114F.120J.282K.283L.288B.行与列的下界相同D.行的元素个数与列的元素个数相同3 .设有数组Ai,j,数组的每个元素长度为3字节，i的值为1到8,j的值为1到10,数组从内存首地址BA开始顺序存放，当用以列为主存放时，元素A5,8的存储首地址为（）。A.BA+141B.BA+180C.BA+222D.BA+2254 .假设以行序为主序存储二维数组A=arrayL100,1.100,设每个数据元素占2个存储单元，基地址为10,那么LOe5,5=（）oA.808B.818C.1010D.10205 .数组A0.5,0.6的每个元素占五个字节，将其按列优先次序存储在起始地址为100O的内存单元中，那么元素A5,5的地址是（）oA. 1175B. 1180C. 1205D. 12106 .有一个二维数组A0:8,1:5,每个数组元素用相邻的4个字节存储，存储器按字节编址，假设存储数组元素A0,l的第一个字节的地址是0,存储数组A的最后一个元素的第一个字节的地址是1）。假设按行存储，那么A3,5和A5,3的第一个字节的地址是（）和（）。假设按列存储，那么A7,1和A2,4的第一个字节的地址是（）和（）。-：A.28B.44C.76D.92E.108F.116G.132H.176I.184J.1887 .将一个AL.100,L.100的三对角矩阵，按行优先存入一维数组Bl298中，A中元素A6诚（即该元素下标i=66,j=65）,在B数组中的位置K为（）。供选择的答案：A.198B.195C.1978 .二维数组A的元素都是6个字符组成的串，行下标i的范围从。到8,列下标j的范圈从1到10。从供选择的答案中选出应填入以下关于数组存储表达中（）内的正确答案。（1）存放A至少需要（）个字节;（2）A的第8列和第5行共占（）个字节;（3）假设A按行存放，元素A8,5的起始地址与A按列存放时的元素（）的起始地址致。供选择的答案:(1) A. 90(2) A. 108(3) A. A8, 5B. 180B. 114B. A3, 10C. 240C. 54C. A5, 89.二维数组A的每个元素是由6个字符组成的串,D. 270E. 540D. 60E. 150D. A0, 9其行下标i=0,1,8,列下标j=l, 2, -,IOo假设A按行先存储，元素A8,5的起始地址与当A按列先存储时的元素（）的起始地址相同。设每个字符占一个字节。A. A8, 5B. A3,10C. A5, 8D. A0, 910 .假设对n阶对称矩阵A以行序为主序方式将其下三角形的元素(包括主对角线上所有元素)依次存放于一维数组B1.(n(n+l)2中，那么在B中确定aki(i<j)的位置k的关系为()。A.i*(i-l)2+jB.j*(j-l)2+iC.i*(i+l)2+jD.j*(j+l)2+i11 .设A是n*n的对称矩阵，将A的对角线及对角线上方的元素以列为主的次序存放在一维数组BL.n(n+D2中，对上述任一元素jn,且iWj)在B中的位置为()。A.i(i-l)2+jB.j(j-l)2+iC.j(j-l)2+i-lD.i(i-l)2+j-l12 .AN,N是对称矩阵，将下面三角(包括对角线)以行序存储到一维数组TN(N+1)/2中，那么对任一上三角元素aij对应Tk的下标k是()oA.i(i-l)2+jB.j(j-l)2+iC.i(j-i)/2+1D.j(i-l)/2+113 .设二维数组AL.m,1.n(即m行n列)按行存储在数组BL.m*n中，那么二维数组元素Ai,j在一维数组B中的下标为()。A.(i-l)*n+jB.(i-l)*n+j-lC.i*(j-l)D.j*m+i-l14 .有一个100*90的稀疏矩阵，非0元素有10个，设每个整型数占2字节，那么用三元组表示该矩阵时，所需的字节数是()。A.60B.66C.18000D.3315 .数组A0.4,-L.-3,5.7中含有元素的个数()。A.55B.45C.36D.1616 .用数组r存储静态链表，结点的next域指向后继，工作指针j指向链中结点，使j沿链移动的操作为()。A.j=rj.nextB.j=j+lC.j=j->nextD.j=rj->next17 .对稀疏矩阵进行压缩存储目的是()。A.便于进行矩阵运算B.便于输入和输出C.节省存储空间D.降低运算的时间复杂度18 .广义表L=(x,y,z),a,(u,t,w),从L表中取出原子项t的运算是()。A.head(tail(tail(L)B.tail(head(head(tail(L)C. head (tail (head (tail (L)D.head(tail(head(tail(tail(L)19 .广义表LS=(a,b,c),(d,e,f),运用head和tail函数取出LS中原子e的运算是()。A.head(tail(LS)B.tail(head(LS)C. head(tai 1(head(tai 1(LS)D. head(tai 1(tai 1(head (LS)20 .广义表A=(a,b,(c,d),(e,(f,g),那么下面式子的值为()Head(Tai1(Head(TaiKTail（八）)A.(g)B.(d)C.cD.d21 .广义表：A=(a,b),B=(A,A),C=(a,(b,A),B),求以下运算的结果：tai1(head(tai1(C)=()°A. (a)B. AC. aD. (b)E.F. (A)A.cB.b,cC.(b,c)D.(b,c)24.广义表(a,b,c,d)的表头是(),表尾是()。A.aB.()C.(a,b,c,d)D.(b,c,d)25.广义表(a,(b,c),d,e)的表头为()oA.aB.a,(b,c)C.(a,(b,c)D.(a)26.设广义表L=(a,b,c),那么L的长度和深度分别为()oA.1和1B.1和3C.1和2D.2和322.广义表运算式Tail(a,b),(c,d)的操作结果是()。A.(c,d)B.c,dC.(c,d)23.广义表L=(a,(b,c),进行Tail(L)操作后的结果为(27.下面说法不正确的选项是()。A.广义表的表头总是一个广义表B.广义表的表尾总是一个广义表D. d)。【中山大学1999 一、10C.广义表难以用顺序存储结构D.广义表可以是一个多层次的结构二、判断题1 .数组不适合作为任何二叉树的存储结构。（）2 .从逻辑结构上看，n维数组的每个元素均属于n个向量。（）3 .稀疏矩阵压缩存储后，必会失去随机存取功能。（）4 .数组是同类型值的集合。（）5 .数组可看成线性结构的一种推广，因此与线性表一样，可以对它进行插入，删除等操作。（）6 .一个稀疏矩阵采用三元组形式表示，假设把三元组中有关行下标与列下标的值互换，并把m和n的值互换，那么就完成了的转置运算。（）7 .二维以上的数组其实是一种特殊的广义表。（）8 .广义表的取表尾运算，其结果通常是个表，但有时也可是个单元素值。（）9 .假设一个广义表的表头为空表，那么此广义表亦为空表。（）10 .广义表中的元素或者是一个不可分割的原子，或者是一个非空的广义表。（11 .所谓取广义表的表尾就是返回广义表中最后一个元素。（）12 .广义表的同级元素（直属于同一个表中的各元素）具有线性关系。（）13 .对长度为无穷大的广义表，由于存储空间的限制，不能在计算机中实现。（）14 .一个广义表可以为其它广义表所共享。（）三、填空题1 .数组的存储结构采用存储方式。2 .设二维数组A-20.30,-30.20,每个元素占有4个存储单元，存储起始地址为200.如按行优先顺序存储,那么元素A25,18的存储地址为11）；如按列优先顺序存储,那么元素AT8,-25的存储地址为（2）。3 .设数组a1.50,L.80的基地址为2000,每个元素占2个存储单元，假设以行序为主序顺序存储，那么元素a4568的存储地址为（1）;假设以列序为主序顺序存储,那么元素a45,68的存储地址为°4 .将整型数组Al.8,1.8按行优先次序存储在起始地址为IoOO的连续的内存单元中，那么元素A7,3的地址是：o5 .二维数组a456（下标从0开始计，a有4*5*6个元素），每个元素的长度是2,那么a234的地址是o（设a000的地址是IoOO,数据以行为主方式存储）6 .设有二维数组A0.9,0.19,其每个元素占两个字节，第一个元素的存储地址为100,假设按列优先顺序存储，那么元素A6,6存储地址为o7 .数组A0.9,0.9的每个元素占5个存储单元,将其按行优先次序存储在起始地址为1000的连续的内存单元中，那么元素A6,8的地址为o8 .二维数组AL.10,0.9中每个元素占4个单元，在按行优先方式将其存储到起始地址为IoOO的连续存储区域时，A5,9的地址是：o9 .用一维数组B与列优先存放带状矩阵A中的非零元素Ai,j（lW!Wh,i-2WjWi+2）,B中的第8个元素是A中的第（中行,第（2）列的元素。10 .设数组A0.8,数组中任一元素Ai,j均占内存48个二进制位，从首地址2000开始连续存放在主内存里，主内存字长为16位，那么（1）存放该数组至少需要的单元数是;（2）存放数组的第8列的所有元素至少需要的单元数是;（3）数组按列存储时，元素A5,8的起始地址是o11 .设n行n列的下三角矩阵A已压缩到一维数组Bl.n*（n+l）/2中，假设按行为主序存储，那么Ai,j对应的B中存储位置为o12 .n阶对称矩阵a满足aij:aji,i,j=L.n,用一维数组t存储时，t的长度为（1）,当i=j»aij=t（2）,i>j,aij=t（3）,i<j,aij=t（4）o13 .己知三对角矩阵A【1.9,L.9的每个元素占2个单元，现将其三条对角线上的元素逐行存储在起始地址为IoOO的连续的内存单元中，那么元素A7,8的地址为O14 .设有一个10阶对称矩阵A采用压缩存储方式(以行为主序存储：a“=l),那么a85的地址为。15 .所谓稀疏矩阵指的是。16 .对矩阵压缩是为了o17 .上三角矩阵压缩的下标对应关系为：o18 .假设一个15阶的上三角矩阵A按行优先顺序压缩存储在一维数组B中，那么非零元素A9.9在B中的存储位置k=O(注：矩阵元素下标从1开始)'aa2a22。31a32。33如果按行序为主序将下三角元素A-(i,j)存储在一个一维数组Bl.n(n+l)2中，对任一个三角矩阵元素A,j,它在数组B中的下标为o20 .当广义表中的每个元素都是原子时，广义表便成了o21 .广义表的表尾是指除第一个元素之外，22.广义表简称表，是由零个或多个原子或子表组成的有限序列，原子与表的差异仅在于(1)。为了区分原子和表，一般用(2)表示表,用(3)表示原子。一个表的长度是指(4),而表的深度是指(5)23.广义表的定义为广义表中括弧的重数。24 .设广义表L=(),(),那么head(L)是S；tail(L)是;L的长度是；深度是(4)o25.广义表A=(9,7,(8,10,(99),12),试用求表头和表尾的操作Head()和Tail()将原子元素99从A中取出来。26 .广义表的深度是o27 .广义表(a,(a,b),d,e,(i,j),k)的长度是(1),深度是(2)。分)】28 .广义表LS=(a,(b,c,d),e),运用head和tail函数取出LS中原子b的运算是。29 .广义表A=(a,b),(c,d,e),取出A中的原子e的操作是：。30 .设某广义表H<A,(a,b,c),运用head函数和tail函数求出广义表H中某元素b的运算式。31 .广义表A(),(a,(b),c),head(tail(head(tail(head（八）)等于。32 .广义表运算式HEAD(TAlL(a,b,c),(x,y,z)的结果是。33 .广义表A=(a,b),(c),(d,e),head(tail(tail(head（八）)的结果是。34 .利用广义表的GetHead和GetTail操作，从广义表L=(apple,pear),(banana,orange)中别离出原子banana的函数表达式是。35 .a数组元素共5个，依次为12,10,5,3,1；b数组元素共4个，依次为4,6,8,15,那么执行如下所示的过程语句sort后得到c数组各元素依次为15,12,10,8,6,5,4,3,1；数组a,b,C的长度分别为1=5,In=4,n=9请在程序中方框内填入正确的成分，完成上述要求。PROCEDUREsort;VARi,j,k,x:integer;d:ARRAY1.mOFinteger;BEGINFORi:=lTOmDOdi:=0);i:=l;j:=l;k:=l;WHILE(i<=l)AND(j<=m)DOBEGINIFai>djTHENBEGINS)_;)_ENDELSEBEGIN(4);(5)END;ck:=x;(6)END;WHILE(7)DOBEGINckr=ai;k:=k+l;i:=i+l；END;WHILE(8)DOBEGINck=dj;k:=k+l;j:=j+l；END;END.sort36 .以下程序段search(a,n,k)在数组a的前n(n>=l)个元素中找出第k(l<=k<=n)小的值。这里假设数组a中各元素的值都不相同。defineMAXN100intaMAXN,n,k;intsearchc(inta,intn,intk)intlow,high,i,j,m,t;k一,;Iow=O;high=n-l;doi=low;j=high;t=alow;dowhile(i<j&&t<aj)j-;if(i<j)ai+=aj;while(i<j&&t>=ai)i+if(i<j)aj-=ai;while(i<j);ai=t;if；if(i<k)low=；elsehigh=;while(4);return(ak);37 .完善以下程序，每题在PASCAL语言(a)和C语言(b)中任选一题。下面是一个将广义表逆置的过程。例如原来广义表为(a,b),c,(d,e),经逆置后为：(e,d),c,(b,a).(a)算法的PASCAL语言过程描述编者略)：(b)算法的C语言过程描述：typedefstructglistnodeinttag;structglistnode*next;unionchardata;structstructglistnode*hp,*tpjptr;val;)*glist,gnode;glistreverse(p)glistp;glistq,h,t,s;if(p=NULL)q=NULL;elseifq=(glist)malIoc(sizeof(gnode);q->tag=O;q->val.data=p->val.data;else(2)if13)_t=reverse(p->val.ptr.tp);s=t;while(s->val.ptr.tp!=NULL)s=s->val.ptr.tp;s->val.ptr.tp=(glist)malIoc(sizeof(gnode);s=s->val.ptr.tp;s->tag=l;s->val.ptr.tp=NULL;s->val.ptr.hp=h;(4)elseq=(glist)malloc(sizeof(gnode);q->tag=l;q->val.ptr.tp=NULL;(5);)return(q);)38 .完善以下程序，每题在PASCAL语言(a)和C语言(b)中任选一题。下面的程序将数列L2,3,n*n,依次按蛇型方式存放在二维数组AL.n,L.n中。即(示意Ia编者略)。(a)算法的PASCAL语言程序描述(编者略)：(b)算法的C语言程序描述：#defineNMAX10includeustdio.ht,main()inti,j,n,k,p,q,m;intaNMAXNMAX;scanf("d”,&n);m=l;for(k=l；Q；k+)if(k<n)q=k；else(2);for(p=l;p<=q;p+)if(3)i=q-p+l;j=p；elsei=p;j=q-p+l;if(4)(i=i+n-q;j=j+11-q;aij=m；(5);)for(i=l；i<=n;i+)for(j=l；j<=n；j+)printf(w%4dw,aij);Printf()；)39 .约瑟夫环问题：设有n个人围坐一圈，并按顺时针方向1n编号。从第S个人开始进行报数，报数到第m个人，此人出圈，再从他的下一个人重新开始从1到In的报数进行下去，直到所有的人都出圈为止。PROCEDUREJosef(A:ARRAY1.nOFinteger;s,m:integer);BEGINFORi:=1TOnDOAih=i;si:=s;FORi:=nDOWrNTO2DOBEGINsi:=(1)；计算出圈人SlIFsl=OTHEN；w:=Asl;Asl出圈FOR:二DOAj:=Aj+l;Ai:=w;END;Write('出圈序列为：')；输出出圈序列FORi:=nDOUrNTO1DOwrite(Ai);writein；END;40 .设有一个背包可以放入的物品重量为S,现有n件物品，重量分别为W,W2,.,W.问能否从这n件物品中选择假设干件放入背包，使得放入的重量之和正好是S。设布尔函数KnaP(S,n)表示背包问题的解，Wi(i=l,2,.,n)均为正整数，并已顺序存储地在数组W中。请在以下算法的下划线处填空，使其正确求解背包问题。Knap(S,n)假设S=O那么Knap*-true否那么假设(S<0)或(S>0且n<l)那么Knapfalse否那么假设Knap(I),=true那么Print(Wn)；Knap-true否那么Knap-Knap(2)四应用题1 .数组AL.8,-2.6,0.6以行为主序存储，设第一个元素的首地址是78,每个元素的长度为4,试求元素A4,2,3的存储首地址。2 .b对角矩阵(alj)n,n,以行主序将b条对角线上的非零元存储在一维数组中，每个数据元素占L个存储单元，存储基地址为S,请用i,j表示出W的存储位置。3 .数组A中，每个元素Ai,j的长度均为32个二进位,行下标从T到9,列下标从1到11,从首地址S开始连续存放主存储器中，主存储器字长为16位。求：(1)存放该数组所需多少单元？(2)存放数组第4列所有元素至少需多少单元？(3)数组按行存放时，元素A7,4的起始地址是多少？(4)数组按列存放时，元素A4,7的起始地址是多少？4 .假设按低下标优先存储整型数组A(-3:8,3:5,-4:0,0:7)时，第一个元素的字节存储地址是100,每个整数占4个字节，问A(0,4,-2,5)的存储地址是什么？5 .设有三维数组A-2:4,0:3,-5:1按列序存放,数组的起始地址为1210,试求A(l,3,-2)所在的地址。6 .三维数组Al.10,-2.6,2.8的每个元素的长度为4个字节,试问该数组要占多少个字节的存储空间？如果数组元素以行优先的顺序存贮，设第一个元素的首地址是100,试求元素A5,0,7的存贮首地址。7 .设有五对角矩阵A=(aQ203,按特殊矩阵压缩存储的方式将其五条对角线上的元素存于数组A-10：m中，计算元素A15,16的存储位置。【东北大学1999一、2(4分)】8 .数组A0.8,1.10的元素是6个字符组成的串，那么存放A至少需要多少个字节？A的第8列和第5行共占多少个字节？假设A按行优先方式存储，元素A8,5的起始地址与当A按列优先方式存储时的哪个元素的起始地址一致？9 .假设按照压缩存储的思想将nXn阶的对称矩阵A的下三角局部(包括主对角线元素)以行序为主序方式存放于一维数组BL.n(n+l)2中，那么，A中任一个下三角元素aij(i2j),在数组B中的下标位置k是什么？10 .设mXn阶稀疏矩阵A有t个非零元素，其三元组表表示为LTMA1.(t+1),L.3,试问：非零元素的个数t到达什么程度时用LTMA表示A才有意义？11 .利用三元组存储任意稀疏数组时，在什么条件下才能节省存储空间。12 .对一个有t个非零元素的Ann矩阵，用B0.tL.3的数组来表示，其中第0行的三个元素分别为m,n,t,从第一行开始到最后一行，每行表示一个非零元素；第一列为矩阵元素的行号，第二列为其列号，第三列为其值。对这样的表示法，如果需要经常进行该操作-确定任意一个元素Aij在B中的位置并修改其值，应如何设计算法可以使时间得到改善？13 .有一个二维数组A0:8,1:5,每个数组元素用相邻的4个字节存储,存储器按字节编址,假设存储数组元素A0,1的第一个字节的地址是0,那么存储数组的最后一个元素的第一个字节的地址是多少?假设按行存储,那么A3,5和A5,3的第一个字节的地址是多少?假设按列存储,那么A7,1和A2,4的第个字节的地址是多少？14 .设有三对角矩阵(aw)n×n,将其三条对角线上的元素逐行的存于数组B(l:3n-2)中，使得Bk=aj,求：(1)用i,j表示k的下标变换公式；(2)假设n=10：每个元素占用L个单元，那么用BK方式比常规存储节省多少单元。15 .A为稀疏矩阵，试从空间和时间角度，比拟采用两种不同的存储结构(二维数组和三元组表)完成Jaii求运算的优缺点。16 .特殊矩阵和稀疏矩阵哪种压缩存储后失去随机存取的功能？为什么？17 .试表达一维数组与有序表的异同。18 .一个nXn的对称矩阵，如果以行或列为主序存入内存，那么其容量为多少？19 .给出数组A：ARRAY3.8,2.6OFlNTEGER;当它在内存中按行存放和按列存放时,分别写出数组元素Ai,j地址计算公式(设每个元素占两个存储单元)。20 .n阶下三角矩阵A(即当i<j时，Wau=O),按照压缩存储的思想，可以将其主对角线以下所有元素(包括主对角线上元素)依次存放于一维数组B中，请写出从第一列开始采用列序为主序分配方式时在B中确定元素aij的存放位置的公式。21 .设有三对角矩阵j)n*n,将其三条对角线上的元素逐行地存于数组B(l:3n-2)中，使得Bkfij,求：(1)用i,j表示k的下标变换公式；(2)用k表示i,j的下标变化公式。22 .算法Print及所引用的数组A的值如下，写出调用Print(D的运行结果(其中n=15)°123456789101112131415ABCDEFG00H0IJKLPROCEDUREprint(i：integer)；BEGINIF(i<=n>AND(AiO'0')THENBEGINPrint(2*i)；write(Ai);Print(2*i+l);END；END；23 .设数组A的长度为2N,前N个元素Al.N递减有序，后N个元素AN+1.2N递增有序，且2N是2的整数次暮,即k=log22N为整数。例如AL.8:90,85,50,10,30,65,80,100满足上述要求，这里N=4,k=3,A的前4个元素和后4个元素分别递减和递增有序。用此例调用如下的DemO过程，并要求：(1)给出for循环中每次执行PerfeCtShUffIe(A,N)和COnIPareEXChange(A,N)的结果；(2)解释Demo的功能；(3)给出Demo的时间复杂度。PROCEDUREPerfectShuffle(VARAiarraytype;N:integer)i：=l；j：=l；WHILEi<=NDOBj:=Ai;Bj+l:=Ai+N;i:=i+l;j:=j+2;Al.2N2N;/BcopytoAPROCEDURECompareExchange(VARAiarraytype;Nrinteger)j：=l；WHILEj<2NDOIFAj>Aj+lTHENAj-Aj+1;交换Aj和Aj+1j：=j+2;PROCEDUREDemo(VARA:arraytype;N:integer)/A的长度为2N,k=log22N为整数FORi:=lTOlog22NDOPerfectShuffle(A,N);CompareExchange(A,N);24 .现有算法及正整数n和数组A如下，求数组C的值。VARA,B,CrArraytl.100ofinteger;FUNCAAA(s,t:integer):integer;IFs=tTHENIFBs=OTHENAAA:=SELSEAAA:=-SELSEBEGINk=AAA(s,(s+t)DIV2);r:=AAA(s+t)DIV2+1,t);IFl>0THENAAA:=1ELSEAAA:=r;IF(r>0)AND(Al>Ar)THENAAA:=rENDENDF;PROCBBB;FORi:=lTOnDOBi:=O;FORi:=lTOnDOBAAA(1,n):=i;FORi:=lTOnDOCBi:=Ai;ENDP;初始值：n=10,A=121,22,323,212,636,939,828,424,55,262;2 133 312125.设有矩阵a且N'执行以下语句后，矩阵C和a的结果分别是什么？(1)FORi:=lTO3DOFORj:=lTO3DOci,j:=aai,j,aj,i(2) FORi:=lTO3DOFORj:=lTO3DOai,j:=aai,j,aj,i-213331i2126 .设矩阵A为Llz1J(1)执行语句FORi:=lTO3DOFORj:=lTO3DOCi,j:=AAi,j,Aj,iU结果C矩阵的值是什么？(2)所选择的下标i,j的次序有关系吗？(3)在语句中，用A代替C,A的结果值是什么？(4)对i,j这对下标取反序，即(3,3),(3,2),(3,1),(1,3),(1,2),(1,1)重复执行(3),把所得结果与(3)中所得结果作比拟。27 .指出以下算法中错误、低效之处，并将其改成一个正确且高效的算法。PROCEDUREdelk(A,m,last,i,k);从数组A1.last中删除第i个元素起的k个元素，m为A上限BEGINIF(i<l)OR(i>last)OR(k<0)0R(last>m)THENwrite(,error*)ELSEFORcount:=1TOkTOFORj:=IastDOWNTOi+1DOAj-1-Aj;Iastz=Iast-IENDP;delk28 .设输入为整数数组Al.n,其中l<=Ai"=k(l<=i<=n);输出数组为bL.n;CL.k是临时工作空间；阅读下述算法后，答复以下问题：PROCDemo(A,B,k)(I)FORi:=lTOkDOCi:=0;(2)FORj:=lTOnDOCAj:=CAj+l;(3)FORi:=2TOkDOCi:=Ci+Ci-1(4)FORj:=nDOWNTO1DO(5) BCAj:=Aj;(6)CAj:=CAj-l(a) .当标号(2)行的循环执行完后，Ci(l<=iCn)的值有何意义？(b) .当标号(3)行的循环执行完后，Ci(k=i<=n)的值有何意义？(c) .算法执行后，B的内容有何特点？(d) .当k=O(n)时，算法的时间复杂度是多少？29 .上三角阵A(N*N)按行主序压缩存放在数组B中，其中Ai,j=Bk.写出用i,j表示的k。30 .设有上三角矩阵(aG.，将其上三角中的元素按先行后列的顺序存于数组B(l:m)中，使得Bk:a/且k=fl(i)+f2(j)+c,请推导出函数fl,f2和常数c,要求fl和f2中不含常数项。20040030030031.设矩阵A=4000(1)假设将A视为对称矩阵，画出对其压缩存储的存储表，并讨论如何存取A中元素a,(0<=i,j<4)；(2)假设将A视为稀疏矩阵，画出A的十字链表结构。10020300000532.设对称矩阵A=2050(1)假设将A中包括主对角线的下三角元素按列的顺序压缩到数组S中，即S:1002300050下标：12345678910试求出A中任一元素的行列下标i,j(k=i,j<=4)与S中元素的下标K之间的关系.(2)假设将A视为稀疏矩阵时，画出其三元组表形式压缩存储表。12000-10100021000000133.设对角线矩阵A=100035J(行列下标i,j满足：lWi,jW5)(1)假设将矩阵A压缩存储到数组S中：1210121000135下标：12345678910111213试求出A中已存储之元素的行列下标(i,j)与S中元素的下标K之间的关系(2)假设将A视为稀疏距阵时，请画出其行逻辑链接顺序表。34.设有一个三维数组acl:dl,c2:d2,c3:d3,其中ci:di是第i维的界偶，如该数组在内存中按行排列，且acl,c2,c3的地址为a,那么请导出下标变量a地1,为,i3的地址,假设每个元素占L个单元。0a22.0.a2,n-1an00n+1.a2/7+1，2.0035.假定有以下nxn矩阵In为奇数)A=an00ann如果用一维数组B按行主次序存储A的非零元素，问：(UA中非零元素的行下标与列下标的关系；(2)给出A中非零元素a”的下标(i,j)与B中的下标R的关系;给出利用好的下标(i,j)定位在BAl A 2 A3 An43 4"A” 4”4 (3)假定矩阵中每个元素占一个存贮单元且B的起始地址为Ao,中的位置公式。36 .对于一个对称矩阵采用压缩存储，只存放它的上三角局部，并按列存放。例如对于一个n*n的对称矩阵A(如右图)，用一个一维数组B来存放它的上三角局部：B=Au,A12>A22>Ab,A23>A33,Au,，Aln,A2n,，Ann同时有两个函数：MAX(i,j)lMIN(i,j),分别计算下标i和j中的大者与小者。试利用它们给出求任意一个Aij在B中存放位置的公式。(假设式中没有MA设I,中和MIN(i,j)那么不给分)37.用三元数组表示稀疏矩阵的转置矩阵,并简要写出解题步骤。38.简述广义表属于线性结构的理由。39 .数组，广义表与线性表之间有什么样的关系？40 .什么是广义表？请简述广义表和线性表的主要区别。41 .求以下广义表的运算结果。(1) CAR(CDR(a,b),(c,d),(e,f)(2) CDR(CAR(a,b),(c,d)t(e,f)(3) CAR(CDR(CAR(a,b),(e,f)(4) CDR(CAR(CDR(a,b),(e,f)(5) CDR(CDR(CAR(a,b),(e,f)注：CAR运算