GESP 六级 · 2024 真题

面向对象的编程思想主要包括（ ）原则。

运行下列代码，屏幕上输出（ ）。

01#include <iostream>
02using namespace std;
03
04class my_class {
05public:
06    static int count;
07    my_class() {
08        count++;
09    }
10    ~my_class() {
11        count--;
12    }
13    static void print_count() {
14        cout << count << " ";
15    }
16};
17int my_class::count = 0;
18int main() {
19    my_class obj1;
20    my_class::print_count();
21    my_class obj2;
22    obj2.print_count();
23    my_class obj3;
24    obj3.print_count();
25    return 0;
26}

运行下列代码，屏幕上输出（ ）。

01#include <iostream>
02using namespace std;
03
04class shape {
05protected:
06    int width, height;
07public:
08    shape(int a = 0, int b = 0) {
09        width = a;
10        height = b;
11    }
12    virtual int area() {
13        cout << "parent class area: " <<endl;
14        return 0;
15    }
16};
17
18class rectangle: public shape {
19public:
20    rectangle(int a = 0, int b = 0) : shape(a, b) { }
21
22    int area () {
23        cout << "rectangle area: ";
24        return (width * height);
25    }
26};
27
28class triangle: public shape {
29public:
30    triangle(int a = 0, int b = 0) : shape(a, b) { }
31
32    int area () {
33        cout << "triangle area: ";
34        return (width * height / 2);
35    }
36};
37
38int main() {
39    shape *pshape;
40    rectangle rec(10, 7);
41    triangle  tri(10, 5);
42
43    pshape = &rec;
44    pshape->area();
45
46    pshape = &tri;
47    pshape->area();
48    return 0;
49}

向一个栈顶为 hs 的链式栈中插入一个指针为 s 的结点时，应执行（ ）。

在栈数据结构中，元素的添加和删除是按照什么原则进行的？

要实现将一个输入的十进制正整数转化为二进制表示，下面横线上应填入的代码为（ ）。

01#include <iostream>
02using namespace std;
03
04stack<int> ten2bin(int n) {
05    stack<int> st;
06    int r, m;
07
08    r = n % 2;
09    m = n / 2;
10    st.push(r);
11
12    while (m != 1) {
13        r = m % 2;
14        st.push(r);
15        m = m / 2;
16    }
17    st.push(m);
18    return st;
19}
20
21int main() {
22    int n;
23    cin >> n;
24    stack<int> bin;
25    bin = ten2bin(n);
26    while (!bin.empty()) {
27        ____________  // 在此处填入代码
28    }
29    return 0;
30}

下面定义了一个循环队列的类，请补全判断队列是否满的函数，横向上应填写（ ）。

01#include <iostream>
02
03using namespace std;
04
05class circular_queue {
06private:
07    int *arr; // 数组用于存储队列元素
08    int capacity; // 队列容量
09    int front; // 队头指针
10    int rear; // 队尾指针
11
12public:
13    circular_queue(int size) {
14        capacity = size + 1; // 为了避免队列满时与队列空时指针相等的情况，多预留一个空间
15        arr = new int[capacity];
16        front = 0;
17        rear = 0;
18    }
19
20    ~circular_queue() {
21        delete[] arr;
22    }
23
24    bool is_empty() {
25        return front == rear;
26    }
27
28    bool is_full() {
29        ____________  // 在此处填入代码
30    }
31
32    void en_queue(int data) {
33        if (is_full()) {
34            cout << "队列已满，无法入队！" << endl;
35            return -1;
36        }
37        arr[rear] = data;
38        rear = (rear + 1) % capacity;
39        return 1;
40    }
41
42    int de_queue() {
43        if (is_empty()) {
44            cout << "队列为空，无法出队！" << endl;
45            return -1; // 出队失败，返回一个特殊值
46        }
47        int data = arr[front];
48        front = (front + 1) % capacity;
49        return data;
50    }
51};

对 "classmycls" 使用哈夫曼（Huffman）编码，最少需要（ ）比特。

二叉树的（ ）第一个访问的节点是根节点。

一棵 5 层的满二叉树中节点数为（ ）。

在求解最优化问题时，动态规划常常涉及到两个重要性质，即最优子结构和（ ）。

青蛙每次能跳 1 或 2 步，下面代码计算青蛙跳到第 $n$ 步台阶有多少种不同跳法。则下列说法，错误的是（ ）。

01int jump_recur(int n) {
02    if (n == 1) return 1;
03    if (n == 2) return 2;
04    return jump_recur(n - 1) + jump_recur(n - 2);
05}
06
07int jump_dp(int n) {
08    vector<int> dp(n + 1); // 创建一个动态规划数组，用于保存已计算的值
09    // 初始化前两个数
10    dp[1] = 1;
11    dp[2] = 2;
12    // 从第三个数开始计算斐波那契数列
13    for (int i = 3; i <= n; ++i) {
14        dp[i] = dp[i - 1] + dp[i - 2];
15    }
16    return dp[n];
17}

阅读以下二叉树的广度优先搜索代码：

01#include <iostream>
02#include <queue>
03
04using namespace std;
05
06// 二叉树节点的定义
07struct TreeNode {
08    int val;
09    TreeNode* left;
10    TreeNode* right;
11    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
12};
13
14// 宽度优先搜索 (BFS) 迭代实现
15TreeNode* bfs(TreeNode* root, int a) {
16    if (root == nullptr) return nullptr;
17
18    queue<TreeNode*> q;
19    q.push(root);
20
21    while (!q.empty()) {
22        TreeNode* node = q.front();
23        q.pop();
24
25        if (node->val == a)
26            return node;
27
28        cout << node->val << " "; // 先访问当前节点
29
30        if (node->left) q.push(node->left); // 将左子节点入队
31        if (node->right) q.push(node->right); // 将右子节点入队
32    }
33    return nullptr;
34}

使用以上算法，在以下这棵树搜索数值 20 时，可能的输出是（ ）。

阅读以下二叉树的深度优先搜索代码：

01#include <iostream>
02#include <stack>
03
04using namespace std;
05
06// 非递归深度优先搜索 (DFS)
07TreeNode* dfs(TreeNode* root, int a) {
08    if (root == nullptr) return nullptr;
09
10    stack<TreeNode*> stk;
11    stk.push(root);
12
13    while (!stk.empty()) {
14        TreeNode* node = stk.top();
15        stk.pop();
16        if (node->val == a)
17            return node;
18
19        cout << node->val << " "; // 访问当前节点
20
21        if (node->right) stk.push(node->right); // 先压入右子节点
22        if (node->left) stk.push(node->left); // 再压入左子节点
23    }
24    return nullptr;
25}

使用以上算法，在二叉树搜索数值 20 时，可能的输出是（ ）。

使用非递归深度优先搜索在上图二叉树中搜索数值 $3$，一共比较的节点数为（ ）。

哈夫曼编码本质上是一种贪心策略。

创建一个对象时，会自动调用该对象所属类的构造函数。如果没有定义构造函数，编译器会自动生成一个默认的构造函数。

定义一个类时，必须手动定义一个析构函数，用于释放对象所占用的资源。

C++ 中类内部可以嵌套定义类。

$000, 001, 011, 010, 110, 111, 101, 100$ 是一组格雷码。

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

完全二叉树可以用数组存储数据。

在 C++ 中，静态成员函数只能访问静态成员变量。

在深度优先搜索中，通常使用队列来辅助实现。

对 $0$-$1$ 背包问题，贪心算法一定能获得最优解。