CSP-J 树与二叉树基础及代码阅读综合测试

本试卷共 25 道单项选择题，每题 4 分，满分 100 分。

一、树、森林与基本概念

1. 一棵含有 37 个节点的树共有（ ）条边。

{{ select(1) }}

• 35
• 36
• 37
• 38

2. 一片森林共有 20 个节点、6 棵树，则这片森林共有（ ）条边。

{{ select(2) }}

• 12
• 13
• 14
• 15

3. 对一个含有 n 个节点的无向图，下列条件中单独使用时不能保证它一定是一棵树的是（ ）。

{{ select(3) }}

• 连通且无环
• 恰好有 n-1 条边
• 连通且恰好有 n-1 条边
• 任意两点之间有且仅有一条简单路径

4. 一棵含有 15 个节点的无向树，所有节点的图论度数之和是（ ）。

{{ select(4) }}

• 14
• 15
• 28
• 30

5. 在一棵有根树中，叶子节点是指（ ）。

{{ select(5) }}

• 没有父节点的节点
• 没有子节点的节点
• 度数一定等于 1 的节点
• 编号最大的节点

6. 在一棵非空二叉树中，有两个孩子的节点数量为 8，则叶子节点数量为（ ）。

{{ select(6) }}

• 7
• 8
• 9
• 10

二、二叉树与完全二叉树

7. 根位于第 1 层时，高度为 6 的二叉树最多有（ ）个节点。

{{ select(7) }}

• 31
• 32
• 63
• 64

8. 一棵含有 20 个节点的完全二叉树，其高度为（ ）。

{{ select(8) }}

• 4
• 5
• 6
• 20

9. 完全二叉树从 1 开始按层编号，节点 15 的父节点编号是（ ）。

{{ select(9) }}

• 6
• 7
• 8
• 30

10. 完全二叉树从 1 开始编号，节点 i 的左、右孩子下标分别是（ ）。

{{ select(10) }}

• 2i-1、2i
• 2i、2i+1
• i/2、i/2+1
• i+1、i+2

11. 一棵含有 31 个节点的完全二叉树，最后一个非叶节点的下标是（ ）。

{{ select(11) }}

• 14
• 15
• 16
• 31

12. 下列关于二叉树的说法正确的是（ ）。

{{ select(12) }}

• 每个节点必须恰好有两个孩子
• 只有右孩子而没有左孩子不是合法二叉树
• 左孩子和右孩子有明确的顺序
• 所有二叉树都是完全二叉树

三、遍历、DFS 与 BFS

下面第 13 题使用如下二叉树：根为 A；A 的左右孩子为 B、C；B 的左右孩子为 D、E；C 的左右孩子为 F、G。

13. 上述二叉树的后序遍历结果是（ ）。

{{ select(13) }}

• ABDECFG
• DBEAFCG
• DEBFGCA
• ABCDEFG

14. 二叉树的层序遍历通常使用（ ）。

{{ select(14) }}

• 栈
• 队列
• set
• map

15. 先序遍历处理节点的顺序是（ ）。

{{ select(15) }}

• 左子树、根、右子树
• 左子树、右子树、根
• 根、左子树、右子树
• 根、右子树、左子树

16. 在无向树上执行 DFS 时，递归函数传入父节点参数的主要目的是（ ）。

{{ select(16) }}

• 防止沿原边返回父节点
• 对邻接表进行排序
• 计算边的权值
• 减少节点编号

17. 对含有 n 个节点的二叉树进行先序、中序、后序或层序遍历，其时间复杂度通常都是（ ）。

{{ select(17) }}

• O(1)
• O(log n)
• O(n)
• O(n^2)

18. 使用 DFS 计算 siz[u] 表示以 u 为根的子树大小时，语句 siz[u] += siz[v] 应当放在（ ）。

{{ select(18) }}

• 调用 dfs(v,u) 之前
• 调用 dfs(v,u) 返回之后
• 整个 DFS 开始之前
• 任何位置都可以

19. 一棵只含有根节点 1 的树，以 1 为根时，叶子节点数量是（ ）。

{{ select(19) }}

• 0
• 1
• 2
• 无法判断

四、遍历序列、BST、堆与哈夫曼树

20. 节点值互不相同时，一般可以唯一确定一棵二叉树的遍历序列组合是（ ）。

{{ select(20) }}

• 先序和后序
• 先序和中序
• 两次先序
• 两次层序

21. 已知一棵二叉树的中序遍历为 BADCE，后序遍历为 BDECA，其先序遍历是（ ）。

{{ select(21) }}

• ABCDE
• BADCE
• ACDEB
• BDECA

22. 对二叉搜索树进行哪一种遍历，可以得到按关键字升序排列的序列？

{{ select(22) }}

• 先序遍历
• 中序遍历
• 后序遍历
• 层序遍历

23. 若按照严格递增顺序依次向普通二叉搜索树插入元素，树可能退化成链，此时查询的最坏时间复杂度为（ ）。

{{ select(23) }}

• O(1)
• O(log n)
• O(n)
• O(n log n)

24. C++ 中的 priority_queue<int> 默认是（ ）。

{{ select(24) }}

• 小根堆，堆顶是最小值
• 大根堆，堆顶是最大值
• 普通先进先出队列
• 双端队列

25. 对权值 5、7、10、15 进行最优合并，每次取出当前最小的两个数合并，最小总代价为（ ）。

{{ select(25) }}

• 37
• 59
• 71
• 74