一、填空题
1. 不相交的树的聚集称之为森林。
2. 从概念上讲,树与二叉树是两种不同的数据结构,将树转化为二叉树的基本目的是_树可采用孩子-兄弟链表(二叉链表)做存储结构,目的是利用二叉树的已有算法解决树的有关问题。
3. 深度为k的完全二叉树至少有2 k-1个结点。至多有2 k-1个结点,若按自上而下,从左到右次序给结点编号(从1开始),则编号最小的叶子结点的编号是2 k-2+1。
4. 在一棵二叉树中,度为零的结点的个数为n
,度为2的结点的个
数为n
2,则有n
= n
2
+1。
5. 一棵二叉树的第i(i≥1)层最多有2 i-1个结点;一棵有n(n>0)个结点的满二叉树共有(n+1)/2个叶子和(n-1) /2个非终端结点。
6.现有按中序遍历二叉树的结果为abc,问有5种不同形态的二叉树
可以得到这一遍历结果。
7. 哈夫曼树是带权路径最小的二叉树。
8. 前缀编码是指任一个字符的编码都不是另一个字符编码的前缀的一种编码方法,是设计不等长编码的前提。
9. 以给定的数据集合{4,5,6,7,10,12,18}为结点权值构造的Huffman树的加权路径长度是 165 。
10. 树被定义为连通而不具有回路的(无向)图。
11. 若一棵根树的每个结点最多只有两个孩子,且孩子又有左、右之分,次序不能颠倒,则称此根树为二叉树。
12. 高度为k,且有个结点的二叉树称为二叉树。
2k-1 满
13. 带权路径长度最小的二叉树称为最优二叉树,它又被称为树。
Huffman
14. 在一棵根树中,树根是为零的结点,而为零的结点是结点。
入度出度树叶
15. Huffman树中,结点的带权路径长度是指由到之间的路径长度与结点权值的乘积。
结点树根
16. 满二叉树是指高度为k,且有个结点的二叉树。二叉树的每一层i上,最多有个结点。
2k-12i-1
二、单选题
1. 具有10个叶结点的二叉树中有 (B) 个度为2的结点。
(A)8 (B)9 (C)10 (D)11
2.对二叉树的结点从1开始进行连续编号,要求每个结点的编号大于其左右孩子的编号,同一结点的左右孩子中,其左孩子的编号小于其右孩子的编号,则可采用_(3)次序的遍历实现编号。
(1)先序(2)中序
(3)后序(4)从根开始按层遍历
3. 由2、3、4、7作为结点权值构造的树的加权路径长度B。
A、33
B、30
C、36
D、40
4. 高度为6的满二叉树,总共有的结点数是B。
A、15
B、63
C、20
D、25
5. 下面描述根树转换成二叉树的特性中,正确的是C。
A、根树转换成的二叉树是唯一的,二叉树的根结点有左、右孩子。
B、根树转换成的二叉树是不唯一的,二叉树的根结点只有左孩子。
C、根树转换成的二叉树是唯一的,二叉树的根结点只有左孩子。
D、根树转换成的二叉树是不唯一的,二叉树的根结点有左、右孩子。
6. 如图所示的4棵二叉树中,不是完全二叉树的是。
A、○
B、○
○○○○
○○○○○○
C、○
D、○
○○○○
○○○○
C
7.某二叉树先序遍历的结点序列是abdgcefh,中序遍历的结点序列是dgbaechf,