数据结构——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.画出与下列已知序列对应的树T:

树的先根次序访问序列为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; }

联系客服:779662525#qq.com(#替换为@)