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

下列代码执行后的输出结果是（ ）。 1 class Animal { 2 public: 3 virtual void speak() { 4 cout << "Animal "; 5 } 6 virtual ~Animal() = default; 7 }; 9 class Cat : public Animal { 10 public: 11 void speak() override { 12 cout << "Cat "; 13 } 14 }; 16 int main() { 17 Animal *p = new Cat(); 18 p->speak(); 19 delete p; 20 return 0; 21 }

• A.Animal
• B.Cat
• C.Animal Cat
• D.编译错误

下列代码中，横线处应填写（ ），才能正确调用基类的带参数构造函数。 1 class Machine { 2 protected: 3 string id; 5 public: 6 Machine(string s) : id(s) {} 7 }; 9 class Robot : public Machine { 10 int level; 12 public: 13 Robot(string s, int n) : __________, level(n) {} 14 };

• A.Machine(s)
• B.Machine::id(s)
• C.super(s)
• D.id(s)

下列代码执行后的输出顺序是（ ）。 1 class Base { 2 public: 3 Base() { 4 cout << "B "; 5 } 6 virtual ~Base() { 7 cout << "~B "; 8 } 9 }; 11 class Derived : public Base { 12 public: 13 Derived() { 14 cout << "D "; 15 } 16 ~Derived() { 17 cout << "~D "; 18 } 19 }; 21 int main() { 22 Base *p = new Derived(); 23 delete p; 24 return 0; 25 }

• A.B D ~B ~D
• B.D B ~D ~B
• C.B D ~D ~B
• D.B D ~B

下列代码执行后的输出结果是（ ）。 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

下面循环队列采用“空出一个位置”的方式区分队空和队满。横线处应填写（ ）。 1 const int MAXN = 8; 2 int data[MAXN]; 3 int front = 0, rear = 0; 5 bool full() { 6 return __________________________; 7 }

• A.rear == front
• B.(front + 1) % MAXN == rear
• C.(rear + 1) % MAXN == front
• D.rear == MAXN - 1

下列函数实现了二叉树的哪种遍历方式（ ）。 void visit(TreeNode *root) { if (root == nullptr) return; visit(root->left); cout << root->val << " "; visit(root->right); }

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

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

下面函数用于计算二叉树的高度，横线处应填写（ ）。 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

以下代码实现二叉树左子树优先的深度优先搜索算法，则横线上应填写（ ）。 1 void dfs(TreeNode *root) { 2 if (root == nullptr) 3 return; 5 stack<TreeNode *> s; 6 s.push(root); 7 while (!s.empty()) { 8 TreeNode *node = s.top(); 9 s.pop(); 10 cout << node->value << " "; 12 ———————————————————————— // 在此处填入代码 13 } 14 }

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

下面函数在二叉搜索树中查找值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

有 5 个字符，其出现频率分别为 2、4、5、9、12。按哈夫曼算法构造编码树，其最小带权路径长度 WPL 为（ ）。

• A.68
• B.69
• C.71
• D.73

下面代码用反射法生成n位格雷编码，横线处应填写（ ）。 1 vector<string> gray(int n) { 2 vector<string> ans = {"0", "1"}; 3 for (int bit = 2; bit <= n; ++bit) { 4 int oldSize = ans.size(); 5 for (int i = oldSize - 1; i >= 0; --i) 6 ans.push_back(__________________________); 7 for (int i = 0; i < oldSize; ++i) 8 ans[i] = "0" + ans[i]; 9 } 10 return ans; 11 }

• A.ans[i] + "1"
• B."0" + ans[i]
• C."1" + ans[i]
• D.ans[oldSize - i - 1]

下面代码计算走到第n级台阶的方法数，每次可以走 1 级或 2 级。横线处应填写（ ）。 1 int ways(int n) { 2 if (n <= 2) 3 return n; 4 vector<int> dp(n + 1); 5 dp[1] = 1; 6 dp[2] = 2; 7 for (int i = 3; i <= n; ++i) 8 dp[i] = __________________________; 9 return dp[n]; 10 }

• A.dp[i - 1] + 1
• B.dp[i - 1] + dp[i - 2]
• C.dp[i - 2] + 2
• D.2 * dp[i - 1]

下面代码求从包含非负元素的数组中选择若干个互不相邻元素所能得到的最大和。横线处应填写（ ）。 1 int maxSum(vector<int> &a) { 2 int n = a.size(); 3 if (n == 0) 4 return 0; 5 if (n == 1) 6 return a[0]; 7 vector<int> dp(n); 8 dp[0] = a[0]; 9 dp[1] = max(a[0], a[1]); 10 for (int i = 2; i < n; ++i) 11 dp[i] = __________________________; 12 return dp[n - 1]; 13 }

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

下面是一维数组实现的 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发生越界

下列代码可以正常编译，因为编译器会自动为Student类生成一个无参数构造函数。 1 class Student { 2 public: 3 Student(int x) { 4 age = x; 5 } 7 private: 8 int age; 9 }; 11 int main() { 12 Student s; 13 }

下列代码合法，因为派生类可以直接访问基类的私有成员value 。 1 class Base { 2 private: 3 int value = 10; 4 }; 6 class Child : public Base { 7 public: 8 int get() { 9 return value; 10 } 11 };

下列代码执行后，输出结果为30 。 queue<int> q; q.push(10); q.push(20); q.push(30); q.pop(); cout << q.front();

一棵完全二叉树按照从上到下、从左到右的顺序，将节点依次存储在数组tree[1] 、 tree[2] 、……中。若节点tree[i]存在左孩子，则其左孩子存储在tree[2 * i]中。

对任意一棵二叉搜索树执行中序遍历，得到的关键字序列一定是非递减的。 void inorder(TreeNode *root) { if (!root) return; inorder(root->left); cout << root->val << " "; inorder(root->right); }

若使用下列代码从节点start开始访问一棵树，则第一次到达某个节点时所经过的边数，一定是从start到该节点的最少边数。 1 vector<int> tree[100]; 2 bool visited[100]; 3 int dist[100]; 5 void search(int start) { 6 queue<int> q; 7 q.push(start); 8 visited[start] = true; 9 dist[start] = 0; 11 while (!q.empty()) { 12 int u = q.front(); 13 q.pop(); 15 for (int v : tree[u]) { 16 if (!visited[v]) { 17 visited[v] = true; 18 dist[v] = dist[u] + 1; 19 q.push(v); 20 } 21 } 22 } 23 }

哈夫曼编码的生成过程基于贪心算法，出现频率越高的字符，其编码长度一定不会比出现频率更低的字符更长。

在位格雷码中，任意两个编码之间都只相差一个二进制位。

下列一维动态规划代码实现的是完全背包问题，因为在处理第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]); } }

下列递归程序能得到正确的斐波那契数，其时间复杂度和空间复杂度都是O(n)。 int fib(int n) { if (n <= 1) return n; return fib(n - 1) + fib(n - 2); }

试题名称：数组划分 时间限制：1.0 s　内存限制：512.0 MB 题目描述：给定 n 个整数构成的数组 A = [a_1, a_2, …, a_n]。 你需要将数组 A 划分为若干非空连续子段。对于划分得到的某个子段，它的偏差值定义为子段内整数和的平方。划分方案的偏差值定义为所有子段偏差值之和。 你需要最小化划分方案的偏差值。 形式化地，你可以将 A 划分为若干非空连续子段 A_1, A_2, …, A_k，使得 A = A_1 + A_2 + … + A_k，这里的 + 代表数组的连接。对于 1 ≤ i ≤ k，设数组 A_i 包含 m_i 个整数。你需要最小化各子段整数和平方之和。 输入格式：第一行，一个正整数 n，表示数组 A 的长度。 第二行，n 个整数 a_1, a_2, …, a_n，表示数组 A。 输出格式：一行，一个整数，表示划分方案偏差值的最小值。 输入样例1：4 1 2 -3 4 输出样例1：6 输入样例2：6 -1 -1 4 -5 -1 4 输出样例2：0 数据范围：对于 40% 的测试点，保证 0 ≤ a_i ≤ 50。 对于所有测试点，保证 1 ≤ n ≤ 2000，−100 ≤ a_i ≤ 100。

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

试题名称：分树规划 时间限制：1.0 s　内存限制：512.0 MB 题目描述：老师有一棵有 n 个结点的树，结点依次以 1, 2, …, n 编号。 老师想将这棵树作为奖品分给两位同学。具体而言，老师会选择一条边并从树上删去它，从而将这棵树分为两个连通块。两位同学分别可以得到其中一个连通块。 如果有同学拿到的连通块结点数明显小于另一位同学，那么这位同学会不太高兴。为了避免这种情况出现，老师想知道两个连通块结点数之差的绝对值最小是多少。 输入格式：第一行，一个正整数 n，表示结点数量。 接下来 n − 1 行，每行两个正整数 u_i, v_i，表示一条连接结点 u_i 和结点 v_i 的边。 输出格式：输出一行，一个整数，表示答案。 输入样例1：4 1 2 2 3 3 4 输出样例1：0 输入样例2：6 1 2 1 3 1 4 1 5 5 6 输出样例2：2 数据范围：对于 40% 的测试点，保证 2 ≤ n ≤ 500。 对于所有测试点，保证 2 ≤ n ≤ 2 × 10^4。

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