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

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

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

{{ select(1) }}

• 抽象
• 封装
• 继承
• 模块化

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

{{ select(2) }}

• 类中定义的所有成员变量和成员函数默认是public访问权限。
• 类的构造函数必须显式声明返回类型为void。
• 在C++中，类的数据一般设置为私有，其公有成员函数提供访问私有数据的唯一途径。
• 同一个类的实例有各自的成员数据和成员函数。

3. 以下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;
}

{{ select(3) }}

• NULL 在C++中无法用于指针初始化，应使用 nullptr。
• obj 的定义应该是 MyClass obj; 而不是指针类型。
• obj->display() 语句存在空指针访问错误，obj 应该初始化为一个有效的对象。
• obj->display() 语句会调用 display() 函数，但它没有输出任何内容。

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

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();
    }
}

{{ select(4) }}

• 栈s的输出顺序是 1 2 3 4 5，队列q的输出顺序是 5 4 3 2 1。
• 栈s的输出顺序是 5 4 3 2 1，队列q的输出顺序是 1 2 3 4 5。
• 栈s的输出顺序是 1 2 3 4 5，队列q的输出顺序是 1 2 3 4 5。
• 栈s的输出顺序是 1 2 3 4 5，队列q的输出顺序是 1 2 3 4 5，程序不会正常执行。

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

{{ select(5) }}

• O(1)
• O(N)
• O(log N)
• O(N³)

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

{{ select(6) }}

• 在一棵二叉树中，叶子结点的度一定是2。
• 满二叉树中每一层的结点数等于 O^(2(层数-1))。
• 在一棵树中，所有结点的度之和等于所有叶子结点的度之和。
• 一棵二叉树的先序遍历结果和中序遍历结果一定相同。

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

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

{{ select(7) }}

• 
• 
• 
• 

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

{{ select(8) }}

• A: 0, B: 10, C: 110, D: 111
• A: 0, B: 10, C: 11, D: 10
• A: 0, B: 101, C: 100, D: 11
• A: 11, B: 10, C: 01, D: 00

9. (  )是3位格雷编码。

{{ select(9) }}

• 000 001 011 010 110 111 101 100
• 000 001 010 011 100 101 110 111
• 000 001 100 101 011 010 111 110
• 000 010 001 011 100 110 101 111

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

#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) 时，输出的结果是（  ）。

{{ select(10) }}

• 5 3 7
• 5 7
• 2 3 4 5 6 7
• 8 7

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

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);
    }
}

{{ select(11) }}

• TreeNode* node = s.top();
• TreeNode* node = s.top(); s.pop();
• TreeNode* node = s.front();
• TreeNode* node = s.front(); s.pop();

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

#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);
        }
    }
}

{{ select(12) }}

• TreeNode* node = q.top();
• TreeNode* node = q.top(); q.pop();
• TreeNode* node = q.front();
• TreeNode* node = q.front(); q.pop();

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

{{ select(13) }}

• 1 2 8 9 4 5 3 6 7
• 1 2 3 4 5 6 6 8 9
• 1 2 3 8 9 6 4 5 7
• 8 4 5 9 2 1 3 6 7

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

{{ select(14) }}

• 动态规划适用于没有重叠子问题的优化问题。
• 动态规划要求问题具有最优子结构和无后效性。
• 动态规划通常通过递归来实现。
• 动态规划与贪心算法不同，贪心算法不适用于有重叠子问题的问题。

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

{{ select(15) }}

• 70
• 90
• 100
• 120