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 在稀疏矩
2、阵的快速转置算法 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
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的方法稍加改动，使算法只占用一个辅助向量空间。【解答】算法（一）FastTransposeTSMatr
4、ix(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;tdataq.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
5、,q;int positionMAXSIZE;B-len=A.len; B-n=A.m; B-m=A.n;if(B-len0)for(col=1;col0;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
6、,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
7、 的地址； （ 1192）注意 ：本章自定义数组的下标从 1 开始。2 设有三对角矩阵（a ij） 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在稀疏矩阵
8、的快速转置算法 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 , ,1 5写一个在十字链表中删除非零元素 aij 的算法。提示 ：“ 删除”两次，释放一次。6画出下面广义表的两种存储结
9、构图示：(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, 1:4, 1:7）时，顺序列出数组 A 的所有元素。11试编写一个以三元组形式输出用十字链表表示的稀疏矩阵中非零元素及其下标的算法。实习题1 若矩阵 Amn 中的某个元素 aij 是第 i 行中的最小值，同时又是第 j 列中的最大值，则称此元素为该矩阵中的一个马鞍点。假设以二维数组存储矩阵，试编写算法求出矩阵中的所有马鞍点。
