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

第五章习题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的方法稍加改动，使算法只占用一个辅助向量空间。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列中的最大值，则称此元素为该矩阵中的一个马鞍点。假设以二维数组存储矩阵，试编写算法求出矩阵中的所有马鞍点。第五章答案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 col,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;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;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,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 = 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 + 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,