单选题

1. 下列哪一项不是面向对象编程的基本特征？{{ select(1) }}

• 继承
• 封装
• 多态
• 链接

2. 为了让 Dog 类的构造函数能正确地调用其父类 Animal 的构造方法，横线线处应填入

   class Animal {
       public:
       std::string name;
       Animal(std::string str) : name(str) {
           std::cout << "Animal created\n";
       }
       virtual void speak() {
           cout << "Animal speaks" << endl;
       }
   };
   class Dog : public Animal {
       std::string breed;
       public:
           Dog(std::string name, std::string b) : _________________, breed(b) {
               std::cout << "Dog created\n";
           }
           void speak() override {
               cout << "Dog barks" << endl;
           }
   };
   int main() {
       Animal* p = new Dog("Rex", "Labrador");
       p->speak();
       delete p;
       return 0;
   }
   

   {{ select(2) }}

   • Animal(name)
   • super(name)
   • Animal::Animal(name)
   • Animal()

3. 代码同上一题，代码执行结果是 {{ select(3) }}

• 输出 Animal speaks
• 输出 Dog barks
• 编译错误
• 程序崩溃

4. 以下关于栈和队列的代码，执行后输出是

   stack<int> s;
   queue<int> q;
   for (int i = 1; i <= 3; ++i) {
       s.push(i);
       q.push(i);
   }
   cout << s.top() << " " << q.front() << endl;
   

   {{ select(4) }}

   • 1 3
   • 3 1
   • 3 3
   • 1 1

5. 在一个循环队列中，front 是指向队头的指针， rear 指向队尾的指针，队列最大容量为 maxSize。判断队列已满的条件是 {{ select(5) }}

• rear == front
• (rear + 1) % maxSize == front
• (rear - 1 + maxSize) % maxSize == front
• (rear - 1) == front

6. 只有最底层的节点未被填满，且最底层节点尽量靠左填充。{{ select(6) }}

• 完美二叉树
• 完全二叉树
• 完满二叉树
• 平衡二叉树

7. 在使用数组表示完全二叉树时，如果一个节点的索引为 $i$（从 $0$ 开始计数），那么其左子节点的索引通常是 {{ select(7) }}

• $(i-1)/2$
• $i+1$
• $i\times 2$
• $i\times 2 + 1$

8. 已知一棵二叉树的前序遍历序列为 GDAFEMHZ，中序遍历序列为 ADFGEHMZ，则其后序遍历序列为 {{ select(8) }}

• ADFGEHMZ
• ADFGHMEZ
• AFDGEMZH
• AFDHZMEG

9. 设有字符集 $\{a, b, c, d, e\}$，其出现频率分别为 $\{5, 8, 12, 15, 20\}$，得到的哈夫曼编码为 {{ select(9) }}

• a: 010
  b: 011
  c: 00
  d: 10
  e: 11
  

• a: 00
  b: 10
  c: 011
  d: 100
  e: 111
  

• a: 10
  b: 01
  c: 011
  d: 100
  e: 111
  

• a: 100
  b: 01
  c: 011
  d: 100
  e: 00
  

10. $3$ 位格雷编码中，编码 101 之后的下一个编码不可能是 {{ select(10) }}

• 100
• 111
• 110
• 001

11. 请将下列 C++ 实现的深度优先搜索（DFS）代码补充完整，横线处应填入。

    struct TreeNode {
        int val;
        TreeNode* left;
        TreeNode* right;
        TreeNode(int x): val(x), left(nullptr), right(nullptr) {}
    };
    void dfs(TreeNode* root, vector<int>& result) {
        if (root == nullptr) return;
        __________________________
    }
    

    {{ select(11) }}

    • result.push_back(root->val);
      dfs(root->left);
      dfs(root->right);
      

    • result.push_back(root->left->val);
      dfs(root->right);
      dfs(root->left);
      

    • result.push_back(root->left->val);
      dfs(root->left);
      dfs(root->right);
      

    • result.push_back(root->right->val);
      dfs(root->right);
      dfs(root->left);
      

12. 给定一个二叉树，返回每一层中最大的节点值，结果以数组形式返回，横线处应填入

    #include <vector>
    #include <queue>
    #include <algorithm>
    struct TreeNode {
        int val;
        TreeNode* left;
        TreeNode* right;
        TreeNode(int x): val(x), left(nullptr), right(nullptr) {}
    };
    vector<int> largestValues(TreeNode* root) {
        vector<int> result;
        if (!root) return result;
        queue<TreeNode*> q;
        q.push(root);
        while (!q.empty()) {
            int sz = q.size();
            int maxVal = INT_MIN;
            for (int i = 0; i < sz; ++i) {
                TreeNode* node;
                _______________________________
                maxVal = max(maxVal, node->val);
                if (node->left) q.push(node->left);
                if (node->right) q.push(node->right);
            }
            result.push_back(maxVal);
        }
        return result;
    }
    

    {{ select(12) }}

    • node = q.end();
    • node = q.front();
    • q.pop(); node = q.front();
    • node = q.front(); q.pop();

13. 下面代码实现一个二叉排序树的插入函数（没有相同的数值），横线处应填入

    struct TreeNode {
        int val;
        TreeNode* left;
        TreeNode* right;
        TreeNode(int x): val(x), left(nullptr), right(nullptr) {}
    };
    void insert(TreeNode*& root, int key) {
        if (!root) {
            root = new TreeNode(key);
            return;
        }
        _______________________________
    }
    

    {{ select(13) }}

    • if (key < root->val)
          insert(root->left, key);
      else if (key > root->val)
          insert(root->right, key);
      

    • if (key < root->val)
          insert(root->right, key);
      else if (key > root->val)
          insert(root->left, key);
      

    • insert(root->left, key);
      insert(root->right, key);
      

    • insert(root->right, key);
      insert(root->left, key);
      

14. 以下关于动态规划算法特性的描述，正确的是 {{ select(14) }}

• 子问题相互独立，不重叠
• 问题包含重叠子问题和最优子结构
• 只能从底至顶迭代求解
• 必须使用递归实现，不能使用迭代

15. 给定 $n$ 个物品和一个最大承重为 $W$ 的背包，每个物品有一个重量 $wt[i]$ 和价值 $val[i]$，每个物品只能选择放或不放。目标是选择若干个物品放入背包，使得总价值最大，且总重量不超过 $W$。关于下面代码，说法正确的是

    int knapsack1D (int W, vector<int>& wt, vector<int>& val, int n) {
        vector<int> dp(W+1, 0);
        for (int i = 0; i < n; ++i) {
            for (int w = W; w >= wt[i]; --w) {
                dp[w] = max(dp[w], dp[w - wt[i]] + val[i]);
            }
        }
        return dp[W];
    }
    

    {{ select(15) }}

    • 该算法不能处理背包容量为 $0$ 的情况
    • 外层循环 $i$ 遍历背包容量，内层遍历物品
    • 从大到小遍历 $w$ 是为了避免重复使用同一物品
    • 这段代码计算的是最小重量而非最大价值

判断题

1. 构造函数可以被声明为 virtual。{{ select(16) }}

• 对
• 错

2. 给定一组字符及其出现的频率，构造出的哈夫曼树是唯一的。{{ select(17) }}

• 对
• 错

3. 为了实现一个队列，使其出队操作（pop）的时间复杂度为 $O(1)$ 并且避免数组删除首元素的 $O(n)$ 问题，一种常见且有效的方法是使用环形数组，通过调整队首和队尾指针来实现。{{ select(18) }}

• 对
• 错

4. 对一棵二叉排序树进行中序遍历，可以得到一个递增的有序序列。{{ select(19) }}

• 对
• 错

5. 如果二叉搜索树在连续的插入和删除操作后，所有节点都偏向一侧，导致其退化为类似于链表的结构，这时其查找、插入、删除操作的时间复杂度会从理想情况下的 $O(logn)$ 退化到 $O(nlogn)$。{{ select(20) }}

• 对
• 错

6. 执行下列代码，my_dog.name 的最终值是 Charlie。

   class Dog {
       public:
           std::string name;
           Dog(std::string str) : name(str) {}
   };
   int main() {
       Dog my_dog("Buddy");
       my_dog.name = "Charlie";
       return 0;
   }
   

   {{ select(21) }}

   • 对
   • 错

7. 下列 C++ 代码可以成功编译，并且子类 Child 的实例能通过其成员函数访问父类 Parent 的属性 value。

   class Parent {
       private:
           int value = 100;
   };
   class Child : public Parent {
       public:
           int get_private_val() {
               return value; // 尝试访问父类的私有成员
           }
   };
   

   {{ select(22) }}

   • 对
   • 错

8. 下列代码中的 tree 向量，表示的是一棵完全二叉树（$-1$ 代表空节点）按照层序遍历的结果。

   #include <vector>
   std::vector<int> tree = {1, 2, 3, 4, -1, 6, 7};
   

   {{ select(23) }}

   • 对
   • 错

9. 在树的深度优先搜索（DFS）中，使用栈作为辅助数据结构以实现“先进后出”的访问顺序。{{ select(24) }}

• 对
• 错

10. 下面代码采用动态规划求解零钱兑换问题：给定 $n$ 种硬币，第 $i$ 种硬币的面值为 $coins[i − 1]$，目标金额为 $amt$，每种硬币可以重复选取，求能够凑出目标金额的最少硬币数量；如果不能凑出目标金额，返回 $-1$。

    int coinChangeDPComp(vector<int> &coins, int amt) {
        int n = coins.size();
        int MAX = amt + 1;
        vector<int> dp(amt + 1, MAX);
        dp[0] = 0;
        for (int i = 1; i <= n; i++) {
            for (int a = 1; a <= amt; a++) {
                if (coins[i - 1] > a)
                    dp[a] = dp[a];
                else
                    dp[a] = min(dp[a], dp[a - coins[i - 1]] + 1);
            }
        }
        return dp[amt] != MAX ? dp[amt] : -1;
    }
    

    {{ select(25) }}

    • 对
    • 错