CCF GESP 2025年9月认证 C++ 6级
下列关于类的说法，错误的是（ ）。
假设变量 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;
}
};下面代码中 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;
}栈的操作特点是（ ）。
循环队列常用于实现数据缓冲。假设一个循环队列容量为 $5$（即最多存放 $4$ 个元素，留一个位置区分空与满），依次进行操作：入队数据 $1$、$2$、$3$，出队 $1$ 个数据，再入队数据 $4$ 和 $5$，此时队首到队尾的元素顺序是（ ）。
以下函数 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;
}已知二叉树的中序遍历是 [D, B, E, A, F, C]，先序遍历是 [A, B, D, E, C, F]。请问该二叉树的后序遍历结果是（ ）。
完全二叉树可以用数组连续高效存储，如果节点从 $1$ 开始编号，则对有两个孩子节点的节点 $i$，（ ）。
设有字符集 {a, b, c, d, e, f}，其出现频率分别为 {5, 9, 12, 13, 16, 45}。哈夫曼算法构造最优前缀编码，以下哪一组可能是对应的哈夫曼编码？（非叶子节点左边分支记作 0，右边分支记作 1，左右互换不影响正确性）。
下面代码生成格雷编码。则横线上应填写（ ）。
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;
}请将下列树的深度优先遍历代码补充完整，横线处应填入（ ）。
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);
}
}令 $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);
}
}在二叉排序树（Binary Search Tree, BST）中查找元素 $50$，从根节点开始：若根值为 $60$，则下一步应去搜索：
删除二叉排序树中的节点时，如果节点有两个孩子，则横线处应填入（ ），其中 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;
}给定 $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];
}