2024年12月 GESP C++ 6级

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

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

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

#include <iostream>
using namespace std;
class MyClass {
    public:
    MyClass() {
        cout << "Constructor called!" << endl;
    }
    void display() {
        cout << "Display function called!" << endl;
    }
};
int main() {
    MyClass* obj = NULL;
    obj->display();
    return 0;
}

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

void processData() {
    stack<int> s;
    queue<int> q;
    for (int i = 1; i <= 5; ++i) {
        s.push(i);
        q.push(i);
    }
    while (!s.empty()) {
        cout << "Stack pop: " << s.top() << endl;
        s.pop();
    }
    while (!q.empty()) {
        cout << "Queue pop: " << q.front() << endl;
        q.pop();
    }
}

$n$ 个节点的双向循环链，在其中查找某个节点的平均时间复杂度是( )。

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

已知字符集 {$A$, $B$, $C$, $D$} 的出现频率如下表所⽰： 字符 频率 $A$ $8$ $B$ $3$ $C$ $1$ $D$ $6$ 根据哈夫曼编码法，下面（ ）是正确的哈夫曼树。

上一题中各字符的哈夫曼编码是（ ）。

( ) 是 $3$ 位格雷编码。

根据下面二叉树和给定的代码，

#include <iostream>
using namespace std;
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
TreeNode* search(TreeNode* root, int val) {
    cout << root->val << " ";
    if (root == NULL || root->val == val) return root;
    if (val < root->val)
        return search(root->left, val);
    else
        return search(root->right, val);
}

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

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

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

void dfs(TreeNode* root) {
    if (root == nullptr)
        return;
    stack<TreeNode*> s;
    s.push(root);
    while (!s.empty()) {
        ———————————————————————— // 在此处填入代码
        cout << node->value << " ";
        if (node->right) s.push(node->right);
        if (node->left) s.push(node->left);
    }
}

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

#include <queue>
void bfs(TreeNode* root) {
    if (root == NULL) return;
    queue<TreeNode*> q;
    q.push(root);
    while (!q.empty()) {
        ———————————————————————— // 在此处填入代码
        cout << node->val << " ";
        if (node->left) {
            q.push(node->left);
        }
        if (node->right) {
            q.push(node->right);
        }
    }
}

使用上题中的宽度优先搜索算法遍历以下这棵树，可能的输出是( )。

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

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

假设背包的最大容量 $W=50$，共有 $n=4$ 个物品可供选择，$4$ 个物品的重量分别为 $w=[10,20,30,40]$，对应的价值分别为 $v=[60,100,120,150]$，则该 $0/1$ 背包问题中，背包的最大价值为（ ）。

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

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

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

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

struct TreeNode {
    int value;
    TreeNode* left;
    TreeNode* right;
};
TreeNode* buildCompleteBinaryTree() {
    TreeNode* root = new TreeNode{1};
    root->left = new TreeNode{2};
    root->right = new TreeNode{3};
    root->left->left = new TreeNode{4};
    root->left->right = new TreeNode{5};
    root->right->left = new TreeNode{6};
    return root;
}

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

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

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

void preorder(TreeNode* root) {
    if (root == NULL) return;
    cout << root->val << " ";
    preorder(root->left);
    preorder(root->right);
}

在二叉树中，宽度优先搜索算法（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$ 开始。

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

试题名称：树上游走

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

题目描述

小杨有一棵包含无穷节点的二叉树（即每个节点都有左儿子节点和右儿子节点；除根节点外，每个节点都有父节点），其中根节点的编号为 $1$，对于节点 $i$，其左儿子的编号为 $2\times i$，右儿子的编号为 $2\times i+1$。

小杨会从节点 $s$ 开始在二叉树上移动，每次移动为以下三种移动方式的任意一种：

• 第 1 种移动方式：如果当前节点存在父亲节点，向上移动到当前节点的父节点，否则不移动；
• 第 2 种移动方式：移动到当前节点的左儿子；
• 第 3 种移动方式：移动到当前节点的右儿子。

小杨想知道移动 $n$ 次后自己所处的节点编号。数据保证最后所处的节点编号不超过 101210^{12}1012。

输入格式

第一行包含两个正整数 $n$ 和 $s$，代表移动次数和初始节点编号。

第二行包含一个长度为 $n$ 且仅包含大写字母 $\mathtt{U}$、$\mathtt{L}$ 和 $\mathtt{R}$ 的字符串，代表每次移动的方式，其中 $\mathtt{U}$ 代表第 1 种移动方式，$\mathtt{L}$ 代表第 2 种移动方式，$\mathtt{R}$ 代表第 3 种移动方式。

输出格式

输出一个正整数，代表最后所处的节点编号。

样例输入 #1

3 2
URR

样例输出 #1

7

说明/提示

小杨的移动路线为 $2\to 1\to 3\to 7$。

对于全部数据，保证有 1≤n≤1061\leq n\leq 10^61≤n≤106，1≤s≤10121\leq s\leq 10^{12}1≤s≤1012。

试题名称：运送物资

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

题目描述

小杨管理着 $m$ 辆货车，每辆货车每天需要向 A 市和 B 市运送若干次物资。小杨同时拥有 $n$ 个运输站点，这些站点位于 A 市和 B 市之间。

每次运送物资时，货车从初始运输站点出发，前往 A 市或 B 市，之后返回初始运输站点。A 市、B 市和运输站点的位置可以视作数轴上的三个点，其中 A 市的坐标为 $0$，B 市的坐标为 $x$，运输站点的坐标为 $p$ 且有 $0<p<x$。货车每次去 A 市运送物资的总行驶路程为 $2p$，去 B 市运送物资的总行驶路程为 $2(x-p)$。

对于第 $i$ 个运输站点，其位置为 pip_ipi​ 且至多作为 cic_ici​ 辆车的初始运输站点。小杨想知道，在最优分配每辆货车的初始运输站点的情况下，所有货车每天的最短总行驶路程是多少。

输入格式

第一行包含三个正整数 $n,m,x$，代表运输站点数量、货车数量和两市距离。

之后 $n$ 行，每行包含两个正整数 pip_ipi​ 和 cic_ici​，代表第 $i$ 个运输站点的位置和最多容纳车辆数。

之后 $m$ 行，每行包含两个正整数 aia_iai​ 和 bib_ibi​，代表第 $i$ 辆货车每天需要向 A 市运送 aia_iai​ 次物资，向 B 市运送 bib_ibi​ 次物资。

输出格式

输出一个正整数，代表所有货车每天的最短总行驶路程。

样例输入 #1

3 4 10
1 1
2 1
8 3
5 3
7 2
9 0
1 10000

样例输出 #1

40186

说明/提示

第 $1$ 辆车的初始运输站点为站点 $3$，第 $2$ 辆车的初始运输站点为站点 $2$。第 $3$ 辆车的初始运输站点为站点 $1$，第 $4$ 辆车的初始运输站点为站点 $3$。此时总驶路程最短，为 $40186$。

对于全部数据，保证有 1≤n,m≤1051\leq n,m\leq 10^51≤n,m≤105，2≤x≤1082\leq x\leq 10^82≤x≤108，0<pi<x0\lt p_i\lt x0<pi​<x，1≤ci≤1051\leq c_i\leq 10^51≤ci​≤105，0≤ai,bi≤1050\leq a_i,b_i\leq 10^50≤ai​,bi​≤105。数据保证 ∑ci≥m\sum c_i\geq m∑ci​≥m。