5.1假设有6行8列的二维数组A，每个元素占用6个字节，存储器按字节编址。已知A的基地址为1000，计算：
数组A共占用多少字节； 数组A的最后一个元素的地址； 按行存储时元素A 36的地址； 按列存储时元素A 36的地址；
5.2设有三对角矩阵A
n×n,将其三条对角线上的元素逐行地存于数组B(1:3n-2)中，使得B[k]= a ij，求：
（1）用i,j表示k的下标变换公式； （2）用k表示i,j的下标变换公式。
5.3假设稀疏矩阵A和B均以三元组表作为存储结构。试写出矩阵相加的算法，另设三元组表C存放结果矩阵。
5.4在稀疏矩阵的快速转置算法
5.2中，将计算position[col]的方法稍加改动，使算法只占用一个辅助向量空间。 5.5写一个在十字链表中删除非零元素a
1 / 10
ij的算法。
5.6画出下面广义表的两种存储结构图示： ((((a), b)), ((( ), d), (e, f))) 5.7求下列xx表运算的结果： （1）HEAD[((a,b),(c,d))]; （2）TAIL[((a,b),(c,d))]; （3）TAIL[HEAD[((a,b),(c,d))]]; （4）HEAD[TAIL[HEAD[((a,b),(c,d))]]]; （5）TAIL[HEAD[TAIL[((a,b),(c,d))]]]; 若矩阵A
m×n中的某个元素a
ij是第i行中的最小值，同时又是第j列中的最大值，则称此元素为该矩阵中的一个马鞍点。假设以二维数组存储矩阵，试编写算法求出矩阵中的所有马鞍点。
第五章答案
5.2设有三对角矩阵A
n×n,将其三条对角线上的元素逐行的存于数组B[ 1..3n-2]中，使得B[k]=a ij，求：
2 / 10
（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中，将计算position[col]的方法稍加改动，使算法只占用一个辅助向量空间。 【解答】算法 （一）
FastTransposeTSMatrix(TSMartrixA,TSMatrix*B)
{/*把矩阵A转置到B所指向的矩阵中去，矩阵用三元组表表示*/ int col,t,p,q;
int position[MAXSIZE]; B->len= A.len;B->n= A.m;B->m= A.n;
3 / 10
if(B->len>0){position[1]=1; for(t=1;t<= A.len;t++) position[
A.data[t].col+1]++;/*position[col]存放第col-1列非零元素的个数,即利用pos[col]来记录第col-1列中非零元素的个数*/
/*求colxx第一个非零元素在
B.data[ ]的位置，存放在position[col]中*/for(col=2;col<= A.n;col++)
position[col]=position[col]+position[col-1]; for(p=1;p< A.len;p++) q=position[col]; B->data[q].row= A.data[p].col; B->data[q].col= A.data[p].row; B->data[q].e=
4 / 10
A.data[p].e;
Position[col]++;}}}算法 (二)
FastTransposeTSMatrix(TSMartrixA,TSMatrix*B){int col,t,p,q; int position[MAXSIZE]; B->len= A.len;B->n= A.m;B->m= A.n;
if(B->len>0){for(col=1;col<= A.n;col++) position[col]=0; for(t=1;t<= A.len;t++) position[
A.data[t].col]++;/*计算每一列的非零元素的个数*/ /*从最后一列起求每一列中第一个非零元素在
5 / 10
B.data[]中的位置，存放在position[col]中*/for(col= A.n,t=
A.len;col>0;col--) {t=t-position[col]; for(p=1;p< A.len;p++){col= A.data[p].col; q=position[col]; B->data[q].row= A.data[p].col; B->data[q].col= A.data[p].row; B->data[q].e= A.data[p].e; Position[col]++;}}}
5.6画出下面广义表的两种存储结构图示：((((a), b)), ((( ), d), (e, f)))
6 / 10
【解答】
第二种存储结构
5.7求下列xx表运算的结果： （1）HEAD[((a,b),(c,d))];(a,b) （2）TAIL[((a,b),(c,d))];((c,d)) （3）TAIL[HEAD[((a,b),(c,d))]];(b) （4）HEAD[TAIL[HEAD[((a,b),(c,d))]]];b （5）TAIL[HEAD[TAIL[((a,b),(c,d))]]];(d) 提示：
第五章数组和xx表 习题
1．假设有6行8列的二维数组A，每个元素占用6个字节，存储器按字节编址。 已知A的基地址为1000，计算： （1）数组A共占用多少字节； （288）
（3）按行存储时，元素A 36的地址；
7 / 10
（1126）
（4）按列存储时，元素A 36的地址； （1192） [注意]：
本章自定义数组的下标从1开始。 2．设有三对角矩阵（a ij）
n×n,将其三条对角线上的元素逐行地存于数组B(1:3n-2)中，使得B[k]= a ij，求：
（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存放结果矩阵。
[提示]：
8 / 10
参考P.28例、P.47例。 4．在稀疏矩阵的快速转置算法
5.2中，将计算position[col]的方法稍加改动，使算法 只占用一个辅助向量空间。 [提示]：
（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．写一个在十字链表中删除非零元素a ij的算法。 [提示]：
“删除”两次，释放一次。
6．画出下面xx表的两种存储结构图示： ((((a), b)), ((( ), d), (e, f))) 第一种存储结构（自底向上看） （1）HEAD[((a,b),(c,d))]; （2）TAIL[((a,b),(c,d))];
9 / 10
（3）TAIL[HEAD[((a,b),(c,d))]];
（4）HEAD[TAIL[HEAD[((a,b),(c,d))]]];b （5）TAIL[HEAD[TAIL[((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．试编写一个以三元组形式输出用十字链表表示的稀疏矩阵中非零元素及其下标的算法。则称此元素为该矩阵中的一个马鞍点。假设以二维数组存储矩阵，试编写算法求出矩阵中的所有马鞍点。
10 / 10
因篇幅问题不能全部显示，请点此查看更多更全内容