2026 年 6 月 GESP C++ 七级真题 · 逐题详解

一、单选题（每题 2 分，共 30 分）

参考答案：B A C D C C D A A C D B B B D

第 1 题

下列 C++ 代码的输出结果是（ ）。

#include<iostream>#include<cmath>usingnamespacestd;intmain(){cout << (int)(sqrt(50) + log2(8));return0;}

• A. 9
• B. 10
• C. 11
• D. 12

答案：B

先分别求出两个函数的值：sqrt(50) 是 50 的平方根，因为 7² = 49、7.1² = 50.41，所以 sqrt(50) ≈ 7.071，是一个 double 类型的浮点数；log2(8) 是以 2 为底 8 的对数，由 2³ = 8 可知 log2(8) = 3.0（同样是 double 类型）。两者相加约为 10.071。接着最外层的 (int) 强制类型转换对这个浮点结果做"向零截断"——即直接丢弃小数部分，而不是四舍五入——10.071 截断后得到 10。因此程序输出 10，选 B。如果误以为强制转换是四舍五入，或者把 sqrt(50) 记成恰好 7，都可能误选其他答案，这道题考察的正是对浮点函数返回值和截断规则的准确把握。

第 2 题

下列关于 <cmath> 或 <math.h> 中的数学库函数的说法，正确的是（ ）。

• A. sqrt(49) 的返回值可以参与浮点运算。
• B. log2(32) 的返回值类型为 int。
• C. pow(2, 5) 的返回值类型一定为 int。
• D. sin(90) 的参数 90 表示 90 度。

答案：A

逐项分析：A 正确——sqrt 的返回类型是 double，一个 double 值当然可以和其他浮点数（或被隐式提升的整数）一起参与浮点运算，比如 sqrt(49) + 0.5 是完全合法的表达式。B 错误——log2 的返回类型同样是 double，即使数学上 log2(32) 恰好等于整数 5，返回值的"类型"依然是 double（5.0），类型和数值是两个概念，不能混为一谈。C 错误——pow 函数的标准原型是 double pow(double, double)，无论传入的实参是不是整数，都会先被隐式转换成 double 再计算，返回值类型是 double 而不是 int；也正因为浮点运算存在精度误差，pow(2, 5) 在某些实现下可能得到 31.999999…，直接强转成 int 会变成 31，这是竞赛中的经典陷阱。D 错误——C/C++ 标准库中所有三角函数的参数一律采用弧度制，sin(90) 里的 90 表示 90 弧度（约等于 14.3 圈多的角度），如果想计算 90 度的正弦值，必须先转换为弧度：sin(90 * PI / 180)。综上选 A。

第 3 题

下列关于 C++ 函数参数传递的说法，正确的是（ ）。

• A. 函数形参一定和实参使用同一块内存。
• B. 值传递时，在函数内修改形参一定会修改实参。
• C. 引用形参绑定到实参后，在函数内修改引用形参通常会影响实参。
• D. 指针形参不能用于修改实参指向的数据。

答案：C

C++ 有三种主要的参数传递方式，它们对内存的处理各不相同。值传递：形参是实参的一份独立拷贝，占用新的内存，函数内对形参的任何修改都只发生在这份拷贝上，与实参无关——所以 B 说"一定会修改实参"恰好说反了，A 说"一定使用同一块内存"也因为值传递的存在而不成立（"一定"这个词太绝对）。引用传递：引用是实参的别名，形参和实参绑定的是同一块内存，函数内通过引用形参做的修改会直接反映到实参上，C 的表述正确。指针传递：指针形参本身是地址的拷贝，但通过解引用操作（*p = 新值）恰恰可以修改实参所指向的那块内存中的数据，这是 C 语言时代就广泛使用的"输出参数"手法，所以 D 说"不能用于修改"完全错误。综上选 C。

第 4 题

有 5 个字符，它们出现的次数分别为 3、4、7、8、9。使用哈夫曼编码时，最小的带权路径长度 WPL 为（ ）。

• A. 62
• B. 64
• C. 67
• D. 69

答案：D

计算 WPL 有一个高效技巧：哈夫曼树构造过程中，每次合并两个最小权值所产生的"新结点权值"，累加起来正好等于 WPL（因为每个叶子的权值会在它到根路径上的每一次合并中被计入一次，累计次数恰好等于它的编码长度）。按此模拟：

• 初始权值集合：3, 4, 7, 8, 9
• 第一次合并最小的 3 和 4，得到新权值 7，累计 7；集合变为 7, 7, 8, 9
• 第二次合并最小的 7 和 7，得到 14，累计 7 + 14 = 21；集合变为 8, 9, 14
• 第三次合并 8 和 9，得到 17，累计 21 + 17 = 38；集合变为 14, 17
• 第四次合并 14 和 17，得到 31，累计 38 + 31 = 69

所有合并权值之和为 69，即 WPL = 69，选 D。也可以用传统方法验证：构造出的哈夫曼树中，3 和 4 的编码长度为 3，7、8、9 的编码长度为 2，WPL = 3×3 + 4×3 + 7×2 + 8×2 + 9×2 = 9 + 12 + 14 + 16 + 18 = 69，两种算法结果一致。

第 5 题

已知网格上每个网格点有一个数字，a[i][j] 表示第 i 行第 j 列处网格点上的数字。若 dp[i][j] 表示从网格左上角（第 0 行第 0 列）走到第 i 行第 j 列时能取得的最大数字和，且每次只能向右或向下移动。对于 i > 0 且 j > 0 的位置，正确的状态转移代码为（ ）。

• A. dp[i][j] = a[i][j] + min(dp[i - 1][j], dp[i][j - 1])
• B. dp[i][j] = max(dp[i - 1][j - 1], dp[i][j])
• C. dp[i][j] = a[i][j] + max(dp[i - 1][j], dp[i][j - 1])
• D. dp[i][j] = a[i][j] + dp[i - 1][j - 1]

答案：C

推导状态转移方程的关键是分析"到达当前状态的所有可能来源"。移动规则限定为只能向右或向下，那么反过来看，要到达位置 (i, j)，上一步只有两种可能：从正上方 (i-1, j) 向下走一步过来，或从正左方 (i, j-1) 向右走一步过来。dp[i][j] 要求"最大数字和"，因此应该在这两个前驱状态的 dp 值中取较大者，再加上当前格子本身的数字 a[i][j]，即 dp[i][j] = a[i][j] + max(dp[i-1][j], dp[i][j-1])，选 C。再看错误项为何错：A 取的是 min，求出来的是"最小数字和"，优化方向与题意相反；B 既没有加上当前格子的值 a[i][j]，前驱位置 (i-1, j-1) 也是对角线方向（本题不允许斜向移动），且拿 dp[i][j] 自己和别人比较逻辑混乱；D 的前驱同样错误地写成了对角线位置 dp[i-1][j-1]，遗漏了真正的两个合法来源。

第 6 题

已知 f[0] = 0，f[1] = 2，并且对 i >= 2 有 f[i] = max(f[i - 1], f[i - 2] + a[i])。若 a[1 .. 5] = {2, 7, 9, 3, 1}，则 f[5] 的值为（ ）。

• A. 10
• B. 11
• C. 12
• D. 22

答案：C

这个递推式是"打家劫舍"模型的标准形式：f[i] 表示考虑前 i 个元素能取得的最大值，每一步要么"不选第 i 个"（继承 f[i-1]），要么"选第 i 个"（此时第 i-1 个不能选，所以是 f[i-2] + a[i]）。先明确下标对应关系：a[1]=2, a[2]=7, a[3]=9, a[4]=3, a[5]=1，然后严格逐步代入：

• f[2] = max(f[1], f[0] + a[2]) = max(2, 0 + 7) = 7 （选了 a[2]=7 更优）
• f[3] = max(f[2], f[1] + a[3]) = max(7, 2 + 9) = 11 （选 a[1] 与 a[3]，2+9=11 更优）
• f[4] = max(f[3], f[2] + a[4]) = max(11, 7 + 3) = 11 （不选 a[4]，维持 11 更优）
• f[5] = max(f[4], f[3] + a[5]) = max(11, 11 + 1) = 12 （f[3]=11 与 a[5]=1 不冲突，可再加 1）

最终 f[5] = 12，选 C。这类手工递推题最容易出错的地方在于下标错位（比如把 a[2] 误当成第一个元素）或跳步心算，稳妥的做法是像上面这样把每一步的两个候选值都写出来再比较。

第 7 题

下面代码是一维数组优化 0/1 背包的核心片段，其中 w[i] 表示第 i 件物品的重量，v[i] 表示第 i 件物品的价值。横线处应填入（ ）。

for (int i = 1; i <= n; i++) {for (int c = W; c >= w[i]; c--) {        __________;    }}

• A. dp[c] = max(dp[c], dp[c + w[i]] + v[i])
• B. dp[c] = min(dp[c], dp[c - w[i]] + v[i])
• C. dp[c] = dp[c - w[i]] + v[i]
• D. dp[c] = max(dp[c], dp[c - w[i]] + v[i])

答案：D

0/1 背包的一维滚动数组写法中，dp[c] 表示背包容量为 c 时能获得的最大价值。处理第 i 件物品时，对每个容量 c 有两种决策：不装物品 i，价值维持原来的 dp[c]；装入物品 i，需要先腾出 w[i] 的容量，价值为 dp[c - w[i]] + v[i]。两者取最大值，即 dp[c] = max(dp[c], dp[c - w[i]] + v[i])，选 D。这里内层循环从 W 递减到 w[i]（从大到小）也与转移方程配套：递减枚举保证计算 dp[c] 时引用的 dp[c - w[i]] 还是"处理上一件物品后"的旧值，物品 i 在本轮中不会被重复使用，这正是 0/1（每件物品至多选一次）的语义。再看错误项：A 中 dp[c + w[i]] 的下标方向反了，c + w[i] 可能超出数组范围，语义上也讲不通（装入物品应该消耗容量而非增加容量）；B 用 min 求的是最小价值，优化方向错误；C 缺少与"不装"情形（原 dp[c]）的比较，等于强制装入每件物品，当装入反而不优时会算出错误答案。

第 8 题

下面程序片段主要体现的算法思想是（ ）。

voiddfs(int x, int y){    vis[x][y] = true;for (int k = 0; k < 4; k++) {int nx = x + dx[k], ny = y + dy[k];if (inside(nx, ny) && a[nx][ny] == 1 && !vis[nx][ny])            dfs(nx, ny);    }}

• A. 泛洪算法
• B. 二分查找
• C. 贪心算法
• D. 归并排序

答案：A

分析代码行为：函数从格子 (x, y) 出发，先把当前格标记为已访问，然后借助方向数组 dx、dy 依次尝试上下左右四个相邻格子，对满足三个条件（在地图范围内、格子值为 1、尚未访问）的邻格递归调用自身。这样一轮递归下来，与起点连通的、值全为 1 的整片区域会被完整地标记一遍——像水从一点漫延开、灌满整个连通区域一样，这正是泛洪填充（Flood Fill）算法的典型递归实现，广泛用于统计连通块数量、图像区域填色、地图分区等场景。选 A。其余选项与代码特征完全不符：二分查找的标志是不断折半缩小区间，贪心算法的标志是每步做局部最优选择，归并排序的标志是分治拆分后合并有序序列，这段代码里都不存在这些结构。

第 9 题

下列关于排序稳定性的说法，正确的是（ ）。

• A. 冒泡排序在只交换相邻逆序元素时是稳定排序
• B. 选择排序一定是稳定排序
• C. 快速排序一定是稳定排序
• D. 稳定排序一定会改变相等元素的相对顺序

答案：A

稳定性的定义是：排序结束后，值相等的元素保持它们在原序列中的先后相对顺序。逐项分析：A 正确——冒泡排序的常规实现只在相邻两个元素严格逆序（左边大于右边）时才交换，两个相等的元素永远不满足交换条件，因此它们的相对位置自始至终不会改变，冒泡排序是稳定的。B 错误——选择排序每轮从未排序区找出最小元素，然后与当前起始位置的元素做一次交换，这个交换是"远距离"的，被换到后面的那个元素可能会跨越若干个与它相等的元素，从而打乱相对顺序（例如序列 5a, 5b, 2 排序后会变成 2, 5b, 5a，两个 5 的顺序颠倒了），所以选择排序通常不稳定，"一定稳定"的说法错误。C 错误——快速排序在划分（partition）过程中同样存在远距离交换，相等元素的相对顺序很容易被破坏，常规实现是不稳定的。D 错误——它把稳定性的定义完全说反了，稳定排序恰恰是"不会改变"相等元素的相对顺序。综上选 A。

第 10 题

无向图的边为 (1, 2), (1, 3), (2, 4), (3, 4), (4, 5)。从顶点 1 开始进行 BFS，每轮根据出队顶点，将与其相邻顶点按编号从小到大入队，则顶点 4 第一次入队时，队列的状态为（ ）。

• A. 1, 2, 3, 4
• B. 2, 3, 4
• C. 3, 4
• D. 3, 4, 5

答案：C

先根据边表整理出每个顶点的邻接关系：顶点 1 的邻居是 {2, 3}，顶点 2 的邻居是 {1, 4}，顶点 3 的邻居是 {1, 4}，顶点 4 的邻居是 {2, 3, 5}，顶点 5 的邻居是 {4}。然后严格模拟 BFS：

1. 起点 1 入队并标记访问，队列 = [1]。
2. 出队 1，检查其邻居 2、3（按编号从小到大）：2 未访问，入队并标记；3 未访问，入队并标记。队列 = [2, 3]。
3. 出队 2，检查其邻居 1、4：1 已访问跳过；4 未访问，入队并标记。——这一刻正是顶点 4 第一次入队的时刻，此时队列中的元素是 [3, 4]（顶点 2 刚刚出队，已不在队列中；顶点 5 还没有被任何顶点扩展到）。

因此答案是 3, 4，选 C。这道题的两个常见误区：一是忘记出队顶点已经离开队列（误选包含 1 或 2 的选项），二是提前把 5 算进去（5 要等到顶点 4 出队时才会入队，此刻还未发生）。

第 11 题

一个长度为 11、下标为 0 到 10 的哈希表采用线性探测法处理冲突，哈希函数为 h(x) = x % 11。依次插入 22、33、4、15、26，则 26 最终存放在下标（ ）。

• A. 0
• B. 4
• C. 5
• D. 6

答案：D

线性探测法的规则是：若哈希函数算出的位置已被占用，就依次检查下一个位置（(pos + 1) % 表长），直到找到空位为止。逐个模拟插入过程：

• 插入 22：h(22) = 22 % 11 = 0，下标 0 为空，放入下标 0。
• 插入 33：h(33) = 33 % 11 = 0，下标 0 已被 22 占用，向后探测下标 1，为空，放入下标 1。
• 插入 4：h(4) = 4 % 11 = 4，下标 4 为空，放入下标 4。
• 插入 15：h(15) = 15 % 11 = 4，下标 4 已被 4 占用，向后探测下标 5，为空，放入下标 5。
• 插入 26：h(26) = 26 % 11 = 4，下标 4 被占（元素 4），探测下标 5 也被占（元素 15），继续探测下标 6，为空，放入下标 6。

所以 26 最终存放在下标 6，选 D。这道题体现了线性探测的"聚集"现象：4、15、26 三个元素的哈希值都是 4，导致它们在表中连成一片（下标 4、5、6），后插入的元素探测路径越来越长。

第 12 题

关于哈希表处理冲突的方法，下列说法正确的是（ ）。

• A. 线性探测法发生冲突后，只能放弃插入该元素。
• B. 链地址法可以把哈希到同一位置的多个元素组织在同一个桶中。
• C. 只要哈希表长度是素数，就一定不会发生冲突。
• D. 开放定址法查找元素时不需要考虑冲突位置。

答案：B

逐项分析：A 错误——线性探测法的设计初衷恰恰是"冲突后不放弃"，它会沿着探测序列（当前位置的下一个、再下一个……）继续寻找空位来安放元素，只有整张表全满时才会插入失败。B 正确——链地址法（拉链法）在哈希表的每个位置上维护一条链表（称为"桶"），所有哈希到同一位置的元素都挂在这个桶的链表中，冲突元素共存而不互相挤占，这是它区别于开放定址法的核心特征。C 错误——把表长设为素数只是让取模结果分布更均匀、减轻聚集的工程技巧，无法从原理上杜绝冲突：只要可能出现的键的数量超过表的槽位数（现实中几乎总是如此），根据鸽笼原理冲突就必然可能发生。D 错误——开放定址法中，元素可能因为冲突而被安置在探测序列的后续位置上，查找时必须从哈希位置出发、沿着与插入时完全相同的探测序列逐个比对，直到找到目标或遇到空位，"不需要考虑冲突位置"恰好与它的工作方式相反。综上选 B。

第 13 题

某算法需要枚举 n 个对象；对每个对象，还需要进行一次二分查找。若二分查找的对象规模也是 n，则该算法的时间复杂度通常为（ ）。

• A. O(n)
• B. O(n log n)
• C. O(n²)
• D. O(log n)

答案：B

分析算法的结构：外层是对 n 个对象的枚举，循环执行 n 次；每次循环内部执行一次规模为 n 的二分查找，单次二分查找每一步都把搜索区间折半，最多折半 log₂n 次就能结束，复杂度为 O(log n)。根据复杂度的乘法法则（外层循环次数 × 内层单次操作代价），总复杂度为 n × log n = O(n log n)，选 B。这种"枚举 + 二分"的组合是竞赛中极其常见的算法框架（如两数之和的排序双元素查找、二分答案套判定等），O(n log n) 是它的标志性复杂度；如果内层换成线性扫描则退化为 O(n²)，可见二分带来的效率提升。

第 14 题

在升序数组中用二分查找第一个大于等于 x 的位置。若当前中点 mid 满足 a[mid] < x，下一步应（ ）。

• A. 令闭区间右边界变为 mid - 1
• B. 令闭区间左边界变为 mid + 1
• C. 立即返回 mid
• D. 交换 a[mid] 与 x

答案：B

目标是找"第一个大于等于 x 的位置"。既然当前 a[mid] < x，结合数组升序的性质可以推出：mid 位置以及 mid 左侧的所有元素都严格小于 x，它们全都不满足"大于等于 x"这个条件，因此答案绝不可能落在 [左边界, mid] 这个范围里，可以放心地把它们整体排除，令左边界收缩为 mid + 1，继续在右半部分查找。选 B。对比错误项：A 是当 a[mid] >= x 时才应该执行的收缩方向（而且那种情况下 mid 本身可能就是答案，通常应写 r = mid 保留候选而不是 mid - 1）；C 直接返回 mid 显然不对，a[mid] 连条件都不满足；D "交换元素"会破坏数组内容，二分查找是只读操作，根本不涉及修改数据。这道题考察的是二分查找中"哪一侧可以被安全排除"的判断逻辑，也是写对二分边界的关键。

第 15 题

在如下网格中，# 表示不能经过的格子，. 表示可以经过的格子。从左上角走到右下角，每次只能向右或向下移动，不同路径共有（ ）条。

. . . . .. # . # .. . . . .# . # . .. . . . .

• A. 5
• B. 6
• C. 7
• D. 8

答案：D

用动态规划计数：设 dp[i][j] 表示从左上角走到第 i 行第 j 列的不同路径数。转移规则为：若 (i, j) 是障碍（#），dp[i][j] = 0；否则 dp[i][j] = dp[i-1][j] + dp[i][j-1]（来自上方与左方的路径数之和，越界视为 0）。起点 dp[0][0] = 1。逐行填表（行列均从 0 计数）：

• 第 0 行全部可通行，且只能一路向右到达：1, 1, 1, 1, 1
• 第 1 行：(1,0)=1（只能从上方来）；(1,1) 是 # 置 0；(1,2) = dp[0][2] + dp[1][1] = 1 + 0 = 1；(1,3) 是 # 置 0；(1,4) = dp[0][4] + dp[1][3] = 1 + 0 = 1。本行：1, 0, 1, 0, 1
• 第 2 行：(2,0) = 1；(2,1) = dp[1][1] + dp[2][0] = 0 + 1 = 1；(2,2) = dp[1][2] + dp[2][1] = 1 + 1 = 2；(2,3) = dp[1][3] + dp[2][2] = 0 + 2 = 2；(2,4) = dp[1][4] + dp[2][3] = 1 + 2 = 3。本行：1, 1, 2, 2, 3
• 第 3 行：(3,0) 是 # 置 0；(3,1) = dp[2][1] + dp[3][0] = 1 + 0 = 1；(3,2) 是 # 置 0；(3,3) = dp[2][3] + dp[3][2] = 2 + 0 = 2；(3,4) = dp[2][4] + dp[3][3] = 3 + 2 = 5。本行：0, 1, 0, 2, 5
• 第 4 行：(4,0) = dp[3][0] + 越界 = 0（注意：虽然 (4,0) 本身是 . 可通行，但它上方是 #、左方越界，没有任何路径能到达它）；(4,1) = dp[3][1] + dp[4][0] = 1 + 0 = 1；(4,2) = dp[3][2] + dp[4][1] = 0 + 1 = 1；(4,3) = dp[3][3] + dp[4][2] = 2 + 1 = 3；(4,4) = dp[3][4] + dp[4][3] = 5 + 3 = 8。本行：0, 1, 1, 3, 8

右下角 dp[4][4] = 8，即共有 8 条不同路径，选 D。填表时特别注意 (4,0) 这类"格子本身可通行但已被障碍彻底切断"的位置，它的 dp 值是 0 而不是 1，漏掉这一点是本题最容易出错的地方。

二、判断题（每题 2 分，共 20 分）

参考答案：✗ ✗ ✗ ✓ ✗ ✓ ✓ ✗ ✓ ✓

第 1 题

使用 cmath 或 math.h 中的三角函数时，角度参数默认采用角度制。

✗ C/C++ 标准数学库中的所有三角函数（sin、cos、tan 及反三角函数等）的参数统一采用弧度制，这是语言标准的规定，没有"默认角度制"一说。如果手头的数据是角度，必须先做单位换算（角度 × π / 180 得到弧度）再传给函数，否则 sin(30) 计算的是 30 弧度（约 4.77 圈处）的正弦值，与 30 度的正弦值 0.5 相去甚远。表述错误。

第 2 题

使用 cmath 或 math.h 中的 pow(2, 10) 计算 2¹⁰ 时，由于参数均为整型 int，返回值类型也为整型 int。

✗ pow 函数的标准原型接收和返回的都是浮点类型（double pow(double, double)）。当传入两个 int 实参时，它们会先经历隐式类型转换变成 double，然后进行浮点运算，返回值类型始终是 double——函数的返回类型由函数原型决定，与调用时实参碰巧是什么类型无关。此外，由于浮点运算的精度问题，pow(2, 10) 在某些平台上可能返回 1023.999999… 这样的近似值，直接截断转 int 会得到 1023 而非 1024，这也是竞赛中整数幂运算推荐用循环累乘或快速幂、避免使用 pow 的原因。表述错误。

第 3 题

0/1 背包使用一维数组优化时，容量从小到大枚举也能保证每件物品最多被选一次。

✗ 一维优化的正确性完全依赖容量的枚举方向。0/1 背包要求容量从大到小枚举：这样更新 dp[c] 时所引用的 dp[c - w[i]] 还保持着"处理上一件物品之后"的旧值，当前物品 i 在这一轮中只会被计入一次。反之，如果容量从小到大枚举，那么小容量的 dp[c - w[i]] 可能已经在本轮被物品 i 更新过（即已经装入了一个物品 i），再用它来更新 dp[c] 就等于第二次装入物品 i——这恰好是"每件物品可选无限次"的完全背包的写法，而不是 0/1 背包。因此"从小到大枚举也能保证最多选一次"的说法错误。

第 4 题

哈希表采用开放定址法时，即使哈希函数设计合理，也仍然可能发生冲突。

✓ 冲突的根源在于"可能出现的键的取值空间"通常远大于"哈希表的槽位数量"，根据鸽笼原理，必然存在两个不同的键被映射到同一个位置的可能性。哈希函数设计得再均匀、再精巧，也只能让键尽量分散、降低冲突发生的频率和聚集程度，而无法在原理上完全消除冲突——这正是为什么每一种哈希表实现都必须配备冲突处理机制（开放定址、链地址等）。表述正确。

第 5 题

同一个图从同一个起点进行深度优先搜索，访问序列一定与邻接点的枚举顺序无关。

✗ DFS 在每个结点处的行为是：按照某种顺序枚举当前结点的邻接点，选中第一个未访问的邻居后立刻深入下去。这意味着邻接点的枚举顺序直接决定了"先走哪条分支"，进而决定了整个访问序列。同一张图、同一个起点，如果邻接点的存储顺序不同（比如邻接表按建边顺序排列，而建边顺序不同；或者一个按编号升序、一个按降序枚举），得到的 DFS 访问序列很可能完全不同。所以"一定无关"的说法错误——DFS 保证的是每个可达结点都被访问一次，但不保证访问顺序唯一。

第 6 题

泛洪算法可以用递归 DFS 实现，但地图很大时可能由于递归层数过深导致调用栈溢出等运行时错误。

✓ 递归实现的泛洪填充，其递归深度取决于连通区域的规模和形状：最坏情况下（比如一整片全部连通的大地图，或蜿蜒的长走廊状区域），递归深度可以达到与格子总数同阶——一张 1000×1000 的全通地图意味着可能上百万层的递归调用。而操作系统给程序分配的调用栈通常只有几 MB，每层递归都要占用栈帧空间，深度过大必然触发栈溢出（Stack Overflow），程序直接崩溃。这正是处理大地图时通常改用"显式栈模拟 DFS"或"BFS 队列"这类不依赖系统调用栈的写法的原因。表述正确。

第 7 题

哈夫曼树中不存在度为 1 的结点。

✓ 回顾哈夫曼树的构造过程：每一步都是取出当前权值最小的两个结点，把它们作为左右孩子合并出一个新的父结点。也就是说，树中每一个内部结点都是由"恰好两个孩子"合并产生的，度必然为 2；叶子结点没有孩子，度为 0。整个构造过程中不存在任何产生"只有一个孩子"结点的步骤，所以哈夫曼树中不可能出现度为 1 的结点。这种"内部结点度全为 2"的二叉树也叫严格二叉树（正则二叉树），它满足"结点总数 = 2 × 叶子数 − 1"的性质。表述正确。

第 8 题

冒泡排序的常见实现是稳定排序，选择排序也是。

✗ 前半句正确：冒泡排序的常见实现只在相邻元素严格逆序时交换，相等元素永远不会被交换，相对顺序得以保持，是稳定排序。但后半句错误：选择排序每一轮在未排序区间找到最小元素后，与区间起始位置的元素做一次交换，这个交换往往跨越多个位置，被换走的那个元素可能越过若干个与它相等的元素，从而破坏相等元素的原有相对顺序（例如 5a, 5b, 2：第一轮最小值 2 与 5a 交换，序列变成 2, 5b, 5a，两个 5 的先后顺序被颠倒）。因此选择排序通常被认为是不稳定的，整句表述错误。

第 9 题

在无权图中从起点执行 BFS 时，某个顶点第一次被访问到的层数等于起点到该顶点经过的最少边数。

✓ BFS 的本质是按"距起点的边数"分层扩展：先访问起点（第 0 层），再访问所有 1 条边可达的顶点（第 1 层），然后是恰好需要 2 条边可达的顶点（第 2 层），依此类推。由于队列先进先出的性质，距离更近的顶点一定先于距离更远的顶点被访问，所以任何顶点第一次被访问时所处的层数，恰好就是从起点到它的最短路径所含的边数。这也是"无权图（或所有边权相等的图）用 BFS 求单源最短路"这一经典结论的理论依据。表述正确。

第 10 题

在二维动态规划中，状态 dp[i][j] 的计算常常依赖其他状态，这些状态的计算必须在完成 dp[i][j] 的计算前完成。

✓ 动态规划的本质是把大问题分解为相互依赖的子问题，并按照依赖关系的拓扑顺序逐个求解。计算 dp[i][j] 时会引用它的前驱状态（例如网格 DP 中的 dp[i-1][j] 和 dp[i][j-1]，区间 DP 中的更短区间等），这些被引用的状态如果尚未计算完成，读到的就是未初始化的垃圾值或错误的中间值，整个递推随之崩塌。因此设计 DP 的循环遍历顺序（先行后列、按区间长度从短到长、按拓扑序等）的核心目的，就是确保"任何状态被使用之前，它已经被正确计算完毕"。表述正确。

三、编程题（每题 25 分，共 50 分）

3.1 编程题 1

试题名称：染色时间限制：1.0 s内存限制：512.0 MB

思路：

第一步是图论建模。题目给出的无向图中每个结点的度数都恰好是 2，且没有重边与自环——这样的图在结构上必然是若干个互不相交的简单环的集合（每个结点恰有两条边，沿任意一条边出发不断"从另一条边离开"，最终必然绕回起点形成环；n 个结点、n 条边、度数全为 2 也从计数上印证了这一点）。

第二步是分析环的染色需求。对一个长度为 L 的环做"相邻结点异色"的染色：如果 L 是偶数，两种颜色 1-2-1-2-… 交替即可完美闭合，2 色足够；如果 L 是奇数，交替染色走到最后一个结点时必然与起点同色冲突，2 色不够，但引入第 3 种颜色（把最后一个结点单独染成第 3 色）就能解决，所以奇环恰好需要 3 色。整张图的答案由"最苛刻"的环决定：所有环都是偶环时答案为 2；只要存在一个奇环，答案就是 3（3 色对任何环都够用，不会更多）。这本质上就是二分图判定——不含奇环的图是二分图，2 色可染。

第三步是代码实现。由于每个结点度数恰为 2，不需要建通用邻接表，用两个数组 a[u]、b[u] 分别记录结点 u 的两个邻居即可。沿环行走时有一个精巧的技巧：已知当前结点 u 和上一个结点 last，下一个结点就是 u 的"另一个邻居"，可以直接用 a[u] + b[u] - last 算出（两个邻居之和减去来路，剩下的就是去路），避免了 if 分支判断。cnt 数组一物两用：既作为访问标记（非 0 即已访问），又记录从环起点出发的步数——绕环一圈回到起点时，cnt[起点] 被最后一步更新为环的长度，据此判断奇偶。对每个未访问结点各走一遍环，整体时间复杂度 O(n)。注意本题是多组数据，每组开始前必须把 a、b、cnt 三个数组在 1..n 范围内完整清零，否则上一组的残留数据会污染本组答案。

#include<iostream>#include<algorithm>usingnamespacestd;int n;int a[100010], b[100010], cnt[100010];voidsolve(){cin >> n;for (int i = 1; i <= n; i++)        a[i] = b[i] = cnt[i] = 0;          // 多组数据，先清空for (int i = 1; i <= n; i++) {int u, v;cin >> u >> v;        b[u] = a[u];                        // 每个结点度数恰为2，用 a、b 存它的两个邻居        a[u] = v;        b[v] = a[v];        a[v] = u;    }bool flag = false;                      // 是否存在奇环for (int i = 1; i <= n; i++) {if (cnt[i])continue;                       // 已在之前的环中访问过int u = i, last = a[u];int v = a[u] + b[u] - last;         // "两邻居之和减去来路"得到前进方向while (!cnt[v]) {            cnt[v] = cnt[u] + 1;            // 记录步数，兼作访问标记            last = u;            u = v;            v = a[u] + b[u] - last;        }if (cnt[i] % 2 != 0)                // 走回起点时 cnt[i] 恰为环长            flag = true;    }if (flag)cout << 3 << endl;elsecout << 2 << endl;}intmain(){int t;cin >> t;while (t--)        solve();return0;}

3.2 编程题 2

试题名称：消消乐时间限制：1.0 s内存限制：512.0 MB

思路：

每次删除一个元素，得分是"删除那一刻它左右两侧邻居之和"——由于删除会让原本不相邻的元素变成邻居，删除顺序不同，同一个元素被删时的邻居也不同，总分随之变化，这正是区间 DP 的典型信号，思考方式与经典的"戳气球"问题完全同构。

正向思考"先删谁"是行不通的：删掉一个元素后数组结构改变，剩余部分不再是原数组的连续区间，子问题无法用简单的区间参数描述。正确的做法是反过来枚举"区间内最后被删除的元素"。定义 f[l][r] 表示把原数组中区间 [l, r] 的所有元素全部删除所能获得的最大总分，并附带一个隐含约定：在删除 [l, r] 的整个过程中，区间外侧紧邻的 a[l-1] 和 a[r+1] 始终存在、从未被删。

在这个定义下枚举 [l, r] 中最后被删除的元素位置 k：既然 k 是最后一个被删的，那么删除它时，[l, k-1] 和 [k+1, r] 早已删空，k 的左邻居正是 a[l-1]、右邻居正是 a[r+1]，这一步贡献 a[l-1] + a[r+1] 分。再看两个子问题是否与定义自洽：删除子区间 [l, k-1] 的整个过程中，位置 k 的元素一直健在（它要留到最后），所以 [l, k-1] 的"右侧外邻居"恰好是 a[k]，同时其"左侧外邻居"是 a[l-1]，完全符合 f[l][k-1] 的定义；f[k+1][r] 同理（左外邻是 a[k]，右外邻是 a[r+1]）。于是得到转移方程：

f[l][r] = max over k∈[l,r] of ( f[l][k-1] + f[k+1][r] + a[l-1] + a[r+1] )

按区间长度从 1 到 n 递增枚举（保证计算长区间时所有更短的子区间已算好），最终答案是 f[1][n]。两个实现细节：其一，a 声明为全局数组，a[0] 和 a[n+1] 自动初始化为 0，恰好实现了题目"邻居不存在时视为 0"的规定，同时也让 k = l 时引用的 f[l][l-1]、k = r 时引用的 f[k+1][r]（即 f[r+1][r]）这类空区间自然取值 0，无需任何特判；其二，单个元素最大 10⁹，n 最大 100，每次删除最多得约 2×10⁹ 分，总分可达 2×10¹¹ 量级，远超 int 上限（约 2.1×10⁹），f 数组必须声明为 long long，否则会溢出出错。三重循环的时间复杂度为 O(n³)，n ≤ 100 时约 10⁶ 次运算，轻松通过。

以样例 1 验证：a = {1, 6, 3, 2, 9, 1}，最优策略下依次删除中间元素让大数字尽量多次充当"邻居"被计分，最大总分为 55，与样例输出一致。

#include<iostream>#include<algorithm>usingnamespacestd;int n;int a[110];                 // 全局数组，a[0] 与 a[n+1] 自动为 0，天然处理边界longlong f[110][110];      // 分数总和可能超出 int，必须用 long longintmain(){cin >> n;for (int i = 1; i <= n; i++)cin >> a[i];for (int i = 1; i <= n; i++)                        // i 为区间长度，从小到大枚举for (int l = 1, r = i; r <= n; l++, r++)        // 枚举所有长度为 i 的区间 [l, r]for (int k = l; k <= r; k++)                // 枚举区间内最后被删除的元素 k                f[l][r] = max(f[l][r], f[l][k - 1] + f[k + 1][r] + a[l - 1] + a[r + 1]);cout << f[1][n] << endl;return0;}

四、知识点分类汇总：这套七级卷子各考点考了几道？

一句话看懂这张表：

• 七级相比六级，考点重心从"面向对象 + 二叉树"转移到了"动态规划 + 搜索（DFS/BFS）+ 哈希表"三大板块，这三块合计 14 道题，占了单选和判断总数的一半以上，标志着七级全面进入算法竞赛的核心内容区；
• 动态规划是第一大考点（6 道），覆盖网格路径最大和、打家劫舍递推、0/1 背包一维优化的枚举方向、带障碍路径计数、DP 计算顺序等多个角度，尤其"一维背包为什么必须逆序枚举"这种原理性辨析题，是七级区别于六级最典型的"能力台阶"；
• 哈希表作为新数据结构首次成规模出现（3 道），线性探测的手工模拟和链地址法的原理辨析都需要真正理解冲突处理机制，而不是死记概念；
• 搜索板块从"会写遍历"升级为理解 DFS 访问序列与枚举顺序的关系、递归深度与栈溢出的工程隐患、BFS 层数与最短路的等价性等更深层的性质；
• 编程题难度跃升明显：第一题需要"度数全为 2 ⇒ 图为环的并集 ⇒ 奇环判定（二分图）"的完整图论推理链，第二题则是与"戳气球"同构的区间 DP，两题都要求先完成抽象建模再落实编码，纯套模板已经不够用了。

也就是说，七级想稳过，重心要放在动态规划的经典模型与实现细节（背包枚举方向、网格 DP、状态依赖顺序）、图的搜索与性质（DFS/BFS 的行为特征、泛洪填充、二分图与奇环）、哈希表的冲突处理机制这三块，同时要开始训练"从题目条件推出图论/DP 模型"的建模能力，这是迈向 CSP 提高组的关键一步。