第5章 综合练习
5.2综合练习
1.
已知二维数组A[1..4,1..6]，其每个元素占3个存储单元，并且A[1,1]的存储地址为1200。试求元素A[2,4]的存储地址（分别对以行序和列序为主序存储时进行讨论），该数组共占用多少个存储单元？
解答:
公式: LOC(i,j)=LOC(c1,c2)+[(i-c1)*(d2-c2+1)+(j-c2)]*L
以行序为主:LOC(A[2,4])=1200+[(2-1)*6+(4-1)]*3=1227
以列序为主:
LOC(A[2,4])=1200+[(4-1)*4+(2-1)]*3=1239
2.
有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主序存储，A[1,1]为第一元素，其存储地址为1，每个元素占一个地址空间，求A[7,5]和A[5,6]的地址。
解答:
公式:
k=
LOC(A[7,5])=7(7-1)/2+5=26
LOC(A[5,6])=5(5-1)/2+6=16
3.
计算数组A[3..8，2..6]在内存中按行优先存放和按列优先存放时，元素A[i,j]的地址计算公式（设每个元素占两个存储单元）。
解答:
公式: LOC(i,j)=LOC(c1,c2)+[(i-c1)*(d2-c2+1)+(j-c2)]*L
以行序为主:LOC(A[i,j])= LOC(A[3,2])+[(i-3)*5+(j-2))*2
以列序为主: LOC(A[i,j])=
LOC(A[3,2])+[(j-2)*6+(i-3))*2
4.
求下标按行优先存储的四维数组顺序存储的地址计算公式。
解答:
LOC(i,j,k,l)=
LOC(c1,c2,c3,c4)+[(i-c1)*(d2-c2+1)*(d3-c3+1)*(d4-c4+1)+(j-c2)*(d3-c3+1)*(d4-c4+1)+
+(k-c3)*(d4-c4+1)+(l-c4)]*L
5.
设有一个二维数组A[m][n]，假设A[0][0]存放位置在644，A[2][2]存放位置在676，每个元素占一个空间，问A[3][3]存放在什么位置？
解答:
因为A[0][0]存放位置在644，A[2][2]存放位置在676，每个元素占一个空间,676-644+1=33, A[2][2]是该行第3个元素, 所以每行15个元素,故A[3][3]的存放在什么位置是692.
6.
将一个A[1..100，1..100]的三对角矩阵，按行优先存入一维数组B[1..m]中，试确定m的值，并求A中元素A[77,78]（即元素下标i=77，j=78）在B数组中的位置K。
解答:
m=100*3-2=292;
A[77,78]（即元素下标i=77，j=78）在B数组中的位置K=2+75*3+3=230
7.
设有一个n´n的对称矩阵A[0..n-1,0..n-1]，为了节约存储，可以只存对角线及对角线以上的元素，或者只存对角线或对角线以下的元素。我们把它们按行存放于一个一维数组B中，称之为对称矩阵A的压缩存储方式。试问：
(1)
存放对称矩阵A上三角部分或下三角部分的一维数组B有多少元素？
(2)
若在一维数组B中从0号位置开始存放，则对称矩阵中的任一元素aij在只存下三角部分的情形下应存于一维数组的什么下标位置？给出计算公式。
(3)
若在一维数组B中从0号位置开始存放，则对称矩阵中的任一元素aij在只存上三角部分的情形下应存于一维数组的什么下标位置？给出计算公式。
解答:
(1) 存放对称矩阵A上三角部分或下三角部分的一维数组B的元素个数为: n(n+1)/2
(2) k=
(3) k=
8.
在三对角矩阵中除主对角线及在主对角线上下最临近的两条对角线上的元素外，所有其它元素均为0。现在要将三对角矩阵A中三条对角线上的元素按行存放在一维数组B中，且a11存放于B[0]。试给出计算A在三条对角线上的元素aij （1£ i £ n, i-1 £ j £ i+1）在一维数组B中的存放位置的计算公式。
解答:
k = 3(i-1) (主对角线左下角，即i=j+1)
k = 3(i-1)+1 (主对角线上，即i=j)
k = 3(i-1)+2 (主对角线上，即i=j-1)
由以上三式，得 k=2(i-1)+j-1 (1£i,j£n; 0£k£3n-3)
9.
设有对称矩阵A[1..n,1..n]，将其上三角元素逐行存于数组B[1..m]中，使得B[k]=a[i,j]且k=f1(i)+f2(j)+c。试推导出函数f1,f2和c。
解答:
上三角矩阵第一行有n个元素，第i-1行有n-（i-1）+1个元素，第一行到第i-1行是梯形，而第i行上第j个元素（即aij）是第i行上第j-i+1个元素，故元素Aij在一维数组中的存储位置（下标k）为：
k=(n+(n-(i-1)+1))(i-1)/2+(j-i+1)=(2n-i+2)(i-1)/2+j-i+1
k=（n+1/2）i-i2/2+j-n，
则得f1（i）=（n+1/2）i-i2/2，f2（j）=j，c=-n。
10.
设A和B均为下三角矩阵，每一个都有n行。因此在下三角区域中各有n（n+1）/2个元素。另设有一个二维数组C，它有n行n+1列。试设计一个方案，将两个矩阵A和B中的下三角区域元素存放于同一个C中。要求将A的下三角区域中的元素存放于C的下三角区域中，B的下三角区域中的元素转置后存放于C的上三角区域中。并给出计算A的矩阵元素aij和B的矩阵元素bij在C中的存放位置下标的公式。
解答:
for (i=0;i<n;i++)
{for (j=0;j<=i;j++)
C[i][j]=A[i][j];
for
(j=i+1;j<=n;j++)
C[i][j]=B[j-1][i];
}
例:A=
B=
C=
A的矩阵元素aij和B的矩阵元素bij在C中的存放位置下标的公式:
A[i][j]=C[i][j]; { 0<=i <n, 0<=j<=i}
B[i][j]=C[j][i+1]; { 0<=i <n, i<=j<=n}
11.
有一个100*90的稀疏矩阵，非零元素有10个，设每个整型数占2字节，则用三元组表示该矩阵时，所需的字节数是多少？
解答: 非零元素有10个，占10个三元组, 行数、列数、和非零元个数占1个三元组
10*3*2+1*3*2=66
12.
求广义表D=(a,(b,( ),c),((d),e))的长度和深度。
解答：长度=3； 深度=3
13.
设广义表L=(( ),( )),试问GetHead(L)，GetTail(L)的值，求L的长度，深度各为多少?
解答： GetHead(L)=（）； GetTail(L)=（（））
14 求下列广义表运算的结果：
(1)
GetHead ((p,h,w))=p
(2)
GetTail((b,k,p,h))=(k,p,h)
(3)
GetHead(GetTail(((a,b),(c,d))))= (c,d)
15.利用广义表的GetHead和GetTail操作写出函数表达式，把以下各题中的单元素banana从广义表中分离出来：
(1)
(apple, pear, banana, orange)
(2)
((apple, pear), (banana, orange))
(3)
((((apple))), ((pear)), (banana),
orange)
(4) (apple,
(pear, (banana), orange))
解答：
(1) H(T(T((apple, pear, banana,
orange))))
(2) H(H(T(((apple, pear),
(banana, orange)))))
(3) H(H(T(T(((((apple))),
((pear)), (banana), orange)))))
(4) H(H(T(H(T((apple, (pear,
(banana), orange)))))))
17. 有三对角矩阵 A[n,n]，将其三条对角线上的元素逐行地存储到向量B[0..3n-3]中，使得B[k]=aij，写一算法求三对角矩阵在这种压缩存储表示下的转置矩阵。
解答： i=(k+1)/3;
j=k-2((k+1)/3)
语句段如下：
for (k=0; k<=3*n-3;k++)
{
i=(k+1)/3;
j=k-2((k+1)/3);
C[j][i]=B[k]; //C是A的转置矩阵
}
18. 编写递归算法，逆转广义表中的数据元素（广义表结点的存储结构采用扩充线性链表结构）。例如：将广义表：(a,((b,c),( )),(((d),e),f))逆转为：((f,(e,(d))),(( ),(c,b)),a)。
void reverse (Glist p,t)
{ Glist q,s,r;
q=null;
while
(p!=null)
{if (p->tag!=0)
{s=p->hp;
reverse(s,r);
p->hp=r;
}
r=p->next; //暂存下一元素指针
p->next=q; //逆置
q=p;
p=r; //恢复下一待逆置元素
}
t=q;
}