5316：[GESP202506六级] 客观题
文件提交：无需freopen
内存限制：128 MB
时间限制：1.000 S
评测方式：文本裁判
金币值：
命题人：
提交：0
解决：0
题目描述
## 一、单选题（每题 2 分，共 30 分）
**第 1 题** 下列哪一项不是面向对象编程的基本特征？()
- 继承
- 封装
- 多态
- 链接
**第 2 题** 为了让 `Dog` 类的构造函数能正确地调用其父类 `Animal` 的构造方法，横线线处应填入()
```cpp
01 class Animal {
02 public:
03 std::string name;
04
05 Animal(std::string str) : name(str) {
06 std::cout << "Animal created\n";
07 }
08 virtual void speak() {
09 cout << "Animal speaks" << endl;
10 }
11 };
12
13 class Dog : public Animal {
14 std::string breed;
15 public:
16 Dog(std::string name, std::string b) : _________________, breed(b) {
17 std::cout << "Dog created\n";
18 }
19 void speak() override {
20 cout << "Dog barks" << endl;
21 }
22 };
23
24 int main() {
25 Animal* p = new Dog("Rex", "Labrador");
26 p->speak();
27 delete p;
28 return 0;
29 }
```
- `Animal(name)`
- `super(name)`
- `Animal::Animal(name)`
- `Animal()`
**第 3 题** 代码同上一题，代码执行结果是( )
- 输出 `Animal speaks`
- 输出 `Dog barks`
- 编译错误
- 程序崩溃
**第 4 题** 以下关于栈和队列的代码，执行后输出是()
```cpp
01 stack s;
02 queue q;
03
04 for (int i = 1; i <= 3; ++i) {
05 s.push(i);
06 q.push(i);
07 }
08 cout << s.top() << " " << q.front() << endl;
```
- `1 3`
- `3 1`
- `3 3`
- `1 1`
**第 5 题** 在一个循环队列中，$front$ 是指向队头的指针，$rear$ 指向队尾的指针，队列最大容量为 $maxSize$。判断队列已满的条件是()
- `rear == front`
- `(rear + 1) % maxSize == front`
- `(rear - 1 + maxSize) % maxSize == front`
- `(rear - 1) == front`
**第 6 题** ()只有最底层的节点未被填满，且最底层节点尽量靠左填充。
- 完美二叉树
- 完全二叉树
- 完满二叉树
- 平衡二叉树
**第 7 题** 在使用数组表示完全二叉树时，如果一个节点的索引为 $i$ (从 $0$ 开始计数），那么其左子节点的索引通常是()
- $\frac{i-1}{2}$
- $i+1$
- $i \times 2$
- $2 \times i + 1$
**第 8 题** 已知一棵二叉树的前序遍历序列为 `GDAFEMHZ`，中序遍历序列为 `ADFGEHMZ`，则其后序遍历序列为()
- `ADFGEHMZ`
- `ADFGHMEZ`
- `AFDGEMZH`
- `AFDHZMEG`
**第 9 题** 设有字符集 `{a, b, c, d, e}`，其出现频率分别为 `{5, 8, 12, 15, 20}`，得到的哈夫曼编码为()
- ```cpp
01 a: 010
02 b: 011
03 c: 00
04 d: 10
05 e: 11
```
- ```cpp
01 a: 00
02 b: 10
03 c: 011
04 d: 100
05 e: 111
```
- ```cpp
01 a: 10
02 b: 01
03 c: 011
04 d: 100
05 e: 111
```
- ```cpp
01 a: 100
02 b: 01
03 c: 011
04 d: 100
05 e: 00
```
**第 10 题** $3$ 位格雷编码中，编码 $101$ 之后的下一个编码不可能是()
- $100$
- $111$
- $110$
- $001$
**第 11 题** 请将下列 `C++` 实现的深度优先搜索 $(DFS)$ 代码补充完整，横线处应填入()
```cpp
01 struct TreeNode {
02 int val;
03 TreeNode* left;
04 TreeNode* right;
05 TreeNode(int x): val(x), left(nullptr), right(nullptr) {}
06 };
07
08 void dfs(TreeNode* root, vector& result) {
09 if (root == nullptr) return;
10
11 __________________________
12 }
```
- ```cpp
01 result.push_back(root->val);
02 dfs(root->left);
03 dfs(root->right);
```
- ```cpp
01 result.push_back(root->left->val);
02 dfs(root->right);
03 dfs(root->left);
```
- ```cpp
01 result.push_back(root->left->val);
02 dfs(root->left);
03 dfs(root->right);
```
- ```cpp
01 result.push_back(root->right->val);
02 dfs(root->right);
03 dfs(root->left);
```
**第 12 题** 给定一个二叉树，返回每一层中最大的节点值，结果以数组形式返回，横线处应填入()
```cpp
01 #include
02 #include
03 #include
04
05 struct TreeNode {
06 int val;
07 TreeNode* left;
08 TreeNode* right;
09 TreeNode(int x): val(x), left(nullptr), right(nullptr) {}
10 };
11
12 vector largestValues(TreeNode* root) {
13 vector result;
14 if (!root) return result;
15
16 queue q;
17 q.push(root);
18
19 while (!q.empty()) {
20 int sz = q.size();
21 int maxVal = INT_MIN;
22 for (int i = 0; i < sz; ++i) {
23 TreeNode* node;
24 ___________________________
25 maxVal = max(maxVal, node->val);
26 if (node->left) q.push(node->left);
27 if (node->right) q.push(node->right);
28 }
29 result.push_back(maxVal);
30 }
31
32 return result;
33 }
```
- ```cpp
01 node = q.end();
```
- ```cpp
02 node = q.front();
```
- ```cpp
01 q.pop();
02 node = q.front();
```
- ```cpp
01 node = q.front();
02 q.pop();
```
**第 13 题** 下面代码实现一个二叉排序树的插入函数 (没有相同的数值），横线处应填入()
```cpp
01 struct TreeNode {
02 int val;
03 TreeNode* left;
04 TreeNode* right;
05 TreeNode(int x): val(x), left(nullptr), right(nullptr) {}
06 };
07
08 void insert(TreeNode*& root, int key) {
09 if (!root) {
10 root = new TreeNode(key);
11 return;
12 }
13 _______________________________
14 }
```
- ```cpp
01 if (key < root->val)
02 insert(root->left, key);
03 else if (key > root->val)
04 insert(root->right, key);
```
- ```cpp
01 if (key < root->val)
02 insert(root->right, key);
03 else if (key > root->val)
04 insert(root->left, key);
```
- ```cpp
01 insert(root->left, key);
02 insert(root->right, key);
```
- ```cpp
01 insert(root->right, key);
02 insert(root->left, key);
```
**第 14 题** 以下关于动态规划算法特性的描述，正确的是()
- 子问题相互独立，不重叠
- 问题包含重叠子问题和最优子结构
- 只能从底至顶迭代求解
- 必须使用递归实现，不能使用迭代
**第 15 题** 给定 $n$ 个物品和一个最大承重为 $W$ 的背包，每个物品有一个重量 $wt[i]$ 和价值 $val[i]$，每个物品只能选择放或不放。目标是选择若干个物品放入背包，使得总价值最大，且总重量不超过 $W$。关于下面代码，说法正确的是()
```cpp
01 int knapsack1D(int W, vector& wt, vector& val, int n) {
02 vector dp(W+1, 0);
03 for (int i = 0; i < n; ++i) {
04 for (int w = W; w >= wt[i]; --w) {
05 dp[w] = max(dp[w], dp[w - wt[i]] + val[i]);
06 }
07 }
08 return dp[W];
09 }
```
- 该算法不能处理背包容量为 $0$ 的情况
- 外层循环 $i$ 遍历背包容量，内层遍历物品
- 从大到小遍历 $w$ 是为了避免重复使用同一物品
- 这段代码计算的是最小重量而非最大价值
## 二、判断题（每题 2 分，共 20 分）
**第 1 题** 构造函数可以被声明为 `virtual`。
- 正确
- 错误
**第 2 题** 给定一组字符及其出现的频率，构造出的哈夫曼树是唯一的。
- 正确
- 错误
**第 3 题** 为了实现一个队列，使其出队操作 ($pop$) 的时间复杂度为 $O(1)$ 并且避免数组删除首元素的 $O(n)$ 问题，一种常见且有效的方法是使用环形数组，通过调整队首和队尾指针来实现。
- 正确
- 错误
**第 4 题** 对一棵二叉排序树进行中序遍历，可以得到一个递增的有序序列。（）
- 正确
- 错误
**第 5 题** 如果二叉搜索树在连续的插入和删除操作后，所有节点都偏向一侧，导致其退化为类似于链表的结构，这时其查找、插入、删除操作的时间复杂度会从理想情况下的 $O(logn)$ 退化到 $O(nlogn)$。
- 正确
- 错误
**第 6 题** 执行下列代码，`my_dog.name` 的最终值是 $Charlie$。
```cpp
01 class Dog {
02 public:
03 std::string name;
04 Dog(std::string str) : name(str) {}
05 };
06
07 int main() {
08 Dog my_dog("Buddy");
09 my_dog.name = "Charlie";
10 return 0;
11 }
```
- 正确
- 错误
**第 7 题** 下列 `C++` 代码可以成功编译，并且子类 $Child$ 的实例能通过其成员函数访问父类 $Parent$ 的属性 $value$。
```cpp
01 class Parent {
02 private:
03 int value = 100;
04 };
05 class Child : public Parent {
06 public:
07 int get_private_val() {
08 return value; // 尝试访问父类的私有成员
09 }
10 };
```
- 正确
- 错误
**第 8 题** 下列代码中的 $tree$ 向量，表示的是一棵完全二叉树 ($-1$ 代表空节点) 按照层序遍历的结果。
```cpp
01 #include
02 std::vector tree = {1, 2, 3, 4, -1, 6, 7};
```
- 正确
- 错误
**第 9 题** 在树的深度优先搜索 $(DFS)$ 中，使用栈作为辅助数据结构以实现“先进后出”的访问顺序。
- 正确
- 错误
**第 10 题** 下面代码采用动态规划求解零钱兑换问题：给定 $n$ 种硬币，第 $𝑖$ 种硬币的面值为 $coins[i-1]$，目标金额为 $𝑎𝑚𝑡$，每种硬币可以重复选取，求能够凑出目标金额的最少硬币数量；如果不能凑出目标金额，返回 `-1`。
```cpp
01 int coinChangeDPComp(vector &coins, int amt) {
02 int n = coins.size();
03 int MAX = amt + 1;
04
05 vector dp(amt + 1, MAX);
06 dp[0] = 0;
07
08 for (int i = 1; i <= n; i++) {
09 for (int a = 1; a <= amt; a++) {
10 if (coins[i - 1] > a)
11 dp[a] = dp[a];
12 else
13 dp[a] = min(dp[a], dp[a - coins[i - 1]] + 1);
14 }
15 }
16 return dp[amt] != MAX ? dp[amt] : -1;
17 }
```
- 正确
- 错误