点金信奥--2025年09月GESP认证C++编程六级真题试卷

第 1 题下列关于类的说法，错误的是( )。

第 2 题假设变量 veh 是类 Car 的一个实例，我们可以调用 veh.move() ，是因为面向对象编程有（）性质。

class Vehicle {
private:
	string brand;
	
public:
	Vehicle(string b) : brand(b) {}
	void setBrand(const string& b) {
		brand = b;
	}
	string getBrand() const {
		return brand;
	}
	void move() const {
		cout << brand << " is moving..." << endl;
	}
};

class Car : public Vehicle {
private:
	int seatCount;
public:
	Car(string b, int seats) : Vehicle(b), seatCount(seats) {}
	void showInfo() const {
		cout << "This car is a " << getBrand()
		     << " with " << seatCount << " seats." << endl;
	}
};

第 3 题下面代码中 v1 和 v2 调用了相同接口 move() ，但输出结果不同，这体现了面向对象编程的（）特性。

class Vehicle {
private:
	string brand;
	
public:
	Vehicle(string b) : brand(b) {}
	
	void setBrand(const string& b) {brand = b;}
	string getBrand() const {return brand;}
	
	virtual void move() const {
		cout << brand << " is moving..." << endl;
	}
};

class Car : public Vehicle {
private:
	int seatCount;
	
public:
	Car(string b, int seats) : Vehicle(b), seatCount(seats) {}
	
	void showInfo() const {
		cout << "This car is a " << getBrand()
		     << " with " << seatCount << " seats." << endl;
	}
	
	void move() const override {
		cout << getBrand() << " car is driving on the road!" << endl;
	}
};

class Bike : public Vehicle {
public:
	Bike(string b) : Vehicle(b) {}
	
	void move() const override {
		cout << getBrand() << " bike is cycling on the path!" << endl;
	}
};

int main() {
	Vehicle* v1 = new Car("Toyota", 5);
	Vehicle* v2 = new Bike("Giant");
	
	v1->move();
	v2->move();
	
	delete v1;
	delete v2;
	return 0;
}

第 4 题栈的操作特点是（）。

第 5 题循环队列常用于实现数据缓冲。假设一个循环队列容量为 5 （即最多存放 4 个元素，留一个位置区分空与满），依次进行操作：入队数据1，2，3，出队1个数据，再入队数据4和5，此时队首到队尾的元素顺序是（）。

第 6 题以下函数 createTree() 构造的树是什么类型？

struct TreeNode {
	int val;
	TreeNode* left;
	TreeNode* right;
	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

TreeNode* createTree() {
	TreeNode* root = new TreeNode(1);
	root->left = new TreeNode(2);
	root->right = new TreeNode(3);
	root->left->left = new TreeNode(4);
	root->left->right = new TreeNode(5);
	return root;
}

第 7 题已知二叉树的中序遍历是 [D, B, E, A, F, C]，先序遍历是 [A, B, D, E, C, F]。请问该二叉树的后序遍历结果是（）。

第 8 题完全二叉树可以用数组连续高效存储，如果节点从 1 开始编号，则对有两个孩子节点的节点 i ，（）。

第 9 题设有字符集 {a, b, c, d, e, f} ，其出现频率分别为 {5, 9, 12, 13, 16, 45} 。哈夫曼算法构造最优前缀编码，以下哪一组可能是对应的哈夫曼编码？（非叶子节点左边分支记作 0，右边分支记作 1，左右互换不影响正确性）。

第 10 题下面代码生成格雷编码，则横线上应填写（）。

vector<string> grayCode(int n) {
	if (n == 0) return {"0"};
	if (n == 1) return {"0", "1"};
	
	vector<string> prev = grayCode(n-1);
	vector<string> result;
	for (string s : prev) {
		result.push_back("0" + s);
	}
	for (_______________) { // 在此处填写代码
		result.push_back("1" + prev[i]);
	}
	return result;
}

第 11 题请将下列树的深度优先遍历代码补充完整，横线处应填入（）。

struct TreeNode {
	int val;
	TreeNode* left;
	TreeNode* right;
	TreeNode(int x): val(x), left(nullptr), right(nullptr) {}
};

void dfs(TreeNode* root) {
	if (!root) return;
	______<TreeNode*> temp; // 在此处填写代码
	temp.push(root);
	while (!temp.empty()) {
		TreeNode* node = temp.top();
		temp.pop();
		cout << node->val << " ";
		if (node->right) temp.push(node->right);
		if (node->left) temp.push(node->left);
	}
}

第 12 题令 $n$ 是树的节点数目，下列代码实现了树的广度优先遍历，其时间复杂度是（）。

void bfs(TreeNode* root) {
	if (!root) return;
	queue<TreeNode*> q;
	q.push(root);
	while (!q.empty()) {
		TreeNode* node = q.front();
		q.pop();
		cout << node->val << " ";
		if (node->left) q.push(node->left);
		if (node->right) q.push(node->right);
	}
}

A. $O(n)$

B. $O(\log n)$

C. $O(n^2)$

D. $O(2^n)$

第 13 题在二叉排序树（Binary Search Tree, BST）中查找元素 50 ，从根节点开始：若根值为 60 ，则下一步应去搜索：

第 14 题删除二叉排序树中的节点时，如果节点有两个孩子，则横线处应填入（），其中 findMax 和 findMin 分别为寻找树的最大值和最小值的函数。

struct TreeNode {
	int val;
	TreeNode* left;
	TreeNode* right;
	TreeNode(int x): val(x), left(nullptr), right(nullptr) {}
};

TreeNode* deleteNode(TreeNode* root, int key) {
	if (!root) return nullptr;
	if (key < root->val) {
		root->left = deleteNode(root->left, key);
	} 
	else if (key > root->val) {
		root->right = deleteNode(root->right, key);
	} 
	else {
		if (!root->left) return root->right;
		if (!root->right) return root->left;
		TreeNode* temp = ____________; // 在此处填写代码
		root->val = temp->val;
		root->right = deleteNode(root->right, temp->val);
	}
	return root;
}

第 15 题给定 $n$ 个物品和一个最大承重为 $W$ 的背包，每个物品有一个重量 $wt[i]$ 和价值 $val[i]$ ，每个物品只能选择放或不放。目标是选择若干个物品放入背包，使得总价值最大，且总重量不超过 $W$ ，则横线上应填写（）。

int knapsack(int W, vector<int>& wt, vector<int>& val, int n) {
	vector<int> dp(W+1, 0);
	for (int i = 0; i < n; ++i) {
		for (int w = W; w >= wt[i]; --w) {
			________________________ // 在此处填写代码
		
		}
	}
	return dp[W];
}

二、判断题（每题 2 分，共 20 分）

第 1 题当基类可能被多态使用，其析构函数应该声明为虚函数。

第 2 题哈夫曼编码是最优前缀码，且编码结果唯一。

第 3 题一个含有 $100$ 个节点的完全二叉树，高度为 $8$。

第 4 题在 C++ STL 中，栈（ std::stack ）的 pop 操作返回栈顶元素并移除它。

第 5 题循环队列通过模运算循环使用空间。

第 6 题一棵有 $n$ 个节点的二叉树一定有 $n-1$ 条边。

第 7 题以下代码实现了二叉树的中序遍历。输入以下二叉树，中序遍历结果是 4 2 5 1 3 6 。

//     1
//    / \
//   2   3
//  / \   \
// 4   5   6
struct TreeNode {
	int val;
	TreeNode* left;
	TreeNode* right;
	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

void inorderIterative(TreeNode* root) {
	stack<TreeNode*> st;
	TreeNode* curr = root;
	while (curr || !st.empty()) {
		while (curr) {
			st.push(curr);
			curr = curr->left;
		}
		curr = st.top();
		st.pop();
		cout << curr->val << " ";
		curr = curr->right;
	}
}

第 8 题下面代码实现的二叉排序树的查找操作时间复杂度是 $O(h)$，其中 $h$ 为树高。

TreeNode* searchBST(TreeNode* root, int val) {
	while (root && root->val != val) {
		root = (val < root->val) ? root->left : root->right;
	}
	return root;
}

第 9 题下面代码实现了动态规划版本的斐波那契数列计算，其时间复杂度是 $O(2^n)$ 。

int fib_dp(int n) {
	if (n <= 1) return n;
	vector<int> dp(n+1);
	dp[0] = 0;
	dp[1] = 1;
	for (int i = 2; i <= n; i++) {
		dp[i] = dp[i-1] + dp[i-2];
	}
	return dp[n];
}

第 10 题有一排香蕉，每个香蕉有不同的甜度值。小猴子想吃香蕉，但不能吃相邻的香蕉。以下代码能找到小猴子吃到最甜的香蕉组合。

// bananas：香蕉的甜度
void findSelectedBananas(vector<int>& bananas, vector<int>& dp) {
	vector<int> selected;
	int i = bananas.size() - 1;
	
	while (i >= 0) {
		if (i == 0) {
			selecte|||push_back(0);
			break;
		}
		
		if (dp[i] == dp[i-1]) {
			i--;
		} else {
			selecte|||push_back(i);
			i -= 2;
		}
	}
	
	reverse(selecte|||begin(), selecte|||end());
	cout << "小猴子吃了第: ";
	for (int idx : selected)
		cout << idx+1 << " ";
	cout << "个香蕉" << endl;
}

int main() {
	vector<int> bananas = {1, 2, 3, 1}; // 每个香蕉的甜
	
	vector<int> dp(bananas.size());
	dp[0] = bananas[0];
	dp[1] = max(bananas[0], bananas[1]);
	for (int i = 2; i < bananas.size(); i++) {
		dp[i] = max(bananas[i] + dp[i-2], dp[i-1]);
	}
	findSelectedBananas(bananas, dp);
	
	return 0;
}

三、编程题（每题 25 分，共 50 分）

第 1 题划分字符串

题面描述

小 A 有一个由 $n$ 个小写字母组成的字符串 $s$。他希望将划分为若干个子串，使得子串中每个字母至多出现一次。

例如，对于字符串 street 来说， str + e + e + t 是满足条件的划分；而 s + tree + t 不是，因为子串tree 中 e 出现了两次。

额外地，小 A 还给出了价值 $a_1,a_2,\cdots,a_n$，表示划分后长度为的子串价值为 $a_i$。小 A 希望最大化划分后得到的子串价值之和。你能帮他求出划分后子串价值之和的最大值吗？

输入格式

第一行，一个正整数 $n$，表示字符串的长度。

第二行，一个包含个小写字母的字符串 s 。

第三行，$n$ 个正整数 $a_1,a_2,\cdots,a_n$，表示不同长度的子串价值。

输出格式

一行，一个整数，表示划分后子串价值之和的最大值。

输入数据#1 复制

6
street
2 1 7 4 3 3

输出数据#1 复制

输入数据#2 复制

8
blossoms
1 1 2 3 5 8 13 21

输出数据#2 复制

数据要求

对于 $40$% 的测试点，保证 $1 \le n \le 10^3$。

对于所有测试点，保证 $1 \le n \le 10^5$，$1 \le a_i \le 10^9$。

第 2 题货物运输

题面描述

A 国有 $n$ 座城市，依次以 $1,2,\cdots,n$ 编号，其中 $1$ 号城市为首都。这 $n$ 座城市由 $n-1$ 条双向道路连接，第 $i$ 条道路

（ $1 \le i \lt n$ ）连接编号为 $u_i,v_i$ 的两座城市，道路长度为 $l_i$。任意两座城市间均可通过双向道路到达。

现在 A 国需要从首都向各个城市运送货物。具体来说，满载货物的车队会从首都开出，经过一座城市时将对应的货物送出，因此车队需要经过所有城市。A 国希望你设计一条路线，在从首都出发经过所有城市的前提下，最小化经过的道路长度总和。注意一座城市可以经过多次，车队最后可以不返回首都。

输入格式

第一行，一个正整数 $n$，表示 A 国的城市数量。

接下来 $n-1$ 行，每行三个整数 $u_i,v_i,l_i$，表示一条双向道路连接编号为 $u_i,v_i$ 的两座城市，道路长度为 $l_i$。

输出格式

一行，一个整数，表示你设计的路线所经过的道路长度总和。

输入数据#1 复制

输出数据#1 复制

输入数据#2 复制

输出数据#2 复制

数据要求

对于 $30$% 的测试点，保证 $1 \le n \le 8$。

对于另外 $30$% 的测试点，保证仅与一条双向道路连接的城市恰有两座。

对于所有测试点，保证 $1 \le n \le 10^5$，$1 \le u_i,v_i \le n$，$1 \le l_i \le 10^9$ 。