1. 二叉树第k层上最多有（ ）个结点。
A. 2k
B. 2k-1
C. 2k-1
D. 2k-1
参考答案：B
2. 二叉树的深度为k,则二叉树最多有（ ）个结点。
A. 2k
B. 2k-1
C. 2k-1
D. 2k-1
参考答案：D
3. 在有向图的邻接表中，每个顶点邻接表链接着该顶点所有（ ）邻接点。
A. 入边
B. 出边
C. 入边和出边
D. 不是入边也不是出边
参考答案：B
4. 假定一棵二叉树中，双分支结点数为15，单分支结点数为30，则叶子结点数为（ ）。
A. 15
B. 16
C. 17
D. 47
参考答案：B
5. 设一棵有n个叶结点的二叉树，除叶结点外每个结点度数都为2，则该树共有（ ）个结点。
A. 2n
B. 2n-1
C.
2n+1
D. 2n+2
参考答案：B
6. 将含有150个结点的完全二叉树从根这一层开始，每一层从左到右依次对结点进行编号，根结点的编号为1，则编号为69的结点的双亲结点的编号为（ ）。
A. 33
B. 34
C. 35
D. 36
参考答案：B
7. 对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则所有顶点邻接表中的结点总数为（ ）。
A. n
B. e
C. 2n
D. 2e
参考答案：D
8. 在一棵度具有5层的满二叉树中结点总数为（ ）。
A. 31
B. 32
C. 33
D. 16
参考答案：A
9.
在一棵二叉树中，若编号为i的结点是其双亲结点的左孩子，则双亲结点的顺序编号为（ ）。
A. i/2
B. 2i-1
C. 2i+1
D. i/2 -1
参考答案：A
10. 权值为{1，2，6，8}的四个结点构成的哈夫曼树的带权路径长度是（ ）。
A. 18
B. 28
C. 19
D. 29
参考答案：D
11. 设某一二叉树先序遍历为abdec，中序遍历为dbeac，则该二叉树后序遍历的顺序是（ ）。
A. abdec
B. debac
C. debca
D. abedc
参考答案：C
12. 在一棵二叉树中，若编号为i的结点存在右孩子，则右孩子的顺序编号为（ ）。
A. 2i
B. 2i-1
C. 2i+1
D. 2i+2
参考答案：C
13. 在一棵度为3的树中，度为3的结点个数为2，度为2的结点个数为1，则度为0的结点个数为（ ）。
A. 4
B. 5
C. 6
D. 7
参考答案：C
14. 在一棵二叉树中，若编号为9的结点存在右孩子，则右孩子的顺序编号为（ ）。
A. 18
B. 16
C. 15
D. 19
参考答案：D
15. 在一个图G中，所有顶点的度数之和等于所有边数之和的（ ）倍。
A. 1/2
B. 1
C. 2
D. 4
参考答案：C
二、判断题（共 10 道试题，共 40 分。）
1. 如果有向图中各个顶点的度都大于2，则该图中必有回路。
A. 错误
B. 正确
参考答案：A
2. 如果无向图中每个顶点的度都大于等于2，则该图中必有回路。
A. 错误
B. 正确
参考答案：B
3. 在树的存储中，若使每个结点带有指向双亲结点的指针，这为在算法中寻找双亲结点带来方便。
A. 错误
B. 正确
参考答案：B
4. 图的广度优先搜索算法通常采用非递归算法求解。
A. 错误
B. 正确
参考答案：B
5. 图中各个顶点的编号是人为的，不是它本身固有的，因此可以根据需要进行改变。
A. 错误
B. 正确
参考答案：B
6.
邻接表只能用于有向图的存储，邻接矩阵对于有向图和无向图的存储都适用。
A. 错误
B. 正确
参考答案：A
7. 对于一棵具有n个结点的任何二叉树，进行前序、中序或后序的任一种次序遍历的空间复杂度为O(log2n)。
A. 错误
B. 正确
参考答案：A
8. 对于一棵具有n个结点，其高度为h的任何二叉树，进行任一种次序遍历的时间复杂度均为O(h)。
A. 错误
B. 正确
参考答案：A
9. 有回路的有向图不能完成拓扑排序。
A. 错误
B. 正确
参考答案：B
10. 二叉树是一棵无序树。
A. 错误
B. 正确
参考答案：A
