四川大学—计算机考研机试真题
- 2026-11-02 02:50:00
考点分析
真题详解
单链表节点交换
问题描述
输入一个单链表，依次交换前2个数，第3、4个数，第5、6个数，…，以此类推，直到操作完整个链表。
如果链表长度是奇数，则最后一个数不用操作。
输出交换之后的链表。
输入格式
第一行包含整数 n，表示节点数量。
第二行包含 n 个整数，表示每个节点的值。
输出格式
共一行，输出交换后的链表。
数据范围
1≤n≤100,
节点取值范围 [1,100]。
输入样例
5
1 2 3 4 5
输出样例
2 1 4 3 5
思考
使用虚拟头节点 dummy，每次处理两个节点：
first = prev->next
second = first->next
将 first 和 second 交换
如果后面还有节点，继续处理下一组
如果链表长度为奇数，最后一个节点因为不满足 prev->next->next != nullptr，会自动保持不变。
时间复杂度O(n)
空间复杂度O(n)
代码
#include<bits/stdc++.h>using namespace std;intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);int N;cin >> N;vector<int> a(N);int mx = 0;for (int i = 0; i < N; ++i) {cin >> a[i];mx = max(mx, a[i]);}// 从最高层向下逐层输出for (int h = mx; h >= 1; --h) {string line;for (int i = 0; i < N; ++i) {if (i > 0) line += ' '; // 列与列之间一个空格line += (a[i] >= h ? '*' : ' '); // 当前列高度足够则画 *}// 去掉行尾多余空格while (!line.empty() && line.back() == ' ') {line.pop_back();}cout << line << '\n';}return 0;}
输出柱状图
问题描述
根据输入的数据对应用‘*’打印出柱状图。
输入格式
第一行包含一个整数 N。
第二行包含 N 个整数 a1,a2,…,aN。
输出格式
按照样例格式输出柱状图。
数据范围
1≤N≤10,
0≤ai≤5
输入样例
3
3 1 2
输出样例
*
* *
* * *
思考
先找出所有柱子的最大高度 mx。
从最高层 mx 开始，逐层向下打印到第 1 层。
对于每一层：
依次检查每一列；
如果该列高度 a[i] >= 当前层 h，输出 *，否则输出空格；
列与列之间输出一个空格；
最后去掉行尾多余空格。
如果所有高度都是 0，则没有任何一层需要输出。
代码
#include<bits/stdc++.h>using namespace std;intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);int N;cin >> N;vector<int> a(N);int mx = 0;for (int i = 0; i < N; ++i) {cin >> a[i];mx = max(mx, a[i]);}// 从最高层向下逐层输出for (int h = mx; h >= 1; --h) {string line;for (int i = 0; i < N; ++i) {if (i > 0) line += ' '; // 列与列之间一个空格line += (a[i] >= h ? '*' : ' '); // 当前列高度足够则画 *}// 去掉行尾多余空格while (!line.empty() && line.back() == ' ') {line.pop_back();}cout << line << '\n';}return 0;}
不甘心的皇后
问题描述
皇后是国际象棋里最厉害的角色。
随着社会的不断发展，越来越多的人们意识到皇后在国际象棋里的地位应该降低，这样国际象棋才会更公平，更有意思。
在传统的棋盘上，皇后能在任意的方向(横,竖,斜)上移动任意的步数。
新的国际象棋规定，皇后在竖直方向上还是可以移动任意的步数，但在除此之外的其他方向上（水平和对角），她只能像国王一样移动一格。
但皇后们并不罢休，即使他们被剥夺了的某些权利，她们也要想办法联合起来，即每个皇后都能被同伴支援保护。
在每个棋盘上，我们在每一列上放一个皇后。
正如前面所说，棋盘上所有的皇后都想要联合起来，也就是说，每两个相邻列的皇后之间的行距离最多只能差一格，这样才可以及时互相支援（下图给出了四个例子，前三个是正确的，最后一个是错误的）。
现在我们给出棋盘的大小和初始状态，你能计算出一共有多少种不同的放置皇后的方法使得所有的皇后都能联合起来吗？
输入格式
本题包括不超过 100组测试数据。
每组数据的第一行包含一个整数 n，代表一个 n×n的棋盘。
接下来的一行包括 n个整数。代表初始时每列已有的皇后的位置：如果这个值为 i
，则代表在这一列上，由上向下数第 i 个格子已经放了皇后；如果这个值为 0，代表这一列还没有皇后，这时你可以在满足题目要求的情况下把一个皇后放在这一列的任意位置。
当 n=0时输入结束，这组数据不包括在需要计算的数据中。
输出格式
对于每一组输入数据，输出一个整数，代表在这种情况下符合条件的放置皇后的方法种数。输出 0代表无法满足条件。
数据范围
n在[1,10]
输入样例
8
0 0 0 0 0 0 0 0
4
1 2 0 3
4
1 2 3 4
4
1 3 2 4
0
输出样例
11814
2
1
0
思考
令 dp[i][r] 表示第 i 列皇后放在第 r 行时的合法方案数。
第 0 列：
如果 a[0] == 0，则第 0 列可以放在任意行，dp[0][r] = 1；
否则只能放在固定行 a[0]，dp[0][a[0]] = 1。
对于第 i 列：
如果该列已经有皇后，即 a[i] != 0，则只能考虑 r = a[i]；
否则考虑所有行 r。
转移条件为相邻列行号差最多为 1，即上一列只能放在 r-1, r, r+1 行。
最后把最后一列所有行的方案数相加。
时间复杂度：O(n^2) 每组数据，n ≤ 10
空间复杂度：O(n^2)
代码
#include<bits/stdc++.h>using namespace std;intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);int n;while (cin >> n && n != 0) {vector<int> a(n);for (int i = 0; i < n; ++i) {cin >> a[i];}// dp[i][r] 表示第 i 列皇后放在第 r 行时的方案数// 行编号从 1 到 nvector<vector<long long>> dp(n, vector<long long>(n + 1, 0));// 初始化第 0 列for (int r = 1; r <= n; ++r) {if (a[0] == 0 || a[0] == r) {dp[0][r] = 1;}}// 逐列转移for (int i = 1; i < n; ++i) {for (int r = 1; r <= n; ++r) {// 如果当前列已经固定，则只能放在指定行if (a[i] != 0 && a[i] != r) {continue;}// 相邻列行号差最多为 1for (int prev = max(1, r - 1); prev <= min(n, r + 1); ++prev) {dp[i][r] += dp[i - 1][prev];}}}// 统计最后一列所有可能行的方案数long long ans = 0;for (int r = 1; r <= n; ++r) {ans += dp[n - 1][r];}cout << ans << '\n';}return 0;}
分解质因数
问题描述
给定一个正整数 n，如果它不是质数，则请你将它分解质因数，并以乘积的形式的输出。
输入格式
输入包含不超过 100组测试数据。
每组数据占一行，包含一个正整数 n。
输出格式
对于每组数据，如果给定的 n是质数，则跳过即可，无需任何输出，否则输出一行结果，将质因数按从小到大的顺序，以乘积的形式的输出。
数据范围
n在[2,10000]
输入样例
10
90
输出样例
2*5
2*3*3*5
思路
对每组输入的 n，先判断它是否为质数。
如果 n 是质数，则直接跳过，不输出任何内容。
如果 n 不是质数，则从 2 开始试除，分解出所有质因数。
将质因数按从小到大的顺序保存，最后用 * 连接输出。
复杂度
质数判断：O(√n)
质因数分解：O(√n)
代码
#include<bits/stdc++.h>using namespace std;boolisPrime(int n){if (n < 2) return false;for (int i = 2; i * i <= n; ++i) {if (n % i == 0) return false;}return true;}intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);int n;while (cin >> n) {// 如果是质数，跳过不输出if (isPrime(n)) continue;vector<int> factors;int x = n;for (int i = 2; i * i <= x; ++i) {while (x % i == 0) {factors.push_back(i);x /= i;}}if (x > 1) {factors.push_back(x);}// 按乘积形式输出for (int i = 0; i < (int)factors.size(); ++i) {if (i > 0) cout << '*';cout << factors[i];}cout << '\n';}return 0;}
极大连通图个数
问题描述
给定一个 n×m的字符矩阵，矩阵由 . 和 w 组成，请你计算 w能组成的极大连通图个数。
斜着相邻也算连通（八个方向相邻都算连通）。
输入格式
第一行包含 n,m。
接下来 n 行，每行 m个字符，表示矩阵。
输出格式
一个整数，表示 w能组成的极大连通图个数。
数据范围
n,m在[1,100]
输入样例
5 10
..w.....ww
.ww..wwwww
.w...w....
..wwww.www
..wwww.www
输出样例
2
思考
遍历整个矩阵：
遇到一个未被访问过的 w，说明发现了一个新的极大连通块，答案加一；
从该位置开始进行 BFS 或 DFS，向八个方向扩展；
把所有相连的 w 都标记为已访问，避免重复计数。
这里直接把访问过的 w 修改成 .，省去额外的 visited 数组。
复杂度
时间复杂度：O(n * m)
空间复杂度：O(n * m)，最坏情况下队列中存放整个矩阵的节点。
代码
#include<bits/stdc++.h>using namespace std;intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);int n, m;cin >> n >> m;vector<string> g(n);for (int i = 0; i < n; ++i) {cin >> g[i];}// 八个方向int dx[8] = {-1, -1, -1, 0, 0, 1, 1, 1};int dy[8] = {-1, 0, 1, -1, 1, -1, 0, 1};int ans = 0;for (int i = 0; i < n; ++i) {for (int j = 0; j < m; ++j) {if (g[i][j] == 'w') {++ans;// BFS 遍历当前连通块queue<pair<int, int>> q;q.push({i, j});g[i][j] = '.'; // 标记为已访问while (!q.empty()) {auto [x, y] = q.front();q.pop();for (int k = 0; k < 8; ++k) {int nx = x + dx[k];int ny = y + dy[k];if (nx >= 0 && nx < n && ny >= 0 && ny < m && g[nx][ny] == 'w') {g[nx][ny] = '.';q.push({nx, ny});}}}}}}cout << ans << '\n';return 0;}
特别的除法
问题描述
输入正整数 a,b,c，输出 a/b小数形式,精确到小数点后 c位。
输入格式
共一行，包含三个整数 a,b,c。
输出格式
一个实数，表示结果。
数据范围
1≤a,b≤10^8,
2≤c≤1000
输入样例
2 3 6
输出样例
0.666667
思考
模拟手算长除法：
先求出整数部分 a / b 和余数 a % b。
每次将余数乘以 10，得到当前小数位，再更新余数，重复 c 次。
再计算第 c + 1 位，用来判断是否需要四舍五入。
如果第 c + 1 位大于等于 5，则从最后一位开始向前进位；如果所有小数位都变成 0 并继续进位，则整数部分加 1。
最后输出整数部分、小数点以及 c 位小数。
复杂度
时间复杂度：O(c)
空间复杂度：O(c)
由于 c ≤ 1000，使用 vector<int> 保存每一位小数即可，不会溢出，也能保证精度。
代码
#include<bits/stdc++.h>using namespace std;intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);long long a, b;int c;cin >> a >> b >> c;// 整数部分和余数long long integerPart = a / b;long long rem = a % b;// 计算小数点后 c 位vector<int> digits(c);for (int i = 0; i < c; ++i) {rem *= 10;digits[i] = rem / b;rem %= b;}// 根据第 c + 1 位决定是否四舍五入rem *= 10;int nextDigit = rem / b;if (nextDigit >= 5) {int i = c - 1;while (i >= 0) {if (digits[i] < 9) {++digits[i];break;} else {digits[i] = 0;--i;}}// 如果所有小数位都进位了，整数部分加 1if (i < 0) {++integerPart;}}// 输出结果cout << integerPart << '.';for (int d : digits) {cout << d;}cout << '\n';return 0;}
求矩阵的鞍点
问题描述
给定一个 n×m的整数矩阵，行的编号为 1∼n，列的编号为 1∼m，求矩阵中的所有鞍点。
鞍点，即该位置上的元素在该行上最大，在该列上最小。
有可能有多个鞍点，也可能没有鞍点。
输入格式
第一行包含两个整数 n,m。
接下来 n 行，每行包含 m个整数。
输出格式
输出所有鞍点的坐标和值。
输出优先级，整体从上到下，同行从左到右。
如果不存在鞍点，则输出 NO。
数据范围
1≤n,m<10,
矩阵元素取值范围 [1,9]。
输入样例
3 4
1 2 3 4
1 2 3 4
1 2 3 4
输出样例
1 4 4
2 4 4
3 4 4
思考
先统计每一行的最大值 rowMax[i] 和每一列的最小值 colMin[j]。
再次遍历矩阵，若某个元素同时满足：
等于所在行的最大值；
等于所在列的最小值；
则它就是一个鞍点。
按照从上到下、同一行从左到右的顺序输出所有鞍点的坐标和值。
如果没有任何鞍点，输出 NO。
复杂度
时间复杂度：O(n × m)
空间复杂度：O(n × m)（存储矩阵），另有 O(n + m) 的辅助数组。
代码
#include<bits/stdc++.h>using namespace std;intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);int n, m;cin >> n >> m;vector<vector<int>> a(n, vector<int>(m));for (int i = 0; i < n; ++i) {for (int j = 0; j < m; ++j) {cin >> a[i][j];}}// 每一行的最大值vector<int> rowMax(n, INT_MIN);// 每一列的最小值vector<int> colMin(m, INT_MAX);for (int i = 0; i < n; ++i) {for (int j = 0; j < m; ++j) {rowMax[i] = max(rowMax[i], a[i][j]);colMin[j] = min(colMin[j], a[i][j]);}}bool found = false;// 按从上到下、同行从左到右的顺序检查for (int i = 0; i < n; ++i) {for (int j = 0; j < m; ++j) {if (a[i][j] == rowMax[i] && a[i][j] == colMin[j]) {cout << i + 1 << ' ' << j + 1 << ' ' << a[i][j] << '\n';found = true;}}}if (!found) {cout << "NO\n";}return 0;}
