中南大学数据结构与算法第5章数组和广义表课后作业答案
更新时间:2024-05-18 09:00:01 阅读量: 综合文库 文档下载
- 中南大学数据结构期末试卷推荐度:
- 相关推荐
第5章数组与广义表习题练习答案
5.1请按行及按列优先顺序列出四维数组A2*3*2*3的所有元素在内存中的存储次序,开始结点为a0000 。 解:
按行优先的顺序排列时,先变化右边的下标,也就是右到左依次变化,这个四维数组的排列是这样的:(将这个排列分行写出以便与阅读,只要按从左到右的顺序存放就是在内存中的排列位置) a0000 a0001 a0002 a0010 a0011 a0012 a0100 a0101 a0102 a0110 a0111 a0112 a0200 a0201 a0202 a0210 a0211 a0212 a1000 a1001 a1002 a1010 a1011 a1012 a1100 a1101 a1102 a1110 a1111 a1112 a1200 a1201 a1202 a1210 a1211 a1212
按列优先的顺序排列恰恰相反,变化最快的是左边的下标,然后向右变化,所以这个四维数组的排列将是这样的,(这里为了便于阅读,也将其书写为分行形式): a0000 a1000 a0100 a1100 a0200 a1200 a0010 a1010 a0110 a1110 a0210 a1210 a0001 a1001 a0101 a1101
a0201 a1201 a0011 a1011 a0111 a1111 a0211 a1211 a0002 a1002 a0102 a1102 a0202 a1202 a0012 a1012 a0112 a1112 a0212 a0212
5.2 给出C语言的三维数组地址计算公式。 解:
因为C语言的数组下标下界是0,所以 Loc(Amnp)=Loc(A000)+((i*n*p)+k)*d
其中 Amnp表示三维数组。Loc(A000)表示数组起始位置。i、j、k表示当前元素的下标,d表示每个元素所占单元数。
5.3 设有三对角矩阵 An*n,将其三条对角线上的元素逐行地存储到向量B[0...3n-3]中,使得B[k]=aij,求: (1)用i , j 表示k的下标变换公式。 (2)用 k 表示 i,j 的下标变换公式。
(1) 解:
要求i,j 到k 的下标变换公式,就是要知道在k之前已有几个非零元素,这些非零元素的个数就是k的值,一个元素所在行为i,所在列为j,则在其前面已有的非零元素个数为: (i*3-1)+j-(i+1)
其中 (i*3-1)是这个元素前面所有行的非零元素个数,j-(i+1)是它所在列前面的非零元素个数 化简可得:
k=2i+j; // c下标是从0开始的。
(2) 解:
因为K和i,j是一一对应的关系,因此这也不难算出:
i=(k+1)/3 //k+1表示当前元素前有几个非零元素,被3整除就得到行号
j=(k+1)%3+(k+1)/3-1 //k+1除以3的余数就是表示当前行中第几个非零元素, //加上前面的0元素所点列数就是当前列号
5.4 设二维数组A5*6的每个元素占4个字节,已知Loc(a00)=1000,A共占多少个字节? A的终端结点a45的起始地位为何?按行和按列优先存储时,a25的起始地址分别为何? 解:
(1)因含5*6=30个元素,因此A共占30*4=120个字节。
(2)a45的起始地址为:
Loc(a45)=Loc(a00)+(i*n+j)*d=1000+(4*6+5)*4=1116
(3)按行优先顺序排列时, a25=1000+(2*6+5)*4=1068
(4)按列优先顺序排列时:(二维数组可用行列下标互换来计算) a25=1000+(5*5+2)*4=1108
5.5 特殊矩阵和稀疏矩阵哪一种压缩存储后会失去随机存取的功能?为什么? 答:
后者在采用压缩存储后将会失去随机存储的功能。因为在这种矩阵中,非零元素的分布是没有规律的,为了压缩存储,就将每一个非零元素的值和它所在的行、列号做为一个结点存放在一起,这样的结点组成的线性表中叫三元组表,它已不是简单的向量,所以无法用下标直接存取矩阵中的元素。
5.6 简述广义表和线性表的区别与联系。 答:
广义表是线性表的推广,线性表是广义表的特例。当广义表中的元素都是原子时,即为线性表。
5.7 画出下列广义表的图形表示:
(1) A(a,B(b,d),C(e,B(b,d),L(f,g))) (2) A(a,B(b,A)) 解:
(1)这是一个再入表。(2)则是一个递归表。
5.8 设广义表L=((),()),试问head(L),tail(L),L的长度,深度各为多少? 解:
●head(L)=() ●tail(L)=(()) ●L的长度为2 ●L的深度为2
5.9 求下列广义表运算的结果:
(1)head ((p,h,w)); (2)tail((b,k,p,h)); (3) head (((a,b),(c,d))); (4)tail(((a,b),(c,d))); (5)head(tail(((a,b),(c,d)))); (6)tailhead)(((a,b),(c,d)))). 答:
(1)head ((p,h,w))=p; (2)tail((b,k,p,h))=(k,p,h); (3)head (((a,b),(c,d)))=(a,b);
(4)tail(((a,b),(c,d)))=((c,d)); (5)head(tail(((a,b),(c,d))))=(c,d); (6)tail(head(((a,b),(c,d))))=(b).
5.10 当三角矩阵采用题5.3所述的压缩存储时,写一算法求三对角矩阵在这种压缩存储表示下的转置矩阵。 解:
转置矩阵就是将矩阵元素的行号与列号互换,根据已知的三对角矩阵的特点,其转置矩阵对角线元素不变,非零的非对角线元素aij与aji互换位置。又知元素的下标和存放一维数组空间位置的关系:k=2i+j。我们可以设计出这个矩阵的转置算法:
#define N 10 //矩阵行、列数
#define Length (3*N-2)//压缩矩阵的长度 typedef struct{ int data[Length]; }DiaMatrix;
void TransMatrix(DiaMatrix * C) { //压缩三对角矩阵转置 int i, j; int t;
for(i=0; i
{ //将对应于行列号的压缩矩阵内的元素互换 t=C->data[2*i+j];
C->data[2*i+j]=C->data[2*j+i]; C->data[2*j+i]=t; }//endif }//end
5.11 当稀疏矩阵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 { //定义三元组表
TriTupleNode data[MaxSize];
int m,n,t;//矩阵行,列及三元组表长度 }TriTupleTable;
//以下为矩阵加算法
void AddTriTuple( TriTupleTable *A, TriTupleTable *B, TriTupleTable *C) {//三元组表表示的稀疏矩阵A,B相加 int k,l; DataType temp; C->m=A->m;//矩阵行数 C->n=A->n;//矩阵列数
C->t=0; //三元组表长度 k=0; l=0;
while (kt&&l
{if((A->data[k].i==B->data[l].i)&&(A->data[k].j==B->data[l].j)) {temp=A->data[k].v+B->data[l].v; if (!temp)//相加不为零,加入C {C->data[c->t].i=A->data[k].i; C->data[c->t].j=A->data[k].j; C->data[c->t++].v=temp; } k++;l++; }
if ((A->data[k].i==B->data[l].i)&&(A->data[k].j
if ((A->data[k].i==B->data[l].i)&&(A->data[k].j>B->data[l].j)) ||(A->data[k].i>B->data[l].i)//将B中三元组加入C {C->data[c->t].i=B->data[l].i; C->data[c->t].j=B->data[l].j; C->data[c->t++].v=B->data[l].v; l++; } }
while (kt)//将A中剩余三元组加入C {C->data[c->t].i=A->data[k].i; C->data[c->t].j=A->data[k].j;
C->data[c->t++].v=A->data[k].v; k++; }
while (l
- 冀教版版五年级科学下册复习资料
- 微生物学复习提纲
- 2013—2014学年小学第二学期教研组工作总结
- 国有土地转让委托服务合同协议范本模板
- 我的固废说明书
- 企业管理诊断报告格式
- 东鼎雅苑施工组织设计
- 谈谈如何做好基层党支部书记工作
- 浮梁县环保局市级文明单位创建工作汇报
- 管理学基础知识
- 大学物理实验报告23 - PN结温度传感器特性1
- 计算机网络实践
- 酒桌上这四种情况下要坐牢,千万别不当回事……
- 国家康居示范工程建设技术要点
- 中国贴布行业市场调查研究报告(目录) - 图文
- 新课标下如何在高中物理教学中培养学生的创新能力初探
- 营养师冬季养生食谱每日一练(7月4日)
- 关注江西2017年第3期药品质量公告
- 建设海绵城市专题习题汇总
- 10万吨年环保净水剂建设项目报告书(2).pdf - 图文
- 中南大学
- 数据结构
- 数组
- 课后
- 广义
- 算法
- 作业
- 答案
- 小班幼儿一日生活游戏化的探索
- 借钱也要买!十大典藏级单反镜头
- cpa2010 - caiguan - 14
- 2015—2017高考政治全国卷大题汇总含答案解析
- 关于针对“内网安全综合管理平台”功能测试报告 - 图文
- 2017年中国柞木地板现状分析及市场前景预测(目录) - 图文
- 邯郸市2018届高三下学期第一次模拟考试数学(理)试题 含答案
- 现代物流 文献综述
- 矿区资源储量核查技术要求解读11.13 - 图文
- 市场人员谈单拉访的基本步骤
- 建国大业观后感
- YETC-210A使用说明 - 图文
- 基于PLC在包装码垛生产线上的自动控制设计 - 图文
- 创业板股权激励研究 - 图文
- 现代教育学知识点
- 科技发展弊大于利一辩辩词
- 元明清文学模拟试题(一)及答案
- 监理大纲(暗标)最终
- 学术道德与规范试题
- 文献综述