第5章习题及解答.doc

假设按行优先存储整数数组A9358时，第一个元素的字节地址是，每个整数占个字节。问下列元素的存储地址是什么？a0000 a1111 a3125 a8247a0000 的存储地址是100。a1111 的存储地址是776。a3125 的存储地址是1784。a8247 的存储地址是4416。设有三对角矩阵Ann，将其三条对角线上的元素存于数组B3n中，使得元素Buv=aij，试推导出从(i,j)到(u,v)的下标变换公式。u = iv = j if i2 | j-i+2 if i2假设一个准对角矩阵：a11 a12a21 a22a33 a34a43 a44 . aij a2m-1,2m-1 a2m-1,2m a2m,2m-1 a2m,2m 按以下方式存储于一维数组B4m中:01 2 3 4 5 6 k 4m-1 4ma 11a 12a21a22a33a34a43aija2m-1,2ma2m,2m-1a2m,2m写出由一对下标(i,j)求k的转换公式。略现有如下的稀疏矩阵A（如图所示），要求画出以下各种表示方法。三元组表示法。十字链表法。 0 0 22 0 -150 13 3 0 0 00 0 0 -6 0 00 0 0 0 0 091 0 0 0 0 00 0 28 0 0 0 略画出下列广义表的存储结构示意图。A=(a,b,c),d,(a,b,c)B=(a,(b,(c,d),e),f)略对于二维数组Amn,其中m=80,n=80，先读入m,n，然后读该数组的全部元素，对如下三种情况分别编写相应算法：求数组A靠边元素之和。求从A00开始的互不相邻的各元素之和。当m=n时，分别求两条对角线的元素之和，否则打印m!=n的信息。有数组A44，把1到16个整数分别按顺序放入A00.A03，A10.A13，A20.A23，A30.A33中，编写一个算法获取数据并求出两条对角线元素的乘积。int mul (int A44)int k=1,s=1;for (i=0; i4 ;i+)for (j=0 ;j4 ;j+)Aij =k;k+;for (i=0; idata=1; L-next =L;rear =L;for (i=2 ;idata=i;s-next=rear-next;rear-next = s;rear = s;p=L; while (p-next != p)i=1;while (inext;i+;q-next=p-next; coutdatanext; cout”the last monky is : ” datamu = A-mu; C-nu = A-nu; C-tu = 0; pa=1 ; pb =1 ; pc=1;while (patu & pbtu)if (A-datapa.i=B-datapb.i)&(A-datapa.j=B-datapb.j)C-datapc.i=A-datapc.i; C-datapc.j=A-datapc.j;C-datapc.v=A-datapa.v + B-datapb.v;C-tu+ ;pc+ ; pa+ ; pb+ ;elseif (A-datapa.i datapb.i)|(A-datapa.i=B-datapb.i&A-datapa.jdatapb.j)C-datapc.i = A-datapa.i; C-datapc.j = A-datapa.j; C-datapc.v = A-datapa.v; C-tu+; pc+ ;pa+;elseC-datapc.i = B-datapb.i;C-datapc.j = B-datapb.j;C-datapc.v = B-datapb.v;c-tu+; pc+; pb+;while ( patu)C-datapc.i = A-datapa.i;C-datapc.j = A-datapa.j;C-datapc.v = A-datapa.v;pc+; pa+;while ( pbtu )C-datapc.i = B-datapb.i; C-datapc.j = B-datapb.j;C-datapc.v = B-datapb.v;pc+; pb+;return(c);假设稀疏矩阵只存放其非0元素的行号、列号和数值，以一维数组顺次存放，行号为-1结束标志。 例如：如图所示的稀疏矩阵M：1 0 0 0 10 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 5 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 M = 则存在一维数组D中： D0=1， D1=1，D2=1，D3=1，D4=5 D5=10，D6=3，D7=9，D8=5，D9=-1 现有两个如上方法存储的稀疏矩阵A和B，它们均为m行n列，分别存放在数组A和B中，编写求矩阵加法C=A+B的算法，C亦放在数组C中。void add (int A , int B , int C )pa=0; pb=0; pc=0; while (Apa+2 & Bpb+2)if (Apa= =Bpb & Apa+1= =Bpb+1)Cpc=Apa;Cpc+1=Apc+1; Cpc+2=Apa+2+Bpb+2 ;pa+=3; pb+=3; pc+=3;elseif (ApaBpb|(Apa= =Bpb & Apa+1Bpb+1)Cpc=Apa;Cpc+1=Apc+1;Cpc+2=Apc+2;pa+=3; pc+=3;elseCpc=Bpb; Cpc+1=Bpb+1;Cpc+2=Bpb+2; pb+=3; pc+=3;while (Apa+2!=0)Cpc=Apa; Cpc+1=Apa+1;Cpc+2=Apc+2;pa+=3; pc+=3;while (Bpa+2!=0)Cpc=Bpb; Cpc+1=Bpb+1;Cpc+2=Bpb+2;pb+=3; pc+=3;return;已知A和B为两个n*n阶的对称矩阵，输入时，对称矩阵只输入下三角形元素，按压缩存储方法存入一维数组A和B中，编写一个计算对称矩阵A和B的乘积的算法。void mul(int A , int B , int C , int n)for (i=0;in;i+)for (j=0;jn;j+) mi=max(i,j);mj=min(i,j);x=mi*(mi-1)/2 + mj-1; Cx=0;for (K=0; KN; K+)u1=max(i.K)