上海市2025CSP-J十连测Round 6卷后感
题目
大感
难度感觉很难，我只有69分，全班排No 3的状态
错题大纲
一 单项选择（错4题）
T4
如果对一个已经升序的数组进行排序，下列算法中可能花费时间反而比乱序数组多的是( )
A.堆排序
B.插入排序
C.冒泡排序
D.快速排序
先来一张统计表
| 排序算法 | 平均时间复杂度 | 最优时间复杂度 | 最坏时间复杂度 | 备注 |
|---|---|---|---|---|
| A. 堆排序 | $O(n log n)$ | $O(n log n)$ | $O(n log n)$ | 不稳定排序 |
| B. 插入排序 | $O(n²)$ | $O(n)$ | $O(n²)$ | 稳定排序，对小数据集高效 |
| C. 冒泡排序 | $O(n²)$ | $O(n)$ | $O(n²)$ | 稳定排序，效率较低 |
| D. 快速排序 | $O(n log n)$ | $O(n log n)$ | $O(n²)$ | 不稳定排序，平均性能最好 |
答案为D
原因如下：快速排序依赖于基准，如果数组已经有序，且选择第一个或最后一个元素作为基准（常见实现方式），则每次划分都会极度不平衡（因为基准是当前子数组的最小或最大值），导致递归深度达到最大（$O(n)$），并且每次划分只能减少一个元素。因此，最坏时间复杂度为$O(n²)$，比乱序数组的平均情况（$O(n log n)$）要慢得多
例如：
初始数组：[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]第一次排序（以 1 为基准）：
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]对右半部分 [2, 3, 4, 5, 6, 7, 8, 9, 10] 排序（以 2 为基准）：
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]对右半部分 [3, 4, 5, 6, 7, 8, 9, 10] 排序（以 3 为基准）：
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]对右半部分 [4, 5, 6, 7, 8, 9, 10] 排序（以 4 为基准）：
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]对右半部分 [5, 6, 7, 8, 9, 10] 排序（以 5 为基准）：
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]对右半部分 [6, 7, 8, 9, 10] 排序（以 6 为基准）：
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]对右半部分 [7, 8, 9, 10] 排序（以 7 为基准）：
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]对右半部分 [8, 9, 10] 排序（以 8 为基准）：
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]对右半部分 [9, 10] 排序（以 9 为基准）：
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]对右半部分 [10] 排序（只有一个元素，无需排序）：
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
代码实现：
#include <iostream>
using namespace std;
// 划分函数，返回基准位置
int partition(int arr[], int low, int high) {
int pivot = arr[low]; // 选择第一个元素为基准
int i = low, j = high;
while (i < j) {
while (i < j && arr[j] >= pivot) j--; // 从右找小于基准的
while (i < j && arr[i] <= pivot) i++; // 从左找大于基准的
if (i < j) swap(arr[i], arr[j]);
}
swap(arr[low], arr[i]); // 将基准放到正确位置
return i;
}
// 快速排序递归函数
void quickSort(int arr[], int low, int high) {
if (low < high) {
int pi = partition(arr, low, high); // 划分
quickSort(arr, low, pi - 1); // 排序左半
quickSort(arr, pi + 1, high); // 排序右半
}
}
// 打印数组
void printArray(int arr[], int n) {
for (int i = 0; i < n; i++)
cout << arr[i] << " ";
cout << endl;
}
int main() {
int arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; // 待排序
int n = sizeof(arr) / sizeof(arr[0]);
printArray(arr, n);
quickSort(arr, 0, n - 1);
printArray(arr, n);
return 0;
}T6
题目：设一个栈与一个队列的初始状态均为空。元素 1、2、3、4、5、6依次进入栈，且每个元素出栈后即进入队列，若出队的顺序为2、4、3、6、5、1，则栈的容量至少应该为( )。
A 2
B 3
C 4
D 5
答案为B，模拟过程如下：
1入栈，容量为1
2入栈，容量为2
2出栈，容量为1
3入栈，容量为2
4入栈，容量为3
4出栈，容量为2
3出栈，容量为1
5入栈，容量为2
6入栈，容量为3
6出栈，容量为2
5出栈，容量为1
1出栈，容量为0
期间最大容量为3，所以栈容量至少为3
T7
题目：整型数组a中有n个元素，能计算a中有多少个数字大于lower且小于upper的函数，应该将下划线依次替换为（ ）
int solve(int a[], int n, int lower, int upper)
{
std::sort(a, a + n);
auto begin = std::_____(a, a + n, lower);
auto end = std::_____(a, a + n, upper);
return end - begin;
}Alower_bound、lower_bound
Blower_bound、upper_bound
Cupper_bound、lower_bound
Dupper_bound、upper_bound
答案为B
原因：
先说好，lb和up是C++的STL容器
lower_bound：返回指向第一个大于或等于目标值的元素的迭代器upper_bound：返回指向第一个大于目标值的元素的迭代器
T11
题目：设有一个含有13个元素的哈希表（0 12），哈希函数是H(key)=key%13。用线性探查法解决冲突，则对于序列{2,8,31,20,19,18,53,27}，18应放在下标为（ ）的位置
A 0
B 4
C 5
D 9
答案为D
核心规则回顾
- 哈希函数：
H(key) = key % 13，计算元素的初始哈希位置。 - 线性探查法：若初始位置已被占用，依次检查下一个位置（下标+1，超过12则循环到0），直到找到空位置。
- 哈希表下标范围：
0~12，共13个位置。
逐元素计算存储位置（重点跟踪18）
1. 元素2
- 初始哈希位置：
H(2) = 2 % 13 = 2 - 位置2为空，存储2 → 哈希表：
[空, 空, 2, 空, 空, 空, 空, 空, 空, 空, 空, 空, 空]
2. 元素8
- 初始哈希位置：
H(8) = 8 % 13 = 8 - 位置8为空，存储8 → 哈希表：
[空, 空, 2, 空, 空, 空, 空, 空, 8, 空, 空, 空, 空]
3. 元素31
- 初始哈希位置：
H(31) = 31 % 13 = 5（13×2=26，31-26=5） - 位置5为空，存储31 → 哈希表：
[空, 空, 2, 空, 空, 31, 空, 空, 8, 空, 空, 空, 空]
4. 元素20
- 初始哈希位置：
H(20) = 20 % 13 = 7（13×1=13，20-13=7） - 位置7为空，存储20 → 哈希表：
[空, 空, 2, 空, 空, 31, 空, 20, 8, 空, 空, 空, 空]
5. 元素19
- 初始哈希位置：
H(19) = 19 % 13 = 6（13×1=13，19-13=6） - 位置6为空，存储19 → 哈希表：
[空, 空, 2, 空, 空, 31, 19, 20, 8, 空, 空, 空, 空]
6. 元素18（目标元素）
- 初始哈希位置：
H(18) = 18 % 13 = 5（13×1=13，18-13=5） - 冲突：位置5已存储31，按线性探查检查下一个位置6；
- 再次冲突：位置6已存储19，继续检查下一个位置7；
- 再次冲突：位置7已存储20，继续检查下一个位置8；
- 再次冲突：位置8已存储8，继续检查下一个位置9；
- 位置9为空，存储18 → 18的最终下标为9。
（后续元素验证，不影响18的结果）
- 元素53：
H(53)=53%13=1（13×4=52，53-52=1），位置1为空，存储53。 - 元素27：
H(27)=27%13=1，位置1已存53，探查位置2（存2）→ 位置3（空），存储27。
结论
18应放在下标为 9 的位置，答案选 D。
二 阅读程序
第一大题
int solve1(int n)
{
int s = 0;
for (int i = 1; i <= n; ++i) {
int f = 1;
for (int j = i; j >= 1; --j) {
f = f * j;
}
s = s + f;
}
return s;
}
int solve2(int n)
{
int s = 0;
for (int i = n; i >= 1; --i)
{
s = s + 1;
s = s * i;
}
return s;
}第二大题
bool move(int b[], int n)
{
for (int i = 0; i < n; ++i) {
if (b[i] == 1) {
b[i] = 0;
} else {
b[i] = 1;
return true;
}
}
return false;
}
void print(int n)
{
int b[n];
for (int i = 0; i < n; ++i) b[i] = 0;
do {
for (int i = 0; i < n; ++i) std::cout << b[i];
std::cout << "\n";
} while (move(b, n));
}
int count(int n)
{
int b[n];
for (int i = 0; i < n; ++i) b[i] = 0;
int c = 0;
do {
c++;
} while (move(b, n));
return c;
}T22
题目：print输出的0与1必然一样多
什么是必然？
必定这样。必然是指客观事物联系和发展的合乎规律的、确定不移的趋势，是在一定条件下的不可避免性和确定性。
所以，√
模拟即可
T27
题目：以下说法错误的是( )
A.print(n)前一半输出全是偶数，后一半输出全是奇数
B.若将print(n)输出的每行内容看成一个数字，则他们是依次递增的
C.print(n)输出的每一行内容都是不同的
D.print(n)输出的每一列内容都是不同的
选B
不是依次递增
是有位数为int n的二进制，但是倒着的，也就是说，如果调用print(2)，则模拟过程如下：
0 0
1 0
0 1
1 1
0 0
把他旋转一下：
0 0 》0
0 1 》1
1 0 》2
1 1 》3
0 0 》0
所以本题选B
第三大题
struct flat_map {
struct {
int key;
int value;
} bucket[65536];
int size = 0;
struct result {
int index;
bool hit;
};
result find(int begin, int end, int key) {
if (begin == end)
return {begin, false};
else {
int mid = begin + (end - begin) / 2;
if (key < bucket[mid].key)
return find(begin, mid, key);
else if (bucket[mid].key < key)
return find(mid + 1, end, key);
else
return {mid, true};
}
}
int get(int key) {
result p = find(0, size, key);
if (p.hit)
return bucket[p.index].value;
else
return 0;
}
void put(int key, int value) {
result p = find(0, size, key);
for (int i = size; i > p.index; --i) {
bucket[i] = bucket[i - 1];
}
size++;
bucket[p.index].key = key;
bucket[p.index].value = value;
}
};T30
题目：若数组bucket的下标在[b,e)范围内存在键k，find(b,e,k)函数返回的hit为false
答案为×
find 函数通过二分查找，在数组 bucket 的区间 [b, e) 内查找键 k：
- 如果找到键
k，返回{索引, true}（hit = true）。 - 如果没找到键
k，返回{应该插入的位置, false}（hit = false）。
找到hit后是true，所以说法错误
T32
题目：记$s$表示容器的大小size，调用get(key)的最坏时间复杂度为（ ）
A $O(s)$
B $O(log s)$
C $O(s log s)$
D $O(s^2)$
根据题意，选B
log 通常指的是以 2 为底的对数（log₂）
T35
题目：若调用put(k,v)时已经存在相同的键k时，以下哪一种处理策略最符合上述代码的逻辑（ ）
A. 熔断 (Breaker):掷出异常，向系统报告错误
B. 回滚 (Rollback):不做任何修改，撤销put操作
C. 覆盖 (Rewrite):将键所对应的老值覆盖成新值
D. 忽略 (lgnore):对有可能出错的操作置之不理
答案为D，程序没有做特别的判断
三 完善程序
第一大题
给定含有n个顶点的有向完全图(顶点编号为$0$到$n-1$)。顶点$x$到$y$的边的权重为g[x][y]了。
请找出一条不重复经过任何点的路径，从顶点$0$出发到顶点$n-1$结束，路径上所有边的权重的异或值尽可能大。
int n, m;
long long g[MAXN][MAXN];
bool visited[MAXN] = {false};
int dfs(int node, int path) {
if (____(1)____)
{
return ____(2)____;
}
int best = 0;
visited[node] = true;
for (int next = 0; next < ____(3)____; ++next)
{
if (____(4)____)
{
best = std::max(best, ____(5)____);
}
}
visited[____(6)____] = ____(7)____;
}
int solve()
{
return ____(8)____;
}T40
node为节点，path为id
所以选A
第二大题
$n$个岛屿由$n$座桥连成环。岛的编号为$0$到$n-1$
，第$i$座桥连第$i$号岛屿第$(i+1) mod n$号岛
某旅行团从第$x_1$号岛出发，依次访问的岛编号为$x_2,...,x_m$
请选择拆掉一座桥，使得旅行团的过桥次数达到最小，令solve函数返回这个最小值
int solve(int n, int m, int x[])
{
int diff[n];
for (int i = 0; i < n; ++i) diff[i] = 0;
int base = 0;
for (int i = 1; i < m; ++i)
{
int prev = x[i - 1];
int next = x[i];
int begin, end;
if (prev < next) {
begin = prev;
end = next;
}
else {
begin = next;
end = prev;
}
base += ____(1)____;
int inc = ____(2)____ ;
diff[____(3)____] += inc;
diff[____(4)____] -= inc;
prev = next;
}
int best = n * m;
int sum = 0;
for (int i = 0; i < n; ++i)
{
____(5)____;
if (best > sum) best = sum;
}
return ____(6)____;
}T42
联系上下文即可
T44
联系上下文即可
T45
联系上下文即可
完
致谢
