题目

上海市2025CSP-J十连测Round 6.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]

代码实现：

#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;
}
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。

二 阅读程序

第一大题

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

联系上下文即可

完

致谢

最后修改：2026 年 05 月 26 日
© 允许规范转载
如果觉得我的文章对你有用，请随意赞赏