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

$1、$ 下列哪一项不是面向对象编程的基本特征？ {{ select(1) }}

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

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

01 class Animal {
02 public:
03     std::string name;
04     Animal(std::string str) : name(str) {
05         std::cout << "Animal created\n";
06     }
07     virtual void speak() {
08         cout << "Animal speaks" << endl;
09     }
10 };
11 class Dog : public Animal {
12     std::string breed;
13 public:
14     Dog(std::string name, std::string b) : _________________, breed(b) {
15         std::cout << "Dog created\n";
16     }
17     void speak() override {
18         cout << "Dog barks" << endl;
19     }
20 };
21 int main() {
22     Animal* p = new Dog("Rex", "Labrador");
23     p->speak();
24     delete p;
25     return 0;
26 }

{{ select(2) }}

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

$3、$ 代码同上一题，代码执行结果是（）。 {{ select(3) }}

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

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

01 stack<int> s;
02 queue<int> q;
03 for (int i = 1; i <= 3; ++i) {
04     s.push(i);
05     q.push(i);
06 }
07 cout << s.top() << " " << q.front() << endl;

{{ 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) }}

• (i - 1) / 2
• i + 1
• i * 2
• 2 * 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）代码补充完整，横线处应填入（）。

01 struct TreeNode {
02     int val;
03     TreeNode* left;
04     TreeNode* right;
05     TreeNode(int x): val(x), left(nullptr), right(nullptr) {}
06 };
07 void dfs(TreeNode* root, vector<int>& result) {
08     if (root == nullptr) return;
09     result.push_back(root->val);
10     dfs(root->left, result);
11     dfs(root->right, result);
12 }

{{ select(11) }}

• 
• 
• 
• 

$12、$ 给定一个二叉树，返回每一层中最大的节点值，结果以数组形式返回，横线处应填入（）。

01 #include <vector>
02 #include <queue>
03 #include <algorithm>
04 struct TreeNode {
05     int val;
06     TreeNode* left;
07     TreeNode* right;
08     TreeNode(int x): val(x), left(nullptr), right(nullptr) {}
09 };
10 vector<int> largestValues(TreeNode* root) {
11     vector<int> result;
12     if (!root) return result;
13     queue<TreeNode*> q;
14     q.push(root);
15     while (!q.empty()) {
16         int sz = q.size();
17         int maxVal = INT_MIN;
18         for (int i = 0; i < sz; ++i) {
19             TreeNode* node = q.front();
20             q.pop();
21             maxVal = max(maxVal, node->val);
22             if (node->left) q.push(node->left);
23             if (node->right) q.push(node->right);
24         }
25         result.push_back(maxVal);
26     }
27     return result;
28 }

{{ select(12) }}

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

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

01 struct TreeNode {
02     int val;
03     TreeNode* left;
04     TreeNode* right;
05     TreeNode(int x): val(x), left(nullptr), right(nullptr) {}
06 };
07 void insert(TreeNode*& root, int key) {
08     if (!root) {
09         root = new TreeNode(key);
10         return;
11     }
12     if (key < root->val)
13         insert(root->left, key);
14     else if (key > root->val)
15         insert(root->right, key);
16 }

{{ select(13) }}

• 
• 
• 
• 

$14、$ 以下关于动态规划算法特性的描述，正确的是（）。 {{ select(14) }}

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

$15、$ 给定 n 个物品和一个最大承重为 W 的背包，每个物品有一个重量 wt[i] 和价值 val[i]，每个物品只能选择放或不放。下面代码是 1D 动态规划的经典解法，关于下面代码，说法正确的是（）。

01 int knapsack1D(int W, vector<int>& wt, vector<int>& val, int n) {
02     vector<int> dp(W + 1, 0);
03     for (int i = 0; i < n; ++i) {
04         for (int w = W; w >= wt[i]; --w) {
05             dp[w] = max(dp[w], dp[w - wt[i]] + val[i]);
06         }
07     }
08     return dp[W];
09 }

{{ 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。

class Dog {
public:
    std::string name;
    Dog(std::string str) : name(str) {}
};
int main() {
    Dog my_dog("Buddy");
    my_dog.name = "Charlie";
    return 0;
}

{{ select(21) }}

• 正确
• 错误

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

01 class Parent {
02 private:
03     int value = 100;
04 };
05 class Child : public Parent {
06 public:
07     int get_private_val() {
08         return value;
09     }
10 };

{{ select(22) }}

• 正确
• 错误

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

01 #include <vector>
02 std::vector<int> tree = {1, 2, 3, 4, -1, 6, 7};

{{ select(23) }}

• 正确
• 错误

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

• 正确
• 错误

$25、$ 下列代码采用动态规划求解零钱兑换问题：给定若干硬币，第 i 种硬币的面值为 coins[i-1]，目标金额为 amt，每种硬币可以重复选取，求能够凑出目标金额的最少硬币数量；如果不能，则返回 -1。该算法正确且逻辑无误。

01 int coinChangeDPComp(vector<int> &coins, int amt) {
02     int n = coins.size();
03     int MAX = amt + 1;
04     vector<int> dp(amt + 1, MAX);
05     dp[0] = 0;
06     for (int i = 1; i <= n; i++) {
07         for (int a = 1; a <= amt; a++) {
08             if (coins[i - 1] > a)
09                 dp[a] = dp[a];
10             else
11                 dp[a] = min(dp[a], dp[a - coins[i - 1]] + 1);
12         }
13     }
14     return dp[amt] != MAX ? dp[amt] : -1;
15 }

{{ select(25) }}

• 正确
• 错误