GESP 客观题评测系统
2024-12-Level-6
2024-12-Level-6
试卷解析总览，可直接查看每题答案与解析。
第 1 题（单选题）
面向对象编程(OOP)是一种特殊的程序设计方法。下面()不是重要的OOP特性。
A.
抽象
B.
封装
C.
继承
D.
模块化
正确答案D
解析详情
【答案】D
【考点】面向对象编程的基本特征
【解析】 面向对象编程（OOP）的三大核心特性是封装、继承和多态。抽象也是其重要基础。模块化是结构化设计和现代编程的通用原则，并非 OOP 特有的核心属性。
【易错点】容易将“模块化”这种通用设计原则误认为是 OOP 专有的特性。
第 2 题（单选题）
以下关于 C++ 中类的说法，哪一项是正确的？
A.
类中定义的所有成员变量和成员函数默认是 public 访问权限。
B.
类的构造函数必须显式声明返回类型为 void。
C.
在 C++ 中，类的数据一般设置为私有，其公有成员函数提供访问私有数据的唯一途径。
D.
同一个类的实例有各自的成员数据和成员函数。
正确答案C
解析详情
【答案】C
【考点】C++ 类的定义与封装
【解析】 C++ 中 class 成员默认访问权限为 private（A 错）；构造函数没有返回类型，连 void 也不能写（B 错）；同一个类的多个实例拥有各自独立的成员变量，但共享同一套成员函数代码（D 错）。通过公有接口访问私有数据是封装的核心实践。
【易错点】误以为同一类的不同对象会拥有不同的函数代码备份，实际上函数代码是共享的。
第 3 题（单选题）
以下C++代码段中存在语法错误或逻辑错误，（）是正确的。
#include <iostream>
using namespace std;
class MyClass {
public:
MyClass() {
cout << "Constructor called!" << endl;
}
void display() {
cout << "Display function called!" << endl;
}
};
int main() {
MyClass* obj = NULL;
obj->display();
return 0;
}A.
NULL 在C++中无法用于指针初始化，应使用 nullptr。
B.
obj 的定义应该是 MyClass obj；而不是指针类型。
C.
obj->display() 语句存在空指针访问错误，obj 应该初始化为一个有效的对象。
D.
obj->display() 语句会调用 display() 函数，但它没有输出任何内容。
正确答案C
解析详情
【答案】C
【考点】指针初始化与空指针解引用
【解析】 代码中将 obj 初始化为 NULL，随后调用 obj->display() 会引发空指针访问错误（解引用空指针），这是严重的逻辑错误。虽然 C++11 推荐使用 nullptr，但 NULL 依然可以用于指针初始化。display 函数内部有 cout 输出，D 描述错误。
【易错点】空指针调用成员函数在 C++ 中属于未定义行为，通常会导致程序崩溃。
第 4 题（单选题）
阅读以下代码，下面哪一项是正确的？
void processData() {
stack<int> s;
queue<int> q;
for (int i = 1; i <= 5; ++i) {
s.push(i);
q.push(i);
}
while (!s.empty()) {
cout << "Stack pop: " << s.top() << endl;
s.pop();
}
while (!q.empty()) {
cout << "Queue pop: " << q.front() << endl;
q.pop();
}
}A.
栈 s 的输出顺序是 1 2 3 4 5，队列 q 的输出顺序是 5 4 3 2 1。
B.
栈 s 的输出顺序是 5 4 3 2 1，队列 q 的输出顺序是 1 2 3 4 5。
C.
栈 s 的输出顺序是 1 2 3 4 5，队列 q 的输出顺序是 1 2 3 4 5。
D.
栈 s 的输出顺序是 1 2 3 4 5，队列 q 的输出顺序是 1 2 3 4 5，程序不会正常执行。
正确答案B
解析详情
【答案】B
【考点】栈（LIFO）与队列（FIFO）的特性
【解析】 栈（stack）遵循后进先出（LIFO）原则，推入 1-5 后，弹出顺序为 5, 4, 3, 2, 1；队列（queue）遵循先进先出（FIFO）原则，推入 1-5 后，弹出顺序为 1, 2, 3, 4, 5。
【易错点】容易记反栈和队列的操作顺序，只需记住栈是像“叠盘子”一样从顶部操作。
第 5 题（单选题）
N 个节点的双向循环链，在其中查找某个节点的平均时间复杂度是()。
A.
B.
C.
D.
正确答案B
解析详情
【答案】B
【考点】链表的时间复杂度分析
【解析】 链表（无论是单向、双向还是循环链表）不支持随机访问。查找特定值必须从头（或某个已知节点）开始逐个遍历，直到找到目标或走完全部节点，因此平均和最坏情况的时间复杂度均为 O(N)。
【易错点】误认为“双向”或“循环”特性可以降低查找复杂度，实际上它们只优化了已知节点前后的插入删除操作。
第 6 题（单选题）
以下关于树的说法，（）是正确的。
A.
在一棵二叉树中，叶子结点的度一定是2。
B.
满二叉树中每一层的结点数等于O(2^{(层数-1)})。
C.
在一棵树中，所有结点的度之和等于所有叶子结点的度之和。
D.
一棵二叉树的先序遍历结果和中序遍历结果一定相同。
正确答案B
解析详情
【答案】B
【考点】二叉树的基础性质
【解析】 叶子结点的度为 0（A 错）；满二叉树第 k 层的节点数确为 2^(k-1)（B 正确）；树中节点总度数等于总边数，也等于总节点数减 1，而非叶子度之和（C 错）；先序和中序遍历仅在树为特定形态（如所有节点只有右子树）时才可能相同（D 错）。
【易错点】注意“度”的定义：结点的度是指该结点拥有的子树数量，叶子结点没有子树，故度为 0。
第 7 题（单选题）
已知字符集 {A, B, C, D} 的出现频率如下表所示：
字符 频率
A 8
B 3
C 1
D 6根据哈夫曼编码法，下面（）是正确的哈夫曼树。
A.
ABCD
/ \
A BCD
/ \
D BC
/ \
B CB.
ABCD
/ \
A BCD
/ \
B CD
/ \
C DC.
ABCD
/ \
D ABC
/ \
A BC
/ \
B CD.
ABCD
/ \
C ABD
/ \
B AD
/ \
A D正确答案A
解析详情
【答案】A
【考点】哈夫曼树的构造过程
【解析】 构造步骤：1. 将 B(3) 和 C(1) 合并为 BC(4)；2. 将新节点 BC(4) 与 D(6) 合并为 BCD(10)；3. 将 BCD(10) 与 A(8) 合并为 ABCD(18)。这要求 A、D、(B,C) 分别位于不同的深度级别。选项 A 的结构符合此贪心选择过程。
【易错点】每次合并时必须选择当前森林中权值最小的两个节点。
第 8 题（单选题）
上一题中各字符的哈夫曼编码是（）。
A.
A: 0, B: 10, C: 110, D: 111
B.
A: 0, B: 10, C: 11, D: 10
C.
A: 0, B: 101, C: 100, D: 11
D.
A: 11, B: 10, C: 01, D: 00
正确答案C
解析详情
【答案】C
【考点】哈夫曼编码的生成
【解析】 基于上一题的构造：最浅层为 A(权值最大)，其次是 D，最深层是 B 和 C。选项 C 给出的方案中，A 是一阶编码(0)，D 是二阶编码(11)，B 和 C 是三阶编码(101, 100)，符合权重越大路径越短的原则，且满足前缀码要求。
【易错点】哈夫曼编码不唯一（左右分支分配 0/1 可互换），但编码长度必须符合权值分布。
第 9 题（单选题）
（）是3位格雷编码。
A.
000 001 011 010 110 111 101 100
B.
000 001 010 011 100 101 110 111
C.
000 001 100 101 011 010 111 110
D.
000 010 001 011 100 110 101 111
正确答案A
解析详情
【答案】A
【考点】格雷码（Gray Code）的定义
【解析】 格雷码的特征是相邻两个编码之间只有一位二进制数发生改变。检查 A 选项：000->001(末位变), 001->011(中位变), 011->010(末位变)... 全部符合。B 选项是普通的二进制递增序列，存在多位同时跳变的情况。
【易错点】格雷码不仅要求中间相邻项满足条件，循环格雷码还要求首尾两项也只有一位之差。
第 10 题（单选题）
根据下面二叉树和给定的代码，
#include <iostream>
using namespace std;
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
TreeNode* search(TreeNode* root, int val) {
cout << root->val << " ";
if (root == NULL || root->val == val) return root;
if (val < root->val)
return search(root->left, val);
else
return search(root->right, val);
}给定以下二叉搜索树，调用函数 search(root,7) 时，输出的结果是（）。
5
/ \
3 7
/ \ / \
2 4 6 8A.
537
B.
57
C.
234567
D.
87
正确答案B
解析详情
【答案】B
【考点】二叉搜索树（BST）的查找路径
【解析】 查找值为 7 的过程：1. 访问根节点 5，打印“5”，因为 7 > 5，向右子树递归；2. 访问右子节点 7，打印“7”，因为 7 == 7，返回结果。查找结束，总输出为“5 7”。
【易错点】注意 `cout` 在递归基判断之前。虽然 7 已经找到，但当前层的 `cout` 依然会执行。
第 11 题（单选题）
阅读以下二叉树的深度优先搜索算法，横线上应填写（）。
void dfs(TreeNode* root) {
if (root == nullptr)
return;
stack<TreeNode*> s;
s.push(root);
while (!s.empty()) {
___ // 在此处填入代码
cout << node->value << "";
if (node->right) s.push(node->right);
if (node->left) s.push(node->left);
}
}A.
TreeNode* node = s.top();
B.
TreeNode* node = s.top(); s.pop();
C.
TreeNode* node = s.front();
D.
TreeNode* node = s.front(); s.pop();
正确答案B
解析详情
【答案】B
【考点】DFS 的非递归实现与栈的操作
【解析】 在利用栈实现非递归 DFS 时，每一轮循环需从栈顶取出并移除一个节点。C++ `std::stack` 获取栈顶用 `top()`，移除用 `pop()`。只 `top()` 而不 `pop()` 会导致死循环；`front()` 是队列（queue）的接口。
【易错点】容易混淆栈（top/pop）和队列（front/pop）的成员函数名。
第 12 题（单选题）
阅读以下二叉树的广度优先搜索的代码，横线上应填写（）。
#include <queue>
void bfs(TreeNode* root) {
if (root == NULL) return;
queue<TreeNode*> q;
q.push(root);
while (!q.empty()) {
// 在此处填入代码
cout << node->val << " ";
if (node->left) {
q.push(node->left);
}
if (node->right) {
q.push(node->right);
}
}
}A.
TreeNode* node = q.top();
B.
TreeNode* node = q.top(); q.pop();
C.
TreeNode* node = q.front();
D.
TreeNode* node = q.front(); q.pop();
正确答案D
解析详情
【答案】D
【考点】BFS 的队列实现规范
【解析】 广度优先搜索（BFS）使用队列存储待访问节点。每一轮从队首取出元素：`q.front()` 获取值，`q.pop()` 弹出节点。`top()` 是栈或优先队列的接口，普通 `std::queue` 不提供 `top()`。
【易错点】如果不执行 `pop()`，队列长度会不断增加且陷入死循环。
第 13 题（单选题）
使用上题中的宽度优先搜索算法遍历以下这棵树，可能的输出是()。
1
/ \
2 3
/ \
8 9 6
/ \
4 5 7A.
128945367
B.
123456689
C.
123896457
D.
845921367
正确答案C
解析详情
【答案】C
【考点】层序遍历（BFS）的顺序确定
【解析】 BFS 按层访问：第一层是 {1}；第二层是 {2, 3}；第三层访问 2 的子节点 {8, 9} 和 3 的子节点 {6}；第四层访问 8 的子节点 {4, 5} 和 6 的子节点 {7}。由于同一层内顺序由入队顺序决定，1-2-3-8-9-6-4-5-7 是一个完全合法的层序序列。
【易错点】注意 BFS 必须访问完当前层的所有节点后，才能访问下一层的节点。
第 14 题（单选题）
以下关于动态规划的描述，（）是正确的。
A.
动态规划适用于没有重叠子问题的优化问题。
B.
动态规划要求问题具有最优子结构和无后效性。
C.
动态规划通常通过递归来实现。
D.
动态规划与贪心算法不同，贪心算法不适用于有重叠子问题的问题。
正确答案B
解析详情
【答案】B
【考点】动态规划（DP）的核心要素
【解析】 动态规划有两个必备条件：最优子结构（子问题的最优解能推导全局最优解）和无后效性（过去的状态不影响未来的选择）。它恰恰是用来解决包含大量“重叠子问题”的情况的（A 错）。虽然可以用带备忘录的递归实现，但递推（自底向上）更为常见（C 描述不全面）。
【易错点】误认为贪心算法和动态规划互斥，实际上它们在最优子结构上是有交集的。
第 15 题（单选题）
设背包的最大容量 W = 8kg，共有 4 个物品可供选择，4 个物品的重量分别为 weights = [2, 3, 5, 7]，对应的价值分别为 values = [30, 40, 60, 80]，则该 0/1 背包问题中，背包的最大价值为（）。
A.
70
B.
90
C.
100
D.
120
正确答案C
解析详情
【答案】C
【考点】0/1 背包问题的计算
【解析】 容量限制为 8kg。可能的组合：1. 物品[2,3]（重5, 价70）；2. 物品[2,5]（重7, 价90）；3. 物品[3,5]（重8, 价100）；4. 单件物品[7]（重7, 价80）。对比可知，选择重量 3kg 和 5kg 的两个物品能获得最大价值 100。
【易错点】容易漏掉权值组合。虽然 7kg 物品单价高，但与 1kg 无法凑单，不如 3+5 组合。
判断题（每题 2 分）
第 1 题（判断题）
构造函数是一种特殊的类成员函数，构造函数的名称和类名相同。但通过函数重载，可以创建多个同名的构造函数，条件是每个构造函数参数列表不同。
正确答案正确
解析详情
【答案】正确
【考点】C++ 构造函数的重载规则
【解析】 构造函数遵循普通的函数重载规则。只要参数的数量或类型不同，编译器就能区分不同的构造函数版本，从而实现对象初始化多样性。
【易错点】注意构造函数不能有返回类型，但重载判定仅看参数列表。
第 2 题（判断题）
类的静态成员函数既能访问类的静态数据成员，也能访问非静态数据成员
正确答案错误
解析详情
【答案】错误
【考点】静态成员函数的访问权限限制
【解析】 静态成员函数属于类而非具体对象，它内部没有 `this` 指针。因此，它只能访问静态成员，无法直接访问需要具体实例才能存在的非静态数据成员。
【易错点】误以为“同在一个类下”就能互相访问，忽略了静态与非静态在内存层面的本质区别。
第 3 题（判断题）
栈中元素的插入和删除操作都在栈的顶端进行，所以方便用单向链表实现。
正确答案正确
解析详情
【答案】正确
【考点】栈的链式存储结构
【解析】 将单向链表的头部定义为栈顶，则入栈对应头插入，出栈对应头删除。这两个操作在单链表中都是 O(1) 复杂度，非常高效。
【易错点】不需要双向链表，因为栈的操作不涉及对前驱节点的查找需求。
第 4 题（判断题）
下面代码构建的树一定是完全二叉树：
struct TreeNode {
int value;
TreeNode* left;
TreeNode* right;
};
TreeNode* buildCompleteBinaryTree() {
TreeNode* root = new TreeNode{1};
root->left = new TreeNode{2};
root->right = new TreeNode{3};
root->left->left = new TreeNode{4};
root->left->right = new TreeNode{5};
root->right->left = new TreeNode{6};
return root;
}正确答案正确
解析详情
【答案】正确
【考点】完全二叉树的形态判断
【解析】 该代码创建了 6 个节点。编号 1 为根，2(左) 3(右) 为第二层，4(左) 5(右) 6(左) 为第三层且紧凑靠左。按层序编号不存在空隙，符合完全二叉树定义。
【易错点】完全二叉树要求除最后一层外全满，且最后一层节点必须从左向右连续排列。
第 5 题（判断题）
在二叉排序树中，左子树所有节点的值都大于根节点的值，右子树所有节点的值都小于根节点的值。
正确答案错误
解析详情
【答案】错误
【考点】二叉排序树（BST）的定义
【解析】 二叉排序树的标准定义是：左子树上所有节点的值均小于其根节点的值，右子树上所有节点的值均大于其根节点的值。题目将大小关系说反了。
【易错点】BST 的关键性质是中序遍历能得到一个递增的有序序列。
第 6 题（判断题）
在生成一个派生类的对象时，只调用派生类的构造函数。
正确答案错误
解析详情
【答案】错误
【考点】派生类对象的构造顺序
【解析】 在创建派生类对象时，系统会首先调用其基类的构造函数来初始化继承来的部分，然后再执行派生类自身的构造函数。构造是一个递归向上的链式过程。
【易错点】误以为派生类是独立的。实际上派生类对象内部包含一个完整的基类子对象。
第 7 题（判断题）
下面的代码实现了二叉树的前序遍历，它通过递归方法访问每个节点并打印节点值。
void preorder(TreeNode* root) {
if (root == NULL) return;
cout << root->val << " ";
preorder(root->left);
preorder(root->right);
}正确答案正确
解析详情
【答案】正确
【考点】二叉树的递归遍历算法
【解析】 前序遍历的顺序是：根节点 -> 左子树 -> 右子树。代码中先 `cout` 根值，再递归左侧，最后递归右侧，完全符合前序遍历定义。
【易错点】容易与中序（左-根-右）或后序（左-右-根）遍历的递归代码顺序搞混。
第 8 题（判断题）
宽度优先搜索算法（BFS）保证了每个节点在最短路径的情况下被访问。
正确答案正确
解析详情
【答案】正确
【考点】BFS 的最优性特征
【解析】 在边权相等的图（或无权图）中，BFS 是按距离起点的层数（边数）向外扩张的。因此，当某个节点第一次被访问时，所经过的路径一定是边数最少的路径。
【易错点】注意前提条件是无权图。在带权图中，最短路径需使用 Dijkstra 或 BFS 的变体算法。
第 9 题（判断题）
在解决简单背包问题时，动态规划的状态转移方程如下：
dp[i][w] = max(dp[i-1][w], dp[i-1][w - weights[i-1]] + values[i-1]);该方程表示：在考虑第 i 个物品时，当前背包容量为 w，如果不放物品 i，则最大价值是 dp[i-1][w]；如果放入物品 i，则最大价值是 dp[i-1][w - weights[i-1]] + values[i-1]，其中数组 weights 和 values 分别表示所有物品的重量和价值，数组下标从 0 开始。
正确答案正确
解析详情
【答案】正确
【考点】0/1 背包问题的状态转移方程
【解析】 这是典型的 0/1 背包状态转移方程：当前最优解取决于“不选当前物品”和“选当前物品并扣除相应容量后的历史最优解+当前价值”中的较大者。描述逻辑清晰准确。
【易错点】注意 `weights[i-1]` 是因为程序员习惯用 1 表示第 i 个物品，而数组下标从 0 开始。
第 10 题（判断题）
栈中元素的插入 and 删除操作都在栈的顶端进行，所以方便用双向链表比单向链表更合适表现。
正确答案错误
解析详情
【答案】错误
【考点】数据结构的选型原则
【解析】 单链表实现栈（头插头删）已经达到了 O(1) 的最优时间复杂度。双向链表虽然也能实现，但每个节点多维护一个指针会造成额外的空间浪费，在性能上并无优势，因此不是“更合适”的选择。
【易错点】并不是功能更强的结构（双向链表）就一定比简单的结构（单链表）更合适，需权衡空间开销。