admin 管理员组文章数量: 1086019
2024年3月14日发(作者：enablecelledit)
第五章 数组与广义表
一、 假设有二维数组A
6*8
，每个元素用相邻的6个字节存储，存储器按字节
编址。已知A的起始存储位置（基地址）为1000。计算：
1、数组A的体积（即存储量）；
2、数组A的最后一个元素a57的第一个字节的地址；
3、按行存储时，元素a14的第一个字节的地址；
4、按列存储时，元素a47的第一个字节的地址；
答案：
1、（6*8）*6=288
2、loc(a57)=1000+(5*8+7)*6=1282或=1000+（288-6）=1282
3、loc(a14)=1000+(1*8+4)*6=1072
4、loc(a47)=1000+(7*6+4)*6=1276
二、假设按低下标(行优先)优先存储整数数组A
9*3*5*8
时第一个元素的字节地址
是100，每个整数占四个字节。问下列元素的存储地址是什么？
（1）a
0000
(2)a
1111
(3)a
3125
(4)a
8247
答案：（1）100
（2）loc(a
1111
)=100+(1*3*5*8+1*5*8+1*8+1)*4=776
(3) loc(a
3125
)=100+(3*3*5*8+1*5*8+2*8+5)*4=1784
(4) loc(a
8247
)=100+(8*3*5*8+2*5*8+4*8+7)*4=4416
五、设有一个上三角矩阵（aij）n*n,将其上三角元素逐行存于数组B[m]中，（m
充分大），使得B[k]=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/2i
2
f2(j)=j
c=-(n+1)
九、已知A为稀疏矩阵，试从空间和时间角度比较采用两种不同的存储结构（二
维数组和三元组表）完成∑aii运算的优缺点。（对角线求和）
解：
1、二维数组
For(i=1;i<=n;i++)
S=s+a[i][i];
时间复杂度：O（n）
2、for(i=1;i<=;i++)
If([k].i==[k].j) s=s+[k].value;
时间复杂度：O（n
2
）
二十一、当稀疏矩阵A和B均以三元组表作为存储结构时，试写出矩阵相加的算
法，其结果存放在三元组表C中。
解：
矩阵相加就是将两个矩阵中同一位置的元素值相加。由于两个稀疏矩阵的非
零元素按三元组表形式存放，在建立新的三元组表C时，为了使三元组元素仍按
行优先排列，所以每次插入的三元组不一定是A的，按照矩阵元素的行列去找A
中的三元组，若有，则加入C，同时，这个元素如果在B中也有，则加上B的这
个元素值，否则这个值就不变;如果A中没有，则找B，有则插入C，无则查找下
一个矩阵元素。
#define MaxSize 10 //用户自定义
typedef int DataType; //用户自定义
typedef struct
{ //定义三元组
int i,j;
DataType v;
}TriTupleNode;
typedef struct
{ //定义三元组表
版权声明：本文标题：数据结构课后习题答案第五章数组与广义表 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://roclinux.cn/b/1710382757a570603.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。
发表评论