a0000 a1000 a0100 a1100 a0200 a1200 a0010 a1010 a0110 a1110 a0210 a1210 a0001 a1001 a0101 a1101 a0201 a1201 a0011 a1011 a0111 a1111 a0211 a1211 a0002 a1002 a0102 a1102 a0202 a1202 a0012 a1012 a0112 a1112 a0212 a0212 关闭
5.2 给出C语言的三维数组地址计算公式。 解：
因为C语言的数组下标下界是0，所以 Loc(Amnp)=Loc(A000)+((i*n*p)+k)*d
其中 Amnp表示三维数组。Loc(A000)表示数组起始位置。i、j、k表示当前元素的下标,d表示每个元素所占单元数。 关闭
5.3 设有三对角矩阵 An*n，将其三条对角线上的元素逐行地存储到向量B[0...3n-3]中，使得B[k]=aij,求：
(1)用i , j 表示k的下标变换公式。 (2)用 k 表示 i,j 的下标变换公式。 (1) 解：
要求i,j 到k 的下标变换公式，就是要知道在k之前已有几个非零元素，这些非零元素的个数就是k的值，一个元素所在行为i,所在列为j,则在其前面已有的非零元素个数为： (i*3-1)+j-(i+1)
其中 (i*3-1)是这个元素前面所有行的非零元素个数，j-(i+1)是它所在列前面的非零元素个数 化简可得：
k=2i+j; // c下标是从0开始的。 (2) 解：
因为K和i,j是一一对应的关系，因此这也不难算出：
i=(k+1)/3 //k+1表示当前元素前有几个非零元素,被3整除就得到行
号
j=(k+1)%3+(k+1)/3-1 //k+1除以3的余数就是表示当前行中第几个非零元素，
//加上前面的0元素所点列数就是当前列号 关闭
5.4 设二维数组A5*6的每个元素占4个字节，已知Loc(a00)=1000，A共占多少个字节? A的终端结点a45的起始地位为何?按行和按列优先存储时，a25的起始地址分别为何? 解：
(1)因含5*6=30个元素，因此A共占30*4=120个字节。 (2)a45的起始地址为：
Loc(a45)=Loc(a00)+(i*n+j)*d=1000+(4*6+5)*4=1116 (3)按行优先顺序排列时， a25=1000+(2*6+5)*4=1068
(4)按列优先顺序排列时：(二维数组可用行列下标互换来计算) a25=1000+(5*5+2)*4=1108 关闭
5.5 特殊矩阵和稀疏矩阵哪一种压缩存储后会失去随机存取的功能?为什么? 答：
后者在采用压缩存储后将会失去随机存储的功能。因为在这种矩阵中，非零元素的分布是没有规律的，为了压缩存储，就将每一个非零元素的值和它所在的行、列号做为一个结点存放在一起，这样的结点组成的线性表中叫三元组表，它已不是简单的向量，所以无法用下标直接存取矩阵中的元素。 关闭
5.6 简述广义表和线性表的区别与联系。 答:
广义表是线性表的推广，线性表是广义表的特例。当广义表中的元素都是原子时，即为线性表。
关闭
5.7 画出下列广义表的图形表示：
(1) A(a,B(b,d),C(e,B(b,d),L(f,g))) (2) A(a,B(b,A)) 解:
(1)这是一个再入表。(2)则是一个递归表。
5.8 设广义表L=((),()),试问head(L),tail(L),L的长度，深度各为多少?
解：
●head(L)=() ●tail(L)=(()) ●L的长度为2 ●L的深度为2
5.9 求下列广义表运算的结果：
(1)head ((p,h,w)); (2)tail((b,k,p,h)); (3) head (((a,b),(c,d))); (4)tail(((a,b),(c,d))); (5)head(tail(((a,b),(c,d)))); (6)tailhead)(((a,b),(c,d)))). 答：
(1)head ((p,h,w))=p;
(2)tail((b,k,p,h))=(k,p,h); (3)head (((a,b),(c,d)))=(a,b); (4)tail(((a,b),(c,d)))=((c,d));
(5)head(tail(((a,b),(c,d))))=(c,d); (6)tail(head(((a,b),(c,d))))=(b).
5.10 当三角矩阵采用题5.3所述的压缩存储时，写一算法求三对角矩阵在这种压缩存储表示下的转置矩阵。 解：
转置矩阵就是将矩阵元素的行号与列号互换，根据已知的三对角矩阵的特点，其转置矩阵对角线元素不变，非零的非对角线元素aij与aji互换位置。又知元素的下标和存放一维数组空间位置的关系：k=2i+j。我们可以设计出这个矩阵的转置算法：
#define N 10 //矩阵行、列数
#define Length (3*N-2)//压缩矩阵的长度 typedef struct{
int data[Length]; }DiaMatrix;
void TransMatrix(DiaMatrix * C) { //压缩三对角矩阵转置 int i, j; int t;
for(i=0; i
{ //将对应于行列号的压缩矩阵内的元素互换 t=C->data[2*i+j];
C->data[2*i+j]=C->data[2*j+i]; C->data[2*j+i]=t; }//endif }//end
5.11 当稀疏矩阵A和B均以三元组表作为存储结构时，试写出矩阵相加的算法，其结果存放在三元组表C中。
解：
矩阵相加就是将两个矩阵中同一位置的元素值相加。由于两个稀疏矩阵的非零元素按三元组表形式存放，在建立新的三元组表C时，为了使三元组元素仍按行优先排列，所以每次插入的三元组不一定是A的，按照矩阵元素的行列去找A中的三元组，若有，则加入C，同时，这个元素如果在B中也有，则加上B的这个元素值，否则这个值就不变;如果A中没有，则找B，有则插入C，无则查找下一个矩阵元素。
#define MaxSize 10 //用户自定义 typedef int DataType; //用户自定义 typedef struct { //定义三元组 int i,j; DataType v; }TriTupleNode; typedef struct
{ //定义三元组表
TriTupleNode data[MaxSize];
int m,n,t;//矩阵行，列及三元组表长度 }TriTupleTable; //以下为矩阵加算法
void AddTriTuple( TriTupleTable *A, TriTupleTable *B, TriTupleTable *C)
{//三元组表表示的稀疏矩阵A,B相加 int k,l;
DataType temp;
C->m=A->m;//矩阵行数 C->n=A->n;//矩阵列数 C->t=0; //三元组表长度 k=0; l=0;
while (kt&&l
{if((A->data[k].i==B->data[l].i)&&(A->data[k].j==B->data[l].j)) {temp=A->data[k].v+B->data[l].v; if (!temp)//相加不为零，加入C {C->data[c->t].i=A->data[k].i; C->data[c->t].j=A->data[k].j; C->data[c->t++].v=temp; }
k++;l++; } if
((A->data[k].i==B->data[l].i)&&(A->data[k].j
C->data[c->t].j=A->data[k].j; C->data[c->t++].v=A->data[k].v; k++; } if
((A->data[k].i==B->data[l].i)&&(A->data[k].j>B->data[l].j)) ||(A->data[k].i>B->data[l].i)//将B中三元组加入C {C->data[c->t].i=B->data[l].i; C->data[c->t].j=B->data[l].j; C->data[c->t++].v=B->data[l].v; l++; } }
while (kt)//将A中剩余三元组加入C {C->data[c->t].i=A->data[k].i; C->data[c->t].j=A->data[k].j; C->data[c->t++].v=A->data[k].v; k++; }
while (l
第六章 树
6.1.假设在树中，结点x是结点y的双亲时,用(x,y)来表示树边.已知一棵树边的集合为
{(i,m),(i,n),(e,i),(b,e),(b,d),(a,b),(g,j),(g,k),(c,g),(c,f),(h,l),(c,h),(a,c)}用树形表示法出此树，并回答下列问题：
(1)哪个是根结点? (2)哪些是叶结点? (3)哪个是g的双亲? (4)哪些是g的祖先?
(5)哪些是g的孩子? (6)哪些是e的子孙? (7)哪些是e的兄弟?哪些是f的兄弟?
(8)结点b和n的层次各是多少? (9)树的深度是多少? (10)以结点c为根的子树的深度是多少? (11) 树的度数是多少? 答：
a是根结点；
dmnfjkl是叶结点； c是g的双亲；