一、单选题逐题解析

第1题｜类的概念

在面向对象编程中，关于类的描述中，不正确的是？

答案：D

解析：类是可以通过继承（Inheritance）来扩展属性和方法的，也可以在派生类中添加新的成员。说"不能修改或扩展"完全违背了面向对象的核心设计理念。

第2题｜哈夫曼编码

关于哈夫曼编码的描述中，不正确的是？

答案：B

解析：这是经典易错点！在哈夫曼树中，频率越高的字符离根越近，编码越短；频率越低的字符离根越远，编码越长。B选项恰好说反了。

🔑 记忆口诀： 高频近根编码短，低频远根编码长。

第3题｜树的遍历识别

以下代码实现了哪种遍历？

void traverse(TreeNode* root) {  if (root == nullptr) return;  cout << root->val << ” ”; // 先访问根  traverse(root->left); // 再递归左子树  traverse(root->right); // 最后递归右子树 }

答案：A（前序遍历）

解析： 遍历顺序由访问根节点的位置决定：

• 根→左→右 = 前序遍历
• 左→根→右 = 中序遍历
• 左→右→根 = 后序遍历

本题先输出根节点值，再递归左右，是标准前序遍历。

第4题｜完全二叉树判断

以下代码用于判断什么？

bool isCompleteTree(TreeNode* root) { // BFS遍历，标记是否遇到过空节点 // 若遇到空节点后还有非空节点 → 不是完全二叉树 }

答案：B（判断是否为完全二叉树）

解析：代码使用BFS逐层扫描，核心逻辑是：一旦遇到空节点，后续不应再出现非空节点。这正是完全二叉树的定义——所有层满填，最后一层从左到右连续。

💡 区分完全二叉树 vs 满二叉树：满二叉树所有节点都有0或2个子节点，完全二叉树只要求"最后一层左对齐"。

第5题｜二叉排序树操作识别

以下代码实现了BST的哪种操作？

TreeNode* op(TreeNode* root, int val) {  if (root == nullptr) return new TreeNode(val); // 空位→创建新节点  if (val < root->val)  root->left = op(root->left, val); // 小→往左  else  root->right = op(root->right, val); // 大→往右  return root; }

答案：B（插入）

解析： 三个关键特征锁定"插入"操作：

1. 遇到空位时 new TreeNode(val) → 创建新节点
2. 按BST规则（小左大右）递归寻找插入位置
3. 返回修改后的子树根节点

如果是查找，找到就返回节点指针，不会new；如果是删除，会有找前驱/后继的逻辑。

第6题｜哈夫曼编码计算

字符集{A,B,C,D}频率{5,1,6,2}，正确的哈夫曼编码是？

答案：B（A:11, B:100, C:0, D:101）

解析： 手动建哈夫曼树是六级必考技能，完整过程如下：

Step 1： 按频率排序：B(1), D(2), A(5), C(6)

Step 2： 取最小的两个合并：

• B(1) + D(2) = 3

Step 3： 剩余{3, A(5), C(6)}，取最小的两个：

• 3 + A(5) = 8

Step 4： 剩余{8, C(6)}：

• C(6) + 8 = 14（根节点）

最终哈夫曼树：

14 / \ C(6) 8 / \ 3 A(5) / \ B(1) D(2)

编码结果： 左0右1 → C:0, A:11, B:100, D:101

🔑 验证技巧： 频率最高的C编码最短(1位)，频率最低的B编码最长(3位)。

第7题｜动态规划基本概念

关于动态规划的描述，正确的是？

答案：B

解析： 动态规划的两个必要条件：

1. 最优子结构
   ：大问题的最优解包含小问题的最优解
2. 重叠子问题
   ：递归过程中会重复计算相同子问题

分治法的子问题互不重叠（如归并排序），DP的子问题有重叠（如斐波那契），这是两者的关键区别。

第8题｜构造函数调用次数

classMyClass{ public:  MyClass() { cout << ”Constructor called!” << endl; } }; int main() {  MyClass obj1; // ①  MyClass obj2 = obj1; // ②  return 0; }

构造函数被调用了几次？

答案：A（1次）

解析： 这是经典陷阱题！

• ① MyClass obj1; → 调用默认构造函数 ✅
• ② MyClass obj2 = obj1; → 调用的是拷贝构造函数（编译器自动生成），不是默认构造函数！

所以默认构造函数只被调用1次。题目问的是"构造函数"，如果理解为"默认构造函数"，答案为1；如果理解为所有构造函数（包括拷贝构造），答案为2。根据选项和出题意图，答案选A。

⚠️ 易错提醒：MyClass obj2 = obj1;是拷贝初始化，不是赋值！它调用拷贝构造函数，而非 operator=。

第9题｜循环队列操作识别

boolenQueue(intvalue) { if (isFull()) return false; if (isEmpty()) front = 0; rear = (rear + 1) % size; arr[rear] = value; return true; }

答案：A（入队）

解析： 三个特征确认是入队操作：

1. 先检查是否满队 isFull()
2. 空队时初始化 front = 0
3. rear = (rear + 1) % size
    是循环队列尾指针后移的标准写法
4. arr[rear] = value
    放入元素

第10题｜DFS统计叶子节点

横线处应填什么？

intcountLeafNodes(TreeNode* root){  stack<TreeNode*> s;  s.push(root);  int count = 0;  while (!s.empty()) {  TreeNode* node = s.top(); s.pop();  if (node->left == nullptr && node->right == nullptr) count++;  if (node->right) s.push(node->right);  // ________________________ 填空  }  return count; }

答案：A（if (node->left) s.push(node->left);）

解析：使用栈实现DFS时，为了实现"先左后右"的访问顺序，需要先压右子节点，再压左子节点（栈是后进先出）。前一行已经压了右子节点，所以横线处应该压左子节点。

💡 栈的LIFO特性决定了压栈顺序与访问顺序相反：想先访问左→就要后压左（让左在上面）。

第11题｜BFS查找节点

横线处应填什么？

TreeNode* findNode(TreeNode* root, int target){ queue<TreeNode*> q; q.push(root); while (!q.empty()) { TreeNode* current = q.front(); q.pop(); if (current->val == target) return current; // ________________________ 填空 } return nullptr; }

答案：A（if (current->left) q.push(current->left); if (current->right) q.push(current->right);）

解析：BFS使用队列，核心操作就是：弹出当前节点，将其子节点入队。选项A正是标准的BFS子节点入队操作。

其他选项错误原因：q.pop() 是弹出不是插入；q.front()是查看队首不是插入；左右互换入队不影响正确性但不符合标准写法——但注意选项D将left和right互换push了，虽然BFS结果不受影响，但A是标准写法。

第12题｜格雷编码生成

vector<string> generateGrayCode(int n){  if (n == 0) return {”0”};  if (n == 1) return {”0”, ”1”};  vector<string> prev = generateGrayCode(n - 1);  vector<string> result;  for (string s : prev) {  result.push_back(”0” + s); // 前半部分加0  }  for (int i = prev.size() - 1; i >= 0; i--) {  // ________________________ 填空  }  return result; }

答案：A（result.push_back("1" + prev[i]);）

解析： 格雷编码的递归构造法（镜像法）：

1. 取n-1位格雷编码
2. 前半部分：每个编码前加"0"
3. 后半部分：将前半部分逆序，每个编码前加"1"

逆序遍历 + 前缀加"1"，所以填 result.push_back("1" + prev[i])。

🔑 格雷编码核心：相邻两个编码恰好有1位不同。镜像反转+加不同前缀保证了连接处也只有1位不同。

第13题｜0/1背包DP

dp[i][j] = max(_________________________);

答案：B（dp[i-1][j], dp[i-1][j - weights[i-1]] + values[i-1]）

解析： 0/1背包的状态转移方程是六级核心考点：

$dp[i][j] = \max(dp[i-1][j], \ dp[i-1][j-w_i] + v_i)$

• 不选第i个物品：dp[i-1][j]
  ，背包容量不变
• 选第i个物品：dp[i-1][j-w_i] + v_i
  ，容量减少$w_i$，价值增加$v_i$

取两者较大值即可。

第14题｜括号匹配

函数末尾应返回什么？

boolisBalanced(string s){  stack<char> st;  for (char c : s) {  if (c == '(' || c == '[' || c == '{') st.push(c);  else {  if (st.empty()) return false;  char top = st.top(); st.pop();  if (不匹配) return false;  }  }  return ________________; }

答案：C（st.empty()）

解析：循环结束后，如果栈为空，说明所有左括号都找到了匹配；如果栈非空，说明有未匹配的左括号。所以返回 st.empty() — 为true表示匹配，false表示不匹配。

第15题｜面向对象多态

关于以下代码，说法错误的是？

Shape* shapePtr = &circle; // 基类指针指向派生类对象 shapePtr->area(); // 调用Circle::area() shapePtr = &rectangle; shapePtr->area(); // 调用Rectangle::area()

答案：A

解析：A说"出现编译错误"——这完全错误！基类指针指向派生类对象是C++多态的标准用法，完全合法。正是因为 area() 被声明为virtual，才能在运行时根据实际对象类型调用正确的函数实现，这就是运行时多态。

B、C、D的描述都是正确的。

二、判断题逐题解析

第1题 ✅ 对

哈夫曼树每次合并权值最小的两个节点，最终带权路径长度最小。

正确。 这是哈夫曼算法的基本性质，也是贪心选择正确性的保证。

第2题 ❌ 错

格雷编码的相邻两个编码之间必须有多位不同。

错误！格雷编码的核心特征恰恰是相邻两个编码之间只有1位不同。这正是格雷编码被发明的原因——减少数据传输时的错误。

第3题 ❌ 错

DFS使用队列作为辅助数据结构以实现"先进后出"。

错误！DFS使用栈（Stack），实现后进先出（LIFO）；BFS才使用队列（Queue），实现先进先出（FIFO）。题目把DFS和BFS的数据结构搞混了。

第4题 ✅ 对

以下代码实现的是二叉树的中序遍历。

void traverse(TreeNode* root) {  if (root == nullptr) return;  traverse(root->left); // 先左  cout << root->val << ” ”; // 再根  traverse(root->right); // 后右 }

正确。 左→根→右，标准中序遍历。

第5题 ✅ 对

C++支持构造函数重载，但默认无参构造函数只能有一个。

正确。函数重载要求参数列表不同，无参构造函数没有参数，自然只能有一个。如果定义了其他构造函数，编译器不再自动生成默认构造函数。

第6题 ❌ 错

BST中，若某节点左子树为空，则该节点一定是树中的最小值节点。

错误！ 反例：

5 \ 8

节点8的左子树为空，但5才是最小值。只有根节点的左子树为空时，根节点才是最小值。对于非根节点，它只是自身子树的最小值，不一定是整棵树的最小值。

第7题 ✅ 对

硬币面额[1,3,4]，目标金额6，最少需要2枚硬币（3+3）。

正确。 DP验证：

• dp[6] = min(dp[5]+1, dp[3]+1, dp[2]+1) = min(3, 2, 3) = 2
• 3+3=6，确实只需2枚。

⚠️ 注意：贪心策略（先选最大的4）会得到4+1+1=3枚，不是最优！这就是为什么需要DP。

第8题 ✅ 对

封装是将数据和行为绑定在一起，并对外隐藏实现细节。

正确。 这是封装（Encapsulation）的标准定义。C++通过 private/protected/public访问控制实现封装。

第9题 ✅ 对

代码创建的树是一棵完全二叉树。

TreeNode* root = new TreeNode{1}; root->left = new TreeNode{2}; root->right = new TreeNode{3}; root->left->left = new TreeNode{4};

树形结构：

1 / \ 2 3 / 4

正确。完全二叉树要求：除最后一层外所有层满填，最后一层从左到右连续。该树第0、1层满填，第2层只有4在最左，满足条件。

第10题 ✅ 对

栈和队列均可以用双向链表实现，插入和删除O(1)。

正确。双向链表在头部和尾部都可以O(1)插入/删除，天然适合实现栈（头部操作）和队列（头删尾插）。

💬 互动时间： 你觉得这次考试哪道题最坑？欢迎在评论区吐槽讨论！

📌 关注我们，获取更多信奥真题解析和备考干货！

本文由编程信奥王老师原创整理，转载请注明出处。