#A. 2023 CSP-S提高组第一轮
2023 CSP-S提高组第一轮
该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
一、选择题
- 在 Linux 系统终端中,以下哪个命令用于创建一个新的目录?
{{ select(1) }}
- newdir
- mkdir
- create
- mkfold
- 中选取 个数字,能组成()个不同四位数(注:最小的四位数是 ,最大的四位数是 )。 {{ select(2) }}
- 96
- 18
- 120
- 84
- 假设 n 是图的顶点的个数,m是图的边的个数,为求解某一问题有下面四种不同时间复杂度的算法。对于 的稀疏图而言,下面的四个选项,哪一项的渐近时间复杂度最小()。
{{ select(3) }}
- 假设有n 根柱子,需要按照以下规则依次放置编号为、...的圆环:每根柱子的底部固定,顶部可以放入圆环,每次从柱子顶部放入圆环时,需要保证任何两个相邻圆环的编号之和是一个完全平方数。请计算当有4根柱子时,最多可以放置( )个圆环 {{ select(4) }}
- 7
- 9
- 11
- 5
- 以下对数据结构的表述不恰当的一项是 {{ select(5) }}
- 队列是一种先进先出(FIFO)的线性结构
- 哈夫曼树的构造过程主要是为了实现图的深度优先搜索
- 散列表是一种通过散列函数将关键字映射到存储位置的数据结构
- 二又树是一种每个结点最多有两个子结点的树结构
- 以下连通无向图中,( )一定可以用不超过两种颜色进行染色 {{ select(6) }}
- 完全三叉树
- 平面图
- 边双连通图
- 欧拉图
- 最长公共子序列长度常常用来衡量两个序列的相似度。其定义如下:给定两个序列 和 ,最长公共子序列(LCS)问题的目标是找到一个最长的新序列,使得序列 既是序列 的子序列,又是序列的子序列,且序列的长度在满足上述条件的序列里是最大的。(注:序列是序列的子序列,当且仅当在保持序列元素顺序的情况下,从序列中删除若干个元素,可以使得剩余的元素构成序列。)则序列
ABCAAAABA
和ABABCBABA
的最长公共子序列长度为( ) {{ select(7) }}
- 4
- 5
- 6
- 7
- 一位玩家正在玩一个特殊的掷骰子的游戏,游戏要求连续掷两次骰子,收益规则如下:玩家第一次掷出点,得到元;第二次掷出点,当 时玩家会失去之前得到的元而当时玩家能保住第一次获得的元。上述。 例如:玩家第一次掷出点得到元后,但第二次再次掷出点,会失去之前得到的元,玩家最终收益为元:如果玩家第一次掷出点第二次掷出点,则最终收益是元。假设骰子挑出任意一点的概率均为,玩家连续掷两次般子后所有可能情形下收益的平均值是多少? {{ select(8) }}
- 7元
- 元
- 元
- 元
- 假设我们有以下的C++代码:
int a=5,b=3,c=4;
bool res = a & b || c ^ b && a | c
请问,res的值是什么?
提示:在 C++中,逻辑运算的优先级从高到低依次为: 逻辑非(!)逻辑与(&&)、逻辑或(||)。位运算的优先级从高到低依次为: 位非(~)、位与(&)、位异或(^)、位或(|)。同时,双目位运算的优先级高于双目逻辑运算:逻辑非和位非优先级相同,且高于所有双目运算符
{{ select(9) }}
- true
- false
- 1
- 0
- 假设快速排序算法的输入是一个长度为n的已排序数组,且该快速排序算法在分治过程总是选择第1个元素作为基准元素。以下哪个选项描述的是在这种情况下的快速排序行为? {{ select(10) }}
- 快速排序对于此类输入的表现最好,因为数组已经排序
- 快速排序对于此类输入的时间复杂度是。
- 快速排序对于此类输入的时间复杂度是
- 快速排序无法对此类数组进行排序因为数组已经排序
- 以下哪个命令,能将一个名为
main.cpp
的 C++源文件,编译并生成一个名为main
的可执行文件? ( )
{{ select(11) }}
g++ -o main main.cpp
g++ -o main.cpp main
g++ main -o main.cpp
g++ main.cpp -o main.cpp
- 在图论中,树的重心是树上的一个结点,以该结点为根时,使得其所有的子树中结点数最多的子树的结点数最少。一棵树可能有多个重心。请问下面哪种树一定只有一个重心( ) {{ select(12) }}
- 4个结点的树
- 6个结点的树
- 7个结点的树
- 8个结点的树
- 如图是一张包含个顶点的有向图,但顶点间不存在拓扑序。如果要删除其中一条边,使这个顶点能进行拓扑排序,请问总共有多少条边可以作为候选的被删除边?
{{ select(13) }}
- 1
- 2
- 3
- 4
- 若,定义,其中,对于给定的自然数,存在序列,其中对于都有,且,称为关于f的不动点,问在到中,关于f的不动点为9的自然数的个数
{{ select(14) }}
- 10
- 11
- 12
- 13
15.现在用如下代码来计算,其时间复杂度为( )
double quick_power(double x, unsigned n) {
if (n == 0) return 1;
if (n == 1) return x;
return quick_power(x, n / 2) * quick_power(x, n / 2) * ((n & 1) ? x : 1);
}
{{ select(15) }}
二、阅读程序
(1)
#include <iostream>
using namespace std;
unsigned short f(unsigned short x) {
x ^= x << 6;
x ^= x >> 8;
return x;
}
int main() {
unsigned short x;
cin >> x;
unsigned short y = f(x);
cout << y << endl;
return 0;
}
假设输入的是不超过 的自然数,完成下面的判断题和单选题:
- 当输入非零时,输出一定不为零。() {{ select(16) }}
- 正确
- 错误
17.将 f
函数的输入参数的类型改为 unsigned int
,程序的输出不变。()
{{ select(17) }}
- 正确
- 错误
18.当输入为“65535”时,输出为“63”( ) {{ select(18) }}
- 正确
- 错误
19.当输入为 1
时,输出为 64
。()
{{ select(19) }}
- 正确
- 错误
20.当输入为 512
时,输出为()。
{{ select(20) }}
- 33280
- 33410
- 33106
- 33346
21.当输入为“64”时,执行完第行后的值为() {{ select(21) }}
- 8256
- 4130
- 4128
- 4160
(2)
#include <iostream>
#include <cmath>
#include <vector>
#include <algorithm>
using namespace std;
long long solve1(int n) {
vector<bool> p(n + 1, true);
vector<long long> f(n + 1, 0), g(n + 1, 0);
f[1] = 1;
for (int i = 2; i * i <= n; i++) {
if (p[i]) {
vector<int> d;
for (int k = i; k <= n; k *= i)
d.push_back(k);
reverse(d.begin(), d.end());
for (int k : d) {
for (int j = k; j <= n; j += k) {
if (p[j]) {
p[j] = false;
f[j] = i;
g[j] = k;
}
}
}
}
}
for (int i = sqrt(n) + 1; i <= n; i++) {
if (p[i]) {
f[i] = i;
g[i] = i;
}
}
long long sum = 1;
for (int i = 2; i <= n; i++) {
f[i] = f[i / g[i]] * (g[i] * f[i] - 1) / (f[i] - 1);
sum += f[i];
}
return sum;
}
long long solve2(int n) {
long long sum = 0;
for (int i = 1; i <= n; i++) {
sum += i * (n / i);
}
return sum;
}
int main() {
int n;
cin >> n;
cout << solve1(n) << endl;
cout << solve2(n) << endl;
return 0;
}
假设输入的 n 是不超过 1000000的自然数,完成下面的判断题和单选题
22.将第15 行删去,输出不变( ) {{ select(22) }}
- 正确
- 错误
23.当输入为10
时,输出的第一行大于第二行。( )
{{ select(23) }}
- 正确
- 错误
24.当输入为1000
时,输出的第一行与第二行相等( )
{{ select(24) }}
- 正确
- 错误
25.的时间复杂度为( ) {{ select(25) }}
26.的时间复杂度为( )
{{ select(26) }}
27.输入为5
时,输出的第二行为( )
{{ select(27) }}
- 20
- 21
- 22
- 23
(3)
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
bool f0(vector<int> &a, int m, int k) {
int s = 0;
for (int i = 0, j = 0; i < a.size(); i++) {
while (a[i] - a[j] > m)
j++;
s += i - j;
}
return s >= k;
}
int f(vector<int> &a, int k) {
sort(a.begin(), a.end());
int g = 0;
int h = a.back() - a[0];
while (g < h) {
int m = g + (h - g) / 2;
if (f0(a, m, k)) {
h = m;
}
else {
g = m + 1;
}
}
return g;
}
int main() {
int n, k;
cin >> n >> k;
vector<int> a(n, 0);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
cout << f(a, k) << endl;
return 0;
}
假设输入总是合法的且,完成下面的判断题和单选题
28.将第24行的m
改为m-1
,输出有可能不变,而剩下情况为少1。( )
{{ select(28) }}
- 正确
- 错误
29.将第22行的g + (h - g) / 2
改为(h + g) >> 1
,输出不变。( )
{{ select(29) }}
- 正确
- 错误
30.当输入为5 7 2 -4 5 1 -3
,输出为5
。( )
{{ select(30) }}
- 正确
- 错误
31.设a数组中最大值减最小值加1为A,则f
函数的时间复杂度为( )
{{ select(31) }}
32.将第10行中的>
替换为>=
,那么原输出与现输出的大小关系为( )
{{ select(32) }}
- 一定小于
- 一定小于等于且不一定小于
- 一定大于等于且不一定大于
- 以上三种情况都不对
33.当输入为5 8 2 -5 3 8 -12
时,输出为( )
{{ select(33) }}
- 13
- 14
- 8
- 15
三、完善程序
( 1 ) (第k小路径) 给定一张n个点 m 条边的有向无环图,顶点编号从到。对于一条路径,我们定义“路径序列”为该路径从起点出发依次经过的顶点编号构成的序列。求所有至少包含一个点的简单路径中,“路径序列”字典序第k小的路径。保证存在至少 k条路径,上述参数满足 和 . 在程序中,我们求出从每个点出发的路径数量。超过的数都用 表示。然后我们根据的值和每个顶点的路径数量,确定路径的起点,然后可以类似地依次求出路径中的每个点。
试补全程序。
#include <iostream>
#include <algorithm>
#include <vector>
const int MAXN = 100000;
const long long LIM = 1000000000000000000ll;
int n, m, deg[MAXN];
std::vector<int> E[MAXN];
long long k, f[MAXN];
int next(std::vector<int> cand, long long &k) {
std::sort(cand.begin(), cand.end());
for (int u : cand) {
if (①) return u;
k -= f[u];
}
return -1;
}
int main() {
std::cin >> n >> m >> k;
for (int i = 0; i < m; ++i) {
int u, v;
std::cin >> u >> v; // 一条从u到v的边
E[u].push_back(v);
++deg[v];
}
std::vector<int> Q;
for (int i = 0; i < n; ++i)
if (!deg[i]) Q.push_back(i);
for (int i = 0; i < n; ++i) {
int u = Q[i];
for (int v : E[u]) {
if (②)
Q.push_back(v);
--deg[v];
}
}
std::reverse(Q.begin(), Q.end());
for (int u : Q) {
f[u] = 1;
for (int v : E[u])
f[u] = ③;
}
int u = next(Q, k);
std::cout << u << std::endl;
while (④) {
⑤;
u = next(E[u], k);
std::cout << u << std::endl;
}
return 0;
}
34.①处应该填写( )
{{ select(34) }}
k >= f[u]
k <= f[u]
k > f[u]
k < f[u]
35.②处应该填写( ) {{ select(35) }}
deg[v] == 1
deg[v] == 0
deg[v] > 1
deg[v] > 0
36.③处应该填写( ) {{ select(36) }}
std::min(f[u] + f[v], LIM)
std::min(f[u] + f[v] + 1, LIM)
std::min(f[u] * f[v], LIM)
std::min(f[u] * (f[v] + 1), LIM)
37.④处应该填写( ) {{ select(37) }}
u != 1
!E[u].empty()
k > 0
k > 1
38.⑤处应该填写( ) {{ select(38) }}
k+=f[u]
k-=f[u]
--k
++k
( 2 ) (最大值之和) 给定整数序列,求该序列所有非空连续子序列的最大值之和。上述参数满足 和 一个序列的非空连续子序列可以用两个下标l和r(其中)表示,对应的序列为。两个非空连续子序列不同,当且仅当下标不同 例如,当原序列为[1,2,1,2] 时,要计算子序列[1]、[2]、[1]、[2]、[1,2]、[2,1]、[1,2]、[1,2,1]、[2,1,2]、[1,2,1,2] 的最大值之和,答案为 18。注意[1,1]和[2,2] 虽然是原序列的子序列,但不是连续子序列,所以不应该被计算。另外,注意其中有一些值相同的子序列,但由于他们在原序列中的下标不同,属于不同的非空连续子序列,所以会被分别计算. 解决该问题有许多算法,以下程序使用分治算法,时间复杂度 。 试补全程序
#include <iostream>
#include <algorithm>
#include <vector>
const int MAXN = 100000;
int n;
int a[MAXN];
long long ans;
void solve(int l, int r) {
if (l + 1 == r) {
ans += a[l];
return;
}
int mid = (l + r) >> 1;
std::vector<int> pre(a + mid, a + r);
for (int i = 1; i < r - mid; ++i) ①;
std::vector<long long> sum(r - mid + 1);
for (int i = 0; i < r - mid; ++i)
sum[i + 1] = sum[i] + pre[i];
for (int i = mid - 1, j = mid, max = 0; i >= l; --i) {
while (j < r && ②) ++j;
max = std::max(max, a[i]);
ans += ③;
ans += ④;
}
solve(l, mid);
solve(mid, r);
}
int main() {
std::cin >> n;
for (int i = 0; i < n; ++i)
std::cin >> a[i];
⑤;
std::cout << ans << std::endl;
return 0;
}
39.①处应填( ) {{ select(39) }}
pre[i] = std::max(pre[i - 1], a[i - 1])
pre[i + 1] = std::max(pre[i], pre[i + 1])
pre[i] = std::max(pre[i - 1], a[i])
pre[i] = std::max(pre[i], pre[i - 1])
40.②处应填( )
{{ select(40) }}
a[j] < max
a[j] < a[i]
pre[j - mid] < max
pre[j - mid] > max
41.③处应填( ) {{ select(41) }}
(long long)(j - mid) * max
(long long)(j - mid) * (i - 1)* max
sum[j - mid]
sum[j - mid] * (i- 1)
42.④处应填( ) {{ select(42) }}
(long long)(r - j) * max
(long long)(r - j) * (mid - i) * max
sum[r - mid] - sum[j - mid]
(sum[r - mid] - sum[j - mid]) * (mid - i)
43.⑤处应填( ) {{ select(43) }}
solve(0,n)
solve(0,n - 1)
solve(1,1)
solve(1,n - 1)