数据结构C语言描述耿国华习题及答案 - 图文 下载本文

内容发布更新时间 : 2024/12/23 22:28:19星期一 下面是文章的全部内容请认真阅读。

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); }