。第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. 归并排序答案A2、第一步先看函数名字dfs(...)DFS就是Depth First Search深度优先搜索3、第二步看看程序在干什么1它先把当前位置标记vis[x][y]true;表示我已经来过这里了。2然后四个方向for(int k0;k4;k)分别尝试上 下 左 右3如果满足inside(...)说明没有越界。4再判断a[nx][ny]1说明可以走。5再判断!vis[nx][ny]说明没有访问过。6于是继续递归。dfs(nx,ny);4、整个过程像什么想象一桶蓝色油漆。倒在地图一个格子。蓝色不断向四周蔓延。□□□□□ □■■■□ □■■■□ □■■■□ □□□□□一直扩散。直到不能扩散。这就是Flood Fill泛洪算法因此答案A。5、为什么其它错1B 、二分查找二分应该看到mid l r这里没有。2C 贪心贪心会不断选择当前最优。这里完全没有。3D 归并排序归并排序一定有分治 merge()这里没有。第9题 排序稳定性答案A、冒泡排序在只交换相邻逆序元素时是稳定排序1、什么叫稳定排序假设有两个学生小王 90 小李 90原来顺序小王 ↓ 小李排序以后仍然小王 ↓ 小李那么就是稳定排序。2、看四个选项1A选项冒泡排序如果只交换相邻逆序元素例如4 3才交换。相等5 5不会交换。因此相等元素顺序保持。稳定。所以A正确。2B选项选择排序每次直接交换最小值。例如5a 4 5b交换后4 5b 5a两个5顺序变了。所以选择排序不稳定。3C选项快速排序快速排序交换很多元素。相等元素位置可能变化。因此不稳定。4D选项稳定排序恰恰是不会改变相等元素顺序。所以D完全说反了。3、常考排序稳定性排序稳定吗冒泡✅插入✅归并✅选择❌快速❌堆排序❌第10题 BFS答案C、3, 41、看图1 ├── 2 │ │ │ | │ │ 3── 4 │ 52、开始队列11第一步弹出1加入2 3队列2 32第二步弹出22连接4于是加入4队列变成3 43这就是4第一次进入队列因此答案C。3、有的同学容易写成2 3 4但是题目说的是根据出队顶点即2已经出队了。所以正确队列3 4第11题 哈希答案D、61、哈希函数h(x)x%112、模拟操作1插入2222%110放002插入3333%110冲突。线性探测。去1。放1。3插入44放4。4插入1515%114冲突。去5。放5。5插入2626%1144占了。5占了。继续6空。放6。6因此答案D。3、线性探测口诀冲突以后1 1 1 …… 直到空位第12题 哈希冲突答案B1、链地址法就是一个桶里面放很多元素。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 11、看题目找第一个 ≥x1假设1 3 5 7 9找62现在mid等于5。56说明5太小。以及左边全部都太小。因此全部不要。左边界移动。lmid1;3答案B。2、为什么1因为mid 都不够。 不包含mid2所以答案一定在右边3、二分四大模板寻找目标mid满足条件后第一个≥xlmid1当a[mid]x第一个xlmid1当a[mid]x最后一个≤xrmid-1当a[mid]x最后一个xrmid-1当a[mid]x第15题 网格DP答案D、81、看地图. . . . . . # . # . . . . . . # . # . . . . . . .1其中#不能走。2只能↓ →3这是标准网格路径计数DP2、状态定义dp[i][j] 表示走到这里的方法数3、状态转移dp[i][j] 上面的路径数 左边路径数即dp[i][j]dp[i-1][j]dp[i][j-1];4、遇到障碍#直接dp0逐格计算完整张DP表后可以得到终点路径总数对应选项D。第一部分815题知识点总结题号知识点考试重点8DFS、Flood Fill四方向搜索、递归、访问标记9排序稳定性稳定排序与不稳定排序的区别10BFS队列变化过程、首次入队时机11哈希表线性探测法处理冲突12哈希冲突链地址法、开放定址法13时间复杂度O(nlogn)的推导14二分查找四大边界模板15网格动态规划路径计数、障碍物处理这一组题目基本涵盖了DFS、BFS、哈希、排序、二分、动态规划。其中第10题BFS队列变化、第14题二分边界、第15题网格DP是考试中最容易失分的题型建议重点掌握。