GESP C++ 六 级 2024年6月真题（180 分钟，总分 100 分）

单选题（共 15 题，每题 2 分，共 30 分）

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

{{ select(1) }}

• 贪心、动态规划、回溯
• 并发、并行、异步
• 递归、循环、分治
• 封装、继承、多态

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

#include <iostream>
using namespace std;
class my_class
{
public:
    static int count;
    my_class()
    {
        count++;
    }
    ~my_class()
    {
        count--;
    }
    static void print_count()
    {
        cout << count << " ";
    }
};
int my_class::count = 0;
int main()
{
    my_class obj1;
    my_class::print_count();
    my_class obj2;
    obj2.print_count();
    my_class obj3;
    obj3.print_count();
    return 0;
}

{{ select(2) }}

• 1 1 1
• 1 2 3
• 1 1 2
• 1 2 2

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

#include <iostream>
using namespace std;
class shape
{
protected:
    int width, height;

public:
    shape(int a = 0, int b = 0)
    {
        width = a;
        height = b;
    }
    virtual int area()
    {
        cout << "parent class area: " << endl;
        return 0;
    }
};
class rectangle : public shape
{
public:
    rectangle(int a = 0, int b = 0) : shape(a, b) {}
    int area()
    {
        cout << "rectangle area: ";
        return (width * height);
    }
};
class triangle : public shape
{
public:
    triangle(int a = 0, int b = 0) : shape(a, b) {}
    int area()
    {
        cout << "triangle area: ";
        return (width * height / 2);
    }
};
int main()
{
    shape *pshape;
    rectangle rec(10, 7);
    triangle tri(10, 5);
    pshape = &rec;
    pshape->area();
    pshape = &tri;
    pshape->area();
    return 0;
}

{{ select(3) }}

• rectangle area: triangle area:
• parent class area: parent class area:
• 运行时报错
• 编译时报错

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

{{ select(4) }}

• hs->next = s;
• s->next = hs; hs = s;
• s->next = hs->next; hs->next = s;
• s->next = hs; hs = hs->next;

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

{{ select(5) }}

• 先进先出
• 先进后出
• 最小值先出
• 随机顺序

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

#include <iostream>
using namespace std;
stack<int> ten2bin(int n)
{
    stack<int> st;
    int r, m;
    r = n % 2;
    m = n / 2;
    st.push(r);
    while (m != 1)
    {
        r = m % 2;
        st.push(r);
        m = m / 2;
    }
    st.push(m);
    return st;
}
int main()
{
    int n;
    cin >> n;
    stack<int> bin;
    bin = ten2bin(n);
    while (!bin.empty())
    {
        _____________________ // 在此处填入代码
    }
    return 0;
}

{{ select(6) }}

• cout << bin.top(); bin.pop();
• bin.pop(); cout << bin.top();
• cout << bin.back(); bin.pop();
• cout << bin.front(); bin.pop();

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

#include <iostream>
using namespace std;
class circular_queue
{
private:
    int *arr;     // 数组用于存储队列元素
    int capacity; // 队列容量
    int front;    // 队头指针
    int rear;     // 队尾指针
public:
    circular_queue(int size)
    {
        capacity = size + 1; // 为了避免队列满时与队列空时指针相等的情况，多预留一个空间
        arr = new int[capacity];
        front = 0;
        rear = 0;
    }
    ~circular_queue()
    {
        delete[] arr;
    }
    bool is_empty()
    {
        return front == rear;
    }
    bool is_full()
    {
        ________________ // 在此处填入代码
    }
    int en_queue(int data)
    {
        if (is_full())
        {
            cout << "队列已满，无法入队！" << endl;
            return -1;
        }
        arr[rear] = data;
        rear = (rear + 1) % capacity;
        return 1;
    }
    int de_queue()
    {
        if (is_empty())
        {
            cout << "队列为空，无法出队！" << endl;
            return -1; // 出队失败，返回一个特殊值
        }
        int data = arr[front];
        front = (front + 1) % capacity;
        return data;
    }
};

{{ select(7) }}

• return (rear + 1) % capacity == front;
• return rear % capacity == front;
• return rear == front;
• return (rear + 1) == front;

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

{{ select(8) }}

• 10
• 20
• 25
• 30

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

{{ select(9) }}

• 先序遍历
• 中序遍历
• 后序遍历
• 以上都是

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

{{ select(10) }}

• 31
• 32
• 33
• 16

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

{{ select(11) }}

• 重叠子问题
• 分治法
• 贪心策略
• 回溯算法

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

int jump_recur(int n)
{
    if (n == 1)
        return 1;
    if (n == 2)
        return 2;
    return jump_recur(n - 1) + jump_recur(n - 2);
}
int jump_dp(int n)
{
    vector<int> dp(n + 1); // 创建一个动态规划数组，用于保存已计算的值
    // 初始化前两个数
    dp[1] = 1;
    dp[2] = 2;
    // 从第三个数开始计算斐波那契数列
    for (int i = 3; i <= n; ++i)
    {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[n];
}

{{ select(12) }}

• 函数jump_recur()采用递归方式。
• 函数jump_dp()采用动态规划方法。
• 当n较大时，函数jump_recur()存在大量重复计算，执行效率低。
• 函数jump_recur()代码量小，执行效率高。

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

#include <iostream>
#include <queue>
using namespace std;
// 二叉树节点的定义
struct TreeNode
{
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
// 宽度优先搜索（BFS）迭代实现
TreeNode *bfs(TreeNode *root, int a)
{
    if (root == nullptr)
        return nullptr;
    queue<TreeNode *> q;
    q.push(root);
    while (!q.empty())
    {
        TreeNode *node = q.front();
        q.pop();
        if (node->val == a)
            return node;
        cout << node->val << " "; // 先访问当前节点
        if (node->left)
            q.push(node->left); // 将左子节点入队
        if (node->right)
            q.push(node->right); // 将右子节点入队
    }
    return nullptr;
}

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

{{ select(13) }}

• 5 2 -4 3 17 9
• -4 2 3 5 9 17
• 5 2 17 -4 3 9
• 以上都不对

14. 同上题中的二叉树，阅读以下二叉树的深度优先搜索代码:

#include <iostream>
#include <stack>
using namespace std;
// 非递归深度优先搜索（DFS）
TreeNode *dfs(TreeNode *root, int a)
{
    if (root == nullptr)
        return nullptr;
    stack<TreeNode *> stk;
    stk.push(root);
    while (!stk.empty())
    {
        TreeNode *node = stk.top();
        stk.pop();
        if (node->val == a)
            return node;
        cout << node->val << " "; // 访问当前节点
        if (node->right)
            stk.push(node->right); // 先压入右子节点
        if (node->left)
            stk.push(node->left); // 再压入左子节点
    }
    return nullptr;
}

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

{{ select(14) }}

• 5 2 -4 3 17 9
• -4 2 3 5 9 17
• 5 2 17 -4 3 9
• 以上都不对

15. 在上题的树中搜索数值3时，采用深度优先搜索一共比较的节点数为（  ）。

{{ select(15) }}

• 2
• 3
• 4
• 5