上海市2025CSP-J十连测Round 6卷后感

博主： admin
发布时间：2025 年 09 月 14 日
23 次浏览
暂无评论
8766字数
分类： OI 编程

# 题目

[上海市2025CSP-J十连测Round 6.pdf](https://www.fmcraft.top/usr/uploads/2025/09/1456863820.pdf)

# 大感

难度感觉很难，我只有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]`

代码实现：

```cpp
#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的函数，应该将下划线依次替换为（  ）**

```cpp
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;
}
```

> A `lower_bound`、`lower_bound`
> B `lower_bound`、`upper_bound`
> C `upper_bound`、`lower_bound`
> D `upper_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
**核心规则回顾**

1. **哈希函数**：`H(key) = key % 13`，计算元素的初始哈希位置。
2. **线性探查法**：若初始位置已被占用，依次检查下一个位置（下标+1，超过12则循环到0），直到找到空位置。
3. 哈希表下标范围：`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**。

## 二 阅读程序

### 第一大题

```cpp
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;
}
```

### 第二大题

```cpp
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

### 第三大题

```cpp
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$结束，路径上所有边的权重的异或值尽可能大。

```cpp
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`函数返回这个最小值

```cpp
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

联系上下文即可

# 完

致谢

最后修改：2025 年 09 月 14 日

如果觉得我的文章对你有用，请随意赞赏

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

评论 *

私密评论

名称 *

🎲

邮箱

地址

上海市2025CSP-J十连测Round 6卷后感

admin • 2025 年 09 月 14 日