一、单项选择题（共 15 道试题，共 60 分。） 得分：60
1. 在一棵度具有5层的满二叉树中结点总数为（ A）。
A. 31
B. 32
C. 33
D. 16
满分：4 分
2. 假定一棵二叉树中，双分支结点数为15，单分支结点数为30，则叶子结点数为（ B）。
A. 15
B. 16
C. 17
D. 47
满分：4 分
3. 权值为{1，2，6，8}的四个结点构成的哈夫曼树的带权路径长度是（ D）。
A. 18
B. 28
C. 19
D. 29
满分：4 分
4. 一个具有n个顶点的无向完全图包含（C ）条边。
A. n（n-1）
B. n（n+1）
C. n（n-1）/2
D. n（n+1）/2
满分：4 分
5. 如果将给定的一组数据作为叶子数值，所构造出的二叉树的带权路径长度最小，则该树称为（A ）。
A. 哈夫曼树
B. 平衡二叉树
C. 二叉树
D. 完全二叉树
满分：4 分
6. 在一棵度为3的树中，度为3的结点个数为2，度为2的结点个数为1，则度为0的结点个数为（ C）。
A. 4
B. 5
C. 6
D. 7
满分：4 分
7. 设一棵有n个叶结点的二叉树，除叶结点外每个结点度数都为2，则该树共有（B ）个结点。
A. 2n
B. 2n-1
C.
2n+1
D. 2n+2
满分：4 分
8. 一棵采用链式存储的二叉树，有11个叶结点,5个一度结点, 该二叉树共有（C ）点。
A. 28
B. 27
C. 26
D. 25
满分：4 分
9. 在一棵二叉树中，若编号为i的结点存在右孩子，则右孩子的顺序编号为（C ）。
A. 2i
B. 2i-1
C. 2i+1
D. 2i+2
满分：4 分
10.
在一棵二叉树中，若编号为i的结点是其双亲结点的左孩子，则双亲结点的顺序编号为（ A）。
A. i/2
B. 2i-1
C. 2i+1
D. i/2 -1
满分：4 分
11. 在一棵树中，（ C）没有前驱结点。
A. 分支结点
B. 叶结点
C. 树根结点
D. 空结点空结点
满分：4 分
12. 设某一二叉树先序遍历为abdec，中序遍历为dbeac，则该二叉树后序遍历的顺序是（C ）。
A. abdec
B. debac
C. debca
D. abedc
满分：4 分
13. 二叉树的深度为k,则二叉树最多有（ D）个结点。
A. 2k
B. 2k-1
C. 2k-1
D. 2k-1
满分：4 分
14. 在一棵二叉树中，若编号为9的结点存在右孩子，则右孩子的顺序编号为（ D）。
A. 18
B. 16
C. 15
D. 19
满分：4 分
15. 二叉树第k层上最多有（B ）个结点。
A. 2k
B. 2k-1
C. 2k-1
D. 2k-1
满分：4 分
二、判断题（共 10 道试题，共 40 分。） 得分：40
1. 有回路的有向图不能完成拓扑排序。 B
A. 错误
B. 正确
满分：4 分
2. 图的广度优先搜索算法通常采用非递归算法求解。 B
A. 错误
B. 正确
满分：4 分B
3. 如果无向图中每个顶点的度都大于等于2，则该图中必有回路。B
A. 错误
B. 正确
满分：4 分
4. 对于一棵具有n个结点，其高度为h的二叉树，进行任一种次序遍历的时间复杂度为O(n)。 B
A. 错误
B. 正确
满分：4 分
5. 对于一棵具有n个结点，其高度为h的任何二叉树，进行任一种次序遍历的时间复杂度均为O(h)。 A
A. 错误
B. 正确
满分：4 分
6. 二叉树是一棵无序树。 A
A. 错误
B. 正确
满分：4 分
7. 图的深度优先搜索是一种典型的回溯搜索的例子，可以通过递归算法求解。 B
A. 错误
B. 正确
满分：4 分
8. 在一棵二叉树中，假定每个结点只有左子女，没有右子女，对它分别进行前序遍历和后序遍历，则具有相同的结果。 A
A. 错误
B. 正确
满分：4 分
9. 图中各个顶点的编号是人为的，不是它本身固有的，因此可以根据需要进行改变。 B
A. 错误
B. 正确
满分：4 分
10. 存储无向图的邻接矩阵是对称的，因此可以只存储邻接矩阵的下（上）三角部分。 B
A. 错误
B. 正确
满分：4 分
