数据结构Ch6习题答案.docx
《数据结构Ch6习题答案.docx》由会员分享，可在线阅读，更多相关《数据结构Ch6习题答案.docx（25页珍藏版）》请在冰点文库上搜索。
数据结构Ch6习题答案
、选择题:
下列关于哈夫曼树的叙述，错误的是（C）。
哈夫曼树根结点的权值等于所有叶结点权值之和。
B.
具有n个叶结点的哈夫曼树共有2n-1个结点。
C.
D.
哈夫曼树是一棵二叉树，因此它的结点的度可以为哈夫曼树是带权路径长度最短的二叉树。
0,1,2。
由3个结点可以构成多少棵不同形态的二叉树
2.
（C）。
C,B,A,则该二叉树结点的中序序列是
Ichild指针指示其前驱;
rchild指针指示其后继。
二叉树按某种顺序线索化后，任一结点均有指向其前趋和后继的线索，这种说法正确B.错误若结点有左子树，则令其Ichild指针指示其左孩子；若结点没有左子树，则令其若结点有右子树，则令其rchild指针指示其右孩子；若结点没有右子树，则令其6.二叉树的前序遍历序列中，任意一个结点均处在其子女结点的前面，这种说法
A.正确B.错误7.对一棵70个结点的完全二叉树，它有（A）个叶子结点。
A.35B.40C.30D.44
&设一棵二叉树中，度为
第1层;
第2层:
第』层:
A.10B.11
n0=n2+1
9•假定根结点的层次为
0,
A.3B.4C
假定根结点的层次为
10.若一棵二叉树中,
A.10
n0=门2+1
】个结点f、
2个结点
4个结点
32个结点
1的结点数为9，则该二叉树的叶子结点的数目为
.12
含有
D.不确定
15个结点的二叉树最小高度为（A）。
1,含有15个结点的二叉树最小高度为4
度为2的结点数为9,该二叉树的叶子结点的数目为
.11
.12
前6戻共心个结点
32-4=28个叶结点
（A）。
.不确定
曲356计结点
11.设根结点的层次为
A.2k-1B.2kC.
0,则高度为k的二叉树的最大结点数为（C）。
z^k+1/f^k+1
2-1D.2
k+1
1,则这棵树的高度为k+1，高度为k+1的二叉树的最大结点数为2-1
12.以知某二叉树的后序遍历序列为abdec，先序遍历序列为cedba，它的中序遍历序列为（D）。
.不确定
若设根结点的层次为
A.debacB
.acbed
.decba
A
©
©
13.设高度为
c
c
B
A
C
©©
A.2hB
h的二叉树上只有度为
©
0和度为
©
2的结点，则此二叉树所包含的结点数至少为
.2h-1
.2h+1
.h+1
厲只点牛弟第层结两兄
除每个这为
14.设n,m为一棵二叉树上的两个结点，在中序遍历时,
A.n在m右方B.n是m祖先C
n在m前的条件是（C）。
.n在m左方D.n是m子孙
15.将一棵有100个结点的完全二叉树从上到下
从左到右依次对结点进行编号，根结点的编号为49的结点的左孩子编
号为（A）。
A.98B.99C.50D
48
16.某二叉树的前序和后序序列正好相反，则该二叉树
）、>1=1/
定是（
B）二叉树。
A.空或只有一个结点
B.高度等于其结点数
•任一结点无左孩子
D.任一结点无右孩子
17.对于一棵满二叉树，m个树叶，n个结点，深度为
C.n=2h-118.判断线索二叉树中某结P有左孩子的条件是（C
A.p!
=nullB.p->lchild!
=nullC
.p->ltag=O
.p->ltag=1
19.实现任意二叉树的后序非递归算法而不使用堆栈结构，最佳方案是二叉树采用
A.二叉链表B.广义存储结构
（C）存储结构。
C.三叉链表D.顺序存储结构
20.在一棵二叉树结点的先序遍历序列，中序遍历序列和后序遍历序列中，所有的叶子结点的先后顺序
A.都不相同
B.完全相同C.先序和中序相同，而与后序不同
（B）。
D.中序和后序相同，而与先序不同
21.下图所示
FF是森林F转换而来的二叉树，那么F—共有（C）个叶子结点。
F丿
A.4
E
©
22.在一非空二叉树的中序遍历序列中,
D
A只有右子树上的所有结点
©
根结点的右边
（
.只有右子树上的部分结点
C.只有左子树上的所有结点
.只有左子树上的部分结点
23.设森林F中有3棵树,
其第一，第二和第三棵树的结点个数分别是
ni，n2和n3
则与森林F相对应的二叉树根结
点的右子树上的结点个数是
A线性表的线性存储结构优于链式存储结构
B.二叉树的第i层上有2i-1个结点，深度为k的二叉树上有2k-1个结点。
二.填空题1.有一棵树如图示，回答下面问题:
（A）;⑵这棵树的叶子结点是（B,E,H,G）;⑶结点C的度是
（2）;⑷这棵树的度是（3）;⑸这棵⑹结点C的孩子是（E,F）,子孙是（E,F,H）;（7）结点F的父亲是（Q，祖先是（A,C）o
2.二叉树的每一个结点至多有
（2）棵子树，且子树有（左右）之分。
3•树的结点包含一个（数据元素）及若干指向其（子树）的分支，结点拥有的子树数称为（度），度为0的结点称为（树叶或终端结点），度不为0的结点称为（非终端结点或分支结点）。
4.对二叉树来说，第k层上至多有（2k-1）个结点。
5.前序遍历序列为abc的不同二叉树有（5）种不同形态。
&一棵含有n个结点的完全二叉树，它的高度是
一棵含有n个结点的完全二叉树，它的高度是h-1层最后一个结点的编号2h-1-1
h层第一个结点的编号2h-1
h层最后一个结点的编号2h-1
2h-1>n>2h-1
n>2h-1
hwlogn+1
h=[logn]+1
k
n=2-1=>k=log2（n+1）
9.深度为k的二叉树至多有（2k-1）个结点。
（[log2n]+1）。
（n+1）个空链域。
10.含有n个结点的二叉树用二叉链表表示，有有2n个链域有n-1个非空链域
11.哈夫曼树是带权路径长度（最短）的二叉树。
12.
具有m个叶子结点的哈夫曼树共（2m-1）个结点。
14.树和二叉树从定义上说是两种不同的数据结构，
解决树的有关问题）。
15•深度为k的完全二叉树至多有（2k-1）个结点；至少有（2k-1）个结点，若按自上而下，从左到右的次序给结点编号（从1开始），则编号最小的叶子结点的编号是（2k-2+1）。
16•已知完全二叉树的第8层有8个结点，则其叶子结点数为（68）个。
第7层的叶结点总数：
26-4
第8层的叶结点总数：
8
17.已知完全二叉树的第7层有10个叶子结点，则整个二叉树的结点个数最多为（235）个。
丿-LtJ个
10吓
30，则总结点数为（129）。
£lOOQQOOOOO01笫T层
18.已知二叉树有50个叶子结点，且仅有一个孩子的结点数为设度为i的结点有ni个，共n个结点
有n0+n1+n2=n（结点总数）
0*no+1*n1+2*n2=n-1（边数）
所以：
no=n2+1
ni=30
19.用数组A[1…n]顺序存储完全二叉树的各结点，则当i<
20.一棵二叉树结点的前序序列为A,B,D,E,GC,F,H,
树结点的后序序列为（DGEBHIFCA。
（n-1）/2时，结点A[i]的右孩子是结点（A[2i+1]）。
I，中序序列为D,B,GE,A,GH,F,I，则该二叉
21.
有m个叶子结点的哈夫曼树上的结点数是
22.
（2m-1）。
设树T的度为4，其中度为1,2,3和4的结点个数分别为4,2,1和1，则T中叶子结点的个数为（8）。
设度为i的结点有ni个
ni=4n2=2n3=1n4=1
no+ni+n2+n3+n4=n
n-1=0*n0+1*n1+2*n2+3*n3+4*n4
23.6个结点可构造出132种不同形态的二叉树。
咼度:
高度:
咼度:
高度:
24.在一棵高度为3的四叉树中,
最多含有21结点。
1+1*4+1*4*4
，结点f的层数为3。
假定根结点
（C,d（e,f）,g（h）
），i（j，k（x,y）））
25.—棵树的广义表表示为a（b
26.一棵树的广义表表示为a（b（c,d（e,f）,g（h））,i（j,k（x,y）））
27.假定一棵三叉树（即度为3的树）的结点个数为50,则它的最小高度为第一层：
第二层:
第三层:
第四层:
30=1个结点
1X3=31=3个结点
1X3X3=32=9个结点
1X3X3X3=33=27个结点
前四层，共40个结点
，结点k的所有祖先的结点数为_2_个。
。
假定根结点的高度为0。
28•对于一棵具有n个结点的树，该树中所有结点的度数之和为即求边数
n-1
29.设二叉树根的高度为1，则：
高度为h的完全二叉树的不同二叉树棵数:
2h-1个结点的完全二叉树）高度为h的满二叉树的不同二叉树棵数：
三•判断题
2h-1,（即最后一层分别有1,2，…,
1.（X）二叉树是一棵无序树。
2.（X）若有一个结点是二叉树中某个子树的前序遍历结果序列的最后一个结点,列的最后一个结点。
则它一定是该子树的中序遍历结果序
3.（V）在一棵二叉树中，假定每个结点只有左子女，没有右子女，对它分别进行中序遍历和后序遍历，则具有相同的遍历结果。
4.
5.
6.
（V）在树的存储中，若使每个结点带有指向前驱结点的指针，将在算法中为寻找前驱结点带来方便。
（V）二叉树是树的特殊情形。
（X）对于一棵具有
n个结点的任何二叉树，进行前序、中序或后序的任一种次序遍历的空间复杂度为
O（log2n）o
7.（X）对于一棵具有
&（X）若有一个叶子结点是二叉树中某个子树的前序遍历结果序列的最后一个结点,果序列的最后一个结点。
9.（V）线索化二叉树中的每个结点通常包含有5个数据成员。
10.（X）若有一个结点是二叉树中某个子树的中序遍历结果序列的最后一个结点，则它一定是该子树的前序遍历结果序列的最后一个结点。
四.其他1•二叉树的遍历方法有哪几种，分别简诉其遍历步骤。
二叉树的遍历方法有先序遍历、中序遍历、后序遍历三种。
（1）先序遍历二叉树算法是:
若二叉树为空，则空操作；否则访问根结点（D）;
先序遍历左子树（L）;先序遍历右子树（R）O
（2）中序遍历二叉树算法是:
若二叉树为空，则空操作；否则
中序遍历左子树（L）;访问根结点（D）;
中序遍历右子树（R）。
（3）后序遍历二叉树算法是:
若二叉树为空，则空操作；否则后序遍历左子树（L）;
后序遍历右子树（R）;
访问根结点（D）。
2•若按中序遍历二叉树的结果为A,C,B。
作出所有能得到这一遍历结果的二叉树。
A
3•二叉树结点数据采用顺序存储结构，存储数组中，如图所示，画出该二叉树的二叉链式表示形式。
2
DATA
A
B
c
D
E
F
G
H
I
J
K
L
M
K
0
PARENT
-1
0
0
0
1
1
2
2
3
3
4
5
5
6
1
A
A
C
D
C
G
G
H
N
H
M
o
M
中序和后序遍历序列，并将该二叉树分解为森林。
5.写出二叉树的先序,
二叉树的先序遍历序列:
ABCDEFGHI
二叉树的中序遍历序列:
BDCAFEHIG
二叉树的后序遍历序列:
DCBFIHGEA
对应的森林:
6.以知一棵二叉树的先序遍历序列为ABECDFGHIJ中序遍历序列为
EBCDAFHIGJ试画出这棵二叉树，并写出其后序
遍历序列。
7.画以数据集｛4,5,
10,12,18｝为结点权值所构造的哈夫曼树，并求其带权路径长度
WPL
6,7,
WPLT2吃+6*3+7粘+18吃+4*4+5卡4+10韬T65
9.有一棵二叉树，其中序和后序遍历序列分别为dgbaechif，gdbeihfca。
画出该二叉树，对该二叉树进行先序线索化,
并求该二叉树所对应的森林。
10.二叉树以二叉链表结构存储，在下列中序遍历序列算法中填上正确的语句。
Statusin_order（BiTreep）
{if（p!
=NULL）
{
（1）in_order（p->lchild）
printf（p->data）;
（2）in_order（p->rchild）
}
11.以二叉链表作为存储结构，试完成下列程序
（1）下列函数是中序输出二叉树的各结点，读程序并在每一个空格初填写一个语句或表达式。
0703班15题
后缀表达式：
ab+cd+*ef-*
16.已知二叉树中的结点类型用BTNode表示，被定义为：
structBTNode{ElemTypedata;BTNode*lchild,*rchild;};
其中data为结点值域，lchild和rchild分别为指向左、右子女结点的指针域。
根据下面函数的定义指出函数的功能。
算法中参数BT指向一棵二叉树的根结点。
IntDST（BTNode*BT,ElemTypex）{
if（BT==NULL）return0;
else{
if（BT->data==x）{BT=NULL;return1;}else{
if（DST（BT->lchild,x））return1;
if（DST（BT->rchild,x））return1;
}算法功能：
elsereturn0;
从一棵二叉树中删除根结点值为x的子树，若删除成功则返回1，否则返回0
升级会员 