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

1. 下列哪一项不是面向对象编程的基本特征？

   {{ select(1) }}

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

2. 为了让 Dog 类的构造函数能正确地调用其父类 Animal 的构造方法，横线处应填入（ ）。

{{ select(2) }}

• Animal(name)
• super(name)
• Animal::Animal(name)
• Animal()

3.（与上一题同一段代码）代码执行结果是（ ）。 {{ select(3) }}

• 输出 Animal speaks
• 输出 Dog barks
• 编译错误
• 程序崩溃

4. 以下关于栈和队列的代码，执行后输出是（ ）。

{{ select(4) }}

• 1 3
• 3 1
• 3 3
• 1 1

5. 在一个循环队列中，front 指向队头，rear 指向队尾，队列最大容量为 maxSize。判断队列已满的条件是（ ）。 {{ select(5) }}

• rear == front
• (rear + 1) % maxSize == front
• (rear - 1 + maxSize) % maxSize == front
• (rear - 1) == front

6.（ ）只有最底层的节点未被填满，且最底层节点尽量靠左填充。 {{ select(6) }}

• 完美二叉树
• 完全二叉树
• 完满二叉树
• 平衡二叉树

7. 在使用数组表示完全二叉树时，如果一个节点的索引为 i（从 0 开始计数），那么其左子节点的索引通常是（ ）。 {{ select(7) }}

• $\dfrac{i - 1}{2}$
• $i + 1$
• $i \times 2$
• $2 \times i + 1$

8. 已知一棵二叉树的前序遍历序列为 GDAFEMHZ，中序遍历序列为 ADFGEHMZ，则其后序遍历序列为（ ）。 {{ select(8) }}

• ADFGEHMZ
• ADFGHMEZ
• AFDGEMZH
• AFDHZMEG

9. 设有字符集 {a, b, c, d, e}，其出现频率分别为 {5, 8, 12, 15, 20}，得到的哈夫曼编码为（ ）。 {{ select(9) }}

• a: 010
  b: 011
  c: 00
  d: 10
  e: 11
  

• a: 00
  b: 10
  c: 011
  d: 100
  e: 111
  

• a: 10
  b: 01
  c: 011
  d: 100
  e: 111
  

• a: 100
  b: 01
  c: 011
  d: 100
  e: 00
  

10. 3 位格雷编码中，编码 101 之后的下一个编码不可能是（ ）。 {{ select(10) }}

• 100
• 111
• 110
• 001

11. 请将下列 C++ 实现的深度优先搜索（DFS）代码补充完整，横线处应填入（ ）。

{{ select(11) }}

• result.push_back(root->val);
  dfs(root->left);
  dfs(root->right);
  

• result.push_back(root->left->val);
  dfs(root->right);
  dfs(root->left);
  

• result.push_back(root->left->val);
  dfs(root->left);
  dfs(root->right);
  

• result.push_back(root->right->val);
  dfs(root->right);
  dfs(root->left);
  

12. 给定一个二叉树，返回每一层中最大的节点值（层序遍历），横线处应填入（ ）。

{{ select(12) }}

• node = q.end();
• node = q.front();
• q.pop(); node = q.front();
• node = q.front(); q.pop();

13. 下面代码实现一个二叉排序树的插入函数（没有相同的数值），横线处应填入（ ）。

{{ select(13) }}

• if (key < root->val)
      insert(root->left, key);
  else if (key > root->val)
      insert(root->right, key);
  

• if (key < root->val)
      insert(root->right, key);
  else if (key > root->val)
      insert(root->left, key);
  

• insert(root->left, key);
  insert(root->right, key);
  

• insert(root->right, key);
  insert(root->left, key);
  

14. 以下关于动态规划算法特性的描述，正确的是（ ）。

{{ select(14) }}

• 子问题相互独立，不重叠
• 问题包含重叠子问题和最优子结构
• 只能从底至顶迭代求解
• 必须使用递归实现，不能使用迭代

15. 给定 $n$ 个物品和一个最大承重为 W 的背包，每个物品有重量 wt[i] 和价值 val[i]，每件物品只能选或不选。关于下面的一维 $0/1$ 背包代码，说法正确的是（ ）。

{{ select(15) }}

• 该算法不能处理背包容量为 0 的情况
• 外层循环 i 遍历背包容量，内层遍历物品
• 从大到小遍历 w 是为了避免重复使用同一物品
• 这段代码计算的是最小重量而非最大价值

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

16. 构造函数可以被声明为 virtual。 {{ select(16) }}

• 正确
• 错误

17. 给定一组字符及其出现的频率，构造出的哈夫曼树是唯一的。 {{ select(17) }}

• 正确
• 错误

18. 为了实现一个队列，使其出队操作（pop）的时间复杂度为 $O(1)$ 并且避免数组删除首元素的 $O(n)$ 问题，常见有效的方法是使用​环形数组。 {{ select(18) }}

• 正确
• 错误

19. 对一棵二叉排序树进行​中序遍历​，可以得到一个递增的有序序列。 {{ select(19) }}

• 正确
• 错误

20. 如果二叉搜索树在连续的插入和删除操作后，所有节点都偏向一侧，导致其退化为类似于链表的结构，这时其查找、插入、删除操作的时间复杂度会从理想情况下的 $O(\log n)$ 退化到 $O(n \log n)$。

    {{ select(20) }}

• 正确
• 错误

21. 执行下列代码，my_dog.name 的最终值是 Charlie。

{{ select(21) }}

• 正确
• 错误

22. 下列 C++ 代码可以成功编译，并且子类 Child 的实例能通过其成员函数访问父类 Parent 的私有属性 value。

{{ select(22) }}

• 正确
• 错误

23. 下列代码中的 tree 向量，表示的是一棵​完全二叉树（-1 代表空节点）按照层序遍历的结果。

{{ select(23) }}

• 正确
• 错误

24. 在树的深度优先搜索（DFS）中，使用栈作为辅助数据结构以实现“先进后出”的访问顺序。 {{ select(24) }}

• 正确
• 错误

25. 下面代码采用动态规划求解零钱兑换：给定若干硬币面值 coins，目标金额 amt，每种硬币可重复选取；若无法凑出目标金额，返回 -1。

{{ select(25) }}

• 正确
• 错误