#CSPS12024. 【2024】CSP-S 提高级 第一轮试题(初赛)
【2024】CSP-S 提高级 第一轮试题(初赛)
【2024】CSP-S 提高级 第一轮试题(初赛)
一、单项选择题(共 15 题,每题 2 分,共计 30 分;每题有且仅有一个正确选项)
1、在 Linux 系统中,如果你想显示当前工作目录的路径,应该使用哪个命令?( ) {{ select(1) }}
- pwd
- cd
- ls
- echo
2、假设一个长度为 n 的整数数组中每个元素互不相同,且这个数组是无序的。要找到这个数组中最大元素的时间复杂度是多少?( ) {{ select(2) }}
- O(n)
- O(log n)
- O(n log n)
- O(1)
3、在 C++中,以下哪个函数调用会造成栈溢出?( ) {{ select(3) }}
- int foo() { return 0; }
- int bar() { int x=1; return x; }
- void baz() { int a[1000]; baz(); }
- void qux() { return; }
4、在一场比赛中,有 10 名选手参加,前三名将获得金银铜牌,若不允许并列,且每名选手只能获得一枚奖牌,则不同的颁奖方式共有多少种?( ) {{ select(4) }}
- 120
- 720
- 504
- 1000
5、下面哪个数据结构最适合实现先进先出(FIFO)的功能?( ) {{ select(5) }}
- 栈
- 队列
- 线性表
- 二叉搜索树
6、已知 , 且对于 有 ,则 的值为:( ) {{ select(6) }}
- 4
- 5
- 6
- 7
7、假设一个包含 n 个顶点的无向图,且该图是欧拉图。以下关于该图的描述中哪一项不一定正确?( ) {{ select(7) }}
- 所有顶点的度数均为偶数
- 该图联通
- 该图存在一个欧拉回路
- 该图的边数是奇数
8、对数组进行二分查找的过程中,以下哪个条件必须满足?( ) {{ select(8) }}
- 数组必须是有序的
- 数组必须是无序的
- 数组长度必须是 2 的幂
- 数组中的元素必须是整数
9、考虑一个自然数 n 以及一个模数 m,你需要计算 n 的逆元(即 n 在模 m 意义下的乘法逆元)。下列哪种算法最为合适?( ) {{ select(9) }}
- 使用暴力方法依次尝试
- 使用扩展欧几里得解法
- 使用快速幂解法
- 使用线性筛法
10、在设计一个哈希表时,为了减少冲突,需要使用适当的哈希函数和冲突解决策略。已知某哈希表中有 n 个键值对,表的装载因子为 。在使用开放地址法解决冲突的过程中,最坏情况下查找一个元素的时间复杂度为( ) {{ select(10) }}
- O(1)
- O(log n)
- O(1/(1-α))
- O(n)
11、假设有一颗 h 层的完全二叉树,该树最多包含多少个节点( ) {{ select(11) }}
- 2^h-1
- 2^{h+1}-1
- 2^h
- 2^{h+1}
12、设有一个10个顶点的完全图,每两个顶点之间都有一条边,有多少个长度为4的环?( ) {{ select(12) }}
- 120
- 210
- 630
- 5040
13、对于一个整数 ,定义 为 的各位数字之和,问使 的最小自然数 是多少?( ) {{ select(13) }}
- 29
- 199
- 299
- 399
14、设有一个长度为 n 的 01 字符串,其中有 k 个 1,每次操作可以交换相邻两个字符。在最坏的情况下将这 k 个 1 移到字符串最右边所需要的交换次数是多少?( ) {{ select(14) }}
- k
- k*(k-1)/2
- (n-k)*k
- (2n-k-1)*k/2
15、如图是一张包含7个顶点的有向图。如果要删除其中一些边,使得从节点1到节点7 没有可行路径,且删除的边数最少,请问总共有多少种可行的删除边的集合?( )
![有向图](file://15有向图.png)
{{ select(15) }}
- 1
- 2
- 3
- 4
二、阅读程序(程序输入不超过数组或字符串定义的范围;判断题正确填A,错误填B;除特殊说明外,判断题1.5分,选择题3分,共计40分)
阅读程序(1)
1 #include <iostream>
2 using namespace std;
3
4 const int N = 1000;
5 int c[N];
6
7 int logic(int x, int y) {
8 return (x & y) ^ ((x ^ y) | (~x & y));
9 }
10 void generate(int a, int b, int *c) {
11 for (int i = 0; i < b; i++) {
12 c[i] = logic(a, i) % (b + 1);
13 }
14 }
15 void recursion(int depth, int *arr, int size) {
16 if (depth <= 0 || size <= 1) return;
17 int pivot = arr[0];
18 int i = 0, j = size - 1;
19 while (i <= j) {
20 while (arr[i] < pivot) i++;
21 while (arr[j] > pivot) j--;
22 if (i <= j) {
23 int temp = arr[i];
24 arr[i] = arr[j];
25 arr[j] = temp;
26 i++;j--;
27 }
28 }
29 recursion(depth - 1, arr, j + 1);
30 recursion(depth - 1, arr + i, size - i);
31 }
32
33 int main() {
34 int a, b, d;
35 cin >> a >> b >> d;
36 generate(a, b, c);
37 recursion(d, c, b);
38 for (int i = 0; i < b; i++) cout << c[i] << " ";
39 cout<<endl;
40 }
判断题:
16、当 时,输出的序列是有序的( ) {{ select(16) }}
- 正确
- 错误
17、当输入“5 5 1”时,输出为“1 1 5 5 5”( ) {{ select(17) }}
- 正确
- 错误
18、假设数组 c 长度无限制,该程序所实现的算法的时间复杂度是 的( ) {{ select(18) }}
- 正确
- 错误
单选题:
19、函数 int logic(int x,int y)
的功能是( )
{{ select(19) }}
- 按位与
- 按位或
- 按位异或
- 以上都不是
20、(4分) 当输入为“10 100 100”时,输出的第 100 个数是( ) {{ select(20) }}
- 91
- 94
- 95
- 98
阅读程序(2)
1 #include <iostream>
2 #include <string>
3 using namespace std;
4
5 const int P = 998244353, N = 1e4 + 10, M = 20;
6 int n, m;
7 string s;
8 int dp[1 << M];
9
10 int solve() {
11 dp[0] = 1;
12 for (int i = 0; i < n; i++) {
13 for (int j = (1 << (m - 1)) - 1; j >= 0; j--) {
14 int k = (j << 1) | (s[i] - '0');
15 if (j != 0 || s[i] == '1')
16 dp[k] = (dp[k] + dp[j]) % P;
17 }
18 }
19 int ans = 0;
20 for (int i = 0; i < (1 << m); i++) {
21 ans = (ans + 1ll * i * dp[i]) % P;
22 }
23 return ans;
24 }
25 int solve2() {
26 int ans = 0;
27 for (int i = 0; i < (1 << n); i++) {
28 int cnt = 0;
29 int num = 0;
30 for (int j = 0; j < n; j++) {
31 if (i & (1 << j)) {
32 num = num * 2 + (s[j] - '0');
33 cnt++;
34 }
35 }
36 if (cnt <= m)(ans += num) %= P;
37 }
38 return ans;
39 }
40
41 int main() {
42 cin >> n >> m;
43 cin >> s;
44 if (n <= 20) {
45 cout << solve2() << endl;
46 }
47 cout << solve() << endl;
48 return 0;
49 }
假设输入的 s 是包含 n 个字符的 01 串,完成下面的判断题和单选题:
判断题
21、函数 solve()
所实现的算法时间复杂度是 。
{{ select(21) }}
- 正确
- 错误
22、输入“11 2 10000000001”时,程序输出两个数 32 和 23。 {{ select(22) }}
- 正确
- 错误
23、(2分) 在 时,solve()
的返回值始终小于 。
{{ select(23) }}
- 正确
- 错误
单选题
24、当 且 时,有多少种输入使得两行的结果完全一致? {{ select(24) }}
- 1024
- 11
- 10
- 0
25、当 时,solve()
的最大可能返回值为?
{{ select(25) }}
- 65
- 211
- 665
- 2059
26、若 ,,solve
和 solve2
的返回值的最大可能的差值为?
{{ select(26) }}
- 1477
- 1995
- 2059
- 2187
阅读程序(3)
1 #include <iostream>
2 #include <cstring>
3 #include <algorithm>
4 using namespace std;
5
6 const int maxn = 1000000 + 5;
7 const int P1 = 998244353, P2 = 1000000007;
8 const int B1 = 2, B2 = 31;
9 const int K1 = 0, K2 = 13;
10
11 typedef long long ll;
12
13 int n;
14 bool p[maxn];
15 int p1[maxn], p2[maxn];
16
17 struct H {
18 int h1, h2, l;
19 H(bool b = false) {
20 h1 = b + K1;
21 h2 = b + K2;
22 l = 1;
23 }
24 H operator + (const H &h) const {
25 H hh;
26 hh.l = l + h.l;
27 hh.h1 = (1ll * h1 * p1[h.l] + h.h1) % P1;
28 hh.h2 = (1ll * h2 * p2[h.l] + h.h2) % P2;
29 return hh;
30 }
31 bool operator == (const H &h)const {
32 return l == h.l && h1 == h.h1 && h2 == h.h2;
33 }
34 bool operator < (const H &h)const {
35 if (l != h.l)return l < h.l;
36 else if (h1 != h.h1)return h1 < h.h1;
37 else return h2 < h.h2;
38 }
39 } h[maxn];
40
41 void init() {
42 memset(p, 1, sizeof(p));
43 p[0] = p[1] = false;
44 p1[0] = p2[0] = 1;
45 for (int i = 1; i <= n; i++) {
46 p1[i] = (1ll * B1 * p1[i - 1]) % P1;
47 p2[i] = (1ll * B2 * p2[i - 1]) % P2;
48 if (!p[i])continue;
49 for (int j = 2 * i; j <= n; j += i) {
50 p[j] = false;
51 }
52 }
53 }
54
55 int solve() {
56 for (int i = n; i; i--) {
57 h[i] = H(p[i]);
58 if (2 * i + 1 <= n) {
59 h[i] = h[2 * i] + h[i] + h[2 * i + 1];
60 } else if (2 * i <= n) {
61 h[i] = h[2 * i] + h[i];
62 }
63 }
64 cout << h[1].h1 << endl;
65 sort(h + 1, h + n + 1);
66 int m = unique(h + 1, h + n + 1) - (h + 1);
67 return m;
68 }
69
70 int main() {
71 cin >> n;
72 init();
73 cout << solve() << endl;
74 }
判断题
27、假设程序运行前能自动将 maxn
改为 ,所实现的算法的时间复杂度是 。
{{ select(27) }}
- 正确
- 错误
28、时间开销的瓶颈是 init()
函数
{{ select(28) }}
- 正确
- 错误
29、若修改常数 或 的值,该程序可能会输出不同的结果 {{ select(29) }}
- 正确
- 错误
单选题
30、在 solve()
函数中,h[ ]
的合并顺序可以看作是:( )
{{ select(30) }}
- 二叉树的 BFS 序
- 二叉树的先序遍历
- 二叉树的中序遍历
- 二叉树的后序遍历
31、输入“10”,输出的第一行是?( ) {{ select(31) }}
- 83
- 424
- 54
- 110101000
32、(4 分)输入“16”,输出的第二行是?( ) {{ select(32) }}
- 7
- 9
- 10
- 12
三、完善程序(共 10 题,每题 3 分,共计 30 分;每题有且仅有一个正确选项)
完善程序(1)
(序列合并)有两个长度为 的单调不降序列 和 ,序列的每个元素都是小于 的非负整数。在 和 中各取一个数相加可以得到 个和,求其中第 小的和。上述参数满足 和
#include <iostream>
using namespace std;
const int maxn = 100005;
int n;
long long k;
int a[maxn], b[maxn];
int *upper_bound(int *a, int *an, int ai) {
int l = 0, r = ___(1)___ ;
while (l < r) {
int mid = (l + r) >> 1;
if (___(2)___) {
r = mid;
} else {
l = mid + 1;
}
}
return ___(3)___ ;
}
long long get_rank(int sum) {
long long rank = 0;
for (int i = 0; i < n; i++) {
rank += upper_bound(b, b + n, sum - a[i]) - b;
}
return rank;
}
int solve() {
int l = 0, r = ___(4)___ ;
while (l < r) {
int mid = ((long long)l + r) >> 1;
if (___(5)___) {
l = mid + 1;
} else {
r = mid;
}
}
return l;
}
int main() {
cin >> n >> k;
for (int i = 0; i < n; ++i)
cin >> a[i];
for (int i = 0; i < n; ++i)
cin >> b[i];
cout << solve() << endl;
return 0;
}
33、(1)处应填( ) {{ select(33) }}
- an-a
- an-a-1
- ai
- ai+1
34、(2)处应填( ) {{ select(34) }}
- a[mid]>ai
- a[mid]>=ai
- a[mid]<ai
- a[mid]<=ai
35、(3)处应填( ) {{ select(35) }}
- a+l
- a+l+1
- a+l-1
- an-l
36、(4)处应填( ) {{ select(36) }}
- a[n-1]+b[n-1]
- a[n]+b[n]
- 2*maxn
- maxn
37、(5)处应填( ) {{ select(37) }}
- get_rank(mid)<k
- get_rank(mid)<=k
- get_rank(mid)>k
- get_rank(mid)>=k
完善程序(2)
(次短路)已知一个 n 个点 m 条边的有向图 G,并且给定图中的两个点 s 和 t,求次短路(长度严格大于最短路的最短路径)。如果不存在,输出一行“-1”。如果存在,输出两行,第一行表示次短路的长度,第二行表示次短路的一个方案。
#include <cstdio>
#include <queue>
#include <utility>
#include <cstring>
using namespace std;
const int maxn = 2e5 + 10, maxm = 1e6 + 10, inf = 522133279;
int n, m, s, t;
int head[maxn], nxt[maxm], to[maxm], w[maxm], tot = 1;
int dis[maxn << 1], *dis2;
int pre[maxn << 1], *pre2;
bool vis[maxn << 1];
void add(int a, int b, int c) {
++tot;
nxt[tot] = head[a];
to[tot] = b;
w[tot] = c;
head[a] = tot;
}
bool upd(int a, int b, int d, priority_queue<pair<int, int> > &q) {
if (d >= dis[b])return false;
if (b < n) ___(1)___;
q.push(___(2)___);
dis[b] = d;
pre[b] = a;
return true;
}
void solve() {
priority_queue<pair<int, int> >q;
q.push(make_pair(0, s));
memset(dis, ___(3)___, sizeof(dis));
memset(pre, -1, sizeof(pre));
dis2 = dis + n;
pre2 = pre + n;
dis[s] = 0;
while (!q.empty()) {
int aa = q.top().second; q.pop();
if (vis[aa])continue;
vis[aa] = true;
int a = aa % n;
for (int e = head[a]; e ; e = nxt[e]) {
int b = to[e], c = w[e];
if (aa < n) {
if (!upd(a, b, dis[a] + c, q))
___(4)___
} else {
upd(n + a, n + b, dis2[a] + c, q);
}
}
}
}
void out(int a) {
if (a != s) {
if (a < n) out(pre[a]);
else out(___(5)___);
}
printf("%d%c", a % n + 1, " \n"[a == n + t]);
}
int main() {
scanf("%d%d%d%d", &n, &m,&s,&t);
s--, t--;
for (int i = 0; i < m; ++i) {
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
add(a - 1, b - 1, c);
}
solve();
if (dis2[t] == inf) puts("-1");
else {
printf("%d\n", dis2[t]);
out(n + t);
}
return 0;
}
38、(1)处应填( ) {{ select(38) }}
- udp(pre[b],n+b,dis[b],q)
- upd(a,n+b,d,q)
- upd(pre[b],b,dis[b],q)
- upd(a,b,d,q)
39、(2)处应填( ) {{ select(39) }}
- make_pair(-d,b)
- make_pair(d,b)
- make_pair(b,d)
- make_pair(-b,d)
40、(3)处应填( ) {{ select(40) }}
- 0xff
- 0x1f
- 0x3f
- 0x7f
41、(4)处应填( ) {{ select(41) }}
- upd(a,n+b,dis[a]+c,q)
- upd(n+a,n+b,dis2[a]+- q)
- upd(n+a,b,dis2[a]+c,q)
- upd(a,b,dis[a]+c,q)
42、(5)处应填( ) {{ select(42) }}
- pre2[a%n]
- pre[a%n]
- pre2[a]
- pre[a%n]+1
相关
在以下作业中: