GESP 六级 · 2024 真题

面向对象编程(OOP)是一种特殊的程序设计方法。下面（ ）不是重要的OOP特性。

以下关于C++中类的说法，哪一项是正确的？

以下C++代码段中存在语法错误或逻辑错误，（ ）是正确的。

01#include <iostream>
02using namespace std;
03
04class MyClass {
05public:
06    MyClass() {
07        cout << "Constructor called!" << endl;
08    }
09    void display() {
10        cout << "Display function called!" << endl;
11    }
12};
13
14int main() {
15    MyClass* obj = NULL;
16    obj->display();
17    return 0;
18}

阅读以下代码，下面哪一项是正确的？

01void processData() {
02    stack<int> s;
03    queue<int> q;
04    for (int i = 1; i <= 5; ++i) {
05        s.push(i);
06        q.push(i);
07    }
08    while (!s.empty()) {
09        cout << "Stack pop: " << s.top() << endl;
10        s.pop();
11    }
12    while (!q.empty()) {
13        cout << "Queue pop: " << q.front() << endl;
14        q.pop();
15    }
16}

N 个节点的双向循环链，在其中查找某个节点的平均时间复杂度是（）。

以下关于树的说法，（ ）是正确的。

已知字符集 {A, B, C, D} 的出现频率如下表所示：

根据哈夫曼编码法，下面（ ）是正确的哈夫曼树。

已知字符集 {A, B, C, D} 的出现频率为 A:8、B:3、C:1、D:6，根据哈夫曼编码法，各字符的哈夫曼编码是（ ）。

（ ）是 $3$ 位格雷编码。

根据下面二叉树和给定的代码，给定以下二叉搜索树，调用函数 search(root, 7) 时，输出的结果是（）。

01#include <iostream>
02using namespace std;
03
04struct TreeNode {
05    int val;
06    TreeNode* left;
07    TreeNode* right;
08    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
09};
10
11TreeNode* search(TreeNode* root, int val) {
12    cout << root->val << " ";
13    if (root == NULL || root->val == val) return root;
14
15    if (val < root->val)
16        return search(root->left, val);
17    else
18        return search(root->right, val);
19}

二叉搜索树根为 $5$，第二层为 $3$ 和 $7$，第三层为 $2$、$4$、$6$、$8$。

阅读以下二叉树的深度优先搜索算法，横线上应填写（）。

01void dfs(TreeNode* root) {
02    if (root == nullptr)
03        return;
04
05    stack<TreeNode*> s;
06    s.push(root);
07    while (!s.empty()) {
08        ____________ // 在此处填入代码
09        cout << node->value << " ";
10
11        if (node->right) s.push(node->right);
12        if (node->left) s.push(node->left);
13    }
14}

阅读以下二叉树的广度优先搜索的代码，横线上应填写（）。

01#include <queue>
02void bfs(TreeNode* root) {
03    if (root == NULL) return;
04
05    queue<TreeNode*> q;
06    q.push(root);
07    while (!q.empty()) {
08        ____________ // 在此处填入代码
09        cout << node->val << " ";
10        if (node->left) {
11            q.push(node->left);
12        }
13        if (node->right) {
14            q.push(node->right);
15        }
16    }
17}

使用宽度优先搜索（BFS）遍历以下这棵树，可能的输出是（ ）。

    1
   / \
  2   3
 / \   \
8   9   6
   / \   \
  4   5   7

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

假设背包的最大容量 $W = 8\text{kg}$，共有 $4$ 个物品可供选择，$4$ 个物品重量分别为 weights = [2, 3, 5, 7]，价值 values = [30, 40, 60, 80]，则该0/1背包问题中最大价值为（）。

构造函数是一种特殊的类成员函数，构造函数的名称和类名相同。但通过函数重载，可以创建多个同名的构造函数，条件是每个构造函数的参数列表不同。

类的静态成员函数既能访问类的静态数据成员，也能访问非静态成员数据。

栈中元素的插入和删除操作都在栈的顶端进行，所以方便用单向链表实现。

下面代码构建的树一定是完全二叉树：

01struct TreeNode {
02    int value;
03    TreeNode* left;
04    TreeNode* right;
05};
06
07TreeNode* buildCompleteBinaryTree() {
08    TreeNode* root = new TreeNode{1};
09    root->left = new TreeNode{2};
10    root->right = new TreeNode{3};
11    root->left->left = new TreeNode{4};
12    root->left->right = new TreeNode{5};
13    root->right->left = new TreeNode{6};
14    return root;
15}

在二叉排序树中，左子树所有节点的值都大于根节点的值，右子树所有节点的值都小于根节点的值。

在生成一个派生类的对象时，只调用派生类的构造函数。

下面的代码实现了二叉树的前序遍历，它通过递归方法访问每个节点并打印节点值。

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

在二叉树中，宽度优先搜索算法（BFS）保证从起点到每个节点的访问路径是边数最少的路径（即最短路径）。

在解决简单背包问题时，动态规划的状态转移方程如下：

dp[i][w] = max(dp[i-1][w], dp[i-1][w - weights[i-1]] + values[i-1]);

该方程表示：在考虑第 $i$ 个物品时，当前背包容量为 $w$，如果不放物品 $i$，则最大价值是 dp[i-1][w]；如果放入物品 $i$，则最大价值是 dp[i-1][w - weights[i-1]] + values[i-1]，其中数组 weights 和 values 分别表示所有物品的重量和值，数组下标从 $0$ 开始。

栈中元素的插入和删除操作都在栈的顶端进行，所以方便用双向链表比单向链表更合适实现。