一、单选题（每题 2 分，共 30 分）

1. 面向对象编程（$\tt OOP$）是一种特殊的程序设计方法。下面（ ）不是重要的 $\tt OOP$ 特性。

{{ select(1) }}

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

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

{{ select(2) }}

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

3. 以下 $\tt 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) }}

• $\tt NULL$ 在 $\tt C$++ 中无法用于指针初始化，应使用 $\tt nullptr$
• $\tt obj$ 的定义应该是 MyClass obj; 而不是指针类型
• obj->display() 语句存在空指针访问错误，$\tt obj$ 应该初始化为一个有效的对象
• obj->display() 语句会调用 $\tt 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^3)$

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

{{ select(6) }}

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

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

   字符	频率
   A	8
   B	3
   C	1
   D	6

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

{{ select(7) }}

•   ABCD
    / \
   A  BCD
      / \
     D  BC
        / \
       B   C
  

•   ABCD
    / \
   A  BCD
      / \
     B  CD
        / \
       C   D
  

•   ABCD
    / \
   D  ABC
      / \
     A  BC
        / \
       B   C
  

•   ABCD
    / \
   C  ABD
      / \
     B  AD
        / \
       A   D
  

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

{{ select(8) }}

• $\tt A: 0,\ B: 10,\ C: 110,\ D: 111$
• $\tt A: 0,\ B: 10,\ C: 11,\ D: 10$
• $\tt A: 0,\ B: 110,\ C: 111,\ D: 10$
• $\tt 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) 时，输出的结果是（ ）。

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

{{ 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. 使用上题中的宽度优先搜索算法遍历以下这棵树，可能的输出是（ ）。

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

{{ select(13) }}

• 1 2 8 9 4 5 3 6 7
• 1 2 3 4 5 6 7 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 = 8\ \tt kg$，共有 $4$ 个物品可供选择，$4$ 个物品的重量分别为 $\tt weights = [2, 3, 5, 7]$，对应的价值分别为 $\tt values = [30, 40, 60, 80]$，则该 $0/1$ 背包问题中，背包的最大价值为（ ）。

{{ select(15) }}

• $70$
• $90$
• $100$
• $120$

二、判断题（每题 2 分，共 20 分）

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

{{ select(16) }}

• 正确
• 错误

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

{{ select(17) }}

• 正确
• 错误

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

{{ select(18) }}

• 正确
• 错误

4. 下面代码构建的树一定是完全二叉树。（ ）

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

{{ select(19) }}

• 正确
• 错误

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

{{ select(20) }}

• 正确
• 错误

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

{{ select(21) }}

• 正确
• 错误

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

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

{{ select(22) }}

• 正确
• 错误

8. 宽度优先搜索算法（$\tt BFS$）保证了每个节点在最短路径的情况下被访问。（ ）

{{ select(23) }}

• 正确
• 错误

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

   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$ 开始。（ ）

{{ select(24) }}

• 正确
• 错误

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

{{ select(25) }}

• 正确
• 错误