1.
下列哪一项不是面向对象编程的基本特征？
2.
为了让 Dog 类的构造函数能正确地调用其父类 Animal 的构造方法，横线线处应填入（ ）。
3.
横线处填入代码Animal(name)，C++代码执行结果是（ ）。
4.
以下关于栈和队列的C++代码，执行后输出是（ ）。
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;
5.
在一个循环队列中， front 是指向队头的指针， rear 指向队尾的指针，队列最大容量为 maxSize 。判断 队列已满的条件是（ ）。
6.
（ ）只有最底层的节点未被填满，且最底层节点尽量靠左填充。
7.
在使用数组表示完全二叉树时，如果一个节点的索引为 （从 开始计数），那么其左子节点的索引通常是（ ）。
8.
已知一棵二叉树的前序遍历序列为 GDAFEMHZ ，中序遍历序列为 ADFGEHMZ ，则其后序遍历序列为（ ）。
9.
设有字符集 {a, b, c, d, e}，其出现频率分别为 {5, 8, 12, 15, 20}，得到的哈夫曼编码为（ ）。
10.
3位格雷编码中，编码 101 之后的下一个编码不可能是（ ）。
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;
_________
}
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;
}
13.
下面C++代码实现一个二叉排序树的插入函数（没有相同的数值），横线处应填入（ ）。
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;
}
_______________________________}
14.
以下关于动态规划算法特性的描述，正确的是（ ）。
15.
给定 n 个物品和一个最大承重为w 的背包，每个物品有一个重量 wt[i]和价值val[i] ，每个物品只能选择放或 不放。目标是选择若干个物品放入背包，使得总价值最大，且总重量不超过 w。关于下面c++代码，说法正确的是（ ）。
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];
}
1.
构造函数可以被声明为 virtual。
2.
给定一组字符及其出现的频率，构造出的哈夫曼树是唯一的。
3.
为了实现一个队列，使其出队操作（ pop ）的时间复杂度为 O(1)并且避免数组删除首元素的 问题，一 种常见且有效的方法是使用环形数组，通过调整队首和队尾指针来实现。
4.
对一棵二叉排序树进行中序遍历，可以得到一个递增的有序序列。
5.
如果二叉搜索树在连续的插入和删除操作后，所有节点都偏向一侧，导致其退化为类似于链表的结构，这时 其查找、插入、删除操作的时间复杂度会从理想情况下的 O(log n)退化到 O(n log n )。
6.
执行下列C++代码， 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;
}
7.
下列 C++ 代码可以成功编译，并且子类 Child 的实例能通过其成员函数访问父类 Parent 的属性 value 。
class Parent {
private:
int value = 100;
};
class Child : public Parent {
public:
int get_private_val() {
return value; // 尝试访问父类的私有成员
}
};
8.
下列C++代码中的 tree 向量，表示的是一棵完全二叉树 ( -1 代表空节点)按照层序遍历的结果。
#include <vector>
std::vector<int> tree = {1, 2, 3, 4, -1, 6, 7};
9.
在树的深度优先搜索（DFS）中，使用栈作为辅助数据结构以实现“先进后出”的访问顺序。
10.
下面C++代码采用动态规划求解零钱兑换问题：给定 种硬币，第 𝑖 种硬币的面值为 𝑐𝑜𝑖𝑛𝑠[𝑖 − 1] ，目标金额为 𝑎𝑚𝑡 ，每种硬币可以重复选取，求能够凑出目标金额的最少硬币数量；如果不能凑出目标金额，返回 -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;
}
1.
试题名称：学习小组
时间限制：1.0 s
内存限制：512.0 MB
3.1.1 题目描述
班主任计划将班级里的 n名同学划分为若干个学习小组，每名同学都需要分入某一个学习小组中。观察发现，如果一个学习小组中恰好包含 k名同学，则该学习小组的讨论积极度为 ak。
给定讨论积极度 a1,a2....an，请你计算将这 n名同学划分为学习小组的所有可能方案中，讨论积极度之和的最大值。
3.1.2 输入格式
第一行，一个正整数 ，表示班级人数。
第二行，n 个非负整数a1,a2....an ，表示不同人数学习小组的讨论积极度。
3.1.3 输出格式
输出共一行，一个整数，表示所有划分方案中，学习小组讨论积极度之和的最大值。
3.1.4 样例
3.1.4.1 输入样例 1
4
1 5 6 3
3.1.4.2 输出样例 1
10
3.1.4.3 输入样例 2
8
0 2 5 6 4 3 3 4
3.1.4.4 输出样例 2
12
3.1.5 数据范围
2.
试题名称：最大因数
时间限制：1.0 s
内存限制：512.0 MB
3.2.1 题目描述
给定一棵有 109个结点的有根树，这些结点依次以1,2,....109 编号，根结点的编号为 1。对于编号为 k（2<=k<=109）的结点，其父结点的编号为 k的因数中除 k以外最大的因数。
现在有 q组询问，第 i（1<=i<=q ）组询问给定xi,yi ，请你求出编号分别为 xi,yi 的两个结点在这棵树上的距离。
两个结点之间的距离是连接这两个结点的简单路径所包含的边数。
3.2.2 输入格式
第一行，一个正整数 q，表示询问组数。
接下来 q行，每行两个正整数 xi,yi ，表示询问结点的编号。
3.2.3 输出格式
输出共 q 行，每行一个整数，表示结点 xi,yi 之间的距离。
3.2.4 样例
3.2.4.1 输入样例 1
3
1 3
2 5
4 8
3.2.4.2 输出样例 1
1
2
1
3.2.4.3 输入样例 2
1
120
650
3.2.4.4 输出样例 2
9
3.2.5 数据范围
