第五章 树
11． 不含任何结点的空树(    )
A）是一棵树                          B）是一棵二叉树 
Ｃ）既不是树也不是二叉树              D）是一棵树也是一棵二叉树
12．二叉树是非线性数据结构，所以(    )
A）它不能用顺序存储结构存储;          B）它不能用链式存储结构存储; 
C）顺序存储结构和链式存储结构都能存储; D）顺序存储结构和链式存储结构都不能使用
13．把一棵树转换为二叉树后，这棵二叉树的形态是(    )
A）唯一的                          B）有多种
C）有多种，但根结点都没有左孩子    D）有多种，但根结点都没有右孩子
9. 11 ， 8 ， 6 ， 2 ， 5 的叶子结点生成一棵哈夫曼树，它的带权路径长度为（  ）
A)  24          B)  72         C)    48            D)  53
10.一棵含18个结点的二叉树的高度至少为(     )
A)  3           B)  4         C)  6            D)  5
11.下面的二叉树中，( C  )不是完全二叉树。

     
10. 设结点x和结点y是二叉树T中的任意两个结点，若在前序序列中x在y之前，而在中序序列中x在y之后，则x和y的关系是（    ）
A）x是y的左兄弟　          　 B）x是y的右兄弟
C）y是x的祖先              D）y是x的孩子
11.设二叉树根结点的层次为1，所有含有15个结点的二叉树中，最小高度是（    ）
A） 6　    　B） 5　        　C） 4            D） 3
7． 下列陈述中正确的是（    ）
A） 二叉树是度为2的有序树　      　B） 二叉树中结点只有一个孩子时无左右之分
C） 二叉树中必有度为2的结点　    　D） 二叉树中最多只有两棵子树，并且有左右之分
8. 树最适合用来表示（    ）
A） 有序数据元素                          B） 无序数据元素
C）  元素之间具有分支层次关系的数据      D） 元素之间无联系的元素
9.  3个结点有（    ）不同形态的二叉树
A） 2            B）  3            C）  4            D）  5
6．二叉树是非线性数据结构，(    )
A）它不能用顺序存储结构存储;            B）它不能用链式存储结构存储; 
C）顺序存储结构和链式存储结构都能存储; 
D）顺序存储结构和链式存储结构都不能使用
7．二叉树上叶结点数等于(    )
A ) 分支结点数加1              B ) 单分支结点数加1
C ) 双分支结点数加1            D ) 双分支结点数减1
8．如将一棵有n个结点的完全二叉树按顺序存放方式，存放在下标编号为0, 1,…, n-1的一维数组中，设某结点下标为k(k>0)，则其双亲结点的下标是(    )
　A )  (k-1)/2          B )  (k+1)/2             C )  k/2            D )  k-1
8. 树最适合用来表示（      ）。
A．有序数据元素                        B．无序数据元素
C. 元素之间具有分支层次关系的数据      D．元素之间无联系的元素
10.有64个结点的完全二叉树的深度为(          ) (根的层次为第1层)。
A. 8              B. 7                  C. 6              D. 5
11.在一棵度为3的树中，度为3的结点有2个，度为2的结点有1个，度为1的结点有２个，那么，该树有（      ）个叶子结点。
A. 4                  B. 5                  C. 6              D. 7
9.一个二叉树按顺序方式存储在一个维数组中，如图
0    1    2    3  4    5    6    7    8    9    10    11  12  13  14
A
B
C
D
 
E
F
 
G
 
 
H
 
I
J
则结点E在二叉树的第（      ）层。(假设树根所在层为第1层)
A、2            B、3              C、4              D、5
10. 由权值分别为 11 ， 8 ， 6 ， 2 ， 5 的叶子结点生成一棵哈夫曼树，它的带权路径长度
为（        ）
A 24            B 71        C 48            D 53
8. 二叉树上叶结点数等于（        ）。
A．分支结点数加1              B．单分支结点数加1
C．双分支结点数加1            D．双分支结点数减1
8. 某二叉树的先序序列和后序序列正好相同，则该二叉树一定是(    )的二叉树。
  A.空或只有一个结点                      B.高度等于其结点数
  C.任一结点无左孩子                      D.任一结点无右孩子
9. 在有n个结点的二叉链表中，值为空的链域的个数为(      )
  A. n-1                                      B. 2n-1
  C. n+1                                      D. 2n+1
10. 一棵含18个结点的二叉树的高度至少为(    )
A. 8           B.  7         C.  6             D.  5
11. 深度优先遍历类似于二叉树的(              )
A.先序遍历        B. 中序遍历    C. 后序遍历    D. 层次遍历
9. 一棵124个叶结点的完全二叉树，最多应有(            )个结点。
A.245        B.246        C.247        D.248
10. 后缀表达式“ 5 6*3 2 + -”的值为（        ）。
A.15          B.25            C.30              D.35
11. 由权值分别为 11 ， 8 ， 6 ， 2 ， 5 的叶子结点生成一棵哈夫曼树，它的带权路径长度为（           ）
      A. 24          B. 71         C.  48            D. 53
7. 对一个满二叉树，m个树叶, n个结点, 深度为为h, 则（        ）。
A. n=2h-1      B.h+m=2n      C.m=h-1      D. n=h+m
8. 在一棵二叉树的二叉链表中，空指针域数等于非空指针域数加(      )。
A.2          B.1            C.0            D.-1
9. 若完全二叉树的结点总个数为100（结点编号从1开始编号，按层序编号），则第58个结点的度为（        ）
    A.2          B.1            C.0            D.不确定
10. 已知完全二叉树的第9层有240个结点，则该完全二叉树的结点数是（            ）
    A.494          B.495           C.496            D.497
二、填空题
1. 一棵深度为5的二叉树，至多有_____________个结点。31
6.图的存储结构有__________________和__________________，遍历图有___________
___、_____________等方法。邻接矩阵  邻接表  深度优先    广度优先
7.深度为ｋ的完全二叉树最多有        个结点。
8.若按层序对深度为ｋ的完全二叉树中全部结点从１开始编号，则叶子结点可能的最小编号为      。
6.设有树如图所示，则结点ｃ的度为___________，层次为___________，树的度为___________，树的高度为___________。结点ｃ的度为２， 层次为２， 树的度为３，高度为４
7.深度为ｋ的完全二叉树至少有___________个结点，最多有___________个结点。，
7.对于一棵具有n个结点的二叉树，当进行链接存储时，其二叉链表中的指针域的总数为_______个，其中_______个用于链接孩子结点，_______个空闲着。2n，n-1，n+1
2. 后缀表达式“2 10 + 5 * 6 – 9 /”的值为             。6
3.由n个权值构成的哈夫曼树共有            个结点。2n-1
6.在一棵树中，  ____  结点没有后继结点。叶
4．后缀表达式“2 10 + 5 * 6 – 9 /”的计算结果为                         。6
4.一棵深度为7的二叉树，最多有          个结点。127
5.若一棵树的括号表示为A(B,C(E,F(G)),D),该树的叶子结点个数为________ ，该树的度为_____________ ，该树的深度为_____________。4、3、4
6.在有n个叶子结点的哈夫曼树中，总结点数是_______。2n-1
1. 深度为4的完全二叉树最少有______个结点，最多有_______个结点。8        15
6. 假定一棵树的广义表表示为A(B(C(D,E),F,G(H,I,J)),K)，则度为3、2、1、二叉树公式0的结点数分别为______、______、______和______个。2        2        0        7
6. 若结点A有其他三个兄弟,B是A的双亲结点,B的度是_______________。4

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。