数据结构第五章.doc

一、 假设有二维数组A6*8，每个元素用相邻的6个字节存储，存储器按字节编址。已知A的起始存储位置（基地址）为1000。计算：1、 数组A的体积（即存储量）；2、 数组A的最后一个元素a57的第一个字节的地址；3、 按行存储时，元素a14的第一个字节的地址；4、 按列存储时，元素a47的第一个字节的地址；答案：1、（6*8）*6=2882、loc(a57)=1000+(5*8+7)*6=1282或=1000+（288-6）=12823、loc(a14)=1000+(1*8+4)*6=10724、loc(a47)=1000+(7*6+4)*6=1276二、假设按低下标(行优先)优先存储整数数组A9*3*5*8时第一个元素的字节地址是100，每个整数占四个字节。问下列元素的存储地址是什么？（1）a0000 (2)a1111 (3)a3125 (4)a8247答案：（1）100 （2）loc(a1111)=100+(1*3*5*8+1*5*8+1*8+1)*4=776 (3) loc(a3125)=100+(3*3*5*8+1*5*8+2*8+5)*4=1784 (4) loc(a8247)=100+(8*3*5*8+2*5*8+4*8+7)*4=4416五、设有一个上三角矩阵（aij）n*n,将其上三角元素逐行存于数组Bm中，（m充分大），使得Bk=aij且k=f1(i)+f2(j)+c。试推导出函数f1,f2和常数C（要求f1和f2中不含常数项）。答：K=n+(n-1)+(n-2)+.+(n-(i-1)+1)+j-i =(i-1)(n+(n-i+2)/2+j-i所以f1(i)=(n+1/2)i-1/2i2 f2(j)=j c=-(n+1)九、已知A为稀疏矩阵，试从空间和时间角度比较采用两种不同的存储结构（二维数组和三元组表）完成aii运算的优缺点。（对角线求和）解：1、二维数组 For(i=1;i=n;i+) S=s+aii; 时间复杂度：O（n）2、for(i=1;im=A-m;/矩阵行数C-n=A-n;/矩阵列数C-t=0; /三元组表长度k=0; l=0;while (kt<)if(A-datak.i=B-datal.i)&(A-datak.j=B-datal.j)temp=A-datak.v+B-datal.v;if (!temp)/相加不为零，加入CC-datac-t.i=A-datak.i;C-datac-t.j=A-datak.j;C-datac-t+.v=temp;k+;l+;if (A-datak.i=B-datal.i)&(A-datak.jdatal.j)|(A-datak.idatal.i)/将A中三元组加入CC-datac-t.i=A-datak.i;C-datac-t.j=A-datak.j;C-datac-t+.v=A-datak.v;k+;if (A-datak.i=B-datal.i)&(A-datak.jB-datal.j)|(A-datak.iB-datal.i)/将B中三元组加入CC-datac-t.i=B-datal.i;C-datac-t.j=B-datal.j;C-datac-t+.v=B-datal.v;l+;while (kt)/将A中剩余三元组加入CC-datac-t.i=A-datak.i;C-datac-t.j=A-datak.j;C-datac-t+.v=A-datak.v;k+;while (lt)/将B中剩余三元组加入CC-datac-t.i=B-datal.i;C-datac-t.j=B-datal.j;C-datac-t+.v=B-datal.v;l+;二十六、试编写一个以三元组形式输出用十字链表表示的稀疏矩阵中非零元素及其下标的算法。解：void Print_OLMatrix(OLMatrix A)/以三元组格式输出十字链表表示的矩阵for(i=0;iright) /逐次遍历每一个行链表printf(%d %d %dn,i,p-j,p-e;/Print_OLMatrix补充题：一、现有如下的稀疏矩阵A（如图所示），要求画出以下各种表示方法。（1）三元组表示法。（2）十字链表法。 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 三元组表示法i j v12345671 4 221 6 -152 2 132 3 33 4 -65 1 916 3 28 略二、画出下列广义表的存储结构示意图。（1）A=(a,b,c),d,(a,b,c)（2）B=(a,(b,(c,d),e),f)三、有数组A44，把1到16个整数分别按顺序放入A00.A03，A10.A13，A20.A23，A30.A33中，编写一个算法获取数据并求出两条对角线元素的乘积。int mul(int A44) int i,j;int k,s; k=1; s=1; for (i=0;i4;i+) for (j=0;j4;j+) Aij=k;k+; for (i=0;i4;i+) s=s*Aii;s=s*Ai3-i; / 计算两条对角线元素的乘积 return s; 四、19.已知广义表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) 20. 广义表A=(a,b,(c,d),(e,(f,g),则下面式子的值为（ ）。Head(Tail(Head(Tail(Tail(A)A. (g) B. (d) C. c D. d21. 已知广义表: A=(a,b), B=(A,A), C=(a,(b,A),B), 求下列运算的结果: tail(head(tail(C) =( )。A.（a） B. A C. a D. (b) E. b F. (A)22. 广义表运算式Tail(a,b),(c,d)的操作结果是（ ）。A. (c,d) B. c,d C. (c,d) D. d23. 广义表L=（a，（b，c），进行Tail（L）操作后的结果为（ ）。A. c B. b，c C.（b，c） D.（b，c）24. 广义表（a,b,c,d）的表头是（ ），表尾是（ ）。A. a B.（） C.（a,b,c,d） D.（b,c,d）25. 广义表（a,(b,c),d,e）的表头为（ ）。 A. a B. a,(b,c) C. (a,(b,c) D. (a)26. 设广义表L=（a,b,c），则L的长度和深度分别为（ ）