GESP 客观题评测系统
2024-03-Level-6
2024-03-Level-6
试卷解析总览，可直接查看每题答案与解析。
第 1 题（单选题）
在构建哈夫曼树时，每次应该选择（）合并。
A.
最小权值的节点
B.
最大权值的节点
C.
随机节点
D.
深度最深的节点
正确答案A
解析详情
【答案】A
【考点】哈夫曼树构建
【解析】 哈夫曼树构建采用贪心策略，每次从当前森林中选取两棵根节点权值最小的树作为左右子树合并，新根节点权值为两者之和。
【易错点】 误选权值最大或深度最深的节点。
第 2 题（单选题）
面向对象的编程思想主要包括以下哪些原则（）?
A.
贪心、动态规划、回溯
B.
并发、并行、异步
C.
递归、循环、分治
D.
封装、继承、多态
正确答案D
解析详情
【答案】D
【考点】面向对象编程基本特征
【解析】 面向对象编程（OOP）的三大核心原则是封装（隐藏细节）、继承（代码复用）和多态（同一接口多种实现）。
【易错点】 将贪心、分治等算法设计思想误认为面向对象原则。
第 3 题（单选题）
在队列中，元素的添加和删除是按照（）原则进行的。
A.
先进先出
B.
先进后出
C.
最小值先出
D.
随机进出
正确答案A
解析详情
【答案】A
【考点】队列的特性
【解析】 队列（Queue）是一种先进先出（First-In-First-Out, FIFO）的受限线性表，只允许在队尾插入，在队头删除。
【易错点】 混淆队列与栈（先进后出）的操作原则。
第 4 题（单选题）
给定一个简单的类定义如下，（）语句在类的外部正确地创建了一个 Circle 对象并调用了 getArea 函数？
class Circle {
private:
double radius;
public:
Circle(double r) : radius(r) {}
double getArea() {
return 3.14 * radius * radius;
}
};A.
Circle c = Circle(5.0); c.getArea(c);
B.
Circle c(5.0); getArea(c);
C.
Circle c = new Circle(5.0); c.getArea();
D.
Circle c(5.0); c.getArea();
正确答案D
解析详情
【答案】D
【考点】C++ 构造函数与对象成员访问
【解析】 C++ 中 `Circle c(5.0)` 调用有参构造函数在栈上创建对象，`c.getArea()` 通过对象名点号访问成员函数。A、B项调用语法错误，C项 `new` 返回指针，需用 `->` 访问。
【易错点】 混淆栈对象（用`.`访问）与堆指针（用`->`访问）的成员调用方式。
第 5 题（单选题）
以下代码希望能在一棵二叉排序树中搜索特定的值，请在横线处填入（），使其能正确实现相应功能。
TreeNode* search(TreeNode* root, int target) {
if (root == NULL || root->val == target) {
return root;
}
if (target < root->val) {
return search(root->left, target);
} else {
return search(root->right, target);
}
}A.
target < root->left
B.
target < root->val
C.
target > root->val
D.
target > root->left
正确答案B
解析详情
【答案】B
【考点】二叉搜索树（BST）的性质
【解析】 二叉排序树定义为：左子树所有节点值小于根，右子树所有节点值大于根。若 `target` 小于当前 `root->val`，根据性质应递归搜索左子树。
【易错点】 混淆二叉搜索树中左右子树与根节点的大小逻辑关系。
第 6 题（单选题）
3位格雷编码的正确顺序是（）。
A.
000, 001, 010, 011, 100, 101, 110, 111
B.
000, 001, 011, 010, 110, 111, 101, 100
C.
000, 010, 001, 011, 100, 110, 101, 111
D.
000, 010, 110, 100, 111, 101, 011, 001
正确答案B
解析详情
【答案】B
【考点】格雷码编码规律
【解析】 格雷码相邻编码之间只有一位二进制位不同。3位格雷码序列依次为：000, 001, 011, 010, 110, 111, 101, 100。A项为普通二进制顺序。
【易错点】 误将二进制递增顺序（0,1,2,3...）当作格雷码顺序。
第 7 题（单选题）
以下动态规划算法的含义与目的是（）。
int function(vector<int>& nums) {
int n = nums.size();
if (n == 0)
return 0;
if (n == 1)
return nums[0];
vector<int> 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];
}A.
计算数组 nums 中的所有元素的和
B.
计算数组 nums 中相邻元素的最大和
C.
计算数组 nums 中不相邻元素的最大和
D.
计算数组 nums 中的最小元素
正确答案C
解析详情
【答案】C
【考点】动态规划应用（不相邻子序列最大和）
【解析】 代码中的状态转移方程 `dp[i] = max(dp[i-1], nums[i] + dp[i-2])` 表示第 i 位取舍逻辑：若取 nums[i] 则不能取前一位，故加 dp[i-2]。这正是计算不相邻元素最大和的经典模型。
【易错点】 误认为是求连续子数组最大和或所有元素之和。
第 8 题（单选题）
阅读以下广度优先搜索的代码：
void bfs(TreeNode* root) {
if (root == NULL) {
return;
}
queue<TreeNode*> q;
q.push(root);
while (!q.empty()) {
TreeNode* current = q.front();
q.pop();
cout << current->val << " ";
if (current->left) {
q.push(current->left);
}
if (current->right) {
q.push(current->right);
}
}
}使用以上算法遍历以下这棵树，可能的输出是（）。
1
/ \
2 3
/ \
8 9 6
/ \
4 5 7
/ \
10 11A.
1 2 8 9 4 5 3 6 7 10 11
B.
1 2 3 4 5 6 7 8 9 10 11
C.
1 2 3 8 9 6 4 5 7 10 11
D.
1 2 3 8 9 4 5 6 7 10 11
正确答案C
解析详情
【答案】C
【考点】广度优先搜索（BFS）层序遍历
【解析】 BFS 按层访问。第一层：1；第二层：2,3；第三层：2的孩子8,9，3的孩子6；第四层：8的孩子4,5，6的孩子7；第五层：4的孩子10,11。拼合即得 1 2 3 8 9 6 4 5 7 10 11。
【易错点】 误将 BFS 过程混淆为 DFS（深度优先搜索）的先序或中序遍历。
第 9 题（单选题）
给定一个空栈，执行以下操作序列：
操作序列： push(1), push(2), push(3), pop(), pop(), push(4), push(5), pop()
最终栈中的元素是（）。
A.
1,2
B.
1,4,5
C.
1,2,5
D.
1,4
正确答案D
解析详情
【答案】D
【考点】栈（Stack）的操作
【解析】 过程模拟：push(1)->[1]；push(2)->[1,2]；push(3)->[1,2,3]；pop()->[1,2]；pop()->[1]；push(4)->[1,4]；push(5)->[1,4,5]；pop()->[1,4]。最终栈内剩余 1,4。
【易错点】 混淆栈的后进先出规则，导致 pop 操作后剩余元素计算错误。
第 10 题（单选题）
一个有 124 个叶子节点的完全二叉树，最多有（）个结点。
A.
247
B.
248
C.
249
D.
250
正确答案B
解析详情
【答案】B
【考点】完全二叉树性质计算
【解析】 二叉树中叶子节点数 n_0 = n_2 + 1，故 n_2 = 123。完全二叉树总节点 n = n_0 + n_1 + n_2 = 124 + n_1 + 123 = 247 + n_1。由于 n_1 只能为 0 或 1，求最多结点即 n_1=1，总数为 248。
【易错点】 忘记计算完全二叉树中可能存在的度为 1 的节点（n_1）。
第 11 题（单选题）
在求解最优化问题时，动态规划常常涉及到两个重要性质，即最优子结构和（）。
A.
重叠子问题
B.
分治法
C.
贪心策略
D.
回溯算法
正确答案A
解析详情
【答案】A
【考点】动态规划的基本特征
【解析】 动态规划有两个必要性质：最优子结构（问题的最优解包含其子问题的最优解）和重叠子问题（子问题被多次重复计算）。
【易错点】 将分治策略（通常子问题的解不被多次使用）或贪心策略误认为动态规划特有的“重叠子问题”性质。
第 12 题（单选题）
若一棵二叉树的先序遍历为：A, B, D, E, C, F、中序遍历为：D, B, E, A, F, C，它的后序遍历为（）。
A.
D, E, B, F, C, A
B.
E, D, B, F, C, A
C.
D, E, B, C, F, A
D.
E, D, B, C, F, A
正确答案A
解析详情
【答案】A
【考点】二叉树遍历推导
【解析】 由先序知 A 为根。由中序知左子树 (D,B,E)，右子树 (F,C)。递归：左子树先序 BDE，中序 DBE，知 B 为根且 D 左 E 右；右子树先序 CF，中序 FC，知 C 为根且 F 为左。结构：A(B(D,E), C(F,空))。后序：D, E, B, F, C, A。
【易错点】 在推导左右子树结构时，根节点与左右节点的相对位置判断错误。
第 13 题（单选题）
线性筛法与埃氏筛法相比的优势是（）。
A.
更容易实现
B.
更节省内存
C.
更快速
D.
更准确
正确答案C
解析详情
【答案】C
【考点】筛法复杂度分析
【解析】 埃氏筛法会对同一个合数进行多次标记（如 6 被 2 和 3 分别标记），而线性筛通过限制只用最小质因子标记合数，保证每个数只被处理一次，时间复杂度为 O(N)，效率更高。
【易错点】 误认为线性筛比埃氏筛更节省空间（实际上线性筛需要额外数组记录最小质因子）。
第 14 题（单选题）
以下代码使用了辗转相除法求解最大公因数，请在横线处填入（），使其能正确实现相应功能。
int gcd(int a, int b) {
while (b != 0) {
___
}
return a;
}A.
int temp = b; b = a / b; a = temp;
B.
int temp = a; a = b / a; b = temp;
C.
int temp = b; b = a % b; a = temp;
D.
b = a % b; a = b;
正确答案C
解析详情
【答案】C
【考点】欧几里得算法（辗转相除法）
【解析】 辗转相除法核心逻辑为 `gcd(a, b) = gcd(b, a % b)`。循环中需利用中间变量 `temp` 暂存 `b`，然后将 `b` 更新为 `a % b`，再将暂存的 `temp` 赋给 `a`。
【易错点】 混淆变量赋值顺序或误用除号（/）代替求余符号（%）。
第 15 题（单选题）
下面的代码片段用于反转单链表，请进行（）修改，使其能正确实现相应功能。
ListNode* reverseLinkedList(ListNode* head) {
ListNode* prev = nullptr;
ListNode* current = head;
while (current != nullptr) {
ListNode* next = current->next;
current->next = next;
prev = current;
current = next;
}
return prev;
}A.
current->next = next; 应该改为 current->next = prev;
B.
ListNode* next = current->next; 应该改为 ListNode* next = prev->next;
C.
current != nullptr 应该改为 current->next != nullptr
D.
ListNode* prev = nullptr; 应该改为 ListNode* prev = head;
正确答案A
解析详情
【答案】A
【考点】链表反转算法
【解析】 反转单链表的核心是让当前节点的 `next` 指向前驱 `prev`。代码中 `current->next = next` 维持了原序，应修正为 `current->next = prev` 以实现指针调头。
【易错点】 对链表节点修改顺序理解有误，导致循环中指针丢失或未实现反向链接。
判断题（每题 2 分）
第 1 题（判断题）
哈夫曼树是一种二叉树。
正确答案正确
解析详情
【答案】正确
【考点】哈夫曼树定义
【解析】 哈夫曼树又称最优二叉树，是一种带权路径长度最短的特殊二叉树。
【易错点】 误以为哈夫曼树是多叉树。
第 2 题（判断题）
在动态规划中，状态转移方程的作用是定义状态之间的关系。
正确答案正确
解析详情
【答案】正确
【考点】动态规划状态转移方程
【解析】 状态转移方程是动态规划的核心，它描述了如何由已知子问题的状态推导出当前问题的状态。
【易错点】 认为状态转移方程只用于定义初始边界。
第 3 题（判断题）
继承是将已有类的属性和方法引入新类的过程。
正确答案正确
解析详情
【答案】正确
【考点】面向对象继承概念
【解析】 继承允许子类获得基类的公有和保护成员，从而实现代码的扩展和复用。
【易错点】 无。
第 4 题（判断题）
完全二叉树的任意一层都可以不满。
正确答案错误
解析详情
【答案】错误
【考点】完全二叉树定义
【解析】 完全二叉树要求除了最后一层，其他每一层都必须是满的，且最后一层的节点靠左对齐。
【易错点】 混淆完全二叉树与普通二叉树的层级结构要求。
第 5 题（判断题）
删除单向链表中的节点，只需知道待删除节点的地址即可，无需访问前一个节点。
正确答案错误
解析详情
【答案】错误
【考点】链表删除操作
【解析】 单向链表删除节点必须修改前驱节点的 `next` 指针，因此必须知道前一个节点的位置。仅知道当前地址无法直接获取前驱。
【易错点】 认为只需释放内存即可，忽略了链表指针逻辑的维护。
第 6 题（判断题）
在宽度优先搜索中，通常使用队列来辅助实现。
正确答案正确
解析详情
【答案】正确
【考点】BFS算法实现
【解析】 宽度优先搜索（BFS）利用队列先进先出的特性来保证按层访问节点。
【易错点】 混淆 BFS（用队列）与 DFS（用栈或递归）的实现工具。
第 7 题（判断题）
哈夫曼编码的主要应用领域是有损数据压缩。
正确答案错误
解析详情
【答案】错误
【考点】哈夫曼编码性质
【解析】 哈夫曼编码是一种无损数据压缩算法，压缩后的数据可以被完全、准确地恢复。
【易错点】 混淆无损压缩与有损压缩（如 JPEG 等）的应用场景。
第 8 题（判断题）
二叉搜索树的查找操作的时间复杂度是。
正确答案错误
解析详情
【答案】错误
【考点】BST 查找复杂度分析
【解析】 二叉搜索树的查找平均复杂度为 O(\log N)，只有在最坏情况下（树退化为链表）才为 O(N)。断言描述不全面。
【易错点】 忽略平衡性对二叉树查找效率的影响。
第 9 题（判断题）
栈的基本操作包括入栈（push）和出栈（pop）。
正确答案正确
解析详情
【答案】正确
【考点】栈的基本操作
【解析】 栈是受限线性表，其核心操作就是在栈顶进行入栈（Push）和出栈（Pop）。
【易错点】 无。
第 10 题（判断题）
使用哈夫曼编码对一些字符进行编码，如果两个字符的频率差异最大，则它们的编码可能出现相同的前缀。
正确答案错误
解析详情
【答案】错误
【考点】哈夫曼编码的前缀性质
【解析】 哈夫曼编码是前缀编码（Prefix Code），没有任何编码是另一个编码的前缀。这是由字符仅存在于叶子节点这一性质决定的。
【易错点】 错误理解前缀编码的定义，认为频率差异大可能导致包含关系。