第5章参考答案08Word文件下载.docx
- 文档编号:8106160
- 上传时间:2023-05-10
- 格式:DOCX
- 页数:30
- 大小:209.82KB
第5章参考答案08Word文件下载.docx
《第5章参考答案08Word文件下载.docx》由会员分享,可在线阅读,更多相关《第5章参考答案08Word文件下载.docx(30页珍藏版)》请在冰点文库上搜索。
5.某二叉树T有n个结点,设按某种顺序对T中的每个结点进行编号,编号值为1,2,…,n,且有如下性质:
T中任意结点v,其编号等于左子树上的最小编号减1,而v的右子树的结点中,其最小编号等于v左子树上结点的最大编号加1。
这是按(B)编号的。
A.中序遍历序列B.先序遍历序列.C.后序遍历序列D.层次顺序
6.设F是一个森林,B是由F转换得到的二叉树,F中有n个非终端结点,B中右指针域为空的结点有(C)个。
A.n-1B.nC.n+1D.n+2
7.一棵完全二叉树上有1001个结点,其中叶子结点的个数是(C)。
A.500B.501C.490D.495
8.设森林F中有3棵树,第一,第二,第三棵树的结点个数分别为N1,N2和N3。
与森林F对应的二叉树根结点的右子树上的结点个数是(D)。
A.N1B.N1+N2C.N2D.N2+N3
9.任何一棵二叉树的叶结点在先序、中序、后序遍历序列中的相对次序(A)。
A.不发生改变B发生改变C.不能确定D:
以上都不对
10.若一棵二叉树的后序遍历序列为dabec,中序遍历序列为debac,则先序遍历序列为(D)。
A.cbedB.decabC.deabcD.cedba
11.若一棵二叉树的先序遍历序列为abdgcefh;
中序遍历的序列为dgbaechf,则后序遍霎
历的结果为(D)。
A.gcefhaB.gdbecfhaC.bdgaechfD.gdbehfca
12.一棵非空二叉树的先序遍历序列与后序遍历序列正好相反,则该二叉树一定满
足(B)。
A.所有的结点均无左孩子B.所有的结点均无右孩子
C.只有一个叶子结点D.是一棵满二叉树
13.引人线索二叉树的目的的是(A
A:
加快查找结点的前驭或后继的速度;
B.为了能在二叉树中方便地进行插人与侧除;
C.为了能方便地找到双亲;
D.使二叉树的遍历结果唯-;
14:
设高度为h的二叉树上只有度为0和度为2的结点,则此类二叉树中所包含的结点
数至少为(B)。
A.2h2h-1C.2h+1D.h+1
15.一个具有567个结点的二叉树的高h为(D)。
“
A.9B:
10C:
9~566之间D.10~567之间
16.给定一个整数集合{3,5,6,7,9},与该整数集合对应的哈夫曼树是图中的(B)
ABCD
二,判断题
×
√
16
17
18
19
20
1.二叉树是树的特殊形式。
(√)
2.由树转换成二叉树,其根结点的右子树总是空的。
3.先根遍厉,棵树和先序遍历与该树对应的二叉树,其结果不同。
(x)
4.先根遍历森林和先序遍历与该森林对应的二叉树,其结果不同。
5.完全二叉树中,若一个结点没有左孩子,则它必是叶子。
6.对于有N个结点的二叉树,其高度为「log,N」+1(х)
7.若一个结点是某二叉树子树的中序遍历序列中的最后一个结点,则它必是该子树的先序遍历序列中的最后一个结点。
(х)
8.若一个结点是某二叉树子树的中序遍历序列中的第一个结点,则它必是该子树的后
序遍历序列中的第一个结点。
9.不使用递归也可实现二叉树的先序、一中序和后序遍历。
10.先序遍历二叉树的序列中,任何结点的子树的所有结点不一定跟在该结点之后。
11.先序和中序遍历用线索树方式存储的二叉树,不必使用栈。
12.在后序线索二叉树中,在任何情况下都能够很方便地找到任意结点的后继。
13.哈夫曼树是带权路径长度最短的树,路径上权值较大的结点离根较近。
14.在哈夫曼编码中,出现频率相同的字符编码长度也一定相同(x)
15.用一维数组存放二叉树时,总是以先序遍历存储结点。
16.由先序序列和后序序列能唯一确定一棵二叉树。
17.由先序序列和中序序列能唯一确定一棵二叉树。
18.对一棵二叉树进行层次遍历时,应借助于一个栈。
19.完全二叉树可采用顺序存储结构实现存储,非完全二叉树则不能。
20.满二叉树一定是完全二叉树,反之未必。
三问答题
1.一棵度为2的树与一棵二叉树有何区别?
树与二叉树之间有何区别?
答:
度为2的树至少有一个节点的读为2,二叉树的度不一定为2;
该树不空,二叉树空以空;
树分为有序树和无序树,二叉树是有序的;
二叉树有左右孩子,而树没有;
二叉树度为0~2,而树的度是大于等于0
区别:
度为2的树有二个分支,没有左右之分;
二叉树也有两个分支,但有左右之分,且左右不能交换。
2.对于图5.38所示二叉树,试给出:
(1)它的顺序存储结构图。
E
F
∧
G
H
(2)二叉链表存储结构示意图
3双亲数组表示法:
-1
I
J
K
M
N
4.无孩子且无兄弟结点是叶结点。
6.证明:
在结点数多于1的哈夫曼树中不存在度为1的结点。
在哈夫曼树的构造过程中,每次都是由两个权最小的结点构成一个父结点,即任一父结点都有两个子结点,故命题成立。
7.证明:
在哈夫曼树中有n个叶结点,则树一共有2n-1结点。
证明:
在二叉树中n0=n2+1,即n2=n0-1而n1=0,这里n0=n
则总结点=n0+n2=n+n-1=2n-1
8.证明由二叉树的先序序列和中序序列可以惟一的确定一棵二叉树。
先序序列的一个结点必然是根结点,而此根结点又将中序序列分成两部分,分别是其左子树和右子树结点,这样递归查找,必然可完成以确定一棵二叉树。
9.已知一棵度为m的树中有n1个度为1的结点,n2个度为2的结点,……,nm个度为m个结点,问,该树共有多少个叶子结点?
多少个非终端结点?
设总结点数为n,该树中共引出的边有:
n1+2*n2+……+m*nm,故结点数n=n1+2*n2+……+m*nm+1
非终端结点数:
s=n1+n2+……+nm
叶子结点p=n-s=n1+2*n2+……+m*nm+1-n1+n2+……+nm
=n2+……+(m-1)*nm
10.在具有n(n>
1)个结点的树中,深度最小的那棵树的度是多少?
它共有多少叶子和非叶子结点?
深度最大的那棵树的度是多少?
深度最小的那棵树的度是2,n-1个叶子和1个非叶子结点。
深度最大的那棵树的度是n,1个叶子和n-1个非叶子结点。
11.设度为h的二叉树上只有度为0和度为2的结点,问该二叉树的结点数可能达到的最大值和最小值。
结点数最大值:
2h-1
最小值:
12.求表达式(a+b*(c-d)-e/f的波兰式(前缀式)和逆波兰式(后缀式)
-+a*b-cd/ef
abcd-*+ef/-
13.画出和下面已知序列对应的树
树的先根次序访问次序为:
GFKDAIEBCHJ
树的后根次序访问次序为:
DIAEKFCJHBG
解:
根据树与二叉树的转换关系以及树和二叉树的遍历定义可以推知,树的先根遍历与其转换的相应二叉树的先序遍历的结果序列相同;
树的后根遍历与其转换的相应二叉树的中序遍历的结果序列相同。
故可按二叉树的规则建立二叉树,然后转换成树。
二叉树:
13.画出和下面已知序列对应的森林
森林的先根次序访问次序为:
ABCDEFGHIJKL
森林的后根次序访问次序为:
CBEFDGAJIKLH
根据森林与二叉树的转换关系以及森林和二叉树的遍历定义可以推知,森林的前序遍历和中序遍历与所转换的二叉树的先序遍历和中序遍历的结果序列相同。
先画出二叉树→森林
15.画出和下面已知序列对应的树T
二叉树的层次访问次序为:
二叉树的中序访问次序为:
16.假设用于通信的电文字符集{a,b,c,d,e,f,g,}中的字母构成,这7个字母在电文中出现的概率分别为{0.31,0.16,0.10,0.08,0.11,0.20,0.04}
(1)为这7个字母设计哈夫曼编码。
(2)对这7个字母进行等长编码,至少需要几位二进制数?
哈夫曼编码比等长编码使电文总长平均压缩多少?
①
a
b
c
d
e
f
g
00
011
110
1110
010
1111
0.31
0.16
0.10
0.08
0.11
0.20
0.04
哈夫曼编码码长:
2*0.31+3*0.16+3*0.10+4*0.08+3*0.11+2*0.20+g*0.04=2.16
等长码长平均缩了13%
四、算法设计题
5-1给定一棵用二叉链表表示的二叉树,其根为root,试写出求二叉树结点数目的算法。
#include"
stdio.h"
alloc.h"
#defineMAXSIZE100
typedefcharelemtype;
typedefstructBiTNode
{elemtypedata;
structBiTNode*lchild;
*rchild;
/*左右孩子指针*/
}BiTNode,*BiTree;
elemtype*s="
ABC00DE0G00F000"
;
intsum=0;
BiTreeCreateBinTree()
{/*以加入结点的先序序列输入,构造二叉链表*/
BiTreeT;
elemtypech;
if(*s=='
\0'
)T=NULL;
ch=*s;
s++;
if(ch=='
0'
/*读入0时,将相应结点置空*/
else{T=(BiTNode*)malloc(sizeof(BiTNode));
/*生成结点空间*/
T->
data=ch;
lchild=CreateBinTree();
/*构造二叉树的左子树*/
rchild=CreateBinTree();
/*构造二叉树的右子树*/
}
returnT;
}
intcount(BiTreeT)
/*统计叶子结点的个数值,递归程序*/
{if(T==NULL)
return0;
/*树空,返回0*/
else
return(count(T->
lchild)+count(T->
rchild)+1)/*树不空,返回子树的结点家1*/
intLeaf2(BiTreeT)
{/*非递归*/
BiTreeSeq[MAXSIZE],p;
intpro=-1,rear=0,sum=0;
if(T==NULL)return0;
p=T;
Seq[rear]=p;
pro++;
while(Seq[pro])
{p=Seq[pro];
if(p->
lchild==NULL&
&
p->
rchild==NULL)sum++;
lchild!
=NULL)Seq[++rear]=p->
lchild;
rchild!
rchild;
returnsum;
voidmain()
{intsum;
BiTreebt;
bt=CreateBinTree();
sum=Leaf2(bt);
printf("
Leafagenum:
%d"
sum);
5.2请设计一个算法,要求该算法把二叉树的叶结点按从左至右的顺序连成一个单链表。
二叉树按lchild,rchild方式存储,连接时用叶结点的rchild域存放链指针。
Linklisthead,per=NULL;
LinklistInorder(BiTree,T)
/*中序遍历二叉树,将叶子结点从左到右链成一个单链表,表头指针为head*/
{if(T)
{Inorder(T->
lchild);
if(T->
T->
rchild==NULL)
if(pre==NULL)
{head=T;
pre=T;
}/*处理第一个叶子结点*/
{pre->
rchild=T;
pre=T;
}/*将个叶子结点插入链表尾*/
Inorder(T->
rchild);
pre->
rchild=NULL;
/*设置表尾结点*/
return;
以上是一个独立的算法
#include"
ABD0G000CE00F00"
BiTreestack[MAXSIZE];
inttop=-1;
voidCreateBinTree(BiTree*T)
/*if(*s=='
)*T=NULL;
*/
else{*T=(BiTNode*)malloc(sizeof(BiTNode));
(*T)->
CreateBinTree(&
((*T)->
lchild));
rchild));
voidPreOrder(BiTreebt)
{/*先序遍历二叉树bt,将叶结点入栈*/
if(bt==NULL)return;
if(bt->
bt->
{stack[++top]=bt;
}/*如果是叶结点,则入栈保存,递归结束*/
PreOrder(bt->
/*先序递归遍历bt的左子树*/
/*先序递归遍历bt的右子树*/
BiTreeLeaflink(BiTreebt)
{/*建立二叉树叶结点链*/
BiTreehead,s;
head=(BiTNode*)malloc(sizeof(BiTNode));
head->
/*建立叶结点链头结点*/
if(bt==NULL)return;
PreOrder(bt);
\n"
);
while(top>
=0)/*当栈非空*/
{s=stack[top--];
/*出栈链*/
s->
rchild=head->
/*插入叶结点链头部*/
rchild=s;
voidInOrderOut(BiTreeT)
/*中序遍历输出二叉树T的结点值*/
{BiTreel,r;
if(T)
{InOrderOut(T->
/*中序遍历二叉树的左子树*/
\n%3c"
T->
data);
/*访问结点的数据*/
InOrderOut(T->
/*中序遍历二叉树的右子树*/
{BiTreebt,s;
bt);
----\n"
InOrderOut(bt);
Leaflink(bt);
5.3给定一棵用二叉链表表示的二叉树,其根指针为root,试写一个求二叉树深度的算法。
inthigh(BiTreeT)
/*求深度算法,递归程序*/
{intn1,n2;
if(T==NULL)
return0;
/*树空,深度为0*/
{n1=high(T->
n2=high(T->
if(n1>
n2)/*树的高度为其最高子树的高度加本层高度*/
return(n1+1);
return(n2+1);
{printf("
/*访问结点的数据*/
{
intn;
n=high(bt);
\nhigh%d"
n);
5.4给定一棵用二叉链表表示的二叉树,其根指针为root,试写一个求二叉树深各结点层数的算法。
intchengci(BiTreeT,intn)
/*统计结点的层数,递归程序*/
{if(T!
=NULL)
{/*非空层数加1*/
\nnode:
%c,cangci:
data,n);
lchild)
chengci(T->
lchild,n+1);
/*左子树不空,递归统计*/
rchild)
rchild,n+1);
/*右子树不空,递归统计*/
chengci(bt,0);
5.5给定一棵用二叉链表表示的二叉树,其根指针为root,试写出将二叉树所有结点的左右子树相互交换的算法。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 参考答案 08