一、单选题（每题 2 分，共 30 分）

1. 在面向对象编程中，下列关于“虚函数”的描述中，错误的是（ ）。 {{ select(1) }}

• 虚函数用于支持运行时多态
• 通过基类指针调用虚函数时，会根据对象实际类型决定调用版本
• 构造函数可以声明为虚函数以支持多态
• 基类析构函数常声明为虚函数以避免资源泄漏

2. 执行如下代码，会输出“钢琴：叮咚叮咚”和“吉他：咚咚当当”。这体现了面向对象编程的（ ）特性。

{{ select(2) }}

• 继承
• 封装
• 多态
• 链接

3. 关于以下代码，说法正确的是（ ）。

{{ select(3) }}

• 执行代码会输出两行，内容分别为：“钢琴：叮咚叮咚”和“吉他：咚咚当当”
• 执行代码会输出两行，内容分别为：“乐器在演奏声音”和“乐器在演奏声音”
• 代码编译出现错误
• 代码运行出现错误

4. 某文本编辑器把用户输入的字符依次压入栈 $S$。用户依次输入 $A,B,C,D$ 后，用户按了两次撤销（每次撤销，弹出栈顶一个字符）。此时栈从栈底到栈顶的内容是：（ ）。 {{ select(4) }}

• A B
• A B C
• A B D
• B C

5. 假设循环队列数组长度为 $N$，其中队空判断条件为：front == rear，队满判断条件为：(rear + 1) % N == front，出队对应的操作为：front = (front + 1) % N，入队对应的操作为：rear = (rear + 1) % N。循环队列长度 $N = 6$，初始 front = 1 , rear = 1，执行操作序列为：入队, 入队, 入队, 出队, 入队, 入队，则最终 $(front, rear)$ 的值是（ ）。 {{ select(5) }}

• $(2, 5)$
• $(2, 0)$
• $(3, 5)$
• $(3, 0)$

6. 以下函数 check() 用于判断一棵二叉树是否为（ ）。

{{ select(6) }}

• 满二叉树
• 完全二叉树
• 二叉搜索树
• 平衡二叉树

7. 以下代码实现了二叉树的（ ）。

{{ select(7) }}

• 前序遍历
• 中序遍历
• 后序遍历
• 层序遍历

8. 下面代码实现了哈夫曼编码，则横线处应填写的代码是（ ）。

{{ select(8) }}

• 
• 
• 
• 

9. 以下关于哈夫曼编码的说法，正确的是（ ）。 {{ select(9) }}

• 哈夫曼编码是定长编码
• 哈夫曼编码中，没有任何一个字符的编码是另一个字符编码的前缀
• 哈夫曼编码一定唯一
• 哈夫曼编码不能用于数据压缩

10. 以下函数实现了二叉排序树（BST）的（ ）操作。

{{ select(10) }}

• 查找
• 插入
• 删除
• 遍历

11. 下列代码实现了树的深度优先遍历，则横线处应填入（ ）。

{{ select(11) }}

• if (node->left) st.push(node->left);
• if (node->left) st.pop(node->left);
• if (node->left) st.front(node->left);
• if (node->left) st.push(node->right);

12. 给定一棵普通二叉树（节点值没有开奖吗），下面代码判断是否存在值为 $x$ 的结点，则横线处应填入（ ）。

{{ select(12) }}

• 
• 
• 
• 

13. 在二叉排序树（Binary Search Tree, BST）中，假设节点值互不相同。给定如下搜索函数，以下说法一定正确的是（ ）。

{{ select(13) }}

• 最坏情况下，访问结点数是 $O(logn)$
• 最坏情况下，访问结点数是 $O(n)$
• 无论如何，访问结点数都不超过树高的一半
• 一定比在普通二叉树中搜索快

14. $0/1$ 背包（每件物品最多选一次）问题通常可用一维动态规划求解，核心代码如下。则下面说法正确的是（ ）。

{{ select(14) }}

• 内层 $j$ 必须从小到大，否则会漏解
• 内层 $j$ 必须从大到小，否则同一件物品会被用多次
• $j$ 从大到小或从小到大都一样
• 只要 dp 初始为 $0$，方向无所谓

15. 以下关于动态规划的说法中，错误的是（ ）。 {{ select(15) }}

• 动态规划方法通常能够列出递推公式
• 动态规划方法的时间复杂度通常为状态的个数
• 动态规划方法有递推和递归两种实现形式
• 对很多问题，递推实现和递归实现动态规划方法的时间复杂度相当

二、判断题（每题 2 分，共 20 分）

16. 以下代码中，构造函数被调用的次数是 1 次。

{{ select(16) }}

• 正确
• 错误

17. 面向对象编程中，封装是指将数据和操作数据的方法绑定在一起，并对外隐藏实现细节。 {{ select(17) }}

• 正确
• 错误

18. 以下代码能够正确统计二叉树中叶子结点的数量。

{{ select(18) }}

• 正确
• 错误

19. 广度优先遍历二叉树可用栈来实现。 {{ select(19) }}

• 正确
• 错误

20. 函数调用管理可用栈来管理。 {{ select(20) }}

• 正确
• 错误

21. 在二叉排序树（BST）中，若某结点的左子树为空，则该结点一定是整棵树中的最小值结点。 {{ select(21) }}

• 正确
• 错误

22. 下面的函数能正确判断一棵树是不是二叉排序树（左边的数字要比当前数字小，右边的数字要比当前数字大）。

{{ select(22) }}

• 正确
• 错误

23. 格雷编码相邻两个编码之间必须有多位不同，以避免数据传输错误。 {{ select(23) }}

• 正确
• 错误

24. 小杨在玩一个闯关游戏，从第 1 关走到第 4 关。每一关的体力消耗如下（下标表示关卡编号）：cost = [0, 3, 5, 2, 4]，其中 cost[i] 表示到达第 i 关需要消耗的体力，cost[0] = 0 表示在开始状态，体力消耗为 0。小杨每次可以从当前关卡前进 1 步或 2 步。按照上述规则，从第 1 关到第 4 关所需消耗的最小体力为 7。 {{ select(24) }}

• 正确
• 错误

25. 假定只有一个根节点的树的深度为 1，则一棵有 个节点的完全二叉树，则树的深度为 $\lfloor \log_2(n) \rfloor + 1$。 {{ select(25) }}

• 正确
• 错误