2025年6月 GESP C++ 6级

下列哪一项不是面向对象编程的基本特征？

1. 为了让 Dog 类的构造函数能正确地调用其父类 Animal 的构造方法，横线处应填入（ ）。

class Animal {
    public:
    std::string name;
    Animal(std::string str) : name(str) {
        std::cout << "Animal created\n";
    }
    virtual void speak() {
        cout << "Animal speaks" << endl;
    }
};
class Dog : public Animal {
    std::string breed;
    public:
    Dog(std::string name, std::string b) : _________________, breed(b) {
        std::cout << "Dog created\n";
    }
    void speak() override {
        cout << "Dog barks" << endl;
    }
};
int main() {
    Animal* p = new Dog("Rex", "Labrador");
    p->speak();
    delete p;
    return 0;
}

代码同上一题，代码执行结果是（ ）。

以下关于栈和队列的代码，执行后输出是（ ）。

stack<int> s;
queue<int> q;
for (int i = 1; i <= 3; ++i) {
    s.push(i);
    q.push(i);
}
cout << s.top() << " " << q.front() << endl;

在一个循环队列中，front 是指向队头的指针，rear 指向队尾的指针，队列最大容量为 maxSize。判断队列已满的条件是（ ）。

（ ）只有最底层的节点未被填满，且最底层节点尽量靠左填充。

在使用数组表示完全二叉树时，如果一个节点的索引为 $i$（从 $0$ 开始计数），那么其左子节点的索引通常是（ ）。

已知一棵二叉树的前序遍历序列为 GDAFEMHZ，中序遍历序列为 ADFGEHMZ，则其后序遍历序列为（ ）。

设有字符集 {$a$, $b$, $c$, $d$, $e$}，其出现频率分别为 {$5$, $8$, $12$, $15$, $20$}，得到的哈夫曼编码为（ ）。

$3$ 位格雷编码中，编码 $101$ 之后的下一个编码不可能是（ ）。

请将下列 C++ 实现的深度优先搜索（DFS）代码补充完整，横线处应填入（ ）。

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x): val(x), left(nullptr), right(nullptr) {}
};
void dfs(TreeNode* root, vector<int>& result) {
    if (root == nullptr) return;
    __________________________
}

给定一个二叉树，返回每一层中最大的节点值，结果以数组形式返回，横线处应填入（ ）。

#include <vector>
#include <queue>
#include <algorithm>
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x): val(x), left(nullptr), right(nullptr) {}
};
vector<int> largestValues(TreeNode* root) {
    vector<int> result;
    if (!root) return result;
    queue<TreeNode*> q;
    q.push(root);
    while (!q.empty()) {
        int sz = q.size();
        int maxVal = INT_MIN;
        for (int i = 0; i < sz; ++i) {
            TreeNode* node;
            _______________________________
            maxVal = max(maxVal, node->val);
            if (node->left) q.push(node->left);
            if (node->right) q.push(node->right);
        }
        result.push_back(maxVal);
    }
    return result;
}

下面代码实现一个二叉排序树的插入函数（没有相同的数值），横线处应填入（ ）。

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x): val(x), left(nullptr), right(nullptr) {}
};
void insert(TreeNode*& root, int key) {
    if (!root) {
        root = new TreeNode(key);
        return;
    }
    _______________________________
}

以下关于动态规划算法特性的描述，正确的是（ ）。

给定 $n$ 个物品和一个最大承重为 $W$ 的背包，每个物品有一个重量 wiw_iwi​ 和价值 viv_ivi​ ，每个物品只能选择放或不放。目标是选择若干个物品放入背包，使得总价值最大，且总重量不超过 $W$ 。关于下面代码，说法正确的是（ ）。

int knapsack1D(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) {
            dp[w] = max(dp[w], dp[w - wt[i]] + val[i]);
        }
    }
    return dp[W];
}

构造函数可以被声明为 virtual。

给定一组字符及其出现的频率，构造出的哈夫曼树是唯一的。

为了实现一个队列，使其出队操作（pop）的时间复杂度为 $O(1)$ 并且避免数组删除首元素的 $O(n)$ 问题，一种常见且有效的方法是使用环形数组，通过调整队首和队尾指针来实现。

对一棵二叉排序树进行中序遍历，可以得到一个递增的有序序列。

如果二叉搜索树在连续的插入和删除操作后，所有节点都偏向一侧，导致其退化为类似于链表的结构，这时其查找、插入、删除操作的时间复杂度会从理想情况下的 $O(\log n)$ 退化到 $O(n)$。

执行下列代码，my_dog.name 的最终值是 Charlie。

class Dog {
    public:
    std::string name;
    Dog(std::string str) : name(str) {}
};
int main() {
    Dog my_dog("Buddy");
    my_dog.name = "Charlie";
    return 0;
}

下列 C++ 代码可以成功编译，并且子类 Child 的实例能通过其成员函数访问父类 Parent 的属性 value。

class Parent {
    private:
    int value = 100;
};
class Child : public Parent {
    public:
    int get_private_val() {
        return value; // 尝试访问父类的私有成员
    }
};

下列代码中的 tree 向量，表示的是一棵完全二叉树 ($-1$ 代表空节点) 按照层序遍历的结果。

#include <vector>
std::vector<int> tree = {1, 2, 3, 4, -1, 6, 7};

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

下面代码采用动态规划求解零钱兑换问题：给定 $n$ 种硬币，第 $i$ 种硬币的面值为 $coins[i-1]$，目标金额为 $amt$，每种硬币可以重复选取，求能够凑出目标金额的最少硬币数量；如果不能凑出目标金额，返回 $-1$。

int coinChangeDPComp(vector<int> &coins, int amt) {
    int n = coins.size();
    int MAX = amt + 1;
    vector<int> dp(amt + 1, MAX);
    dp[0] = 0;
    for (int i = 1; i <= n; i++) {
        for (int a = 1; a <= amt; a++) {
            if (coins[i - 1] > a)
                dp[a] = dp[a];
            else
                dp[a] = min(dp[a], dp[a - coins[i - 1]] + 1);
        }
    }
    return dp[amt] != MAX ? dp[amt] : -1;
}

试题名称：学习小组

时间限制：1.0 s | 内存限制：512.0 MB

题目描述

班主任计划将班级里的 $n$ 名同学划分为若干个学习小组，每名同学都需要分入某一个学习小组中。观察发现，如果一个学习小组中恰好包含 $k$ 名同学，则该学习小组的讨论积极度为 aka_kak​。

给定讨论积极度 a1,a2,…,ana_1, a_2, \ldots, a_na1​,a2​,…,an​，请你计算将这 $n$ 名同学划分为学习小组的所有可能方案中，讨论积极度之和的最大值。

输入格式

第一行，一个正整数 $n$，表示班级人数。

第二行，$n$ 个非负整数 a1,a2,…,ana_1, a_2, \ldots, a_na1​,a2​,…,an​，表示不同人数学习小组的讨论积极度。

输出格式

输出共一行，一个整数，表示所有划分方案中，学习小组讨论积极度之和的最大值。

样例输入 #1

4
1 5 6 3

样例输出 #1

10

样例输入 #2

8
0 2 5 6 4 3 3 4

样例输出 #2

12

说明/提示

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

对于所有测试点，保证 $1\le n\le 1000$，0≤ai≤1040\le a_i\le 10^40≤ai​≤104。

试题名称：最大因数

时间限制：1.0 s | 内存限制：512.0 MB

题目描述

给定一棵有 10910^9109 个结点的有根树，这些结点依次以 1,2,…,1091, 2, \dots, 10^91,2,…,109 编号，根结点的编号为 $1$。对于编号为 $k$（2≤k≤1092 \leq k \leq 10^92≤k≤109）的结点，其父结点的编号为 $k$ 的因数中除 $k$ 以外最大的因数。

现在有 $q$ 组询问，第 $i$（$1\le i\le q$）组询问给定 xi,yix_i, y_ixi​,yi​，请你求出编号分别为 xi,yix_i, y_ixi​,yi​ 的两个结点在这棵树上的距离。两个结点之间的距离是连接这两个结点的简单路径所包含的边数。

输入格式

第一行，一个正整数 $q$，表示询问组数。

接下来 $q$ 行，每行两个正整数 xi,yix_i, y_ixi​,yi​，表示询问结点的编号。

输出格式

输出共 $q$ 行，每行一个整数，表示结点 xi,yix_i, y_ixi​,yi​ 之间的距离。

样例输入 #1

3
1 3
2 5
4 8

样例输出 #1

1
2
1

样例输入 #2

1
120 650

样例输出 #2

9

说明/提示

对于 $60\%$ 的测试点，保证 1≤xi,yi≤10001 \leq x_i, y_i \leq 10001≤xi​,yi​≤1000。

对于所有测试点，保证 $1\le q\le 1000$，1≤xi,yi≤1091 \leq x_i, y_i \leq 10^91≤xi​,yi​≤109。