内容发布更新时间 : 2024/6/29 17:04:13星期一 下面是文章的全部内容请认真阅读。

else {

scanf(\

if(ch=='@') printf(\ else printf(\ } }

12、（1）功能：将栈中元素倒置。 （2）功能：删除栈中的e元素。 （3）功能：将队列中的元素倒置。 第五章习题答案 1、（1）数组A共占用48*6=288个字节； （2）数组A的最后一个元素的地址为1282；

（3）按行存储时loc（A36）=1000+[（3-1）*8+6-1]*6=1126 （4）按列存储时loc（A36）=1000+[（6-1）*6+3-1]*6=1192 9、（1）（a，b）（2）（（c，d））（3）（b）（4）b（5）（d） 10、D

第六章 习题答案

1、三个结点的树的形态有两个；三个结点的二叉树的不同形态有5个。 3、证明：分支数=n1+2n2+…+knk （1） n= n0+n1+…+nk （2）

∵n=分支数+1 （3）

将（1）（2）代入（3）得 n0= n2+2n3+3n4+…+（k-1）nk+1 4、

注：C结点作为D的右孩子（画图的时候忘记了，不好意思） 5、n0=50，n2=n0-1=49，所以至少有99个结点。 6、（1）前序和后序相同：只有一个结点的二叉树 （2）中序和后序相同：只有左子树的二叉树 （3）前序和中序相同：只有右子树的二叉树

7、证明：∵n个结点的K叉树共有nk个链域，分支数为n-1（即非空域）。 ∴空域=nk-（n-1）=nk-n+1 8、对应的树如下：

9、（答案不唯一） 哈夫曼树如下图所示：

哈夫曼编码如下： 频率 编码 0.07 0010 0.19 10 0.02 00000 0.06 0001 0.32 01 0.03 00001 0.21 11 0.10 0011

11、对应的二叉树如下：

12、求下标分别为i和j的两个桔点的最近公共祖先结点的值。 typedef int ElemType;

void Ancestor(ElemType A[],int n,int i,int j) {while(i!=j)

if(i>j) i=i/2;

else j=j/2;

printf(\所查结点的最近公共祖先的下标是%d,值是%d\}

15、编写递归算法，对于二叉树中每一个元素值为X的结点，删去以它为根的子树，并释放相应的空间。

void Del_Sub(BiTree T)

{ if(T->lchild) Del_Sub(T->lchild); if(T->rchild) Del_Sub(T->rchild); free(T); }

void Del_Sub_x(BiTree T,int x) { if(T->data==x) Del_Sub(T); else

{if(T->lchild) Del_Sub_x(T->lchild,x); if(T->rchild) Del_Sub_x(T->rchild,x); } } 22、

int Width(BiTree bt) {if (bt==NULL) return (0); else

{BiTree p,Q[50]; int front=1,rear=1,last=1; int temp=0, maxw=0; Q[rear]=bt; while(front<=last) {p=Q[front++]; temp++;

if (p->lchild!=NULL) Q[++rear]=p->lchild; if (p->rchild!=NULL) Q[++rear]=p->rchild; {last=rear; if(temp>maxw) maxw=temp; temp=0;} }

return (maxw); }