发布时间 : 星期日 文章数据结构——C语言描述课后答案更新完毕开始阅读
的基地址为1000，计算：
（1） 数组A共占用多少字节； （288）
（2） 数组A的最后一个元素的地址； （1282） （3） 按行存储时，元素A36的地址； （1126） （4） 按列存储时，元素A36的地址； （1192） [注意]：本章自定义数组的下标从1开始。
2． 设有三对角矩阵（aij）n×n ,将其三条对角线上的元素逐行地存于数组B(1:3n-2)中，使得B[k]= 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 )
3. 假设稀疏矩阵A和B均以三元组表作为存储结构。试写出矩阵相加的算法，另设三元组表C存放结果矩阵。
void TSMatrix_Add(TSMatrix A,TSMatrix B,TSMatrix &C)//三元组表示的稀疏矩阵加法 {
C.mu=A.mu;C.nu=A.nu;C.tu=0; pa=1;pb=1;pc=1;
for(x=1;x<=A.mu;x++) //对矩阵的每一行进行加法 {
while(A.data[pa].i while(A.data[pa].i==x&&B.data[pb].i==x)//行列值都相等的元素 { if(A.data[pa].j==B.data[pb].j) { ce=A.data[pa].e+B.data[pb].e; if(ce) //和不为0 { C.data[pc].i=x; C.data[pc].j=A.data[pa].j; C.data[pc].e=ce; pa++;pb++;pc++; } }//if else if(A.data[pa].j>B.data[pb].j) { C.data[pc].i=x; C.data[pc].j=B.data[pb].j; C.data[pc].e=B.data[pb].e; pb++;pc++; } else { C.data[pc].i=x; C.data[pc].j=A.data[pa].j; C.data[pc].e=A.data[pa].e pa++;pc++; } }//while while(A.data[pa]==x) //插入A中剩余的元素(第x行) { C.data[pc].i=x; C.data[pc].j=A.data[pa].j; C.data[pc].e=A.data[pa].e pa++;pc++; } while(B.data[pb]==x) //插入B中剩余的元素(第x行) { C.data[pc].i=x; C.data[pc].j=B.data[pb].j; C.data[pc].e=B.data[pb].e; pb++;pc++; } }//for C.tu=pc; }//TSMatrix_Add 4．在稀疏矩阵的快速转置算法5.2中，将计算position[col]的方法稍加改动，使算法 只占用一个辅助向量空间。 5．写一个在十字链表中删除非零元素aij的算法。 [提示]：“删除”两次，释放一次。 6．画出下面广义表的两种存储结构图示： ((((a), b)), ((( ), d), (e, f))) 7．求下列广义表运算的结果： （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))]]]; b （5） TAIL[HEAD[TAIL[((a,b),(c,d))]]]; (d) 实习题 若矩阵Am×n中的某个元素aij是第i行中的最小值，同时又是第j列中的最大值，则称此元素为该矩阵中的一个马鞍点。假设以二维数组存储矩阵，试编写算法求出矩阵中的所有马鞍点。 void Get_Saddle(int A[m][n])//求矩阵A中的马鞍点 { for(i=0;i for(min=A[i][0],j=0;j if(A[i][j] if(A[i][j]==min) //判断这个(些)最小值是否鞍点 { for(flag=1,k=0;k printf(\ } }//for }//Get_Saddle 第六章 数和二叉树 1．试分别画出具有3个结点的树和3个结点的二叉树的所有不同形态。 2．对题1所得各种形态的二叉树，分别写出前序、中序和后序遍历的序列。 3．已知一棵度为k的树中有n1个度为1的结点，n2个度为2的结点，……，nk个度为k的结点，则该树中有多少个叶子结点？ [提示]：参考 P.116 性质3 ∵ n=n0 + n1 + …… + nk B=n1 + 2n2 + 3n3 + …… + knk n= B + 1 ∴ n0 + n1 + …… + nk = n1 + 2n2 + 3n3 + …… + knk + 1 ∴ n0 = n2 + 2n3 + …… + (k-1)nk + 1 4.假设一棵二叉树的先序序列为EBADCFHGIKJ，中序序列为ABCDEFGHIJK，请画出该二叉树。 [提示]：参考 P.148 6． 已知二叉树有50个叶子结点，则该二叉树的总结点数至少应有多少个？ [提示]：一个叶子结点，总结点数至多有多少个？可压缩一度结点。 7． 给出满足下列条件的所有二叉树： a) 前序和中序相同 b) 中序和后序相同 c) 前序和后序相同 [提示]：去异存同。 a) D L R 与L D R 的相同点：D R，如果无 L，则完全相同, 如果无 LR，…。 b) L D R 与L R D 的相同点：L D，如果无 R，则完全相同。 c) D L R 与L R D 的相同点：D，如果无 L R，则完全相同。 （如果去D，则为空树） 7． n个结点的K叉树，若用具有k个child域的等长链结点存储树的一个结点，则空的Child域有多少个？ [提示]：参考 P.119 8．画出与下列已知序列对应的树Ｔ： 树的先根次序访问序列为GFKDAIEBCHJ； 树的后根次序访问序列为DIAEKFCJHBG。 [提示]： （1）先画出对应的二叉树 （2）树的后根序列与对应二叉树的中序序列相同 9．假设用于通讯的电文仅由8个字母组成，字母在电文中出现的频率分别为： 0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10 （1）请为这8个字母设计哈夫曼编码， （2）求平均编码长度。 10．已知二叉树采用二叉链表存放,要求返回二叉树T的后序序列中的第一个结点的指针,是否可不用递归且不用栈来完成?请简述原因. [提示]：无右子的“左下端” 11. 画出和下列树对应的二叉树： 12．已知二叉树按照二叉链表方式存储，编写算法，计算二叉树中叶子结点的数目。 13．编写递归算法：对于二叉树中每一个元素值为x的结点，删去以它为根的子树，并释放相应的空间。 [提示]： [方法1]：（1）按先序查找；（2）超前查看子结点（3）按后序释放； void DelSubTree(BiTree *bt, DataType x) { if ( *bt != NULL && (*bt) ->data==x ) { FreeTree(*bt); *bt =NULL; } else DelTree( *bt, x) void DelTree(BiTree bt, DataType x) { if ( bt ) { if (bt->LChild && bt->LChild->data==x) { FreeTree(bt->LChild); bt->LChild=NULL; } if (bt->RChild && bt->RChild->data==x) { FreeTree(bt->RChild); bt->RChild=NULL; }