ARTICLE · 1196932
C++ GESP 2026年9月六级真题及解析
一、单项选择题（共 15 题，每题 2 分，共计 30 分；每题有且仅有一个正确选项）
下列关于 C++ 中继承和多态的描述中，错误的是（ ）。
A. 通过基类指针调用虚函数时，会根据对象实际类型决定调用版本。
B. 基类析构函数常声明为虚函数，以便通过基类指针正确释放派生类对象。
C. 派生类可以重写基类中的虚函数。
D. 构造函数可以声明为 virtual，以便在构造对象时实现动态绑定。
【解析】构造函数在对象构造时调用，此时对象的动态类型尚未确立，无法进行动态绑定，因此 C++ 明确规定构造函数不能声明为虚函数。
【答案】D
下列代码中， d1->work();和d2->work();输出不同结果的主要原因是（ ）。
classDevice {
public:
virtualvoidwork(){
cout << "Device is working" << endl;
}
virtual ~Device() {}
};
classPrinter :public Device {
public:
voidwork()override{
cout << "Printer is printing" << endl;
}
};
classScanner :public Device {
public:
voidwork()override{
cout << "Scanner is scanning" << endl;
}
};
intmain(){
Device* d1 = new Printer();
Device* d2 = new Scanner();
d1->work();
d2->work();
delete d1;
delete d2;
return0;
}
A. Printer 和 Scanner 使用了相同的构造函数。
B. work() 是虚函数，且 d1 和 d2 实际指向不同派生类对象，发生动态绑定。
C. d1 和 d2 是不同的指针变量。
D. 程序中使用了 delete 释放对象。
【解析】work() 被声明为 virtual，两个派生类分别重写。通过基类指针调用虚函数时，运行期根据指针实际指向的对象类型选择对应版本，这就是动态绑定（多态），因此 d1 调用 Printer::work、d2 调用 Scanner::work。指针是否为不同变量、构造函数、delete 都与输出内容无关。
【答案】B
下面代码在 main() 中有一行会导致编译错误，请找出来。
classStudent {
public:
Student(string n, int s) : name(n), score(s) {}
stringgetName(){
return name;
}
voidsetScore(int s){
score = s;
}
private:
string name;
int score;
};
intmain(){
Student stu("Tom", 85);
cout << stu.getName(); // ①
stu.setScore(90); // ②
stu.score = 100; // ③
cout << stu.getName(); // ④
return0;
}
A. 第 ① 行
B. 第 ② 行
C. 第 ③ 行
D. 第 ④ 行
【解析】score 是类的 private 成员，只能在类的成员函数内部访问。①④ 调用的是 public 成员函数，②调用的是 public 的 setScore，都合法；③在类外直接访问私有成员 stu.score，违反访问权限，编译报错。
【答案】C
某文本编辑器把用户输入的字符依次压入栈 S。用户依次输入 X, Y, Z, W 后，连续执行两次撤销操作。每次撤销都会弹出栈顶一个字符。此时栈从栈底到栈顶的内容是（ ）。
A. X Y
B. X Y Z
C. Y Z
D. X Z
【解析】依次压栈后，栈底到栈顶为 X、Y、Z、W（栈顶是 W）。第一次撤销弹出 W，第二次撤销弹出 Z，剩余从栈底到栈顶为 X Y。
【答案】A
假设循环队列数组长度为 N = 7，队空判断条件为 front == rear。入队和出队操作如下：
constint N = 7;
int q[N];
int front = 3, rear = 3;
voidenqueue(int x){
q[rear] = x;
rear = (rear + 1) % N;
}
voiddequeue(){
front = (front + 1) % N;
}
依次执行：
enqueue(10);
enqueue(20);
enqueue(30);
dequeue();
enqueue(40);
dequeue();
enqueue(50);
最终 (front, rear) 的值是（ ）。
A. (5, 1)
B. (4, 0)
C. (5, 0)
D. (3, 1)
【解析】逐步跟踪指针（front 只受 dequeue 影响，rear 只受 enqueue 影响）：
enqueue(10)：q[3]=10，rear=4；
enqueue(20)：q[4]=20，rear=5；
enqueue(30)：q[5]=30，rear=6；
dequeue()：front=4；
enqueue(40)：q[6]=40，rear=(6+1)%7=0（发生回绕）；
dequeue()：front=5；
enqueue(50)：q[0]=50，rear=(0+1)%7=1。
最终 (front, rear) = (5, 1)。
【答案】A
以下函数 check() 用于判断一棵二叉树是否为（ ）。
boolcheck(TreeNode* root){
if (!root) returntrue;
queue<TreeNode*> q;
q.push(root);
bool hasNull = false;
while (!q.empty()) {
TreeNode* cur = q.front();
q.pop();
if (cur == nullptr) {
hasNull = true;
} else {
if (hasNull) returnfalse;
q.push(cur->left);
q.push(cur->right);
}
}
returntrue;
}
A. 满二叉树
B. 完全二叉树
C. 二叉搜索树
D. 平衡二叉树
【解析】层序遍历（BFS）中，空节点（nullptr）也一并入队，并用 hasNull 记录"已经遇到过空节点"。一旦在遇到空节点之后又出现非空节点，说明节点没有按层序连续排列，返回 false——这正是完全二叉树的定义（前 k 层满、最后一层节点靠左连续）。
【答案】B
以下代码实现了二叉树的哪种遍历方式？
voidtraverse(TreeNode* root){
if (root == nullptr) return;
cout << root->val << " ";
traverse(root->left);
traverse(root->right);
}
A. 前序遍历
B. 中序遍历
C. 后序遍历
D. 层序遍历
【解析】访问顺序是先输出根节点，再递归左子树，最后递归右子树，即"根 → 左 → 右"，属于前序遍历（先序遍历）。中序是左根右，后序是左右根，层序需要队列。
【答案】A
已知一棵二叉树的先序遍历序列为：A B D E H C F G，中序遍历序列为：D B H E A F C G，则该二叉树的后序遍历序列是（ ）。
A. D H E B F G C A
B. D E H B F G C A
C. H D E B F C G A
D. D H E B G F C A
【解析】先序首元素 A 为根；中序中 A 左侧 D B H E 为左子树、右侧 F C G 为右子树。
左子树：先序 B D E H、中序 D B H E → 根 B，左孩子 D，右子树先序 E H、中序 H E → 根 E，H 为 E 的左孩子。
右子树：先序 C F G、中序 F C G → 根 C，左孩子 F，右孩子 G。
后序 = 左子树 + 右子树 + 根 = D H E B + F G C + A = D H E B F G C A。
【答案】A
有 6 个字符，它们出现的次数分别为：{3, 4, 7, 8, 12, 15}，现在用哈夫曼编码为这些字符编码，最小加权路径长度 WPL 的值为（ ）。
A. 113
B. 119
C. 126
D. 31
【解析】每次取当前最小的两个权值合并：
3 + 4 = 7 → 集合 {7, 7, 8, 12, 15}
7 + 7 = 14 → {8, 12, 14, 15}
8 + 12 = 20 → {14, 15, 20}
14 + 15 = 29 → {20, 29}
20 + 29 = 49 → 合并完成
WPL 等于所有中间结点权值之和：7 + 14 + 20 + 29 + 49 = 119。
【答案】B
对 n 个不同符号进行哈夫曼编码。若生成的哈夫曼树共有 63 个结点，则 n 的值是（ ）。
A. 31
B. 32
C. 63
D. 64
【解析】哈夫曼树每个内部结点都有两个孩子。设叶子数为 n，则内部结点数为 n − 1，总结点数 = n + (n − 1) = 2n − 1。由 2n − 1 = 63 得 n = 32。
【答案】B
在格雷码中，相邻两个编码只能有一位不同。若当前编码为 110，则它的下一个编码不可能是（ ）。
A. 010
B. 111
C. 100
D. 001
【解析】逐个比较与 110 的差异位数：010 只差第 1 位；111 只差第 3 位；100 只差第 2 位；而 001 与 110 的第 1、2、3 位全都不同（差 3 位），不符合"只差一位"的要求。
【答案】D
给定一棵二叉树，采用广度优先搜索 BFS 返回其右视图，其中右视图中的每个节点都是该层最右侧的节点。横线处应填写（ ）。
vector<int> rightSideView(TreeNode* root){
vector<int> result;
if (!root) return result;
queue<TreeNode*> q;
q.push(root);
while (!q.empty()) {
int sz = q.size();
for (int i = 0; i < sz; ++i) {
TreeNode* node = q.front();
q.pop();
__________________________
if(node->left) q.push(node->left);
if (node->right) q.push(node->right);
}
}
return result;
}
A. if (i == 0) result.push_back(node->val);
B. if (i == sz - 1) result.push_back(node->val);
C. result.push_back(q.front()->val);
D. if (node->right) result.push_back(node->right->val);
【解析】sz 记录的是当前层的节点个数，内层循环按顺序处理本层的每一个节点。右视图取每层最右边的节点，即本层第 sz 个（下标 sz − 1）节点，故在 i == sz - 1 时把 node->val 存入结果。A 取的是每层最左侧（左视图）；C 取的是下一个待处理节点，且可能取到别的层；D 是下一层节点，位置也不对。
【答案】B
下面代码实现二叉搜索树的插入操作。假设树中不存在重复值，横线处应填写（ ）。
TreeNode* insertNode(TreeNode* root, int x){
if (root == nullptr) {
returnnew TreeNode(x);
}
if (x < root->val) {
__________________________
} else {
root->right = insertNode(root->right, x);
}
return root;
}
A. root->left = insertNode(root->left, x);
B. root = insertNode(root->left, x);
C. root->right = insertNode(root->left, x);
D. insertNode(root->left, x);
【解析】BST 中比根小的值要插入左子树，递归结果必须接回 root->left，否则新结点与树失去联系，插入失败。B 把返回值赋给 root 会破坏根指针；C 参数与赋值位置矛盾（递归左子树却接到右边）；D 丢弃了返回值，子树根结点没被更新。
【答案】A
给定一个整数数组 a，每个元素表示一个位置上的数值。要求从数组中选择若干个元素，使得任意两个被选择的元素在原数组中都不相邻，并且所选元素的总和最大。函数 choose(vector & a) 返回能够得到的最大总和，则横线处应填写（ ）。
intchoose(vector<int>& a){
if (a.empty()) return0;
int n = a.size();
if (n == 1) return a[0];
vector<int> dp(n, 0);
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. max(dp[i - 1], dp[i - 2] + a[i])
C. max(dp[i - 2], a[i])
D. dp[i - 1] + dp[i - 2]
【解析】这就是"打家劫舍"模型。对第 i 个元素只有两种决策：不选它，答案为 dp[i−1]；选它，则第 i−1 个不能选，答案为 dp[i−2] + a[i]。取较大者，即 max(dp[i - 1], dp[i - 2] + a[i])。
【答案】B
下面代码实现 0/1 背包的一维动态规划。第 i 个物品重量为 wt[i]，价值为 val[i]，背包容量为 W。横线处应填写（ ）。
intknapsack(int W, vector<int>& wt, vector<int>& val){
int n = wt.size();
vector<int> dp(W + 1, 0);
for (int i = 0; i < n; ++i) {
for (int w = W; w >= wt[i]; --w) {
__________________________
}
}
return dp[W];
}
A. dp[w] = max(dp[w], dp[w - wt[i]] + val[i]);
B. dp[w] = max(dp[w - 1], dp[w - wt[i]] + val[i]);
C. dp[w] = dp[w] + val[i];
D. dp[w - wt[i]] = max(dp[w], val[i]);
【解析】0/1 背包的状态转移：dp[w] 表示容量 w 内能取得的最大价值，对第 i 件物品有"不放"与"放"两种选择，即 dp[w] = max(dp[w], dp[w - wt[i]] + val[i])。内层容量倒序枚举正是为了保证 dp[w - wt[i]] 仍是上一轮的状态，每件物品最多选一次。B 改错了转移基准，C 变成无条件累加（不判断容量与价值取舍），D 下标写反、赋值目标也错了。
【答案】A
二、判断题（共 10 题，每题 2 分，共计 20 分）
C++ 中构造函数可以声明为虚函数，从而实现运行时多态。
A. 正确
B. 错误
【解析】构造函数不能是虚函数。虚函数机制依赖对象已构造完成的结构（虚函数表指针 vptr），而构造函数执行时对象尚未构造完毕，无法进行动态绑定。只有析构函数可以声明为虚函数。
【答案】错误
通过指向 Base 的指针删除 Derived 对象时，一定会先调用 Derived 的析构函数，再调用 Base 的析构函数。
A. 正确
B. 错误
【解析】只有当 Base 的析构函数是虚函数时，delete p 才会先调用 Derived 的析构函数再调用 Base 的析构函数；若基类析构函数非虚，则只会调用 Base 的析构函数，派生类部分的资源无法释放（属于未定义行为）。题目说"一定"，过于绝对，错误。
【答案】错误
在 C++ STL 中，stack 的 pop() 函数会返回栈顶元素并将其删除。
A. 正确
B. 错误
【解析】STL 中 stack::pop() 的返回类型是 void，它只负责删除栈顶元素，不返回该元素。要取出栈顶元素需要先调用 top()，再调用 pop()。
【答案】错误
程序运行后会输出 2。
#include<iostream>
usingnamespacestd;
intmain(){
queue<int> q;
q.push(1);
q.push(2);
q.push(3);
q.pop();
cout << q.front() << endl;
return0;
}
A. 正确
B. 错误
【解析】queue 先进先出：依次入队 1、2、3；pop() 删除队首元素 1，此时队首变为 2；front() 返回 2。程序输出 2，说法正确。
【答案】正确
下列函数试图将整数 x 插入到一棵二叉搜索树中。假设二叉搜索树满足如下性质：对于任意结点，左子树中所有结点的值均小于该结点的值，右子树中所有结点的值均大于或等于该结点的值。判断该函数是否能够在插入后保持二叉搜索树性质。
structTreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
TreeNode* insertNode(TreeNode* root, int x){
if (root == nullptr) {
returnnew TreeNode(x);
}
if (x < root->val) {
root->right = insertNode(root->right, x);
} else {
root->left = insertNode(root->left, x);
}
return root;
}
A. 正确
B. 错误
【解析】判断分支完全写反了：x < root->val（较小值）应该插入左子树，x >= root->val 应该插入右子树。现在把小于根的值插到了右子树、大于等于根的值插到了左子树，直接破坏 BST 的有序性质（对该树中序遍历将得不到非递减序列）。
【答案】错误
哈夫曼编码一定唯一，只要字符频率相同，得到的编码也一定完全相同。
A. 正确
B. 错误
【解析】哈夫曼编码不唯一。当出现权值相同的结点时，合并顺序（谁左谁右、先合并哪一对）可以不同；左右子树分支标 0/1 也可交换，都会得到 WPL 相同但码字不同的方案。故"编码一定完全相同"错误。
【答案】错误
若用数组按层序存储完全二叉树，且根节点下标为 0，则下标为 i 的节点左孩子下标为 2 * i + 1，右孩子下标为2 * i + 2。
A. 正确
B. 错误
【解析】根下标从 0 开始时的标准关系：i 的左孩子为 2i + 1，右孩子为 2i + 2，父结点为 ⌊(i − 1) / 2⌋。（若根从下标 1 开始，则是 2i 与 2i + 1。）
【答案】正确
以下代码可以正确地按层换行输出二叉树的节点值。
voidprintByLevel(TreeNode* root){
if (!root) return;
queue<TreeNode*> q;
q.push(root);
while (!q.empty()) {
for (int i = 0; i < q.size(); ++i) {
TreeNode* cur = q.front();
q.pop();
cout << cur->val << " ";
if (cur->left) q.push(cur->left);
if (cur->right) q.push(cur->right);
}
cout << endl;
}
}
A. 正确
B. 错误
【解析】内层循环的终止条件 i < q.size() 每次迭代都会**重新计算 q.size()**，而循环体内又不断把下一层的孩子入队，队列长度持续变大，导致本层循环会"顺带"处理下一层甚至更多节点，无法按层正确换行。正确写法应先把本层节点数缓存下来，如 int sz = q.size(); 再用 i < sz。
【答案】错误
使用栈非递归实现二叉树前序遍历时，若希望先访问左子树，通常应先将右孩子入栈，再将左孩子入栈。
A. 正确
B. 错误
【解析】栈是后进先出，要让左孩子先被弹出访问，就必须先压右孩子、再压左孩子，这样左孩子位于栈顶。该说法正确。
【答案】正确
动态规划问题通常要求具有最优子结构，并且常常存在重叠子问题。
A. 正确
B. 错误
【解析】动态规划适用的两个基本条件是：最优子结构（问题的最优解包含子问题的最优解，保证状态转移的正确性）和重叠子问题（同一子问题被多次求解，因此需要记忆化/表格化避免重复计算）。说法正确。
【答案】正确
三、编程题
1. 条形蛋糕
题目描述
输入格式
输出格式
一行一个正整数，表示最大总销售价格。
4
1 5 8 9
10
10
1 5 8 9 10 17 17 20 24 30
30
说明/提示
题目分析
状态定义
设 表示：长度为 的蛋糕切割后能获得的最大总售价。
初始状态
长度为 0 的蛋糕收益为 0。
状态转移
对于长度为 的蛋糕，可以枚举第一段的长度 ()：
第一段直接卖，获得 剩余长度 继续最优切割，获得
因此：
参考程序
#include<bits/stdc++.h>
usingnamespacestd;
constint N = 1010;
int n;
int p[N], f[N];
intmain(){
cin >> n;
for(int i = 1; i <= n; i++) cin >> p[i];
for(int i = 1; i <= n; i++){
for(int j = 1; j <= i; j++)
f[i] = max(f[i], f[i - j] + p[j]);
}
cout << f[n];
return0;
}
2. 满二叉树
题目描述
输入格式
第一行，一个正整数 ，表示有根二叉树结点数量。
接下来 行，每行两个非负整数 ，表示结点 的左儿子编号和右儿子编号，整数之间以空格分隔。
输出格式
输出一行，一个整数，表示所有子树中满二叉树的数量。
4
2 3
4 0
0 0
0 0
2
3
2 3
0 0
0 0
3
说明/提示
数据范围
对于 的测试点，保证 。
对于所有测试点，保证 。
题目分析
左子树必须是满二叉树。 右子树必须是满二叉树。 左子树的深度 = 右子树的深度。
参考程序
#include<bits/stdc++.h>
usingnamespacestd;
constint N = 100010;
int L[N], R[N];
int n, res;
intdfs(int u){
if (u == 0) return0;
int hl = dfs(L[u]);
int hr = dfs(R[u]);
if (hl != -1 && hl == hr) {
res++;
return hl + 1;
}
return-1;
}
intmain(){
cin >> n;
for (int i = 1; i <= n; i ++)
cin >> L[i] >> R[i];
dfs(1);
cout << res;
return0;
}
