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

第 1 题 下列哪一项不是面向对象编程的基本特征？

{{ select(1) }}

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

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

{{ 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 题 在使用数组表示完全二叉树时，如果一个节点的索引为 （从 开始计数），那么其左子节点的索引通常是（ ）。

{{ select(7) }}

• (i - 1)/2
• i + 1
• i * 2
• 2 * i + 1

第 8 题 已知一棵二叉树的前序遍历序列为 GDAFEMHZ ，中序遍历序列为 ADFGEHMZ ，则其后序遍历序列为（ ）。

{{ select(8) }}

• ADFGEHMZ
• ADFGHMEZ
• AFDGEMZH
• AFDHZMEG

第 9 题 设有字符集 {a, b, c, d, e}，其出现频率分别为 {5, 8, 12, 15, 20}，得到的哈夫曼编码为（ ）。

{{ select(9) }}

• 
• 
• 
• 

第 10 题 3位格雷编码中，编码 101 之后的下一个编码不可能是（ ）。

{{ select(10) }}

• 100
• 111
• 110
• 001

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

{{ select(11) }}

• 
• 
• 
• 

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

{{ select(12) }}

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

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

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

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

{{ select(13) }}

• 
• 
• 
• 

第 14 题 以下关于动态规划算法特性的描述，正确的是（ ）。

{{ select(14) }}

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

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

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 是为了避免重复使用同一物品
• 这段代码计算的是最小重量而非最大价值

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

第 1 题 构造函数可以被声明为 virtual。

{{ select(16) }}

• 正确√
• 错误×

第 2 题 给定一组字符及其出现的频率，构造出的哈夫曼树是唯一的。

{{ select(17) }}

• 正确√
• 错误×

第 3 题 为了实现一个队列，使其出队操作（ pop ）的时间复杂度为并且避免数组删除首元素的$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 题 下面代码采用动态规划求解零钱兑换问题：给定 种硬币，第 𝑖 种硬币的面值为 𝑐𝑜𝑖𝑛𝑠[𝑖 − 1] ，目标金额为𝑎𝑚𝑡 ，每种硬币可以重复选取，求能够凑出目标金额的最少硬币数量；如果不能凑出目标金额，返回 -1 。

{{ select(25) }}

• 正确√
• 错误×