试题
大感
我们这一次并没有批分数，所以关于上海市2025CSP-J十连测Round 7的内容我们会分为$Part 1$和$Part 2$
这一次我估计很难
上海市2025CSP-J十连测Round 7 题干
一、单项选择题
共15题、每题2分，共计30分，每题有且仅有一个正确选项。
- 如果开始时计算机处于小写输入状态，现在有一只小老鼠反复按照CapsLock、字母键A、字母键S和字母键D的顺序循环按键，即CapsLock、A、S、D、CapsLock、A、S、D……则屏幕上输出的第2025个字符是字母（）。
A. A
B. S
C. D
D. a - 在8位二进制补码中，10101011表示的是十进制下的（）。
A. -85
B. -43
C. 43
D. 85 - 给定一个含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$ - 表达式$a*(b+c)-d$的后缀表达形式为（）。
A. $abc d*+-$
B. $abc+*d-$
C. $abc*+d-$
D. $-+*abcd$ - 约定二叉树的根节点高度为1。一棵结点数为2025的二叉树最少有（）个叶子结点；一棵结点数为2025的二叉树最小的高度值是（）。
A. 1，11
B. 1，12
C. 2，11
D. 2，12 - 向一个栈顶指针为$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$ - 2-3树是满足两个条件的树：①所有叶结点到根的路径长度相同；②所有非叶子结点有两个或三个子结点。如果一棵2-3树有10个叶结点，那么它可能有（）个非叶结点。
A. 3
B. 4
C. 6
D. 8 - 由四个没有区别的点构成的简单无向连通图的个数是（）。
A. 6
B. 7
C. 8
D. 9 - 设含有10个元素的集合的全部子集数为S，其中由7个元素组成的子集数为T，则$\frac{T}{S}$的值（）。
A. $\frac{5}{32}$
B. $\frac{15}{128}$
C. $\frac{1}{8}$
D. $\frac{21}{125}$ - 如下图所示，共有13个格子。对任何一个格子进行一次操作，会使得它自己以及与它上下左右相邻的格子中的数字改变（由1变0，或由0变1）。现在要使得所有的格子中的数字都变为0，至少需要（）次操作。
A. 3
B. 4
C. 5
D. 6 - 一个1×8的方格图形（不可旋转）用黑、白两种颜色填涂每个方格。如果每个方格只能填涂一种颜色，且不允许两个黑格相邻，共有（）种填涂方案。
A. 8
B. 55
C. 56
D. 64 - 设G是有n个结点、m条边（$n \leq m$）的连通图，必须删去G的（）条边，才能使得G变成一棵树。
A. $m - n + 1$
B. $m - n$
C. $m + n + 1$
D. $n - m + 1$ - 有7个一模一样的苹果，放到3个一样的盘子中，一共有（）种放法。
A. 7
B. 8
C. 21
D. 2187 - 若$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 - 以下是32位机器和64位机器的区别是（）。
A. 显示器不同
B. 硬盘大小不同
C. 寻址空间不同
D. 输入法不同
二、阅读程序
判断题1分，选择题3分，共计40分；判断题正确填T，错误填F。
第1题
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是非负整数。
判断题
- solve1(11)的返回值为6（）。
- solve2(12345)的返回值为906（）。
- 对所有的$n > 0$，必有solve1(n) <= n（）。
- solve1(0)的返回值为0（）。
选择题
- 关于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) - 若将solve1函数中第一句n++去掉，将solve2函数中for循环的i += 2改为i += 1，则新返回值与原来相比（）。
A. solve1不变，solve2变大
B. solve1不变，solve2变小
C. solve1变小，solve2不变
D. solve1变大，solve2不变 - 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题
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";
}判断题
- 若依次输入数据2 2 1 3 3 1，程序返回的结果是3（）。
- 如果$n = 0$或$m = 0$，程序返回的结果是1（）。
- 如果两个序列完全相同，程序返回的结果是$2^n$（）。
- 输出时，执行solve(0,0)+mod是多余的运算（）。
选择题
- 该程序的主要功能是（）。
A. 计算两个序列的最长公共子序列的长度
B. 计算两个序列的公共子序列的数量
C. 计算两个序列的公共子串的数量
D. 计算两个序列的相同元素个数 - 该程序的时间复杂度为（）。
A. $\Theta(n + m)$
B. $\Theta(n \cdot m)$
C. $\Theta(2^{m + n})$
D. $\Theta(nlogm)$ - 当$a[i] = b[j]$时，返回值需要减去solve(i+1,j+1)的原因是（）。
A. 排除重复情况
B. 排除错误情况
C. 优化程序的空间效率
D. 优化程序的时间效率
第3题
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);
}判断题
- 当输入k为1时候，输出1（）。
- 当输入k为1000时候，输出1 5 2 4 3（）。
选择题
- 关于程序输出的序列所满足的性质，错误的是（）。
A. 输出的每个数字各不相同
B. 输出的数字都在1到n之间
C. 输出的相邻的数字差距不会超过1
D. 最先输出的数字在程序中是最先被确定的 - 下列说法正确的是（）。
A. 越大的k一定会输出越长的序列
B. k若是奇数，输出序列的长度一定也是奇数
C. 程序的时间复杂度为(k!)
D. gen递归是树形递归 - 若程序输出的第一个数字为2，第二数字为4，剩下还有三个数字，则输入的k（）。
A. 最小值是60，最大值是65
B. 最小值是65，最大值是70
C. 最小值是70，最大值是75
D. 最小值是75，最大值是80 - 如果使得输出序列出现7，则输入k最少需要（）。
A. 343
B. 874
C. 2170
D. 5040
三、完善程序
单选题，每小题3分，共计30分。
第1题
有一个用户，在连续的n天里，都会收到积分，也会消费积分。积分在获得后的m天内有效（m为一个给定的整数），过期失效。在第i天，用户将会获得$p_i$分，他需要消费$c_i$分。若积分不足，则用掉全部积分后用其他方式消费。消费积分时，先用最早的。当天获取的积分可以当天消费。请计算这个用户一共消费了多少积分。
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";
}
}- （1）处应填（）。
A. tail
B. tail + 1
C. i + head
D. tail++ - （2）处应填（）。
A. head < tail || c > 0
B. head < tail || p > 0
C. head < tail && c > 0
D. head < tail && p > 0 - （3）处应填（）。
A. queue[head] > c
B. queue[tail] > c
C. queue[head + 1] > c
D. queue[tail - 1] > c - （4）处应填（）。
A. queue[head++]
B. queue[head]
C. queue[tail--]
D. queue[tail] - （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用于解决这个问题。
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;
}- （1）处应填（）。
A. $q[p[i]] = i$
B. $q[i] = p[i]$
C. $q[i] = i$
D. $q[p[i]] = p[i]$ - （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 - （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]) - （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]) - （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]
此处评论已关闭