GESP 六级 · 2025 真题

在面向对象编程中，类是一种重要的概念。下面关于类的描述中，不正确的是（）。

哈夫曼编码是一种数据压缩算法。以下关于哈夫曼编码的描述中，不正确的是（）。

以下代码实现了树的哪种遍历方式？

01void traverse(TreeNode* root) {
02    if (root == nullptr) return;
03    cout << root->val << " ";
04    traverse(root->left);
05    traverse(root->right);
06}

以下关于完全二叉树的代码描述，正确的是（）。

01bool isCompleteTree(TreeNode* root) {
02    if (root == nullptr) return true;
03    queue<TreeNode*> q;
04    q.push(root);
05    bool hasNull = false;
06    while (!q.empty()) {
07        TreeNode* node = q.front();
08        q.pop();
09        if (node == nullptr) {
10            hasNull = true;
11        } else {
12            if (hasNull) return false;
13            q.push(node->left);
14            q.push(node->right);
15        }
16    }
17    return true;
18}

以下代码实现了二叉排序树的哪种操作？

01TreeNode* op(TreeNode* root, int val) {
02    if (root == nullptr) return new TreeNode(val);
03    if (val < root->val) {
04        root->left = op(root->left, val);
05    } else {
06        root->right = op(root->right, val);
07    }
08    return root;
09}

给定字符集 {A, B, C, D} 的出现频率分别为 {5, 1, 6, 2}，则正确的哈夫曼编码是（）。

关于动态规划的描述，正确的是（）。

以下代码中，类的构造函数被调用了（ ）次。

01class MyClass {
02public:
03    MyClass() {
04        cout << "Constructor called!" << endl;
05    }
06};
07int main() {
08    MyClass obj1;
09    MyClass obj2 = obj1;
10    return 0;
11}

以下代码实现了循环队列的哪种操作？

01class CircularQueue {
02    int* arr;
03    int front, rear, size;
04public:
05    CircularQueue(int k) {
06        size = k;
07        arr = new int[k];
08        front = rear = -1;
09    }
10    bool enQueue(int value) {
11        if (isFull()) return false;
12        if (isEmpty()) front = 0;
13        rear = (rear + 1) % size;
14        arr[rear] = value;
15        return true;
16    }
17};

以下代码用于统计二叉树的叶节点数量，请在横线处填入代码。

01int countLeafNodes(TreeNode* root) {
02    if (root == nullptr) return 0;
03
04    stack<TreeNode*> s;
05    s.push(root);
06    int count = 0;
07    while (!s.empty()) {
08        TreeNode* node = s.top();
09        s.pop();
10
11        if (node->left == nullptr && node->right == nullptr) {
12            count++;
13        }
14
15        if (node->right) s.push(node->right);
16        ____________ // 在此处填入代码
17    }
18    return count;
19}

以下代码使用队列查找二叉树中的目标节点，请在横线处填入代码。

01TreeNode* findNode(TreeNode* root, int target) {
02    if (root == nullptr) return nullptr;
03
04    queue<TreeNode*> q;
05    q.push(root);
06    while (!q.empty()) {
07        TreeNode* current = q.front();
08        q.pop();
09
10        if (current->val == target) {
11            return current; // 找到目标节点
12        }
13
14        ____________ // 在此处填入代码
15    }
16    return nullptr; // 未找到目标节点
17}

以下代码生成格雷编码，请在横线处填入代码。

01vector<string> generateGrayCode(int n) {
02    if (n == 0) return {"0"};
03    if (n == 1) return {"0", "1"};
04
05    vector<string> prev = generateGrayCode(n - 1);
06    vector<string> result;
07
08    for (string s : prev) {
09        result.push_back("0" + s); // 在前缀添加 0
10    }
11    for (int i = prev.size() - 1; i >= 0; i--) {
12        ____________ // 在此处填入代码
13    }
14    return result;
15}

以下 $0/1$ 背包代码中，横线处应填入的内容是（）。

01int knapsack(int W, vector<int>& weights, vector<int>& values) {
02    int n = weights.size();
03    vector<vector<int>> dp(n + 1, vector<int>(W + 1, 0));
04
05    for (int i = 1; i <= n; i++) {
06        for (int j = 1; j <= W; j++) {
07            if (weights[i-1] > j) {
08                dp[i][j] = dp[i-1][j]; // 当前物品装不下
09            } else {
10                dp[i][j] = max(____________); // 在此处填入代码
11            }
12        }
13    }
14    return dp[n][W];
15}

以下代码判断括号是否匹配，请在横线处填入代码。

01bool isBalanced(string s) {
02    stack<char> st;
03    for (char c : s) {
04        if (c == '(' || c == '[' || c == '{') {
05            st.push(c);
06        } else {
07            if (st.empty()) return false; // 无括号匹配
08            char top = st.top();
09            st.pop();
10            if ((c == ')' && top != '(') ||
11                (c == ']' && top != '[') ||
12                (c == '}' && top != '{')) {
13                return false;
14            }
15        }
16    }
17    return ____________; // 在此处填入代码
18}

关于下面代码，说法错误的是（）。

01class Shape {
02protected:
03    string name;
04
05public:
06    Shape(const string& n) : name(n) {}
07
08    virtual double area() const {
09        return 0.0;
10    }
11};
12
13class Circle : public Shape {
14private:
15    double radius;
16
17public:
18    Circle(const string& n, double r) : Shape(n), radius(r) {}
19
20    double area() const override {
21        return 3.14159 * radius * radius;
22    }
23};
24
25class Rectangle : public Shape {
26private:
27    double width;   // 宽度
28    double height;  // 高度
29
30public:
31    Rectangle(const string& n, double w, double h) : Shape(n), width(w), height(h) {}
32
33    double area() const override {
34        return width * height;
35    }
36};
37
38int main() {
39    Circle circle("MyCircle", 5.0);
40    Rectangle rectangle("MyRectangle", 4.0, 6.0);
41
42    Shape* shapePtr = &circle;
43    cout << "Area: " << shapePtr->area() << endl;
44
45    shapePtr = &rectangle;
46    cout << "Area: " << shapePtr->area() << endl;
47
48    return 0;
49}

哈夫曼树在构造过程中，每次合并权值最小的两个节点，最终生成的树带权路径长度最小。

格雷编码的相邻两个编码之间必须有多位不同，以避免数据传输错误。

在树的深度优先搜索（DFS）中，使用队列作为辅助数据结构以实现“先进后出”的访问顺序。

01void traverse(TreeNode* root) {
02    if (root == nullptr) return;
03    traverse(root->left);
04    cout << root->val << " ";
05    traverse(root->right);
06}

以下代码实现的是一棵树的中序遍历：

TreeNode* root = new TreeNode{1};
root->left = new TreeNode{2};
root->right = new TreeNode{3};
root->left->left = new TreeNode{4};

C++ 支持构造函数重载，但默认无参数的构造函数只能有一个。

二叉排序树（BST）中，若某节点的左子树为空，则该节点一定是树中的最小值节点。

在动态规划解决一维硬币找零问题时，若硬币面额为 [1, 3, 4]，目标金额为 $6$，则最少需要 $2$ 枚硬币（3+3）。

面向对象编程中，封装是指将数据和行为绑定在一起，并对外隐藏实现细节。

以下代码创建的树是一棵完全二叉树：

TreeNode* root = new TreeNode{1};
root->left = new TreeNode{2};
root->right = new TreeNode{3};
root->left->left = new TreeNode{4};

栈和队列均可以用双向链表实现，插入和删除操作的时间复杂度为 $O(1)$。