5324：[GESP202403] 六级客观题
文件提交：无需freopen
内存限制：128 MB
时间限制：1.000 S
评测方式：文本裁判
金币值：
命题人：
提交：0
解决：0
题目描述
# 一、单选题（每题 2 分，共 30 分）
1. 在构建哈夫曼树时，每次应该选择（ ）合并。
- 最小权值的节点
- 最大权值的节点
- 随机节点
- 深度最深的节点
2. 面向对象的编程思想主要包括以下哪些原则（ ）？
- 贪心、动态规划、回溯
- 并发、并行、异步
- 递归、循环、分治
- 封装、继承、多态
3. 在队列中，元素的添加和删除是按照（ ）原则进行的。
- 先进先出
- 先进后出
- 最小值先出
- 随机进出
4. 给定一个简单的类定义如下，（ ）语句在类的外部正确地创建了一个`Circle`对象并调用了 getArea 函数？
- `Circle c = Circle(5.0); c.getArea(c);`
- `Circle c(5.0); getArea(c);`
- `Circle c = new Circle(5.0); c.getArea();`
- `Circle c(5.0); c.getArea();`
5. 已知字符 `0` 的ASCII编码的十进制表示为48，则执行下面C++代码后，输出是（ ）
- `target < root->left`
- `target < root->val`
- `target > root->val`
- `target > root->left`
6. 3 位格雷编码的正确顺序是（ ）。
- 000, 001, 010, 011, 100, 101, 110, 111
- 000, 001, 011, 010, 110, 111, 101, 100
- 000, 010, 001, 011, 100, 110, 101, 111
- 000, 010, 110, 100, 111, 101, 011, 001
7. 以下动态规划算法的含义与目的是（ ）。
```cpp
int function(vector& nums) {
int n = nums.size();
if (n == 0)
return 0;
if (n == 1)
return nums[0];
vector dp(n, 0);
dp[0] = nums[0];
dp[1] = max(nums[0], nums[1]);
for (int i = 2; i < n; ++i) {
dp[i] = max(dp[i - 1], nums[i] + dp[i - 2]);
}
return dp[n - 1];
}
```
- 计算数组`nums`中的所有元素的和
- 计算数组`nums`中相邻元素的最大和
- 计算数组 `nums` 中不相邻元素的最大和
- 计算数组 `nums `中的最小元素
8. 阅读以下广度优先搜索的代码：
使用以上算法遍历以下这棵树，可能的输出是（ ）。
- `1 2 8 9 4 5 3 6 7 10 11`
- `1 2 3 4 5 6 7 8 9 10 11`
- `1 2 3 8 9 6 4 5 7 10 11`
- `1 2 3 8 9 4 5 6 7 10 11`
9. 给定一个空栈，执行以下操作序列：
操作序列：` push(1), push(2), push(3), pop(), pop(), push(4), push(5), pop()`
最终栈中的元素是（ ）。
- `1, 2`
- `1, 4, 5`
- `1, 2, 5`
- `1, 4`
10. 一个有 124 个叶子节点的完全二叉树，最多有（ ）个结点。
- 247
- 248
- 249
- 250
11. 在求解最优化问题时，动态规划常常涉及到两个重要性质，即最优子结构和（ ）。
- 重叠子问题
- 分治法
- 贪心策略
- 回溯算法
12. 若一棵二叉树的先序遍历为：A, B, D, E, C, F、中序遍历为：D, B, E, A, F, C，它的后序遍历为（ ）。
- D, E, B, F, C, A
- E, D, B, F, C, A
- D, E, B, C, F, A
- E, D, B, C, F, A
13. 线性筛法与埃氏筛法相比的优势是（ ）。
- 更容易实现
- 更节省内存
- 更快速
- 更准确
14. 以下代码使用了辗转相除法求解最大公因数，请在横线处填入（ ），使其能正确实现相应功能。
- `int temp = b; b = a / b; a = temp;`
- `int temp = a; a = b / a; b = temp;`
- `int temp = b; b = a % b; a = temp;`
- `b = a % b; a = b;`
15. 下面的代码片段用于反转单链表，请进行（ ）修改，使其能正确实现相应功能。
- `current->next = next; 应该改为 current->next = prev;`
- `ListNode* next = current->next; 应该改为 ListNode* next = prev->next;`
- `current != nullptr 应该改为 current->next != nullptr`
- `ListNode* prev = nullptr; 应该改为 ListNode* prev = head;`
# 二、判断题（每题 2 分，共 20 分）
16. 哈夫曼树是一种二叉树。
- 正确
- 错误
17. 在动态规划中，状态转移方程的作用是定义状态之间的关系。
- 正确
- 错误
18. 继承是将已有类的属性和方法引入新类的过程。
- 正确
- 错误
19. 完全二叉树的任意一层都可以不满。
- 正确
- 错误
20. 删除单向链表中的节点，只需知道待删除节点的地址即可，无需访问前一个节点。
- 正确
- 错误
21. 在宽度优先搜索中，通常使用队列来辅助实现。
- 正确
- 错误
22. 哈夫曼编码的主要应用领域是有损数据压缩。
- 正确
- 错误
23. 二叉搜索树的查找操作的时间复杂度是$O(N)$。
- 正确
- 错误
24. 栈的基本操作包括入栈（push）和出栈（pop）。
- 正确
- 错误
25. 使用哈夫曼编码对一些字符进行编码，如果两个字符的频率差异最大，则它们的编码可能出现相同的前缀。
- 正确
- 错误