数据结构习题及答案 4文档格式.docx
《数据结构习题及答案 4文档格式.docx》由会员分享，可在线阅读，更多相关《数据结构习题及答案 4文档格式.docx（14页珍藏版）》请在冰点文库上搜索。
（C）元素之间具有分支层次关系的数据（D）元素之间无联系的数据
13.任何一棵二叉树的叶结点在先序、中序和后序遍历序列中的相对次序（）
（A）不发生改变（B）发生改变（C）不能确定D.以上都不对
14.实现任意二叉树的后序遍历的非递归算法而不使用栈结构,最佳方案是二叉树采用（）存储结构。
（A）二叉链表（B）广义表存储结构（C）三叉链表（D）顺序存储结构
15.对一个满二叉树,m个树叶,n个结点,深度为h,则（）
（A）n=h+m（B）h+m=2n（C）m=h-1（D）n=2h-1
16.如果某二叉树的前序为stuwv,中序为uwtvs,那么该二叉树的后序为（）
（A）uwvts（B）vwuts（C）wuvts（D）wutsv
17.具有五层结点的二叉平衡树至少有（）个结点。
（A）10（B）12（C）15（D）17
二、判断题
1.二叉树中任何一个结点的度都是2。
（ ）
2.由二叉树结点的先根序列和后根序列可以唯一地确定一棵二叉树。
（ ）
3.一棵哈夫曼树中不存在度为1的结点。
4.平衡二叉排序树上任何一个结点的左、右子树的高度之差的绝对值不大于2（ ）
1×
2×
3√4√
三、填空题
1.指出树和二叉树的三个主要差别___________,___________,_______________。
①树的结点个数至少为1，而二叉树的结点个数可以为0；
②树种结点的最大读书没有限制，而二叉树结点的最大度数不能超过2；
③树的结点无左右之分，而二叉树的结点有左右之分。
2.从概念上讲,树与二叉树是两种不同的数据结构,将树转化为二叉树的基本目的是____________
树可采用二叉树的存储结构并利用二叉树的已有算法解决树的有关问题。
3.若结点A有三个兄弟（包括A本身）,并且B是A的双亲结点,B的度是_______________
4
4.若一棵具有n个结点的二叉树采用标准链接存储结构,那么该二叉树所有结点共有_______个空指针域。
n+1
5.已知二叉树的前序序列为ABDEGCFHIJ,中序序列为DBGEAHFIJC,写出后序序列_______________。
DGEBHJIFCA
6.已知二叉树的后序序列为FGDBHECA,中序序列为BFDGAEHC,并写出前序序列_________________。
ABDEGCEH
7.找出满足下列条件的二叉树
1）先序和中序遍历，得到的结点访问顺序一样。
_________________________
2）后序和中序遍历，得到的结点访问顺序一样。
3）先序和后序遍历，得到的结点访问顺序一样。
__________________________
①无左子树②无右子树③仅一个结点的二叉树
8.一棵含有n个结点的k叉树，可能达到的最大深度和最小深度各是多少？
____________________
最大n,最小┕log2n┙+1
9.一棵二叉树有67个结点，这些结点的度要么是0，要么是2。
这棵二叉树中度为2的结点有______________________个。
22
10.含有100个结点的树有_______________________________________条边。
99
四、问答题
1.一棵深度为h的满m叉树具有如下性质:
第h层上的结点都是叶结点,其余各层上每个结点都有m棵非空子树。
若按层次从上到下,每层从左到右的顺序从1开始对全部结点编号,试计算:
（1）第k层结点数（1≤k≤h）。
（2）整棵树结点数。
（3）编号为i的结点的双亲结点的编号。
（4）编号为i的结点的第j个孩子结点（若有）的编号。
答：
（1）mk-1
（2）（mh-1）/（m-1）
（3）i=1时，该结点为根，无双亲结点；
否则其双亲结点的编号为（i+m-2）/m
（4）编号为i的结点的第j个孩子结点（若有）的编号为i*m+（j-（m-1））
2.证明：
一个满k叉树上的叶子结点数n0和非叶子结点数n1之间满足以下关系：
n0=（k-1）n1+1
证明：
设树结点为n,则n=n0+n1
因是满k叉树,每个非叶子结点引出k个分支，故有k*n1个分支。
除根外，每个分支引出一个结点，则树共有k*n1+1个结点。
所以n0+n1=k*n1+1
n0=（k-1）*n1+1
3.已知一组元素为（50,28,78,65,23,36,13,42,71）,请完成以下操作:
（1）画出按元素排列顺序逐点插入所生成的二叉排序树BT。
（2）分别计算在BT中查找各元素所要进行的元素间的比较次数及平均比较次数。
（3）画出在BT中删除（23〉后的二叉树。
4.有七个带权结点,其权值分别为3,7,8,2,6,10,14,试以它们为叶结点构造一棵哈夫曼树（请按照每个结点的左子树根结点的权小于等于右子树根结点的权的次序构造〉,并计算出带权路径长度WPL及该树的结点总数。
5.有一电文共使用五种字符a,b,c,d,e,其出现频率依次为4,7,5,2,9。
（1）试画出对应的编码哈夫曼树（要求左子树根结点的权小于等于右子树根结点的权）。
（2）求出每个字符的晗夫曼编码。
（3）求出传送电文的总长度。
（4）并译出编码系列1100011100010101的相应电文。
五、算法设计
已知一棵具有n个结点的完全二叉树被顺序存储在一维数组A[n]中,试编写一个算法输出A[i]结点的双亲和所有孩子。
voidparent（inta[],intn,inti）
{
if（i==1）
{
printf（"
无双亲\n"
）;
return;
}
Else
printf（"
双亲:
%d\n"
a[（i-1）/2]）;
voidchild（inta[],intn,inti）/*i为序号*/
intqueue[MAX],front=0,tail=0,p;
/*队列作为辅助，存储孩子的序号*/
queue[0]=i;
tail++;
while（front<
tail）
p=queue[front++];
if（p!
=i）
%d"
a[p-1]）;
/*自身不输出*/
if（2*p<
=n）
queue[tail++]=2*p;
if（2*p+1<
=n）queue[tail++]=2*p+1;
}
main（）
inta[MAX],n,i;
请输入二叉树的结点个数:
"
scanf（"
%d"
&
n）;
input（a,n）;
请输入i:
i）;
parent（a,n,i）;
child（a,n,i）;
二叉树其他运算的算法（只作参考）
#include"
stdio.h"
malloc.h"
typedefstructnode
chardata;
structnode*lchild,*rchild;
}NODE;
NODE*T;
voidcreate（NODE**T）//创建二叉树
{charch;
ch=getchar（）;
if（ch=='
'
）*T=NULL;
else
{*T=（NODE*）malloc（sizeof（NODE））;
（*T）->
data=ch;
create（&
（（*T）->
lchild））;
rchild））;
}}
voidinorder（NODE*p）//中序编历二叉树
{if（p!
=NULL）
{inorder（p->
lchild）;
%c"
p->
data）;
inorder（p->
rchild）;
intnum=0;
voidcount（NODE*p）//统计出二叉树中单孩子的结点数方法1
count（p->
if（p->
lchild!
=NULL&
&
p->
rchild==NULL||p->
lchild==NULL&
rchild!
num++;
voidcount1（NODE*p,int*num1）
count1（p->
lchild,num1）;
（*num1）++;
rchild,num1）;
intonechild（NODE*t）//统计出二叉树中单孩子的结点数方法2
intnum1,num2;
if（t==NULL）return（0）;
elseif（t->
t->
=NULL||t->
rchild==NULL）
return（onechild（t->
lchild）+onechild（t->
rchild）+1）;
num1=onechild（t->
num2=onechild（t->
return（num1+num2）;
intsum（NODE*t）//统计出二叉树中所有结点数
{if（t==NULL）return（0）;
else
return（sum（t->
lchild）+sum（t->
intleaf（NODE*t）//统计出二叉树中叶子结点数
if（t==NULL）return（0）;
if（t->
rchild==NULL）
return（leaf（t->
lchild）+leaf（t->
else
voidpreorder1（NODE*root）//非递归二叉树前序编历
{NODE*p,*s[100],*q;
//q为p的双亲结点
inttop=0;
//top为栈顶指针
p=root;
q=p;
while（（p!
=NULL）||（top>
0））
{while（p!
{printf（"
s[++top]=p;
p=p->
lchild;
p=s[top--];
rchild;
}}
voiddelk（NODE**root,chark）//删去并释放数据值为k的叶结点
if（（*root）==NULL）return;
if（（*root）->
lchild==NULL&
（*root）->
rchild==NULL&
data==k）{*root=NULL;
return;
p=*root;
{
while（p!
if（p->
rchild==NULL&
data==k）
{if（q->
lchild==p）q->
lchild=NULL;
elseq->
rchild=NULL;
free（p）;
q=p;
p=p->
voidlev_traverse（NODE*T）//按层次从上到下,每层从右到左的顺序列出二叉树所有结点的数据信息
{NODE*q[100],*p;
inthead,tail;
q[0]=T;
head=0;
tail=1;
while（head<
{p=q[head++];
%c"
q[tail++]=p->
intdepth（NODE*t）//求二叉树的深度
if（t->
lchild==NULL&
rchild==NULL）return
（1）;
num1=depth（t->
lchild）;
num2=depth（t->
rchild）;
if（num1>
num2）
return（num1+1）;
return（num2+1）;
intonechild3（NODE*root）//非递归统计出二叉树共有多少个度为1的结点
{NODE*p,*s[100];
inttop=0,num=0;
p=root;
while（（p!
{while（p!
{if（p->
rchild==NULL||p->
s[++top]=p;
p=s[top--];
returnnum;
intlike（NODE*t1,NODE*t2）//判定两颗二叉树是否相似
intlike1,like2;
if（t1==t2&
t2==NULL）return
（1）;
if（t1==NULL&
t2!
=NULL||t1!
t2==NULL）return（0）;
like1=like（t1->
lchild,t2->
like2=like（t1->
rchild,t2->
return（like1&
like2）;
chara[100];
//数组顺序存储二叉树
voidchange（NODE*t,inti）//将二叉树的链接存储转换为顺序存储
if（t!
=NULL）
{a[i]=t->
data;
change（t->
lchild,2*i）;
rchild,2*i+1）;
intcomplete（NODE*t）//判断二叉树是否为完全二叉树
inti,flag=0;
change（t,1）;
for（i=1;
i<
100;
i++）
{if（!
flag&
a[i]=='
\0'
）flag=1;
if（flag&
a[i]!
='
）break;
if（i==100）return
（1）;
elsereturn（0）;
升级会员 