admin 管理员组文章数量: 1086019
2024年4月22日发(作者：form的属性)
第四章练习题
1．对于任何一棵二叉树T，如果其终端结点数为n
0
，度为2的结点数为n
2
，则（A ）。
A．n
0
=n
2
+1 B．n
2
=n
0
+1 C．n
0
=2n
2
+1 D．n
2
=2n
0
+1
2．有m个叶结点的哈夫曼树所具有的结点数为（D ）。
A．m B．m+1 C．2m D．2m-1
3.在一棵度为3树中，度为3的结点数为2个，度为2的结点数为1个，度为1的结点数为
2个，则度为0的结点数为（C ）个。
A.4 B.5 C.6 D.7
4．二叉树通常有 存储结构和 存储结构。顺序、链式
5．对于一棵满二叉树，若有m个叶子，则结点数为 ；若满二叉树的结点数为n，
则其高度为 。2m-1 、log2（n+1）
6．森林的后序遍历序列正是相应二叉树的 遍历序列，森林的先序遍历序列正是相
应二叉树的 遍历序列。中序 、先序
7．在一棵具有n个结点的完全二叉树中，从树根起，自上而下、自左至右地给所有结点编
号。设根结点编号为1。若编号为i的结点有右孩子，那么其右孩子的编号为 ；
若编号为i的结点有父结点，那么其父结点的编号为 。2i+1、[i/2]
8．已知一棵二叉树的前序序列是：ABCDEFG，这棵二叉树的中序序列是：CBDAEGF，请
构造出该二叉树。
9．深度为k的二叉树，结点数最多有（ B ）。
A．2
k
B．2
k
-1 C．2
k-1
D．2
k-1
-1
10. 在一棵度为3树中，度为3的结点数为2个，度为2的结点数为1个，度为1的结点数
为2个，则度为0的结点数为（C ）个。
A.4 B.5 C.6 D.7
11．具有65个结点的完全二叉树其深度为 （B ）。
1
A.8 B.7 C.6 D.5
12．设只包含根结点的二叉树的高度为0，则高度为k的二叉树最大结点数为 ，最小
结点数为 。2-1、k+1
13．在有n个结点的二叉链表中，指向孩子结点的指针有 个，空指针域有
个。 n-1、n+1
14．由一棵二叉树的前序序列和 序列可以确定这棵二叉树。设某二叉树的
后序遍历为ABKCBPM，则可知该二叉树的根为 。中序、M
15．设某通讯电文由A、B、C、D、E、F六个字符组成，它们在电文中出现的次数分别是
16，5，9，3，20，1，试画出编码用的哈夫曼树。
编码用的哈夫曼树如图所示。
k+1
16.若已知两棵二叉树B1和B2皆为空，或者皆不空且B1的左、右子树和B2的左、右子树
分别相似，则称二叉树B1和B2相似。试编写算法，判别给定两棵二叉树是否相似。
int Bitree_Sim(Bitree B1,Bitree B2)//判断两棵树是否相似的递归算法
{
if(!B1&&!B2) return 1;
else
if(B1&&B2&&Bitree_Sim(B1->lchild,B2->lchild)&&Bitree_Sim(B1->rchild,B2->rchild))
return 1;
else return 0;
}//Bitree_Sim
17．在一棵度为3的树中，度为3的结点数为2，度为2的结点数为1，度为1的结点数为
2，那么度为0的结点数为（ C ）
A. 4 B. 5 C. 6 D. 7
2
版权声明：本文标题：第四章练习题 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.roclinux.cn/p/1713730578a648895.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。
发表评论