山东大学软件学院人工智能直博预推免机试模拟卷（1）

这套题重点补双指针 二分查找 DFS / BFS 连通块 0/1 背包 字符串动态规划不属于官方真题是按预推免机试常见难度设计的模拟题。C1. 最长无重复字符子串题目描述给定一个字符串 s请求出其中不含重复字符的最长连续子串长度。输入格式输入一个字符串 s。输出格式输出最长无重复字符子串的长度。示例输入abcabcbb输出3解释最长无重复子串是 abc长度为 3。考点双指针 滑动窗口 哈希记录参考代码#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); string s; cin s; vectorint lastPosition(256, -1); int left 0; int answer 0; for (int right 0; right (int)s.size(); right) { char ch s[right]; if (lastPosition[ch] left) { left lastPosition[ch] 1; } lastPosition[ch] right; answer max(answer, right - left 1); } cout answer \n; return 0; }C2. 第一个大于等于目标值的位置题目描述给定一个长度为 n 的升序数组以及 q 次查询。每次查询给定一个整数 x请输出数组中第一个大于等于 x 的元素位置。如果不存在这样的元素输出-1。数组下标从 1 开始。输入格式第一行输入 n 和 q。第二行输入 n 个升序整数。接下来 q 行每行输入一个整数 x。输出格式每次查询输出一行答案。示例输入5 4 1 3 5 7 9 4 5 10 1输出3 3 -1 1考点二分查找 lower_bound 边界处理参考代码#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, q; cin n q; vectorint a(n 1); for (int i 1; i n; i) { cin a[i]; } while (q--) { int x; cin x; int left 1; int right n; int answer -1; while (left right) { int mid left (right - left) / 2; if (a[mid] x) { answer mid; right mid - 1; } else { left mid 1; } } cout answer \n; } return 0; }C3. 岛屿数量题目描述给定一个 n × m 的地图。地图中1 表示陆地 0 表示海洋上下左右相邻的陆地属于同一个岛屿。请输出地图中岛屿的数量。输入格式第一行输入 n 和 m。接下来 n 行每行输入一个长度为 m 的字符串只包含0和1。输出格式输出岛屿数量。示例输入4 5 11000 11000 00100 00011输出3考点DFS BFS 连通块 矩阵搜索参考代码#include bits/stdc.h using namespace std; int n, m; vectorstring grid; vectorvectorint visited; int dx[4] {1, -1, 0, 0}; int dy[4] {0, 0, 1, -1}; void dfs(int x, int y) { visited[x][y] 1; for (int k 0; k 4; k) { int nx x dx[k]; int ny y dy[k]; if (nx 0 || nx n || ny 0 || ny m) continue; if (visited[nx][ny]) continue; if (grid[nx][ny] 0) continue; dfs(nx, ny); } } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin n m; grid.resize(n); visited.assign(n, vectorint(m, 0)); for (int i 0; i n; i) { cin grid[i]; } int answer 0; for (int i 0; i n; i) { for (int j 0; j m; j) { if (grid[i][j] 1 !visited[i][j]) { answer; dfs(i, j); } } } cout answer \n; return 0; }C4. 0/1 背包问题题目描述有 n 件物品和一个容量为 W 的背包。第 i 件物品的重量为weight[i]价值为value[i]。每件物品最多只能选择一次。请问在不超过背包容量的前提下能够获得的最大价值是多少输入格式第一行输入 n 和 W。接下来 n 行每行输入两个整数weight value输出格式输出最大价值。示例输入4 5 1 2 2 4 3 4 4 5输出8解释选择第 2 件和第 3 件物品总重量为 5总价值为 8。考点动态规划 0/1 背包 空间优化参考代码#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, W; cin n W; vectorint dp(W 1, 0); for (int i 1; i n; i) { int weight, value; cin weight value; for (int j W; j weight; j--) { dp[j] max(dp[j], dp[j - weight] value); } } cout dp[W] \n; return 0; }C5. 最长公共子序列题目描述给定两个字符串 a 和 b请求出它们的最长公共子序列长度。子序列不要求连续但要求相对顺序一致。输入格式第一行输入字符串 a。第二行输入字符串 b。输出格式输出最长公共子序列长度。示例输入abcde ace输出3解释最长公共子序列是 ace长度为 3。考点字符串动态规划 二维 DP 经典 LCS 问题参考代码#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); string a, b; cin a b; int n a.size(); int m b.size(); vectorvectorint dp(n 1, vectorint(m 1, 0)); for (int i 1; i n; i) { for (int j 1; j m; j) { if (a[i - 1] b[j - 1]) { dp[i][j] dp[i - 1][j - 1] 1; } else { dp[i][j] max(dp[i - 1][j], dp[i][j - 1]); } } } cout dp[n][m] \n; return 0; }这套卷的复习价值这套 C 卷主要补 A、B 卷没有完全覆盖的几个高频点C1滑动窗口处理字符串连续区间问题 C2二分查找考察边界和模板稳定性 C3DFS 连通块图搜索基础 C40/1 背包经典动态规划 C5LCS字符串动态规划对于保研机试来说最容易翻车的不是不会难算法而是二分边界写错 DFS 没有 visited 背包循环方向写反 字符串 DP 下标错一位 题目读错“连续”和“不连续”。这 5 道题刚好专门训练这些坑。