一、单项选择题（共 15 题，每题 2 分，共计 30 分；每题有且仅有一个正确选项）

1. 下列关于 C++ 中类的描述，正确的是( )。 {{ select(1) }}

• 如果类没有用户声明的构造函数，那么编译器会隐式声明一个默认构造函数
• 类的析构函数可以被重载，一个类可以有多个析构函数
• 类中的所有成员都必须声明为 public
• 类和结构体在 C++ 中没有区别，包括默认访问权限也相同

2. 下列代码中，s1->draw(); 和 s2->draw(); 输出不同结果的主要原因是( )。

{{ select(2) }}

• draw() 是普通成员函数
• Shape 中的 draw() 被声明为虚函数
• Circle 和 Rectangle 中使用了 public 继承
• 指针变量名不同

3. 下面的代码在 main() 中有一行会导致编译错误，请找出来。

   

   {{ select(3) }}

• 第 ① 行
• 第 ② 行
• 第 ③ 行
• 第 ④ 行

4. 游乐园的过山车每次限坐 4 人，用循环队列管理排队(容量 MAX=5，空一格判满)。下面代码执行后，循环队列是否已满？rear 的值是多少？

   

{{ select(4) }}

• 已满，rear = 1
• 未满，rear = 1
• 已满，rear = 2
• 未满，rear = 4

5. 在以下计算机系统应用场景中，最适合使用循环队列的是( )。 {{ select(5) }}

• 函数调用过程中，保存局部变量和返回地址
• 表达式求值中的运算符优先级处理
• 操作系统中的进程优先级调度(高优先级先执行)
• 生产者和消费者问题中的共享缓冲区

6. 在二叉搜索树(BST)中，若中序遍历的序列为{1, 2, 3, 4, 5}，且先序遍历的第一个序列元素为3，则下列说法正确的是( )。

{{ select(6) }}

• 该树一定是一棵完全二叉树。
• 元素4和5不可能是兄弟节点。
• 元素1所在节点的深度可能大于3(根节点深度为1)。
• 元素2一定是元素1的父节点。

7. 某二叉树共有10个结点，记为A~J，已知它的先序遍历序列为:A B D H I E C F J G，中序遍历序列为:H D I B E A F J C G，则该二叉树的后序遍历序列是( )。 {{ select(7) }}

• H I D E B J F G C A
• H I D B E J F G C A
• I H D E B J F G C A
• H I D E B F J G C A

8. 下列关于树的遍历的说法中，正确的一项是( )。 {{ select(8) }}

• 对任意一棵树进行深度优先遍历，所得序列一定唯一。
• 已知一棵二叉树的先序遍历和后序遍历序列，可以唯一确定这棵二叉树。
• 已知一棵二叉树的先序遍历和中序遍历序列，可以唯一确定这棵二叉树。
• 已知一棵二叉树的先序遍历序列，可以唯一确定这棵二叉树。

9. 有6 个字符，它们出现的次数分别为:{2, 3, 3, 4, 6, 8}，现在用哈夫曼编码为这些字符编码，最小加权路径长度WPL(每个字符的出现次数×它的编码长度，再把每个字符结果加起来)的值为( )。 {{ select(9) }}

• 58
• 60
• 62
• 64

10. 对 $n$ 个不同符号的符号进行哈夫曼编码。若生成的哈夫曼树共有 $m$ 个结点，则 $m$ 的值是()。 {{ select(10) }}

• 60
• 58
• 57
• 56

11. 关于格雷编码(Gray Code)，下列说法正确的是( )。 {{ select(11) }}

• 格雷编码中，编码位数越多，相邻编码之间变化的位数也越多
• 格雷编码中，相邻两个编码的二进制位恰好有一位不同
• 格雷编码就是把普通二进制编码按位取反后得到的结果
• 格雷编码不能用于数字电路和状态转换的设计中

12. 给定一棵二叉树，采用广度优先搜索 (BFS) 算法，返回右视图所有节点的值。其中右视图定义为：二叉树的右视图是从树的右侧看过去时可见的节点集合，即右视图中的每个节点都是某一层中最右侧的节点。

{{ select(12) }}

• 
• 
• 
• 

13. 下列关于树的深度优先搜索(DFS)的说法中，正确的是( )。 {{ select(13) }}

• 对树进行 DFS 时，一定是按层从上到下依次访问结点
• 对任意一棵树进行 DFS，得到的遍历序列唯一
• 对一棵树进行 DFS 时，常借助递归或栈实现
• DFS 只能用于二叉树，不能用于普通树

14. 小朋友们去邻里拜年，每个家里有不同数量的糖果。规则是：不能连续进入两个相邻的房子(即不能同时取相邻两家的糖果)。目标是拿到最多糖果。以下是代码实现，请补全横线。

    

    {{ select(14) }}

• dp[i] = dp[i - 1] + nums[i];
• dp[i] = max(dp[i - 1], dp[i - 2] * nums[i]);
• dp[i] = max(dp[i - 1], dp[i - 2] + nums[i]);
• dp[i] = dp[i - 2] + nums[i];

15. 元宵节晚上，小朋友沿着一条发光石板路前进，每次可向前走 1 块或 2 块石板。动态规划定义如下：$dp[i] = dp[i - 1] + dp[i - 2]$，下面关于 $dp[i]$ 的含义最合适的是( )。 {{ select(15) }}

• 走到第 i 块石板的不同走法数量
• 走到第 i 块石板时，已经走过的石板总数
• 从第 i 块石板走回起点的最少步数
• 从第 i 块石板走回起点的最大步数

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

16. 下面定义了一个表示二维坐标点的类 Point，并提供了一个带参数的构造函数，但第 ② 行 Point b; 会调用编译器自动生成的默认构造函数，将b.x 和 b.y 被初始化为 0.0，程序可以正常编译运行。

    

    {{ select(16) }}

• 正确
• 错误

17. C++ 中的继承支持单继承和多继承，但子类无法直接访问父类的私有成员。

    {{ select(17) }}

• 正确
• 错误

18. 对如下结构的树，执行travel 函数，输出结果是 1 2 3 4 5。

{{ select(18) }}

• 正确
• 错误

19. 若所有字符出现频率相同，则哈夫曼编码一定会得到完全二叉树。

    {{ select(19) }}

• 正确
• 错误

20. 哈夫曼编码是一种变长的前缀编码，在解码时不需要额外的分隔符就能唯一还原，这是因为在哈夫曼树中，任何一个字符的叶子结点都不会成为另一个字符结点的祖先。

    {{ select(20) }}

• 正确
• 错误

21. 在 C++ 中使用一维数组 vector<int> tree 存储按层序遍历的完全二叉树时，若根节点存储在 tree[0]，则对于任意非空节点 tree[i]，其右孩子(如果存在)必然位于 tree[2 * i + 2]。

    {{ select(21) }}

• 正确
• 错误

22. 在 C++ 中使用栈来非递归地实现二叉树的前序遍历时，为了保证遍历顺序正确，在处理完当前结点后，应该先将该结点的左孩子压入栈中，然后再将右孩子压入栈中。

    {{ select(22) }}

• 正确
• 错误

23. 设二叉树共有 n 个结点，函数 preorderTraversal 以下代码的时间复杂度为 $O(n)$，空间复杂度为 $O(n)$。

{{ select(23) }}

• 正确
• 错误

24. 下列代码实现了一个0-1背包的一维动态规划代码，内层循环是经典的逆序写法。若将内层循环改成正序遍历(即 for (int j = w[i]; j <= W; j++) )，仍能得到正确答案。

    

    {{ select(24) }}

• 正确
• 错误

25. 在动态规划问题中，状态空间相同且没有重复计算的情况下，“状态转移方程+递推”与“递归+记忆化搜索”的时间复杂度通常相同。

    {{ select(25) }}

• 正确
• 错误