GESP 六级 · 2025 真题

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

阅读以下代码，回答第 1、2 小题：

01class Animal {
02public:
03    std::string name;
04
05    Animal(std::string str) : name(str) {
06        std::cout << "Animal created\n";
07    }
08    virtual void speak() {
09        cout << "Animal speaks" << endl;
10    }
11};
12
13class Dog : public Animal {
14    std::string breed;
15public:
16    Dog(std::string name, std::string b) : ____________, breed(b) {
17        std::cout << "Dog created\n";
18    }
19    void speak() override {
20        cout << "Dog barks" << endl;
21    }
22};
23
24int main() {
25    Animal* p = new Dog("Rex", "Labrador");
26    p->speak();
27    delete p;
28    return 0;
29}

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

01stack<int> s;
02queue<int> q;
03
04for (int i = 1; i <= 3; ++i) {
05    s.push(i);
06    q.push(i);
07}
08cout << s.top() << " " << q.front() << endl;

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

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

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

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

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

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

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

01struct TreeNode {
02    int val;
03    TreeNode* left;
04    TreeNode* right;
05    TreeNode(int x): val(x), left(nullptr), right(nullptr) {}
06};
07
08void dfs(TreeNode* root, vector<int>& result) {
09    if (root == nullptr) return;
10
11    ____________
12}

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

01#include <vector>
02#include <queue>
03#include <algorithm>
04
05struct TreeNode {
06    int val;
07    TreeNode* left;
08    TreeNode* right;
09    TreeNode(int x): val(x), left(nullptr), right(nullptr) {}
10};
11
12vector<int> largestValues(TreeNode* root) {
13    vector<int> result;
14    if (!root) return result;
15
16    queue<TreeNode*> q;
17    q.push(root);
18
19    while (!q.empty()) {
20        int sz = q.size();
21        int maxVal = INT_MIN;
22        for (int i = 0; i < sz; ++i) {
23            TreeNode* node;
24            ____________
25            maxVal = max(maxVal, node->val);
26            if (node->left) q.push(node->left);
27            if (node->right) q.push(node->right);
28        }
29        result.push_back(maxVal);
30    }
31
32    return result;
33}

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

01struct TreeNode {
02    int val;
03    TreeNode* left;
04    TreeNode* right;
05    TreeNode(int x): val(x), left(nullptr), right(nullptr) {}
06};
07
08void insert(TreeNode*& root, int key) {
09    if (!root) {
10        root = new TreeNode(key);
11        return;
12    }
13
14    ____________
15}

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

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

01int knapsack1D(int W, vector<int>& wt, vector<int>& val, int n) {
02    vector<int> dp(W+1, 0);
03    for (int i = 0; i < n; ++i) {
04        for (int w = W; w >= wt[i]; --w) {
05            dp[w] = max(dp[w], dp[w - wt[i]] + val[i]);
06        }
07    }
08    return dp[W];
09}

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

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

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

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

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

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

01class Dog {
02public:
03    std::string name;
04    Dog(std::string str) : name(str) {}
05};
06
07int main() {
08    Dog my_dog("Buddy");
09    my_dog.name = "Charlie";
10    return 0;
11}

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

01class Parent {
02private:
03    int value = 100;
04};
05class Child : public Parent {
06public:
07    int get_private_val() {
08        return value; // 尝试访问父类的私有成员
09    }
10};

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

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

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

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

01int coinChangeDPComp(vector<int>& coins, int amt) {
02    int n = coins.size();
03    int MAX = amt + 1;
04
05    vector<int> dp(amt + 1, MAX);
06    dp[0] = 0;
07
08    for (int i = 1; i <= n; i++) {
09        for (int a = 1; a <= amt; a++) {
10            if (coins[i - 1] > a)
11                dp[a] = dp[a];
12            else
13                dp[a] = min(dp[a], dp[a - coins[i - 1]] + 1);
14        }
15    }
16    return dp[amt] != MAX ? dp[amt] : -1;
17}