一、单项选择题(共 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 分