一、单选题（每题 2 分，共 30 分）
第 1 题
下列代码执行后的输出结果是（ ）。
class Animal {
public:
virtual void speak() {
cout << "Animal ";
}
virtual ~Animal() = default;
};
class Cat : public Animal {
public:
void speak() override {
cout << "Cat ";
}
};
int main() {
Animal *p = new Cat();
p->speak();
delete p;
return 0;
}
A. Animal
B. Cat
C. Animal Cat
D. 编译错误
答案：B
知识点解析
本题考查虚函数与多态（动态绑定）。speak 在基类中声明为 virtual，派生类 Cat 用 override 重写了它。当基类指针 p 指向派生类对象时，通过 p 调用虚函数会在运行期根据对象的实际类型绑定到 Cat::speak，输出 Cat。若没有 virtual 关键字，则会按指针的静态类型调用 Animal::speak。这正是 C++ 多态机制的核心：虚函数 + 基类指针/引用。
第 2 题
下列代码中，横线处应填写（ ），才能正确调用基类的带参数构造函数。
class Machine {
protected:
string id;
public:
Machine(string s) : id(s) {}
};
class Robot : public Machine {
int level;
public:
Robot(string s, int n) : __________, level(n) {}
};
A. Machine(s)
B. Machine::id(s)
C. super(s)
D. id(s)
答案：A
知识点解析
本题考查派生类构造函数对基类构造函数的调用方式。当基类没有默认构造函数时，派生类必须在初始化列表中用“基类名(参数)”的形式显式调用基类构造函数，即 Machine(s)，A 正确。C 的 super(s) 是其他语言（如 Java）的写法，C++ 中不存在；B 不是合法的构造调用语法；D 中 id 是基类的成员，派生类不能在初始化列表中直接初始化基类的成员，必须通过基类构造函数完成。
第 3 题
下列代码执行后的输出顺序是（ ）。
class Base {
public:
Base() {
cout << "B ";
}
virtual ~Base() {
cout << "~B ";
}
};
class Derived : public Base {
public:
Derived() {
cout << "D ";
}
~Derived() {
cout << "~D ";
}
};
int main() {
Base *p = new Derived();
delete p;
return 0;
}
A. B D ~B ~D
B. D B ~D ~B
C. B D ~D ~B
D. B D ~B
答案：C
知识点解析
本题考查构造函数与析构函数的调用顺序。构造时先基类后派生类，输出 B D；析构时顺序严格相反，先派生类后基类，输出 ~D ~B。另外，由于基类析构函数是 virtual，用 Base* 指针 delete 派生类对象时会先调用 ~Derived 再调用 ~Base（若析构函数不是虚函数，通过基类指针 delete 派生类对象的行为是未定义的）。完整输出为 B D ~D ~B，选 C。
第 4 题
下列代码执行后的输出结果是（ ）。
stack<int> s;
queue<int> q;
for (int i = 2; i <= 6; i += 2) {
s.push(i);
q.push(i);
}
s.pop();
q.pop();
cout << s.top() << " " << q.front();
A. 2 4
B. 4 4
C. 4 6
D. 6 2
答案：B
知识点解析
本题考查 stack（后进先出）与 queue（先进先出）的行为区别。两者依次压入 2、4、6：栈执行 s.pop() 弹出的是栈顶 6，再取 s.top() 得 4；队列执行 q.pop() 弹出的是队首 2，再取 q.front() 得 4。因此输出 “4 4”，选 B。C、D 选项都是把两种数据结构的取出规则弄混所致。
第 5 题
下面循环队列采用“空出一个位置”的方式区分队空和队满。横线处应填写（ ）。
const int MAXN = 8;
int data[MAXN];
int front = 0, rear = 0;
bool full() {
return __________________________;
}
A. rear == front
B. (front + 1) % MAXN == rear
C. (rear + 1) % MAXN == front
D. rear == MAXN - 1
答案：C
知识点解析
本题考查循环队列“牺牲一个存储单元”判满的方法。rear 指向下一个待插入位置、front 指向队首。当 (rear + 1) % MAXN == front 时，说明再插入一个元素 rear 就会“追上” front，此时数组中恰好只剩一个空位，约定此状态为队满，C 正确。A 选项 rear == front 是队空的条件，若用它判满就无法区分空与满；B 选项把 front 和 rear 的角色写反了；D 选项只适用于不回绕的线性数组，忽略了循环队列对 MAXN 取模的特性。
第 6 题
下列函数实现了二叉树的哪种遍历方式（ ）。
void visit(TreeNode *root) {
if (root == nullptr)
return;
visit(root->left);
cout << root->val << " ";
visit(root->right);
}
A. 前序遍历
B. 中序遍历
C. 后序遍历
D. 层序遍历
答案：B
知识点解析
本题考查二叉树遍历方式的区分。代码先递归访问左子树，再输出根结点的值，最后递归访问右子树，访问顺序为“左 → 根 → 右”，是中序遍历，选 B。前序遍历是“根 → 左 → 右”（输出语句在两次递归之前），后序遍历是“左 → 右 → 根”（输出语句在两次递归之后），层序遍历则需借助队列逐层访问，与递归写法无关。
第 7 题
已知一棵二叉树的先序遍历序列为 A B D E C F，中序遍历序列为 D B E A C F，则其后序遍历序列是（ ）。
A. D E B F C A
B. D B E F C A
C. E D B F C A
D. D E B C F A
答案：A
知识点解析
本题考查由先序 + 中序序列还原二叉树并求后序。先序首个元素 A 是根；在中序 D B E A C F 中，A 左侧的 D B E 属于左子树、右侧的 C F 属于右子树。左子树：先序 B D E、中序 D B E，根为 B，D 是其左孩子、E 是其右孩子；右子树：先序 C F、中序 C F，根为 C，F 是其右孩子。后序按“左 → 右 → 根”输出：左子树得 D E B，右子树得 F C，最后是根 A，即 D E B F C A，选 A。
第 8 题
下面函数用于计算二叉树的高度，横线处应填写（ ）。
int height(TreeNode *root) {
if (root == nullptr)
return 0;
int leftH = height(root->left);
int rightH = height(root->right);
return __________________________;
}
A. leftH + rightH
B. min(leftH, rightH) + 1
C. max(leftH, rightH)
D. max(leftH, rightH) + 1
答案：D
知识点解析
本题考查二叉树高度的递归定义。树的高度等于 1 加上左右子树高度的较大值：空树高度为 0，非空树取左右子树中更深的一棵，再加上根结点所在的这一层，故填 max(leftH, rightH) + 1，D 正确。A 选项把两棵子树高度相加，只在特殊形态下碰巧正确；B 选项取 min 求的是最浅分支相关量；C 选项忘记加上根结点这一层，对所有非空树都少 1。
第 9 题
以下代码实现二叉树左子树优先的深度优先搜索算法，则横线上应填写（ ）。
void dfs(TreeNode *root) {
if (root == nullptr)
return;
stack<TreeNode *> s;
s.push(root);
while (!s.empty()) {
TreeNode *node = s.top();
s.pop();
cout << node->value << " ";
________________________ // 在此处填入代码
}
}
A.
s.push(node->right);
s.push(node->left);
B.
s.push(node->left);
s.push(node->right);
C.
if (node->right)
s.push(node->right);
if (node->left)
s.push(node->left);
D.
if (node->left)
s.push(node->left);
if (node->right)
s.push(node->right);
答案：C
知识点解析
本题考查用栈模拟深度优先搜索的入栈顺序。栈是后进先出的，若想先访问左子树，就必须让右子树先入栈、左子树后入栈（后入栈的先出栈被访问），因此先 push(node->right) 再 push(node->left)；同时入栈前必须判空，否则空指针入栈后出栈解引用会崩溃。C 选项两个条件都满足。A 选项没有判空，遇到叶子结点就会出错；B、D 选项入栈顺序颠倒，会先访问右子树，不是“左子树优先”。
第 10 题
下面函数在二叉搜索树中查找值 x。横线处应填写（ ）。
TreeNode *searchBST(TreeNode *root, int x) {
if (root == nullptr || root->val == x)
return root;
if (x < root->val)
return searchBST(root->left, x);
return __________________________;
}
A. searchBST(root->left, x)
B. searchBST(root->right, x)
C. searchBST(root, x + 1)
D. root->right
答案：B
知识点解析
本题考查二叉搜索树（BST）的查找性质。BST 满足“左子树所有结点 < 根 < 右子树所有结点”。前两个分支已处理“空树/已找到”与“x 较小去左子树”的情况，剩下 x > root->val 时目标只可能在右子树，应递归 searchBST(root->right, x)，B 正确。A 选项与上一分支重复且方向错误；C 选项改变查找目标没有意义；D 选项直接返回右孩子结点，没有继续向下查找，找到的未必是值为 x 的结点。
第 11 题
有 5 个字符，其出现频率分别为 2、4、5、9、12。按哈夫曼算法构造编码树，其最小带权路径长度 WPL 为（ ）。
A. 68
B. 69
C. 71
D. 73
答案：B
知识点解析
本题考查哈夫曼树的构造过程与 WPL 的计算。哈夫曼算法每次从集合中取出权值最小的两棵树合并。过程：2 + 4 = 6；5 + 6 = 11；9 + 11 = 20；12 + 20 = 32。WPL 等于各次合并产生的权值之和（即所有非叶结点权值总和）：6 + 11 + 20 + 32 = 69。也可用“叶权值 × 深度”验证：12 深度 1、9 深度 2、5 深度 3、2 和 4 深度 4，WPL = 12 + 18 + 15 + 8 + 16 = 69，选 B。
第 12 题
下面代码用反射法生成 n 位格雷编码，横线处应填写（ ）。
vector<string> gray(int n) {
vector<string> ans = {"0", "1"};
for (int bit = 2; bit <= n; ++bit) {
int oldSize = ans.size();
for (int i = oldSize - 1; i >= 0; --i)
ans.push_back(__________________________);
for (int i = 0; i < oldSize; ++i)
ans[i] = "0" + ans[i];
}
return ans;
}
A. ans[i] + "1"
B. "0" + ans[i]
C. "1" + ans[i]
D. ans[oldSize - i - 1]
答案：C
知识点解析
本题考查反射法构造格雷码。n 位格雷码由 n-1 位格雷码扩展而来：原序列正序加前缀 “0”，原序列逆序加前缀 “1”，这样相邻编码仍只差一位。代码中第二个循环已给原有编码统一加前缀 “0”，横线处是逆序复制时加前缀 “1”，故填 “1” + ans[i]，C 正确。A 是后缀拼接，不改变前缀，无法保证相邻只差一位；B 没有加前缀 “1”，逆序复制出的串与第二个循环加了前缀 “0” 之后的原编码完全相同，产生重复编码；D 没有添加任何前缀。
第 13 题
下面代码计算走到第 n 级台阶的方法数，每次可以走 1 级或 2 级。横线处应填写（ ）。
int ways(int n) {
if (n <= 2)
return n;
vector<int> dp(n + 1);
dp[1] = 1;
dp[2] = 2;
for (int i = 3; i <= n; ++i)
dp[i] = __________________________;
return dp[n];
}
A. dp[i - 1] + 1
B. dp[i - 1] + dp[i - 2]
C. dp[i - 2] + 2
D. 2 * dp[i - 1]
答案：B
知识点解析
本题考查动态规划入门——爬楼梯问题。走到第 i 级的最后一步只有两种可能：从第 i-1 级走 1 级，或从第 i-2 级走 2 级，两类方案互不重叠且覆盖所有情况，故 dp[i] = dp[i-1] + dp[i-2]，即斐波那契数列，B 正确。A、C 选项把“方案数”与“步数”混为一谈；D 选项翻倍没有实际意义。边界 dp[1] = 1、dp[2] = 2（1+1 与 2 两种走法）也与该递推吻合。
第 14 题
下面代码求从包含非负元素的数组中选择若干个互不相邻元素所能得到的最大和。横线处应填写（ ）。
int maxSum(vector<int> &a) {
int n = a.size();
if (n == 0)
return 0;
if (n == 1)
return a[0];
vector<int> dp(n);
dp[0] = a[0];
dp[1] = max(a[0], a[1]);
for (int i = 2; i < n; ++i)
dp[i] = __________________________;
return dp[n - 1];
}
A. dp[i - 1] + a[i]
B. dp[i - 2] + a[i]
C. max(dp[i - 1], dp[i - 2] + a[i])
D. max(dp[i - 1], a[i])
答案：C
知识点解析
本题考查“打家劫舍”型线性 DP（选互不相邻元素求最大和）。对第 i 个元素只有两种决策：不选它，答案继承 dp[i-1]；选它，则第 i-1 个不能选，答案为 dp[i-2] + a[i]。两者取最大值，即 max(dp[i-1], dp[i-2] + a[i])，C 正确。A 选项没有排除相邻冲突；B 选项漏掉了“不选第 i 个”的情况（如 a = {3, 10, 1} 时，按 B 计算 dp[2] = dp[0] + a[2] = 4，而正确答案是只选 10 这个元素，应为 10）；D 选项忽略了 dp[i-2] 中可能累积的更优解。由于数组元素非负，该转移可以正确求解。
第 15 题
下面是一维数组实现的 0/1 背包。内层循环必须从大到小枚举容量，主要原因是（ ）。
for (int i = 0; i < n; ++i) {
for (int w = W; w >= weight[i]; --w) {
dp[w] = max(dp[w], dp[w - weight[i]] + value[i]);
}
}
A. 保证每件物品最多被选择一次
B. 保证物品必须按照重量从大到小选择
C. 降低时间复杂度到 O(n)
D. 防止数组 dp 发生越界
答案：A
知识点解析
本题考查 0/1 背包一维优化的原理。二维转移 dp[i][w] 依赖的是上一行（第 i-1 件物品时）的 dp[i-1][w - weight[i]]。一维滚动时，若容量从小到大枚举，更新 dp[w] 时 dp[w - weight[i]] 已在本轮被更新过（可能已包含物品 i），相当于物品 i 被重复选取，变成了完全背包；只有从大到小枚举，才能保证计算 dp[w] 时用到的还是“尚未考虑物品 i”的旧值，即每件物品最多选一次，A 正确。B、D 与枚举顺序无关；时间复杂度仍是 O(nW)，C 错误。
二、判断题（每题 2 分，共 20 分）
第 1 题
下列代码可以正常编译，因为编译器会自动为 Student 类生成一个无参数构造函数。
class Student {
public:
Student(int x) {
age = x;
}
private:
int age;
};
int main() {
Student s;
}
答案：×
知识点解析
本题考查默认构造函数的生成规则。只要类中显式定义了任何一个构造函数（如 Student(int)），编译器就不再自动生成无参的默认构造函数，因此 Student s; 找不到匹配的构造函数，无法编译。若既要保留带参构造又要支持无参创建，需自己补写 Student() = default; 或给参数设置默认值。说法错误。
第 2 题
下列代码合法，因为派生类可以直接访问基类的私有成员 value。
class Base {
private:
int value = 10;
};
class Child : public Base {
public:
int get() {
return value;
}
};
答案：×
知识点解析
本题考查访问控制与继承的关系。基类的 private 成员虽然被派生类对象“拥有”，但对派生类的成员函数完全不可见，Child::get() 中直接访问 value 会编译失败。若希望派生类能访问，应把 value 声明为 protected（对派生类可见、对外界仍封闭），或通过基类提供的公有接口访问。说法错误。
第 3 题
下列代码执行后，输出结果为 30。
queue<int> q;
q.push(10);
q.push(20);
q.push(30);
q.pop();
cout << q.front();
答案：×
知识点解析
本题考查队列的先进先出特性。依次入队 10、20、30 后，q.pop() 移除的是最先入队的 10，此时队首变为 20，输出应为 20 而不是 30。若把队列当成栈（后进先出、弹出 30），就会得出错误结论。说法错误。
第 4 题
一棵完全二叉树按照从上到下、从左到右的顺序，将节点依次存储在数组 tree[1]、tree[2]、…… 中。若节点 tree[i] 存在左孩子，则其左孩子存储在 tree[2 * i] 中。
答案：√
知识点解析
本题考查完全二叉树的数组存储性质。从 1 开始按层序（从上到下、从左到右）编号存储时，下标满足：结点 i 的左孩子是 2i、右孩子是 2i + 1、父结点是 i / 2。这一性质使得完全二叉树无需指针即可用数组表示，也是堆（priority_queue 的底层结构）实现的基础。说法正确。
第 5 题
对任意一棵二叉搜索树执行中序遍历，得到的关键字序列一定是非递减的。
void inorder(TreeNode *root) {
if (!root)
return;
inorder(root->left);
cout << root->val << " ";
inorder(root->right);
}
答案：√
知识点解析
本题考查二叉搜索树（BST）的中序遍历性质。BST 满足“左子树 < 根 < 右子树”，而中序遍历按“左 → 根 → 右”访问。由递归结构归纳可知：左子树输出的所有值都小于根，右子树输出的所有值都大于根，因此整棵树的中序序列必然非递减。这也是“对 BST 中序遍历可得有序序列”这一经典结论，常用于验证一棵树是否为 BST。说法正确。
第 6 题
若使用下列代码从节点 start 开始访问一棵树，则第一次到达某个节点时所经过的边数，一定是从 start 到该节点的最少边数。
vector<int> tree[100];
bool visited[100];
int dist[100];
void search(int start) {
queue<int> q;
q.push(start);
visited[start] = true;
dist[start] = 0;
while (!q.empty()) {
int u = q.front();
q.pop();
for (int v : tree[u]) {
if (!visited[v]) {
visited[v] = true;
dist[v] = dist[u] + 1;
q.push(v);
}
}
}
}
答案：√
知识点解析
本题考查 BFS（广度优先搜索）求最短路的原理。队列先进先出，结点按与起点距离的远近“分层”入队：所有距离为 d 的结点处理完后，才会处理距离为 d + 1 的结点，且每个结点入队时用 dist[u] + 1 记录距离、用 visited 防止重复入队。因此每个结点第一次被访问时记录的距离就是从 start 到它的最少边数。在边权相等的图中，BFS 首次到达即最短。说法正确。
第 7 题
哈夫曼编码的生成过程基于贪心算法，出现频率越高的字符，其编码长度一定不会比出现频率更低的字符更长。
答案：√
知识点解析
本题考查哈夫曼编码的贪心性质。构造时每次合并当前权值最小的两棵树，频率越高的字符被合并得越晚，在树中的深度越浅，编码越短。可以证明：若字符 a 的频率高于 b，则哈夫曼树中 depth(a) ≤ depth(b)，否则交换它们的位置会得到 WPL 更小的树，与 WPL 最小矛盾。因此高频字符的编码长度一定不大于低频字符。说法正确。
第 8 题
在 n 位格雷码中，任意两个编码之间都只相差一个二进制位。
答案：×
知识点解析
本题考查格雷码的定义。格雷码的性质是“相邻”两个编码之间只相差一个二进制位，使按序遍历时每次只翻转一位，而不是“任意两个”编码都只差一位。反例：2 位格雷码 00、01、11、10 中，00 与 11 相差两位。把“相邻”扩大成“任意”是常见错误。说法错误。
第 9 题
下列一维动态规划代码实现的是完全背包问题，因为在处理第 i 种物品时，同一种物品可能被重复选择。
for (int i = 0; i < n; ++i) {
for (int w = weight[i]; w <= W; ++w) {
dp[w] = max(dp[w], dp[w - weight[i]] + value[i]);
}
}
答案：√
知识点解析
本题考查一维数组下完全背包与 0/1 背包的区别。内层容量 w 从小到大枚举时，计算 dp[w] 之前，dp[w - weight[i]] 已在“考虑第 i 种物品”的这一轮中被更新过，其中可能已包含物品 i，即同一种物品可以被重复选取——这正是完全背包的转移方式。而 0/1 背包每件物品至多选一次，必须让容量从大到小枚举。说法正确。
第 10 题
下列递归程序能得到正确的斐波那契数，其时间复杂度和空间复杂度都是 O(n)。
int fib(int n) {
if (n <= 1)
return n;
return fib(n - 1) + fib(n - 2);
}
答案：×
知识点解析
本题考查递归求斐波那契数的复杂度。fib(n) 的递归调用展开成一棵二叉树，fib(n-2)、fib(n-3) 等子问题被大量重复计算，调用次数随 n 指数级增长，时间复杂度为指数级（约 O(1.618ⁿ)，粗略上界 O(2ⁿ)），远超 O(n)；空间上受递归深度限制为 O(n)。若要达到时间 O(n)，应使用数组递推或记忆化搜索。说法错误。
三、编程题（每题 25 分，共 50 分）
数组划分
时间限制 1.0 s 内存限制 512.0 MB
题目描述
给定 n 个整数构成的数组 A = [a₁, a₂, ..., aₙ]。
你需要将数组 A 划分为若干非空连续子段。对于划分得到的某个子段，它的偏差值定义为子段内整数和的平方。划分方案的偏差值定义为所有子段偏差值之和。
你需要最小化划分方案的偏差值。
形式化地，你可以将 A 划分为若干非空连续子段 A₁, A₂, ..., Aₖ，使得 A = A₁ + A₂ + ... + Aₖ，这里的 + 代表数组的连接。对于 1 ≤ i ≤ k，设数组 Aᵢ = [a₁⁽ⁱ⁾, ..., aₘᵢ⁽ⁱ⁾] 包含 mᵢ 个整数。你需要最小化 ∑ᵏᵢ₌₁ (∑ᵐⁱⱼ₌₁ aⱼ⁽ⁱ⁾)²。
输入格式
第一行，一个正整数 n，表示数组 A 的长度。
第二行，n 个整数 a₁, a₂, ..., aₙ，表示数组 A。
输出格式
一行，一个整数，表示划分方案偏差值的最小值。
样例
4
1 2 -3 4
6
6
-1 -1 4 -5 -1 4
0
数据范围
对于 40% 的测试点，保证 0 ≤ aᵢ ≤ 50。
对于所有测试点，保证 1 ≤ n ≤ 2000，−100 ≤ aᵢ ≤ 100。
参考程序（答案）
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 2005;
const long long oo = 1e18;
int n;
int a[N], pre[N];
long long f[N];
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
pre[i] = pre[i - 1] + a[i];
}
for (int i = 1; i <= n; i++) {
f[i] = oo;
for (int j = 0; j < i; j++)
f[i] = min(f[i], f[j] + 1ll * (pre[i] - pre[j]) * (pre[i] - pre[j]));
}
printf("%lld\n", f[n]);
return 0;
}
分树规划
时间限制 1.0 s 内存限制 512.0 MB
题目描述
老师有一棵有 n 个结点的树，结点依次以 1, 2, ..., n 编号。
老师想将这棵树作为奖品分给两位同学。具体而言，老师会选择一条边并从树上删去它，从而将这棵树分为两个连通块。两位同学分别可以得到其中一个连通块。
如果有同学拿到的连通块结点数明显小于另一位同学，那么这位同学会不太高兴。为了避免这种情况出现，老师想知道两个连通块结点数之差的绝对值最小是多少。
输入格式
第一行，一个正整数 n，表示结点数量。
接下来 n − 1 行，每行两个正整数 uᵢ, vᵢ，表示一条连接结点 uᵢ 和结点 vᵢ 的边。
输出格式
输出一行，一个整数，表示答案。
样例
4
1 2
2 3
3 4
0
6
1 2
1 3
1 4
1 5
5 6
2
数据范围
对于 40% 的测试点，保证 2 ≤ n ≤ 500。
对于所有测试点，保证 2 ≤ n ≤ 2 × 10⁴。
参考程序（答案）
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 2e4 + 5;
const int E = N << 1;
int n;
int h[N], to[E], nx[E], et;
int ans;
void ae(int u, int v) {
et++;
to[et] = v;
nx[et] = h[u];
h[u] = et;
}
int dfs(int u, int p=0) {
int sz = 1;
for (int i = h[u]; i; i = nx[i])
if (to[i] != p)
sz += dfs(to[i], u);
ans = min(ans, abs(n - 2 * sz));
return sz;
}
int main() {
scanf("%d", &n);
for (int i = 1; i < n; i++) {
int u, v;
scanf("%d%d", &u, &v);
ae(u, v);
ae(v, u);
}
ans = n;
dfs(1);
printf("%d\n", ans);
return 0;
}
由于工作量较大，若存在错漏欢迎大家评论区指正。祝各位考生顺利通过！觉得有用，欢迎点赞、在看、转发三连。
