试卷解析 · 理解每一步

2025-09-Level-7

试卷解析总览，可直接查看每题答案与解析。

单选题

第 1 题（单选题，2 分）

已知小写字母 b 的 ASCII 码为 98，下列 C++ 代码的输出结果是（）。

#include <iostream>
using namespace std;
int main() {
    char a = 'b' + 1;
    cout << a;
    return 0;
}

正确答案B

解析详情

答案 B字符与 ASCII；字符运算；输出类型

思路与推导

字符 'b' 的码值是 98，'b'+1 得到 99，对应字符 'c'。赋给 char 后用 cout 输出的是字符本身，因此输出 c，选 B。

第 2 题（单选题，2 分）

已知 a 为 int 类型变量，p 为 int * 类型变量，下列表达式不符合语法的是（）。

a * a

p * p

a && a

p && p

正确答案B

解析详情

答案 B指针类型；运算符适用对象；C++ 表达式语法

思路与推导

int 变量可以做乘法，逻辑与也可用于整型和指针的真假判断；但两个指针之间不能直接做乘法，所以 p * p 非法。其余三项语法上都成立。

第 3 题（单选题，2 分）

下列关于C++类的说法，错误的是（）。

如果一个类包含纯虚函数，则它不能包含成员变量。

如果一个类包含纯虚函数，则不能用它定义对象。

派生类对象占用的内存总是不小于基类对象。

派生类可以不实现基类的虚函数。

正确答案A

解析详情

答案 A抽象类；纯虚函数；继承与对象模型

思路与推导

含纯虚函数的类是抽象类，不能直接定义对象（B 对）；派生类若不实现该虚函数，自己也继续是抽象类（D 对）；派生类通常至少包含基类子对象（C 作为常规结论可成立）。
“抽象类不能有成员变量”是错误说法，抽象类完全可以有数据成员，因此选 A。

第 4 题（单选题，2 分）

已知数组 a 的定义 int a[10] = {-1};，下列说法不正确的是（）。

数组 a 至少占用 10 个 int 大小的内存，一般为 40 个字节。

数组 a 的所有元素均被初始化为 -1。

语句 a[-1] = 0；不会产生编译错误，但会导致难以预测的运行结果。

语句 a[13] = 0；不会产生编译错误，但会导致难以预测的运行结果。

正确答案B

解析详情

答案 B数组初始化；越界访问；未定义行为

思路与推导

int a[10] = {-1}; 只显式给第一个元素赋 -1，其余元素按规则补 0，不会全部是 -1，所以 B 不正确。A 的内存规模描述合理，C、D 都是越界写入，虽可能编译通过但运行结果未定义。

第 5 题（单选题，2 分）

一棵完全二叉树有165个结点，则叶结点有多少个？()

正确答案C

解析详情

答案 C完全二叉树；叶子结点数量

思路与推导

完全二叉树结点数为 n 时，叶子结点数为 ⌈n/2⌉。这里 n=165，所以叶子数为 ⌈165/2⌉=83，对应 C。

第 6 题（单选题，2 分）

下列关于二叉树的说法，错误的是（）。

二叉排序树的中序遍历顺序与元素排序的顺序是相同的。

自平衡二叉查找树（AVL树）是一种二叉排序树。

n 个元素的二叉排序树，其高一定为

\lfloor \log_2 n \rfloor

。

任意的森林，都可以映射为一颗二叉树进行表达和存储。

正确答案C

解析详情

答案 C二叉排序树；AVL 树；树高性质；森林与二叉树转换

思路与推导

A 正确：BST 中序遍历是非降序。B 正确：AVL 是自平衡 BST。D 正确：森林可用“左孩子右兄弟”映射为二叉树。
C 错在“树高一定为 ⌊log2 n⌋”：BST 高度与插入顺序相关，最坏可退化到 O(n)，并非固定值。

第 7 题（单选题，2 分）

下列关于树和图的说法，错误的是（）。

保留树的所有节点，并把树的每个节点指向其父节点，则可以将树转换为一个有向弱连通图。

保留树的所有节点，并把树的每个节点指向其子节点，则可以将树转换为一个有向无环图。

每个连通图都存在生成树。

每个存在生成树的有向图，都一定是强连通的。

正确答案D

解析详情

答案 D树与图转换；有向无环图；连通与强连通

思路与推导

A、B 都是把树边定向后的常见结论：分别得到有向弱连通图/有向无环图。C 也正确：每个连通图都有生成树。
D 错：有向图存在生成树（常指以某根可达所有点的分支）并不推出强连通，强连通要求任意两点互相可达，条件更强。

第 8 题（单选题，2 分）

对一个包含V个顶点、E条边的图，执行广度优先搜索，其最优时间复杂度是（）。

O(V + E)

O(V)

O(E)

O(V^{2})

正确答案A

解析详情

答案 A图遍历复杂度；BFS

思路与推导

BFS 会访问每个顶点一次，并遍历每条边（邻接表实现下每条边最多被检查常数次），总复杂度是 O(V+E)。因此选 A。

第 9 题（单选题，2 分）

以下哪个方案不能合理解决或缓解哈希表冲突（）。

用新元素覆盖发生冲突的哈希表项。

在每个哈希表项处，使用单链表管理该表项的冲突元素。

建立额外的单链表，用来管理所有发生冲突的元素。

使用不同的哈希函数再建立一个哈希表，用来管理所有发生冲突的元素。

正确答案A

解析详情

答案 A哈希冲突处理；开放/封闭策略

思路与推导

冲突时直接覆盖旧元素会导致原数据丢失，无法保证查找正确性，不是合理冲突处理方案。链地址法、集中管理冲突元素、二级哈希等都可作为可行思路。

第 10 题（单选题，2 分）

以下关于贪心法和动态规划的说法中，错误的是（）。

对特定的问题，贪心法不一定适用。

当特定的问题适用贪心法时，通常比动态规划的时间复杂度更低。

对很多问题，递推实现和递归实现动态规划方法的时间复杂度相当。

采用动态规划的算法一定具有多项式时间复杂度。

正确答案D

解析详情

答案 D贪心与动态规划；复杂度分类

思路与推导

A 正确，很多问题不满足贪心选择性质。B 常见情形下也成立。C 对同一 DP 状态转移，递归记忆化与递推通常同阶。
D 错在“DP 一定是多项式时间”：状态空间可能本身是指数级或伪多项式，DP 并不自动保证多项式时间。

第 11 题（单选题，2 分）

下面程序的输出为（）。

#include <iostream>
using namespace std;
int fib(int n) {
    if (n == 0)
        return 1;
    return fib(n - 1) + fib(n - 2);
}
int main() {
    cout << fib(6) << endl;
    return 0;
}

无法正常结束。

正确答案D

解析详情

答案 D递归边界；程序终止性

思路与推导

fib 只设置了 n==0 的边界，调用 fib(6) 会递归到 fib(1)、fib(-1)、fib(-2)...，对负数没有终止条件，递归不会正常收敛，程序会异常终止（如栈溢出）。因此选 D。

第 12 题（单选题，2 分）

下面程序的时间复杂度为（）。

int rec_fib[MAX_N];
int fib(int n) {
    if (n <= 1)
        return n;
    if (rec_fib[n] != 0)
        return rec_fib[n];
    return fib(n - 1) + fib(n - 2);
}

O(\phi^{n})

\phi = \frac{\sqrt{5} + 1}{2}

O(2^{n})

O(n^{2})

O(n)

正确答案A

解析详情

答案 A递归复杂度；斐波那契递推

思路与推导

该函数虽然检查了 rec_fib[n]，但没有把新结果写回缓存，实质仍是朴素 fib 递归。其调用规模与斐波那契数同阶，时间复杂度为 O(φ^n)，对应 A。

第 13 题（单选题，2 分）

下面 init_sieve 函数的时间复杂度为()。

int sieve[MAX_N];
void init_sieve(int n) {
    for (int i = 1; i <= n; i++)
        sieve[i] = i;
    for (int i = 2; i <= n; i++)
        for (int j = i; j <= n; j += i)
            sieve[j] --;
}

O(n)

O(n \log \log n)

O(n \log n)

O(n^{2})

正确答案C

解析详情

答案 C调和级数；筛法循环复杂度

思路与推导

第一层初始化是 O(n)。双层循环总次数约为 n/1 + n/2 + ... + n/n = n·H_n = O(n log n)。因此整体复杂度为 O(n log n)，选 C。

第 14 题（单选题，2 分）

下面 count_triple 函数的时间复杂度为()。

int gcd(int m, int n) {
    if (m == 0) return n;
    return gcd(n % m, m);
}
int count_triple(int n) {
    int cnt = 0;
    for (int v = 1; v * v * 4 <= n; v++)
        for (int u = v + 1; u * (u + v) * 2 <= n; u += 2)
            if (gcd(u, v) == 1) {
                int a = u * u - v * v;
                int b = u * v * 2;
                int c = u * u + v * v;
                cnt += n / (a + b + c);
            }
    return cnt;
}

O(n^2)

O(n^2 \log n)

O(n \log n)

O(n)

正确答案C

解析详情

答案 C循环计数；欧几里得算法复杂度

思路与推导

v 的范围约到 √n；对每个 v，u 的可选规模近似与 n/v 成反比求和后给出对数因子，且 gcd 调用是对数级。综合主导量可写为 O(n log n)，对应 C。

第 15 题（单选题，2 分）

下列选项中，哪个不可能是下图的深度优先遍历序列（）。

2,3,5,7,8,9,6,4,1

5, 7, 8, 9, 1, 2, 4, 3, 6

6, 8, 9, 5, 7, 1, 2, 3, 4

8, 5, 7, 9, 1, 2, 3, 6, 4

正确答案B

解析详情

答案 B深度优先遍历序列判定；图遍历顺序约束

思路与推导

DFS 序列要求“先一路深入、再回溯”，且每一步都必须沿图中存在的边到达。结合题图检查可知 B 的访问顺序违反了该深入/回溯约束，因此不可能由一次 DFS 产生；其余选项可通过合适邻接访问次序实现。

判断题

第 1 题（判断题，2 分）

C++语言中，表达式 9 && 12 的结果类型为 int、值为 8。

正确答案错误

解析详情

答案错误逻辑与运算；C++ 布尔语义

思路与推导

在 C++ 中，9 && 12 会先按“非零即真”做逻辑与，结果为真，转成整数是 1，不是 8。

第 2 题（判断题，2 分）

C++语言中，在有 int a[10]; 定义的内围内，通过表达式 a[-1] 进行访问将导致编译错误。

正确答案错误

解析详情

答案错误数组越界；编译期与运行期错误

思路与推导

a[-1] 通常不会触发编译错误，因为语法合法；问题是运行时越界访问，行为未定义。

第 3 题（判断题，2 分）

选择排序一般是不稳定的。

正确答案正确

解析详情

答案正确排序稳定性；选择排序

思路与推导

选择排序会把当前最小元素与前面位置交换，可能改变相等元素的相对次序，因此一般是不稳定排序。

第 4 题（判断题，2 分）

C++语言中，float 和 int 类型一般都是 4 字节，因此 float 类型能够表达不同的浮点数值的数量，与 int 类型能够表达不同的整数值的数量是相同的。

正确答案错误

解析详情

答案错误浮点表示；数值离散集合

思路与推导

虽然 float 和 int 常见都占 4 字节，但编码方式不同。float 需分配符号位/指数/尾数，能表示的数值分布与 int 完全不同，数量与范围特性也不等同。

第 5 题（判断题，2 分）

使用 math.h 或 cmath 头文件中的对数函数，表达式 log(256) 的结果类型为 double、值约为 8.0。

正确答案错误

解析详情

答案错误对数函数；自然对数

思路与推导

cmath 中 log(x) 默认是自然对数 ln(x)。log(256)=ln(256)≈5.545，不是 8；8 对应的是以 2 为底的对数。

第 6 题（判断题，2 分）

一棵有N个节点的完全二叉树，则树的深度为 $\lfloor\log_{2}(N)\rfloor+1$ 。()

正确答案正确

解析详情

答案正确完全二叉树深度公式

思路与推导

含 N 个结点的完全二叉树深度为 ⌊log2 N⌋+1，这是完全二叉树按层填充性质的直接结论。

第 7 题（判断题，2 分）

邻接表和邻接矩阵都是图的存储形式。通常，使用邻接表比使用邻接矩阵的时间复杂度更低。

正确答案错误

解析详情

答案错误邻接表与邻接矩阵；时空复杂度

思路与推导

邻接表和邻接矩阵是存储结构，不是绝对“邻接表时间复杂度更低”。不同操作复杂度取决于任务与图密度，例如判边在矩阵是 O(1)，邻接表通常要查找链表/向量。

第 8 题（判断题，2 分）

C++语言中，类的构造函数可以声明为私有（private）。

正确答案正确

解析详情

答案正确访问控制；构造函数

思路与推导

构造函数可以声明为 private，常用于单例或限制对象创建方式（如通过静态工厂函数）。

第 9 题（判断题，2 分）

泛洪算法的递归实现容易造成溢出，因此大的二维地图算法中，一般使用广度优先搜索实现。

正确答案正确

解析详情

答案正确泛洪算法；递归深度；BFS/DFS 实现

思路与推导

递归 DFS 在大图上可能因调用层数过深导致栈溢出；使用队列的 BFS 是迭代实现，通常更稳健，因此工程中常优先采用 BFS 版本。

第 10 题（判断题，2 分）

很多游戏中为玩家设置多种可供学习的技能，要学习特定技能又往往需要先学习1个或以上的前置技能。尽管这样的技能间依赖关系常被玩家称为“技能树”，但它并不一定是树，更可能是有向无环图。

正确答案正确

解析详情

答案正确DAG；依赖关系建模

思路与推导

技能依赖常表现为“前置约束”，允许一个技能有多个前置或被多个技能依赖，这更符合有向无环图而非严格树结构。