CCF GESP 2025年3月认证 C++ 6级
一
单选题
第 1 题
在面向对象编程中，类是一种重要的概念。下面关于类的描述中，不正确的是（ ）。
第 2 题
哈夫曼编码是一种数据压缩算法。以下关于哈夫曼编码的描述中，不正确的是（ ）。
第 3 题
以下代码实现了树的哪种遍历方式？
void traverse(TreeNode* root) {
if (root == nullptr) return;
cout << root->val << " ";
traverse(root->left);
traverse(root->right);
}
第 4 题
以下关于完全二叉树的代码描述，正确的是（ ）。
bool isCompleteTree(TreeNode* root) {
if (root == nullptr) return true;
queue<TreeNode*> q;
q.push(root);
bool hasNull = false;
while (!q.empty()) {
TreeNode* node = q.front();
q.pop();
if (node == nullptr) {
hasNull = true;
} else {
if (hasNull) return false;
q.push(node->left);
q.push(node->right);
}
}
return true;
}
第 5 题
以下代码实现了二叉排序树的哪种操作？
TreeNode* op(TreeNode* root, int val) {
if (root == nullptr) return new TreeNode(val);
if (val < root->val) {
root->left = op(root->left, val);
} else {
root->right = op(root->right, val);
}
return root;
}
第 6 题
给定字符集 $\{A, B, C, D\}$ 的出现频率分别为 $\{5, 1, 6, 2\}$，则正确的哈夫曼编码是（ ）。
第 7 题
关于动态规划的描述，正确的是（ ）。
第 8 题
以下代码中，类的构造函数被调用了（ ）次。
class MyClass {
public:
MyClass() {
cout << "Constructor called!" << endl;
}
};
int main() {
MyClass obj1;
MyClass obj2 = obj1;
return 0;
}
第 9 题
以下代码实现了循环队列的哪种操作？
class CircularQueue {
int* arr;
int front, rear, size;
public:
CircularQueue(int k) {
size = k;
arr = new int[k];
front = rear = -1;
}
bool enQueue(int value) {
if (isFull()) return false;
if (isEmpty()) front = 0;
rear = (rear + 1) % size;
arr[rear] = value;
return true;
}
};
第 10 题
以下代码实现了二叉树的深度优先搜索（DFS），并统计叶子结点的数量，则横线上应填写（ ）。
int countLeafNodes(TreeNode* root) {
if (root == nullptr) return 0;
stack<TreeNode*> s;
s.push(root);
int count = 0;
while (!s.empty()) {
TreeNode* node = s.top();
s.pop();
if (node->left == nullptr && node->right == nullptr) {
count++;
}
if (node->right) s.push(node->right);
________________________ // 在此处填入代码
}
return count;
}
第 11 题
以下代码实现了二叉树的广度优先搜索（BFS），并查找特定值的节点，则横线上应填写（ ）。
TreeNode* findNode(TreeNode* root, int target) {
if (root == nullptr) return nullptr;
queue<TreeNode*> q;
q.push(root);
while (!q.empty()) {
TreeNode* current = q.front();
q.pop();
if (current->val == target) {
return current; // 找到目标节点
}
// 在此处填入代码
}
return nullptr; // 未找到目标节点
}
第 12 题
以下代码用于生成 $n$ 位格雷编码。横线上应填写（ ）。
vector<string> generateGrayCode(int n) {
if (n == 0) return {"0"};
if (n == 1) return {"0", "1"};
vector<string> prev = generateGrayCode(n - 1);
vector<string> result;
for (string s : prev) {
result.push_back("0" + s); // 在前缀添加 0
}
for (int i = prev.size() - 1; i >= 0; i--) {
________________________ // 在此处填入代码
}
return result;
}
第 13 题
以下代码实现了 0/1 背包问题的动态规划解法。假设物品重量为 weights[]，价值为 values[]，背包容量为 $W$，横线上应填写（ ）。
int knapsack(int W, vector<int>& weights, vector<int>& values) {
int n = weights.size();
vector<vector<int>> dp(n + 1, vector<int>(W + 1, 0));
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= W; j++) {
if (weights[i-1] > j) {
dp[i][j] = dp[i-1][j]; // 当前物品装不下
} else {
dp[i][j] = max(__________________); // 在此处填入代码
}
}
}
return dp[n][W];
}
第 14 题
以下代码用于检查字符串中的括号是否匹配，横线上应填写（ ）。
bool isBalanced(string s) {
stack<char> st;
for (char c : s) {
if (c == '(' || c == '[' || c == '{') {
st.push(c);
} else {
if (st.empty()) return false; // 无左括号匹配
char top = st.top();
st.pop();
if ((c == ')' && top != '(') ||
(c == ']' && top != '[') ||
(c == '}' && top != '{')) {
return false;
}
}
}
return _______________; // 在此处填入代码
}
第 15 题
关于下面代码，说法错误的是（ ）。
class Shape {
protected:
string name;
public:
Shape(const string& n) : name(n) {}
virtual double area() const {
return 0.0;
}
};
class Circle : public Shape {
private:
double radius;
public:
Circle(const string& n, double r) : Shape(n), radius(r) {}
double area() const override {
return 3.14159 * radius * radius;
}
};
class Rectangle : public Shape {
private:
double width; // 宽度
double height; // 高度
public:
Rectangle(const string& n, double w, double h) : Shape(n), width(w), height(h) {}
double area() const override {
return width * height;
}
};
int main() {
Circle circle("MyCircle", 5.0);
Rectangle rectangle("MyRectangle", 4.0, 6.0);
Shape* shapePtr = &circle;
cout << "Area: " << shapePtr->area() << endl;
shapePtr = &rectangle;
cout << "Area: " << shapePtr->area() << endl;
return 0;
}
单选题部分已到底了。