GESP C++ 编程六级 · 2026 年 6 月卷

下列关于 C++ 中继承和多态的描述中，错误的是（ ）。

• A.通过基类指针调用虚函数时，会根据对象实际类型决定调用版本。
• B.基类析构函数常声明为虚函数，以便通过基类指针正确释放派生类对象。
• C.派生类可以重写基类中的虚函数。
• D.构造函数可以声明为virtual ，以便在构造对象时实现动态绑定。

下列代码中， d1->work();和d2->work();输出不同结果的主要原因是（ ）。 1 class Device { 2 public: 3 virtual void work() { 4 cout << "Device is working" << endl; 5 } 6 virtual ~Device() {} 7 }; 9 class Printer : public Device { 10 public: 11 void work() override { 12 cout << "Printer is printing" << endl; 13 } 14 }; 16 class Scanner : public Device { 17 public: 18 void work() override { 19 cout << "Scanner is scanning" << endl; 20 } 21 }; 23 int main() { 24 Device* d1 = new Printer(); 25 Device* d2 = new Scanner(); 27 d1->work(); 28 d2->work(); 30 delete d1; 31 delete d2; 32 return 0; 33 }

• A.Printer 和 Scanner 使用了相同的构造函数。
• B.work() 是虚函数，且 d1 和 d2 实际指向不同派生类对象，发生动态绑定。
• C.d1 和 d2 是不同的指针变量。
• D.程序中使用了 delete 释放对象。

下面代码在main()中有一行会导致编译错误，请找出来。 1 class Student { 2 public: 3 Student(string n, int s) : name(n), score(s) {} 5 string getName() { 6 return name; 7 } 9 void setScore(int s) { 10 score = s; 11 } 13 private: 14 string name; 15 int score; 16 }; 18 int main() { 19 Student stu("Tom", 85); 20 cout << stu.getName(); // ① 21 stu.setScore(90); // ② 22 stu.score = 100; // ③ 23 cout << stu.getName(); // ④ 24 return 0; 25 }

• A.第①行
• B.第②行
• C.第③行
• D.第④行

某文本编辑器把用户输入的字符依次压入栈S 。用户依次输入X, Y, Z, W后，连续执行两次撤销操作。每次撤销都会弹出栈顶一个字符。此时栈从栈底到栈顶的内容是（ ）。

• A.X Y
• B.X Y Z
• C.Y Z
• D.X Z

假设循环队列数组长度为N = 7 ，队空判断条件为front == rear 。入队和出队操作如下：依次执行：最终(front, rear)的值是（ ）。 1 const int N = 7; 2 int q[N]; 3 int front = 3, rear = 3; 5 void enqueue(int x) { 6 q[rear] = x; 7 rear = (rear + 1) % N; 8 } 10 void dequeue() { 11 front = (front + 1) % N; 12 } 1 enqueue(10); 2 enqueue(20); 3 enqueue(30); 4 dequeue(); 5 enqueue(40); 6 dequeue(); 7 enqueue(50);

• A.(5, 1)
• B.(4, 0)
• C.(5, 0)
• D.(3, 1)

以下函数check()用于判断一棵二叉树是否为（ ）。 1 bool check(TreeNode* root) { 2 if (!root) return true; 4 queue<TreeNode*> q; 5 q.push(root); 7 bool hasNull = false; 9 while (!q.empty()) { 10 TreeNode* cur = q.front(); 11 q.pop(); 13 if (cur == nullptr) { 14 hasNull = true; 15 } else { 16 if (hasNull) return false; 17 q.push(cur->left); 18 q.push(cur->right); 19 } 20 } 22 return true; 23 }

• A.满二叉树
• B.完全二叉树
• C.二叉搜索树
• D.平衡二叉树

以下代码实现了二叉树的哪种遍历方式？ 1 void traverse(TreeNode* root) { 2 if (root == nullptr) return; 4 cout << root->val << " "; 5 traverse(root->left); 6 traverse(root->right); 7 }

• A.前序遍历
• B.中序遍历
• C.后序遍历
• D.层序遍历

已知一棵二叉树的先序遍历序列为： 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

有6个字符，它们出现的次数分别为：{3, 4, 7, 8, 12, 15}，现在用哈夫曼编码为这些字符编码，最小加权路径长度WPL的值为（ ）。

• A.113
• B.119
• C.126
• D.31

对n个不同符号进行哈夫曼编码。若生成的哈夫曼树共有63个结点，则n的值是（ ）。

• A.31
• B.32
• C.63
• D.64

在格雷码中，相邻两个编码只能有一位不同。若当前编码为110 ，则它的下一个编码不可能是（ ）。

• A.010
• B.111
• C.100
• D.001

给定一棵二叉树，采用广度优先搜索 BFS 返回其右视图，其中右视图中的每个节点都是该层最右侧的节点。横线处应填写（ ）。 1 vector<int> rightSideView(TreeNode* root) { 2 vector<int> result; 3 if (!root) return result; 5 queue<TreeNode*> q; 6 q.push(root); 8 while (!q.empty()) { 9 int sz = q.size(); 11 for (int i = 0; i < sz; ++i) { 12 TreeNode* node = q.front(); 13 q.pop(); 15 __________________________ 17 if (node->left) q.push(node->left); 18 if (node->right) q.push(node->right); 19 } 20 } 22 return result; 23 }

• 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);

下面代码实现二叉搜索树的插入操作。假设树中不存在重复值，横线处应填写（ ）。 1 TreeNode* insertNode(TreeNode* root, int x) { 2 if (root == nullptr) { 3 return new TreeNode(x); 4 } 6 if (x < root->val) { 7 __________________________ 8 } else { 9 root->right = insertNode(root->right, x); 10 } 12 return root; 13 }

• 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);

给定一个整数数组a ，每个元素表示一个位置上的数值。要求从数组中选择若干个元素，使得任意两个被选择的元素在原数组中都不相邻，并且所选元素的总和最大。函数choose(vector<int>& a)返回能够得到的最大总和，则横线处应填写（ ）。 1 int choose(vector<int>& a) { 2 if (a.empty()) return 0; 4 int n = a.size(); 5 if (n == 1) return a[0]; 7 vector<int> dp(n, 0); 8 dp[0] = a[0]; 9 dp[1] = max(a[0], a[1]); 11 for (int i = 2; i < n; ++i) { 12 dp[i] = __________________________; 13 } 15 return dp[n - 1]; 16 }

• 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]

下面代码实现 0/1 背包的一维动态规划。第i个物品重量为wt[i] ，价值为val[i] ，背包容量为W 。横线处应填写（ ）。 1 int knapsack(int W, vector<int>& wt, vector<int>& val) { 2 int n = wt.size(); 3 vector<int> dp(W + 1, 0); 5 for (int i = 0; i < n; ++i) { 6 for (int w = W; w >= wt[i]; --w) { 7 __________________________ 8 } 9 } 11 return dp[W]; 12 }

• 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]);

C++ 中构造函数可以声明为虚函数，从而实现运行时多态。

通过指向Base的指针删除Derived对象时，一定会先调用Derived的析构函数，再调用Base的析构函数。 1 #include <iostream> 2 using namespace std; 4 class Base { 5 public: 6 ~Base() { 7 cout << "Base destructor" << endl; 8 } 9 }; 11 class Derived : public Base { 12 public: 13 ~Derived() { 14 cout << "Derived destructor" << endl; 15 } 16 }; 18 int main() { 19 Base* p = new Derived(); 20 delete p; 21 return 0; 22 }

在 C++ STL 中， stack的pop()函数会返回栈顶元素并将其删除。

程序运行后会输出2 。 int main() { queue<int> q; q.push(1); q.push(2); q.push(3); q.pop(); cout << q.front() << endl; return 0; }

下列函数试图将整数x插入到一棵二叉搜索树中。假设二叉搜索树满足如下性质：对于任意结点，左子树中所有结点的值均小于该结点的值，右子树中所有结点的值均大于或等于该结点的值。判断该函数是否能够在插入后保持二叉搜索树性质。 1 struct TreeNode { 2 int val; 3 TreeNode* left; 4 TreeNode* right; 5 TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} 6 }; 8 TreeNode* insertNode(TreeNode* root, int x) { 9 if (root == nullptr) { 10 return new TreeNode(x); 11 } 13 if (x < root->val) { 14 root->right = insertNode(root->right, x); 15 } else { 16 root->left = insertNode(root->left, x); 17 } 19 return root; 20 }

哈夫曼编码一定唯一，只要字符频率相同，得到的编码也一定完全相同。

若用数组按层序存储完全二叉树，且根节点下标为0 ，则下标为i的节点左孩子下标为 2 * i + 1，右孩子下标为 2 * i + 2 。

以下代码可以正确地按层换行输出二叉树的节点值。 1 void printByLevel(TreeNode* root) { 2 if (!root) return; 4 queue<TreeNode*> q; 5 q.push(root); 7 while (!q.empty()) { 8 for (int i = 0; i < q.size(); ++i) { 9 TreeNode* cur = q.front(); 10 q.pop(); 11 cout << cur->val << " "; 13 if (cur->left) q.push(cur->left); 14 if (cur->right) q.push(cur->right); 15 } 16 cout << endl; 17 } 18 }

使用栈非递归实现二叉树前序遍历时，若希望先访问左子树，通常应先将右孩子入栈，再将左孩子入栈。

动态规划问题通常要求具有最优子结构，并且常常存在重叠子问题。

试题名称：条形蛋糕 时间限制：1.0 s　内存限制：512.0 MB 题目描述：寒假到了，小杨同学打算找一份兼职，顺便体验一下打工人的生活。 小杨同学给一家蛋糕店发送了一份自己的简历，希望可以在寒假来这里帮忙。店长最近正好遇到了一个难题：店里每天会做一条长条蛋糕，但是不同长度的蛋糕块卖出的价格不同，应该怎么分才能卖得最多呢？ 有趣的是店长曾经学习过计算机专业。他最近对动态规划算法很感兴趣，于是打算用这个问题考一考小杨同学，问题如下： · 给定一条长度为 n 的长条蛋糕和一个价格表，该价格表表示长度为 i（i = 1, 2, …, n）的蛋糕块的价格为 p_i。求蛋糕的分割方案，使得总销售价格最大，注意蛋糕块的长度必须为整数。 输入格式：第一行一个正整数 n（1 ≤ n ≤ 10^3），表示长条蛋糕的总长度。 第二行 n 个正整数 p_1, p_2, …, p_n（1 ≤ p_i ≤ 10^5），表示不同长度蛋糕块的价格。 输出格式：一行一个正整数，表示最大总销售价格。 输入样例1：4 1 5 8 9 输出样例1：10 输入样例2：10 1 5 8 9 10 17 17 20 24 30 输出样例2：30 样例解释1：第一个样例中，长度为 1 的蛋糕价值为 1，长度为 2 的蛋糕价值为 5，长度为 3 的蛋糕价值为 8，长度为 4 的蛋糕价值为 9； 总长度为 4 的长条蛋糕，有 {4}, {1, 3}, {2, 2}, {1, 1, 2}, {1, 1, 1, 1} 五种本质不同的分法。 其对应的总销售价格分别为 9, 9, 10, 7, 4，故最大总销售价格为 10。 第二个样例中，长度为 10 的长条蛋糕，销售价格最大的分法为 {10}，最大总销售价格为 30。 数据范围：对于 40% 的测试点，保证 1 ≤ n ≤ 10^3。

作答说明：按题目要求完成程序或作品；需要在线运行与自动判分时，可在站内选择「在线考试」。

试题名称：满二叉树 时间限制：1.0 s　内存限制：512.0 MB 题目描述：给定一棵包含 n 个结点的有根二叉树，结点依次以 1, 2, …, n 编号，根结点编号为 1。 对于结点 i，其左儿子的编号记为 l_i，右儿子编号记为 r_i。特别地，如果左儿子不存在则 l_i = 0，如果右儿子不存在则 r_i = 0。 树中每个结点都对应一棵以其为根的子树。请你求出给定有根树的所有 n 棵子树中，有多少棵子树是满二叉树。 满二叉树是指所有叶子深度均相同，且除叶子外均有两个儿子的二叉树，例如以下三棵二叉树均是满二叉树：一棵只有 1 个节点的二叉树；一棵有 3 个节点的二叉树，根节点带有两个儿子；一棵有 7 个节点的二叉树，每个非叶子节点都带有两个儿子。 例如，对于如下 3 个节点的满二叉树： () / \ () () 在上面这棵有 3 个节点的二叉树中，有 3 个子树是满二叉树（包括整个树本身，及所有的单个叶子节点）； 又例如，对于如下 5 个节点的二叉树： (1) / \ (2) (3) / \ (4) (5) 在上面这棵有 5 个节点的二叉树中，有 4 个子树是满二叉树（包括节点 3 的子树，以及所有单个叶子节点）。 输入格式：第一行，一个正整数 n，表示有根二叉树结点数量。 接下来 n 行，每行两个非负整数 l_i, r_i，表示结点 i 的左儿子编号和右儿子编号，整数之间以空格分隔。 输出格式：输出一行，一个整数，表示所有子树中满二叉树的数量。 输入样例1：4 2 3 4 0 0 0 0 0 输出样例1：2 输入样例2：3 2 3 0 0 0 0 输出样例2：3 数据范围：对于 40% 的测试点，保证 1 ≤ n ≤ 500。 对于所有测试点，保证 1 ≤ n ≤ 10^5。

作答说明：按题目要求完成程序或作品；需要在线运行与自动判分时，可在站内选择「在线考试」。