5291：[GESP202509六级] 客观题
文件提交：无需freopen
内存限制：128 MB
时间限制：1.000 S
评测方式：文本裁判
金币值：
命题人：
提交：0
解决：0
题目描述
## 一、单选题（每题 2 分，共 30 分）
**第 1 题** 下列关于类的说法，错误的是 ( )
- 构造函数不能声明为虚函数，但析构函数可以。
- 函数参数如声明为类的引用类型，调用时不会调用该类的复制构造函数。
- 静态方法属于类而不是某个具体对象，因此推荐用 类名::方法(...) 调用。
- 静态方法属于类而不是某个具体对象，因此推荐用 类名::方法(...) 调用。
**第 2 题** 假设变量 `veh` 是类 `Car` 的一个实例，我们可以调用 `veh.move()`，是因为面向对象编程有 ( ) 性质。
```cpp
01 class Vehicle {
02 private:
03 string brand;
04
05 public:
06 Vehicle(string b) : brand(b) {}
07
08 void setBrand(const string& b) { brand = b; }
09 string getBrand() const { return brand; }
10
11 void move() const {
12 cout << brand << " is moving..." << endl;
13 }
14 };
15
16 class Car : public Vehicle {
17 private:
18 int seatCount;
19
20 public:
21 Car(string b, int seats) : Vehicle(b), seatCount(seats) {}
22
23 void showInfo() const {
24 cout << "This car is a " << getBrand()
25 << " with " << seatCount << " seats." << endl;
26 }
27 };
```
- 继承 `(Inheritance)`
- 封装 `(Encapsulation)`
- 多态 `(Polymorphism)`
- 链接 `(Linking)`
**第 3 题** 下面代码中 `v1` 和 `v2` 调用了相同接口 `move()`，但输出结果不同，这体现了面向对象编程的 ( ) 特性
```cpp
01 class Vehicle {
02 private:
03 string brand;
04
05 public:
06 Vehicle(string b) : brand(b) {}
07
08 void setBrand(const string& b) { brand = b; }
09 string getBrand() const { return brand; }
10
11 virtual void move() const {
12 cout << brand << " is moving..." << endl;
13 }
14 };
15
16 class Car : public Vehicle {
17 private:
18 int seatCount;
19
20 public:
21 Car(string b, int seats) : Vehicle(b), seatCount(seats) {}
22
23 void showInfo() const {
24 cout << "This car is a " << getBrand()
25 << " with " << seatCount << " seats." << endl;
26 }
27
28 void move() const override {
29 cout << getBrand() << " car is driving on the road!" << endl;
30 }
31 };
32
33 class Bike : public Vehicle {
34 public:
35 Bike(string b) : Vehicle(b) {}
36
37 void move() const override {
38 cout << getBrand() << " bike is cycling on the path!" << endl;
39 }
40 };
41
42 int main() {
43 Vehicle* v1 = new Car("Toyota", 5);
44 Vehicle* v2 = new Bike("Giant");
45
46 v1->move();
47 v2->move();
48
49 delete v1;
50 delete v2;
51 return 0;
52 }
```
- 继承 (`Inheritance`)
- 封装 (`Encapsulation`)
- 多态 (`Polymorphism`)
- 链接 (`Linking`)
**第 4 题** 栈的操作特点是 ( )
- 先进先出
- 先进后出
- 随机访问
- 双端进出
**第 5 题** 循环队列常用于实现数据缓冲。假设一个循环队列容量为 $5$ (即最多存放 $4$ 个元素，留一个位置区分空与满)，依次进行操作：入队数据 $1，2，3$，出队 $1$ 个数据，再入队数据 $4$ 和 $5$，此时队首到队尾的元素顺序是 ( )
- `[2, 3, 4, 5]`
- `[1, 2, 3, 4]`
- `[3, 4, 5, 2]`
- `[2, 3, 5, 4]`
**第 6 题** 以下函数 `createTree()` 构造的树是什么类型？ ( )
```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 TreeNode* createTree() {
09 TreeNode* root = new TreeNode(1);
10 root->left = new TreeNode(2);
11 root->right = new TreeNode(3);
12 root->left->left = new TreeNode(4);
13 root->left->right = new TreeNode(5);
14 return root;
15 }
```
- 满二叉树
- 完全二叉树
- 二叉排序树
- 其他都不对
**第 7 题** 已知二叉树的 中序遍历是 `[D, B, E, A, F, C]`，先序遍历是 `[A, B, D, E, C, F]`。请问该二叉树的后序遍历结果是( )
- `[D, E, B, F, C, A]`
- `[D, B, E, F, C, A]`
- `[D, E, B, C, F, A]`
- `[B, D, E, F, C, A]`
**第 8 题** 完全二叉树可以用数组连续高效存储，如果节点从 $1$ 开始编号，则对有两个孩子节点的节点 $i$ ( )
- 左孩子位于 $2i$，右孩子位于 $2i+1$
- 完全二叉树的叶子节点可以出现在最后一层的任意位置
- 所有节点都有两个孩子
- 左孩子位于 $2i+1$，右孩子位于 $2i+2$
**第 9 题** 设有字符集 `{a, b, c, d, e, f}`，其出现频率分别为 `{5, 9, 12, 13, 16, 45}`。哈夫曼算法构造最优前缀编码，以下哪一组可能是对应的哈夫曼编码？(非叶子节点左边分支记作 $0$，右边分支记作 $1$，左右互换不影响正确性)。 ( )
- `a: 00；b: 01；c: 10；d: 110；e: 111；f: 0`
- `a: 1100；b: 1101；c: 100；d: 101；e: 111；f: 0`
- `a: 000；b: 001；c: 01；d: 10；e: 110；f: 111`
- `a: 10；b: 01；c: 100；d: 101；e: 111；f: 0`
**第 10 题** 下面代码生成格雷编码，则横线上应填写 ( )
```cpp
01 vector grayCode(int n) {
02 if (n == 0) return {"0"};
03 if (n == 1) return {"0", "1"};
04
05 vector prev = grayCode(n–1);
06 vector result;
07 for (string s : prev) {
08 result.push_back("0" + s);
09 }
10 for (_______________) { // 在此处填写代码
11 result.push_back("1" + prev[i]);
12 }
13 return result;
14 }
```
- `int i = 0; i < prev.size(); i++`
- `int i = prev.size()-1; i >= 0; i--`
- `auto s : prev`
- `int i = prev.size()/2; i < prev.size(); i++`
**第 11 题** 请将下列树的深度优先遍历代码补充完整，横线处应填入 ( )
```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) {
09 if (!root) return;
10 ______ temp; // 在此处填写代码
11 temp.push(root);
12 while (!temp.empty()) {
13 TreeNode* node = temp.top();
14 temp.pop();
15 cout << node–>val << " ";
16 if (node–>right) temp.push(node–>right);
17 if (node–>left) temp.push(node–>left);
18 }
19 }
```
- `vector`
- `list`
- `queue`
- `stack`
**第 12 题** 令 $n$ 是树的节点数目，下列代码实现了树的广度优先遍历，其时间复杂度是( )。
```cpp
01 void bfs(TreeNode* root) {
02 if (!root) return;
03 queue q;
04 q.push(root);
05 while (!q.empty()) {
06 TreeNode* node = q.front();
07 q.pop();
08 cout << node–>val << " ";
09 if (node–>left) q.push(node–>left);
10 if (node–>right) q.push(node–>right);
11 }
12 }
```
- $O(n)$
- $O(logn)$
- $O(n^2)$
- $O(2^n)$
**第 13 题** 在二叉排序树 `(Binary Search Tree, BST)` 中查找元素 $50$，从根节点开始：若根值为 $60$，则下一步应去搜索( )
- 左子树
- 右子树
- 随机
- 根节点
**第 14 题** 删除二叉排序树中的节点时，如果节点有两个孩子，则横线处应填入( )，其中 `findMax` 和 `findMin` 分别为寻找树的最大值和最小值的函数。
```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 TreeNode* deleteNode(TreeNode* root, int key) {
09 if (!root) return nullptr;
10 if (key < root–>val) {
11 root–>left = deleteNode(root–>left, key);
12 }
13 else if (key > root–>val) {
14 root–>right = deleteNode(root–>right, key);
15 }
16 else {
17 if (!root–>left) return root–>right;
18 if (!root–>right) return root–>left;
19 TreeNode* temp = ____________; // 在此处填写代码
20 root–>val = temp–>val;
21 root–>right = deleteNode(root–>right, temp–>val);
22 }
23 return root;
24 }
```
- `root->left`
- `root->right`
- `findMin(root->right)`
- `findMax(root->left)`
**第 15 题** 给定 $n$ 个物品和一个最大承重为 $W$ 的背包，每个物品有一个重量 $wt[i]$ 和价值 $val[i]$，每个物品只能选择放或不放。目标是选择若干个物品放入背包，使得总价值最大，且总重量不超过 $W$，则横线上应填写 ( )
```cpp
01 int knapsack(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 ________________________ // 在此处填写代码
06
07 }
08 }
09 return dp[W];
10 }
```
- `dp[w] = max(dp[w], dp[w] + val[i]);`
- `dp[w] = dp[w - wt[i]] + val[i];`
- `dp[w] = max(dp[w - 1], dp[w - wt[i]] + val[i]);`
- `dp[w] = max(dp[w], dp[w - wt[i]] + val[i]);`
## 二、判断题（每题 2 分，共 20 分）
**第 1 题** 当基类可能被多态使用，其析构函数应该声明为虚函数。
- 正确
- 错误
**第 2 题** 哈夫曼编码是最优前缀码，且编码结果唯一。
- 正确
- 错误
**第 3 题** 一个含有 $100$ 个节点的完全二叉树，高度为 $8$。
- 正确
- 错误
**第 4 题** 在 `C++ STL` 中，栈 (`std::stack`) 的 `pop` 操作返回栈顶元素并移除它。
- 正确
- 错误
**第 5 题** 循环队列通过模运算循环使用空间。
- 正确
- 错误
**第 6 题** 一棵有 $n$ 个节点的二叉树一定有 $n-1$ 条边。
- 正确
- 错误
**第 7 题** 以下代码实现了二叉树的中序遍历。输入以下二叉树，中序遍历结果是 `4 2 5 1 3 6`。
```bash
1
/ \
2 3
/ \ \
4 5 6
```
```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 inorderIterative(TreeNode* root) {
09 stack st;
10 TreeNode* curr = root;
11
12 while (curr || !st.empty()) {
13 while (curr) {
14 st.push(curr);
15 curr = curr->left;
16 }
17 curr = st.top(); st.pop();
18 cout << curr->val << " ";
19 curr = curr->right;
20 }
21 }
```
- 正确
- 错误
**第 8 题** 下面代码实现的二叉排序树的查找操作时间复杂度是 $O(h)$，其中 $h$ 为树高。
```cpp
01 TreeNode* searchBST(TreeNode* root, int val) {
02 while (root && root->val != val) {
03 root = (val < root->val) ? root->left : root->right;
04 }
05 return root;
06 }
```
- 正确
- 错误
**第 9 题** 下面代码实现了动态规划版本的斐波那契数列计算，其时间复杂度是 $O(2^n)$。
```cpp
01 int fib_dp(int n) {
02 if (n <= 1) return n;
03 vector dp(n+1);
04 dp[0] = 0;
05 dp[1] = 1;
06 for (int i = 2; i <= n; i++) {
07 dp[i] = dp[i-1] + dp[i-2];
08 }
09 return dp[n];
10 }
```
- 正确
- 错误
**第 10 题** 有一排香蕉，每个香蕉有不同的甜度值。小猴子想吃香蕉，但不能吃相邻的香蕉。以下代码能找到小猴子吃到最甜的香蕉组合。
```cpp
01 // bananas：香蕉的甜度
02 void findSelectedBananas(vector& bananas, vector& dp) {
03 vector selected;
04 int i = bananas.size() - 1;
05
06 while (i >= 0) {
07 if (i == 0) {
08 selected.push_back(0);
09 break;
10 }
11
12 if (dp[i] == dp[i-1]) {
13 i--;
14 } else {
15 selected.push_back(i);
16 i -= 2;
17 }
18 }
19
20 reverse(selected.begin(), selected.end());
21 cout << "小猴子吃了第: ";
22 for (int idx : selected)
23 cout << idx+1 << " ";
24 cout << "个香蕉" << endl;
25 }
26
27 int main() {
28 vector bananas = {1, 2, 3, 1}; // 每个香蕉的甜
29
30 vector dp(bananas.size());
31 dp[0] = bananas[0];
32 dp[1] = max(bananas[0], bananas[1]);
33 for (int i = 2; i < bananas.size(); i++) {
34 dp[i] = max(bananas[i] + dp[i-2], dp[i-1]);
35 }
36 findSelectedBananas(bananas, dp);
37
38 return 0;
39 }
```
- 正确
- 错误