GESP2026年6月认证C++七级( 第一部分选择题（8-15））精讲

。

第8题 DFS算法思想

1、题目代码：

void dfs(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

2、第一步：先看函数名字

dfs(...)

DFS

就是

Depth First Search（深度优先搜索）

3、第二步：看看程序在干什么

（1）它先把当前位置标记

vis[x][y]=true;

表示

"我已经来过这里了。"

（2）然后四个方向

for(int k=0;k<4;k++)

分别尝试

上 下 左 右

（3）如果满足

inside(...)

说明没有越界。

（4）再判断

a[nx][ny]==1

说明可以走。

（5）再判断

!vis[nx][ny]

说明没有访问过。

（6）于是继续递归。

dfs(nx,ny);

4、整个过程像什么？

想象一桶蓝色油漆。

倒在地图一个格子。

蓝色不断向四周蔓延。

□□□□□ □■■■□ □■■■□ □■■■□ □□□□□

一直扩散。

直到不能扩散。

这就是

Flood Fill（泛洪算法）

因此

答案A。

5、为什么其它错？

（1）B 、二分查找

二分应该看到

mid l r

这里没有。

（2）C 贪心

贪心会不断选择当前最优。

这里完全没有。

（3）D 归并排序

归并排序一定有

分治 merge()

这里没有。

第9题 排序稳定性

答案：

A、冒泡排序在只交换相邻逆序元素时是稳定排序

1、什么叫稳定排序？

假设有两个学生

小王 90 小李 90

原来顺序

小王 ↓ 小李

排序以后

仍然

小王 ↓ 小李

那么就是

稳定排序。

2、看四个选项

（1）A选项

冒泡排序

如果只交换

相邻逆序元素

例如

4 3

才交换。

相等

5 5

不会交换。

因此

相等元素顺序保持。

稳定。

所以A正确。

（2）B选项

选择排序

每次直接交换最小值。

例如

5a 4 5b

交换后

4 5b 5a

两个5顺序变了。

所以

选择排序

不稳定。

（3）C选项

快速排序

快速排序交换很多元素。

相等元素位置可能变化。

因此

不稳定。

（4）D选项

稳定排序

恰恰是

不会改变

相等元素顺序。

所以D完全说反了。

3、常考排序稳定性

第10题 BFS

答案：

C、3, 4

1、看图

1 ├── 2 │ │ │ | │ │ 3── 4 │ 5

2、开始

队列

1

（1）第一步

弹出1

加入

2 3

队列

2 3

（2）第二步

弹出2

2连接

4

于是

加入4

队列变成

3 4

（3）这就是

4第一次进入队列

因此答案

C。

3、有的同学容易写成

2 3 4

但是题目说的是

根据出队顶点

即

2已经出队了。

所以正确队列

3 4

第11题 哈希

答案：

D、6

1、哈希函数

h(x)=x%11

2、模拟操作：

（1）插入22

22%11=0

放0

0

（2）插入33

33%11=0

冲突。

线性探测。

去1。

放1。

（3）插入4

4

放4。

（4）插入15

15%11=4

冲突。

去5。

放5。

（5）插入26

26%11=4

4占了。

5占了。

继续

6空。

放6。

（6）因此答案

D。

3、线性探测口诀

冲突以后

+1 +1 +1 …… 直到空位

第12题 哈希冲突

答案：

B

1、链地址法

就是

一个桶

里面放很多元素。

2、例如

桶3 ↓ 22 ↓ 33 ↓ 44

都可以。

因此

B正确。

3、其它为什么错？

（1）选项A

冲突当然还能继续插。

错误。

（2）选项C

再好的哈希

也可能冲突。

例如

11 22

都会到0。

（3）选项D

开放定址法

查找必须沿探测序列继续找。

否则找不到。

第13题 时间复杂度

答案：

B、O(nlogn)

1、题目说

（1）枚举

n

个对象。

每个对象

做一次

二分。

（2）枚举

O(n)

（3）二分

O(logn)

2、总复杂度

就是乘法。

n × logn

即

O(nlogn)

答案B。

3、时间复杂度口诀

（1）连续执行

+

（2）嵌套循环

×

（3）所以

n × logn

第14题 二分查找

答案：

B、令闭区间左边界变为mid + 1

1、看题目

找

第一个 ≥x

（1）假设

1 3 5 7 9

找

6

（2）现在

mid

等于5。

5<6

说明

5太小。

以及

左边全部都太小。

因此

全部不要。

左边界移动。

l=mid+1;

（3）答案

B。

2、为什么？

（1）因为

mid 都不够。 不包含mid

（2）所以

答案一定在

右边

3、二分四大模板

第15题 网格DP

答案：

D、8

1、看地图

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

（1）其中

#

不能走。

（2）只能

↓ →

（3）这是标准

网格路径计数DP

2、状态定义：

dp[i][j] 表示走到这里的方法数

3、状态转移：

dp[i][j] = 上面的路径数 + 左边路径数

即

dp[i][j]=dp[i-1][j]+dp[i][j-1];

4、遇到障碍

#

直接

dp=0

逐格计算完整张DP表后，可以得到终点路径总数，对应选项D。

第一部分（8～15题）知识点总结

这一组题目基本涵盖了DFS、BFS、哈希、排序、二分、动态规划。其中第10题（BFS队列变化）、第14题（二分边界）、第15题（网格DP）是考试中最容易失分的题型，建议重点掌握。