上海市2025CSP-J十连测Round 7卷后感（Part 1）

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

# 试题

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

# 大感

我们这一次并没有批分数，所以关于**上海市2025CSP-J十连测Round 7**的内容我们会分为$Part 1$和$Part 2$
这一次我估计很难

# 上海市2025CSP-J十连测Round 7 题干

## 一、单项选择题

共15题、每题2分，共计30分，每题有且仅有一个正确选项。

1. 如果开始时计算机处于小写输入状态，现在有一只小老鼠反复按照CapsLock、字母键A、字母键S和字母键D的顺序循环按键，即CapsLock、A、S、D、CapsLock、A、S、D……则屏幕上输出的第2025个字符是字母（）。
   A. A
   B. S
   C. D
   D. a
2. 在8位二进制补码中，10101011表示的是十进制下的（）。
   A. -85
   B. -43
   C. 43
   D. 85
3. 给定一个含N个不相同数字的数组，在最坏情况下，找出其中最大或最小的数，至少需要$N-1$次比较操作。则最坏情况下，在该数组中同时找最大与最小的数至少需要（）次比较操作。（「」表示向上取整，⌊⌋表示向下取整）
   A. $\left\lceil\frac{3N}{2}\right\rceil - 2$
   B. $\left\lfloor\frac{3N}{2}\right\rfloor - 2$
   C. $2N - 2$
   D. $2N - 4$
4. 表达式$a*(b+c)-d$的后缀表达形式为（）。
   A. $abc d*+-$
   B. $abc+*d-$
   C. $abc*+d-$
   D. $-+*abcd$
5. 约定二叉树的根节点高度为1。一棵结点数为2025的二叉树最少有（）个叶子结点；一棵结点数为2025的二叉树最小的高度值是（）。
   A. 1，11
   B. 1，12
   C. 2，11
   D. 2，12
6. 向一个栈顶指针为$hs$的链式栈中插入一个指针s指向的结点时，应执行（）。
   A. $hs \to next = s;$
   B. $s \to next = hs; hs = s;$
   C. $s \to next = hs \to next; hs \to next = s;$
   D. $s \to next = hs; hs = hs \to next$
7. 2-3树是满足两个条件的树：①所有叶结点到根的路径长度相同；②所有非叶子结点有两个或三个子结点。如果一棵2-3树有10个叶结点，那么它可能有（）个非叶结点。
   A. 3
   B. 4
   C. 6
   D. 8
8. 由四个没有区别的点构成的简单无向连通图的个数是（）。
   A. 6
   B. 7
   C. 8
   D. 9
9. 设含有10个元素的集合的全部子集数为S，其中由7个元素组成的子集数为T，则$\frac{T}{S}$的值（）。
   A. $\frac{5}{32}$
   B. $\frac{15}{128}$
   C. $\frac{1}{8}$
   D. $\frac{21}{125}$
10. 如下图所示，共有13个格子。对任何一个格子进行一次操作，会使得它自己以及与它上下左右相邻的格子中的数字改变（由1变0，或由0变1）。现在要使得所有的格子中的数字都变为0，至少需要（）次操作。
    A. 3
    B. 4
    C. 5
    D. 6
11. 一个1×8的方格图形（不可旋转）用黑、白两种颜色填涂每个方格。如果每个方格只能填涂一种颜色，且不允许两个黑格相邻，共有（）种填涂方案。
    A. 8
    B. 55
    C. 56
    D. 64
12. 设G是有n个结点、m条边（$n \leq m$）的连通图，必须删去G的（）条边，才能使得G变成一棵树。
    A. $m - n + 1$
    B. $m - n$
    C. $m + n + 1$
    D. $n - m + 1$
13. 有7个一模一样的苹果，放到3个一样的盘子中，一共有（）种放法。
    A. 7
    B. 8
    C. 21
    D. 2187
14. 若$f_0 = 0$，$f_1 = 1$，$f_{n+1} = \frac{f_n + f_{n-1}}{2}$，则随着i的增大，$f_i$将接近于（）。
    A. $\frac{1}{2}$
    B. $\frac{2}{3}$
    C. $\frac{\sqrt{5} - 1}{2}$
    D. 1
15. 以下是32位机器和64位机器的区别是（）。
    A. 显示器不同
    B. 硬盘大小不同
    C. 寻址空间不同
    D. 输入法不同

## 二、阅读程序

判断题1分，选择题3分，共计40分；判断题正确填T，错误填F。

### 第1题

```c
int solve1(int n) {
    n++;
    int size = 0;
    int digit[16];
    int pow = 1;
    int s = 0;
    while (n > 0) {
        digit[size] = n % 10;
        size++;
        n /= 10;
        s += pow;
        pow *= 5;
    }
    while (size > 0) {
        --size;
        pow /= 5;
        s += (digit[size] / 2) * pow;
        if (digit[size] % 2 == 0) break;
    }
    return s - 1;
}

int solve2(int n) {
    int s = 0;
    for (int i = 1; i <= n; i += 2) {
        int t = i;
        bool pass = true;
        while (t > 0) {
            int x = t % 10;
            if (x % 2 == 0) {
                pass = false;
                break;
            }
            t /= 10;
        }
        if (pass) s++;
    }
    return s;
}
```

保证solve1与solve2的参数n是非负整数。

#### 判断题

16. solve1(11)的返回值为6（）。
17. solve2(12345)的返回值为906（）。
18. 对所有的$n > 0$，必有solve1(n) <= n（）。
19. solve1(0)的返回值为0（）。

#### 选择题

20. 关于solve1(n)与solve2(n)的大小关系，当$n \geq 0$时，下列说法正确的是（）。
    A. 必然有solve1(n) < solve2(n)
    B. 必然有solve1(n) == solve2(n)
    C. 只有当n为偶数时，才有solve1(n) = solve2(n)
    D. 只有当n为奇数时，才有solve1(n) == solve2(n)
21. 若将solve1函数中第一句n++去掉，将solve2函数中for循环的i += 2改为i += 1，则新返回值与原来相比（）。
    A. solve1不变，solve2变大
    B. solve1不变，solve2变小
    C. solve1变小，solve2不变
    D. solve1变大，solve2不变
22. solve1(n)与solve2(n)的时间复杂度为（）。
    A. $\Theta(logn)$、$\Theta(logn^2)$
    B. $\Theta(logn)$、$\Theta(n)$
    C. $\Theta(logn)$、$\Theta(nlogn)$
    D. $\Theta(n)$、$\Theta(n^2)$

### 第2题

```c
int a[maxn];
int b[maxn];
int n, m;
const long long mod = 1000000007;
bool filled[maxn][maxn];
long long mem[maxn][maxn];

long long solve(int i, int j) {
    if (filled[i][j]) return mem[i][j];
    if (i == n) return 1;
    if (j == m) return 1;
    filled[i][j] = true;
    if (a[i] == b[j]) {
        long long sum = solve(i + 1, j) + solve(i, j + 1);
        return mem[i][j] = sum % mod;
    } else {
        return mem[i][j] = (solve(i + 1, j) - solve(i + 1, j + 1)) % mod;
    }
}

int main() {
    std::cin >> n >> m;
    for (int i = 0; i < n; ++i) std::cin >> a[i];
    for (int i = 0; i < m; ++i) std::cin >> b[i];
    std::cout << (solve(0, 0) + mod) % mod << "\n";
}
```

#### 判断题

23. 若依次输入数据2 2 1 3 3 1，程序返回的结果是3（）。
24. 如果$n = 0$或$m = 0$，程序返回的结果是1（）。
25. 如果两个序列完全相同，程序返回的结果是$2^n$（）。
26. 输出时，执行solve(0,0)+mod是多余的运算（）。

#### 选择题

27. 该程序的主要功能是（）。
    A. 计算两个序列的最长公共子序列的长度
    B. 计算两个序列的公共子序列的数量
    C. 计算两个序列的公共子串的数量
    D. 计算两个序列的相同元素个数
28. 该程序的时间复杂度为（）。
    A. $\Theta(n + m)$
    B. $\Theta(n \cdot m)$
    C. $\Theta(2^{m + n})$
    D. $\Theta(nlogm)$
29. 当$a[i] = b[j]$时，返回值需要减去solve(i+1,j+1)的原因是（）。
    A. 排除重复情况
    B. 排除错误情况
    C. 优化程序的空间效率
    D. 优化程序的时间效率

### 第3题

```c
long long k;
int n;
int p[20];
bool used[20] = {false};
long long frac[20];

void gen(int i) {
    if (i > n) {
        for (int i = 1; i <= n; ++i) std::cout << p[i] << " ";
        return;
    }
    for (int a = 1; a <= n; ++a) if (!used[a]) {
        if (k <= frac[n - i]) {
            p[i] = a;
            used[a] = true;
            gen(i + 1);
            return;
        } else {
            k -= frac[n - i];
        }
    }
}

int main() {
    n = 1;
    std::cin >> k;
    frac[0] = frac[1] = 1;
    while (k > frac[n]) {
        k -= frac[n];
        frac[n + 1] = frac[n] * (n + 1);
        n++;
    }
    gen(1);
}
```

#### 判断题

30. 当输入k为1时候，输出1（）。
31. 当输入k为1000时候，输出1 5 2 4 3（）。

#### 选择题

32. 关于程序输出的序列所满足的性质，错误的是（）。
    A. 输出的每个数字各不相同
    B. 输出的数字都在1到n之间
    C. 输出的相邻的数字差距不会超过1
    D. 最先输出的数字在程序中是最先被确定的
33. 下列说法正确的是（）。
    A. 越大的k一定会输出越长的序列
    B. k若是奇数，输出序列的长度一定也是奇数
    C. 程序的时间复杂度为(k!)
    D. gen递归是树形递归
34. 若程序输出的第一个数字为2，第二数字为4，剩下还有三个数字，则输入的k（）。
    A. 最小值是60，最大值是65
    B. 最小值是65，最大值是70
    C. 最小值是70，最大值是75
    D. 最小值是75，最大值是80
35. 如果使得输出序列出现7，则输入k最少需要（）。
    A. 343
    B. 874
    C. 2170
    D. 5040

## 三、完善程序

单选题，每小题3分，共计30分。

### 第1题

有一个用户，在连续的n天里，都会收到积分，也会消费积分。积分在获得后的m天内有效（m为一个给定的整数），过期失效。在第i天，用户将会获得$p_i$分，他需要消费$c_i$分。若积分不足，则用掉全部积分后用其他方式消费。消费积分时，先用最早的。当天获取的积分可以当天消费。请计算这个用户一共消费了多少积分。

```c
const int max_size = 100000;
int queue[max_size];
int head = 0;
int tail = 0;

int main() {
    int n, m;
    std::cin >> n >> m;
    int sum = 0;
    for (int i = 0; i < n; ++i) {
        int p, c;
        std::cin >> p >> c;
        queue[_(1)_] = p;
        while (_(2)_) {
            if (_(3)_) {
                queue[head] -= c;
                sum += c;
                c = 0;
            } else {
                int amount = _(4)_;
                c -= amount;
                sum += amount;
            }
        }
        if (_(5)_ > m) {
            head++;
        }
        std::cout << sum << "\n";
    }
}
```

36. （1）处应填（）。
    A. tail
    B. tail + 1
    C. i + head
    D. tail++
37. （2）处应填（）。
    A. head < tail || c > 0
    B. head < tail || p > 0
    C. head < tail && c > 0
    D. head < tail && p > 0
38. （3）处应填（）。
    A. queue[head] > c
    B. queue[tail] > c
    C. queue[head + 1] > c
    D. queue[tail - 1] > c
39. （4）处应填（）。
    A. queue[head++]
    B. queue[head]
    C. queue[tail--]
    D. queue[tail]
40. （5）处应填（）。
    A. head - tail
    B. tail - head
    C. tail + head
    D. i - head + 1

### 第2题

给定一个1到n的排列$p_1, p_2, ..., p_n$。请统计排列中所有长度大于等于2的连续子序列的次大数之和。定义$max_2(a_i, a_{i+1}, ..., a_j)$表示从$a_i$开始到$a_j$结束的连续子序列中，排名第二大的数，这个数就是一个连续子序列的次大数之和。题目就是要求：$\sum_{1 \leq i < j \leq n} max_2(a_i, a_{i+1}, ..., a_j)$。solve用于解决这个问题。

```c
int q[maxn];
int prev[maxn];
int next[maxn];

long long solve(int n, int p[]) {
    for (int i = 1; i <= n; ++i) {
        _(1)_;
    }
    p[0] = q[0] = prev[0] = 0;
    p[n + 1] = q[n + 1] = next[n + 1] = n + 1;
    for (int i = 1; i <= n; ++i) {
        int num = _(2)_;
        int prev_num = p[i - 1];
        int next_num = p[i + 1];
        prev[num] = _(3)_;
        next[num] = _(4)_;
    }
    long long sum = 0;
    for (int num = 1; num <= n; ++num) {
        int prev_num = prev[num];
        int prev_prev_num = prev[prev_num];
        int next_num = next[num];
        int next_next_num = next[next_num];
        sum += (long long)num * (q[num] - q[prev_num]) * _(5)_;
        sum += (long long)num * (q[next_num] - q[num]) * _(6)_;
        _(7)_ = prev_num;
        _(8)_ = next_num;
    }
    return sum;
}
```

41. （1）处应填（）。
    A. $q[p[i]] = i$
    B. $q[i] = p[i]$
    C. $q[i] = i$
    D. $q[p[i]] = p[i]$
42. （2）（3）（4）处应填（）。
    A. p[i]，prev_num，next_num
    B. q[i]，next_num，prev_num
    C. p[i]，next_num，prev_num
    D. q[i]，prev_num，next_num
43. （5）处应填（）。
    A. (q[prev_num] - q[prev_prev_num])
    B. (q[next_next_num] - q[prev_num])
    C. (q[next_num] - q[prev_prev_num])
    D. (q[next_next_num] - q[next_num])
44. （6）处应填（）。
    A. (q[prev_num] - q[prev_prev_num])
    B. (q[next_next_num] - q[prev_num])
    C. (q[next_num] - q[prev_prev_num])
    D. (q[next_next_num] - q[next_num])
45. （7）（8）处应填（）。
    A. prev[prev_num]，next[next_num]
    B. prev[next_num]，next[prev_num]
    C. next[prev_num]，prev[next_num]
    D. next[next_num]，prev[prev_num]

最后修改：2025 年 09 月 15 日

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

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

评论 *

私密评论

名称 *

🎲

邮箱

地址

上海市2025CSP-J十连测Round 7卷后感（Part 1）

admin • 2025 年 09 月 15 日

# 试题

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

# 大感

我们这一次并没有批分数，所以关于**上海市2025CSP-J十连测Round 7**的内容我们会分为$Part 1$和$Part 2$
这一次我估计很难

# 上海市2025CSP-J十连测Round 7 题干

## 一、单项选择题

共15题、每题2分，共计30分，每题有且仅有一个正确选项。

## 二、阅读程序

判断题1分，选择题3分，共计40分；判断题正确填T，错误填F。

### 第1题

保证solve1与solve2的参数n是非负整数。

#### 判断题

16. solve1(11)的返回值为6（）。
17. solve2(12345)的返回值为906（）。
18. 对所有的$n > 0$，必有solve1(n) <= n（）。
19. solve1(0)的返回值为0（）。

#### 选择题

### 第2题

```c
int a[maxn];
int b[maxn];
int n, m;
const long long mod = 1000000007;
bool filled[maxn][maxn];
long long mem[maxn][maxn];

int main() {
    std::cin >> n >> m;
    for (int i = 0; i < n; ++i) std::cin >> a[i];
    for (int i = 0; i < m; ++i) std::cin >> b[i];
    std::cout << (solve(0, 0) + mod) % mod << "\n";
}
```

#### 判断题

#### 选择题

### 第3题

```c
long long k;
int n;
int p[20];
bool used[20] = {false};
long long frac[20];

int main() {
    n = 1;
    std::cin >> k;
    frac[0] = frac[1] = 1;
    while (k > frac[n]) {
        k -= frac[n];
        frac[n + 1] = frac[n] * (n + 1);
        n++;
    }
    gen(1);
}
```

#### 判断题

30. 当输入k为1时候，输出1（）。
31. 当输入k为1000时候，输出1 5 2 4 3（）。

#### 选择题

## 三、完善程序

单选题，每小题3分，共计30分。

### 第1题

```c
const int max_size = 100000;
int queue[max_size];
int head = 0;
int tail = 0;

### 第2题

```c
int q[maxn];
int prev[maxn];
int next[maxn];

上海市2025CSP-J十连测Round 7卷后感（Part 1）

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

IP地址修改器 [bilibili配套]

关于 2025 CSP

FMCRAFT Res领地插件使用教程【官方 and 非官方】

个人对于身高歧视的评价

关于 2025 年浙江省初中名校发展共同体七年级第一学期考试反思

【科技补全76】新概念英语点读工具NCE-Flow、在线文件管理器copyparty 部署指北

【abc436】AtCoder Beginner Contest 436

吾辈既居权威之下，所成之事必谬

乙巳岁九月十四修博客服务器感怀

2023年CSP-J第一轮卷后感

上海市2025CSP-J十连测Round 7卷后感（Part 1）

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

上海市2025CSP-J十连测Round 7卷后感（Part 1）

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