数据结构课后习题及解析第五章

1、第五章习题5.1 假设有6行8列的二维数组a，每个元素占用6个字节，存储器按字节编址。已知a的基地址为1000，计算：数组a共占用多少字节；数组a的最后一个元素的地址；按行存储时元素a36的地址；按列存储时元素a36的地址；5.2 设有三对角矩阵ann ,将其三条对角线上的元素逐行地存于数组b(1:3n-2)中，使得bk= aij ，求：（1） 用i,j表示k的下标变换公式；（2） 用k表示i,j的下标变换公式。5.3假设稀疏矩阵a和b均以三元组表作为存储结构。试写出矩阵相加的算法，另设三元组表c存放结果矩阵。5.4在稀疏矩阵的快速转置算法5.2中，将计算positioncol的方法稍加改动，

2、使算法只占用一个辅助向量空间。5.5写一个在十字链表中删除非零元素aij的算法。5.6画出下面广义表的两种存储结构图示： (a), b), ( ), d), (e, f)5.7求下列广义表运算的结果：（1） head(a,b),(c,d);（2） tail(a,b),(c,d);（3） tailhead(a,b),(c,d);（4） headtailhead(a,b),(c,d);（5） tailheadtail(a,b),(c,d);实习题若矩阵amn中的某个元素aij是第i行中的最小值，同时又是第j列中的最大值，则称此元素为该矩阵中的一个马鞍点。假设以二维数组存储矩阵，试编写算法求出矩阵中

3、的所有马鞍点。第五章答案5.2设有三对角矩阵ann,将其三条对角线上的元素逐行的存于数组b1.3n-2中，使得bk=aij，求：（1）用i,j表示k的下标变换公式；（2）用k表示i、j的下标变换公式。【解答】（1）k=2(i-1)+j(2) i=k/3+1, j=k/3+k%3 （ 取整，%取余）5.4在稀疏矩阵的快速转置算法5.2中，将计算positioncol的方法稍加改动，使算法只占用一个辅助向量空间。【解答】算法（一） fasttransposetsmatrix(tsmartrix a, tsmatrix *b) /*把矩阵a转置到b所指向的矩阵中去，矩阵用三元组表表示*/int co

4、l,t,p,q;int positionmaxsize;b-len=a.len; b-n=a.m; b-m=a.n;if(b-len0) position1=1; for(t=1;t=a.len;t+) positiona.datat.col+1+; /*positioncol存放第col-1列非零元素的个数, 即利用poscol来记录第col-1列中非零元素的个数*/*求col列中第一个非零元素在b.data 的位置，存放在positioncol中*/for(col=2;col=a.n;col+) positioncol=positioncol+positioncol-1; for(p=1;

5、pdataq.row=a.datap.col; b-dataq.col=a.datap.row; b-dataq.e=a.datap.e; positioncol+;算法(二)fasttransposetsmatrix(tsmartrix a, tsmatrix *b) int col,t,p,q;int positionmaxsize;b-len=a.len; b-n=a.m; b-m=a.n;if(b-len0) for(col=1;col=a.n;col+) positioncol=0; for(t=1;t0;col-) t=t-positioncol; positioncol=t+1;

6、for(p=1;pdataq.row=a.datap.col; b-dataq.col=a.datap.row; b-dataq.e=a.datap.e; positioncol+;5.6画出下面广义表的两种存储结构图示： (a), b), ( ), d), (e, f)【解答】第一种存储结构 第二种存储结构5.7求下列广义表运算的结果：（1） head(a,b),(c,d); (a,b)（2） tail(a,b),(c,d); (c,d) （3） tailhead(a,b),(c,d); (b)（4） headtailhead(a,b),(c,d); b（5） tailheadtail(a,

7、b),(c,d); (d)提示：第五章 数组和广义表习 题1 假设有6行8列的二维数组a，每个元素占用6个字节，存储器按字节编址。已知a的基地址为1000，计算：（1） 数组a共占用多少字节； （288）（2） 数组a的最后一个元素的地址； （1282）（3） 按行存储时，元素a36的地址； （1126）（4） 按列存储时，元素a36的地址； （1192）注意：本章自定义数组的下标从1开始。2 设有三对角矩阵（aij）nn ,将其三条对角线上的元素逐行地存于数组b(1:3n-2)中，使得bk= aij ，求：（1） 用i,j表示k的下标变换公式；（2） 用k表示i,j的下标变换公式。 i =

8、k/3 + 1, j = k%3 + i - 1 = k%3 + k/3 或：i = k/3 + 1, j = k - 2( k/3 )2 假设稀疏矩阵a和b均以三元组表作为存储结构。试写出矩阵相加的算法，另设三元组表c存放结果矩阵。提示：参考p.28例、p.47例。4在稀疏矩阵的快速转置算法5.2中，将计算positioncol的方法稍加改动，使算法只占用一个辅助向量空间。提示：（1） position k 中为第k列非零元素个数，k = 1, 2, , n（2） position 0 = 1; （第1列中第一个非零元素的正确位置）（3） position k = position k 1

9、+ position k , k = 1, 2, , n（4） position k = position k 1 , k = n, n 1 , ,15写一个在十字链表中删除非零元素aij的算法。提示：“删除”两次，释放一次。6画出下面广义表的两种存储结构图示： (a), b), ( ), d), (e, f)第一种存储结构（自底向上看）7求下列广义表运算的结果：（1） head(a,b),(c,d);（2） tail(a,b),(c,d);（3） tailhead(a,b),(c,d);（4） headtailhead(a,b),(c,d); b（5） tailheadtail(a,b),(c,d); (d)参考题8试设计一个算法，将数组a（0:n-1）中的元素循环右移k位，并要求只用一个元素大小的附加存储，元素移动或交换次数为o(n)。9假设按低下标优先（以最左的下标为主序）存储整数数组a（1:8, 1:2, 1:4, 1:7）时，第一个元素的字节地址是100，每个整数占4个字节，问元素a(4, 2, 3, 5)的存储地址是什么？10. 高下标优先（以最右的下标为主序）存储整数数组a（1:8, 1:2,