2024CSPJ初赛模拟题(五)
一、单项选择（共 15 题，每题 2 分，共计 30 分）
1.“太极生两仪,两仪生四象,四象生八卦” 体现了以下哪一种算法思想( )
{{ select(1) }}
- 枚举
- 贪心
- 分治
- 递归
2.计算机存储的基本单位( )
{{ select(2) }}
- bit
- Byte
- GB
- KB
3.已知 2023 年 10 月 1 日是周日，问 2008 年 10 月 1 日是周几( )
{{ select(3) }}
- 周二
- 周三
- 周四
- 周五
4.中缀表达式(a+b)*c+d 的前缀表达式为 ( )。
{{ select(4) }}
- ab+c*d+
- abcd+*+
- +*+abcd
- +abc*d+
5.十进制小数 9.875 对应的二进制小数为（ ）。
{{ select(5) }}
- 1001.111
- 1001.1111
- 1011.111
- 1011.1111
6.有 n 个独立的点，每次可以用一条边连接其中两个点，问至少连多少条边，可 以使得其中任意两个点都可以通过一条路径互相到达（）。
{{ select(6) }}
- n/2
- n
- 2n
- n-1
7.二叉查找树具有如下性质：每个结点的值都大于其左子树上所有结点的值、小 于其右子树上所有结点的值。那么， 二叉查找树的（ ）是一个从小到大递增的 有序序列。
{{ select(7) }}
- 先序遍历
- 中序遍历
- 后序遍历
- 广度优先遍历
8.抛一枚正反面向上概率均为 1/2 的硬币 4 次，问正面和反面出现次数相等的概 率为 （） {{ select(8) }}
- 1/2
- 3/8
- 1/4
- 以上都不是
9、不包含数字 1 的三位数（不含前导零）有（）个
{{ select(9) }}
- 900
- 648
- 729
- 836
10、 以下不是基于比较的排序为 （）
{{ select(10) }}
- 快速排序
- 基数排序
- 冒泡排序
- 插入排序
11、一个简单无向图共有 16 条边，每个点的度数均为 4，问一共有多少个点( )
{{ select(11) }}
- 4
- 8
- 12
- 16
12、考虑如下递归算法，问调用 solve(5,2)的返回值 ( )
int solve(int n, int m)
if(m==0||m==n) return 1;
else return solve(n-1,m-1)+solve(n-1,m);
{{ select(12) }}
- 7
- 8
- 9
- 10
13、不透明的袋子里有 3 个相同形状的球,其中 2 个是红球，1 个是黑球，有 3 名 选手依次进行抽取，拿到红球则放回袋子，拿到黑球则不放回，问第 3 名选手抽 到红球的概率为 ( )
{{ select(13) }}
- 2/3
- 2/9
- 23/27
- 26/27
14、用 1*2 的多米诺骨牌完全覆盖 5*2 的矩阵有多少种方案（ ） {{ select(14) }}
- 5
- 6
- 7
- 8
15.用 0 到 9 这 10 个数字，可组成（）个没有重复数字的四位偶数。
{{ select(15) }}
- 5040
- 210
- 3024
- 2296
二、阅读程序（除特殊说明外，判断题 1.5 分，选择题 4 分，共计 40 分）
1、
第一行，两个整数 n,m (1<=n,m<=300000) 第二行 n 个数 a_i (1<=a_i<=1000000000)
接下来 m 行，每行两个整数 l,r (1<=l<=r<=n)
16、第 7 行，j+(1<<i)-1<=n 改成 j<=n,可能会导致数组越界( )
{{ select(16) }}
- 正确
- 错误
17、 第 8 行,删去括号 ,程序结果不变( )
{{ select(17) }}
- 正确
- 错误
18、 若将第 26 行的 Log2[len] 替换为 log2(len) ,程序结果不变( )
{{ select(18) }}
- 正确
- 错误
19、 输出结果不可能为 0( )
{{ select(19) }}
- 正确
- 错误
20、 该算法的时间复杂度为( )
{{ select(20) }}
- O((n+m)logn)
- O(nlogn+m)
- O(mnlogn)
- O(mlogn+n)
21、 输入
5 1
3 5 7 4 2
1 4
输出结果为( )
{{ select(21) }}
- 5 7
- 4 7
- 3 7
- 5 4
2、
输入保证 n>=2，n 为偶数
22、 输入 n=6 时,map[3][5]的值是 4。（ ）
{{ select(22) }}
- 正确
- 错误
23、 程序运行到 20 行时，map[n][0,...,n-1]为 n 个两两不相同的数。 ( )
{{ select(23) }}
- 正确
- 错误
24、 输出的值形成一个矩阵，且该矩阵关于从左上到右下的对角线对称。 ( )
{{ select(24) }}
- 正确
- 错误
25、 值为 x 的位置有(i1,j1)(i2,j2),…,则任意的两个位置的 i 和 j 都不相 同。 ( )
{{ select(25) }}
- 正确
- 错误
26、当 n=8 时，输出的第 4 行的值的和是( )。
{{ select(26) }}
- 28
- 36
- 8
- 7
27、 输入为 n，输出的从右上到左下对角线的值的和是( )。
{{ select(27) }}
- n+1
- n
- n(n-1)/2
- (n+1)n/2
3、
规定输入一个字符串和一个正整数。
28、 若输入的字符串是升序的，那么无论 n 为多少，第 13 行的循环都不会执行 （执行条件不满足）。 ( )
{{ select(28) }}
- 正确
- 错误
29、若输入的 n 等于 2，对于 27 行，第一次执行完的字符串 a 与第二次执行完 的 字符串 a 最多只有两个字符位置不同。 ( )
{{ select(29) }}
- 正确
- 错误
30、 程序执行完第 7 行时，第 k+1 个字符到第 l-1 个字符的 ASCII 码是（非 严格） 递减的。 ( )
{{ select(30) }}
- 正确
- 错误
31、若输入的 n 大于a 的长度，可以把 n 改为a 的长度，输出答案保持不变。（ ）
{{ select(31) }}
- 正确
- 错误
32、 若输入字符串 a 为 12345, n 为 3，输出（ ）。(3 分)
{{ select(32) }}
- 15432
- 54321
- 12543
- 12354
33、若输入字符串 a 为 13355, n 为 2，输出（ ）。(3 分)
{{ select(33) }}
- 13355
- 55331
- 13553
- 15533
三、完善程序（单选题，每小题 3 分，共计 30 分）
1、次大公约数）定义 sgcd(x,y)表示 x 和 y 的次大公约数，即能同时整除 x,y 的正整数中第二大的数。如果次大公约数不存在，此时 sgcd(x,y)=-1。
给定 n 个数,分别为 a_1,a_2,...,a_n。求
sgcd(a_1,a_1),sgcd(a_1,a_2),...,sgcd(a_1,a_n)。
样例 输入
4
12450 1 2 450
输出
6225 -1 1 75
数据范围：1<=n<=100000,1<=a_i<= 10^12
1. #include <bits/stdc++.h>
2. using namespace std;
3. typedef long long ll;
4. ll gcd(ll x, ll y) {
5. if (x == 0)
6. return y;
7. return gcd(① );
8. }
9. bool vis[1000005];
10. ll n, a[100005], x, cnt, p[10005], g;
11. int main() {
12. cin >> n;
13. for (ll i = 1; i <= n; i++) scanf("%lld", &a[i]);
14. ll x = a[1];
15. for (ll i = 2; ② <= x; i++) {
16. if (x % i == 0) {
17. p[++cnt] = i;
18. ③
19. }
20. }
21. if (x != 1)
22. p[++cnt] = x;
23. for (ll i = 1; i <= n; i++) {
24. g = gcd(a[1], a[i]);
25. if (④) {
26. printf("-1 ");
27. continue;
28. }
29. for (ll j = 1; j <= cnt; j++) {
30. if (g % p[j] == 0) {
31. printf("%lld ", ⑤);
32. break;
33. }
34. }
35. }
36. return 0;
37. }
34、①处应填（ ）
{{ select(34) }}
- y, y % x
- x % y, y
- y % x, x
- x, y % x
35、②处应填（ ）
{{ select(35) }}
- i
- i * i
- p[i]
- p[i] * p[i]
36、③处应填（ ）
{{ select(36) }}
- x/=i;
- if (x % i == 0) x /= i;
- while (x % i == 0) x /= i;
- while (x % i) x /= i;
37、 ④处应填（）
{{ select(37) }}
- g == 1
- g > 1
- g == 0
- g
38、⑤处应填（ ）
{{ select(38) }}
- g
- p[j]
- g * p[j]
- g / p[j]
2、 (八数码)八数码问题，就是在一个含有 1-8 和 x 的 3*3 方格中，每次可以将 x 与其相 邻位置的数字交换。使得最后变成
1 2 3 4
5 6 7 8
x
你要做的就是实现八数码的解决方案，并要求交换次数最少。
样例 输入
2 3 4
1 5 x
7 6 8
输出
19
1. #include <bits/stdc++.h>
2. using namespace std;
3. int bfs(string st) {
4. string end = "12345678x";
5. queue<string> q;
6. unordered_map<string, int> d;
7. q.push(st);
8. d[st] = 0;
9. int dx[] = { -1, 0, 1, 0 }, dy[] = { ① };
10. while (!q.empty()) {
11. string t = q.front();
12. q.pop();
13. int di = d[t], k = t.find('x'), x = k / 3, ② ;
14. if (t == end)
15. return di;
16. for (int i = 0; i < 4; i++) {
17. int a = x + dx[i], b = y + dy[i];
18. if ( ③ ) {
19. swap(t[k], t[a * 3 + b]);
20. if (④) {
21. d[t] = di + 1;
22. q.push(t);
23. }
24. ⑤
25. }
26. }
27. }
28. return -1;
29. }
30. int main() {
31. string st;
32. for (int i = 0; i < 9; i++) {
33. char c;
34. cin >> c;
35. st += c;
36. }
37. cout << bfs(st);
38. return 0;
39. }
39、①处应填（）
{{ select(39) }}
- 0,1,0,-1
- 1,-1,0,0
- 0,0,1,-1
- 1,0,-1,0
40、②处应填（ ）
{{ select(40) }}
- y = k / 3
- y = k % 3
- y = k / 3 + 1
- y = k % 3 + 1
41、③处应填（ ）
{{ select(41) }}
- a > 0 && a <= 3 && b > 0 && b <= 3
- a > 0 || a <= 3 || b > 0 || b <= 3
- a >= 0 && a < 3 && b >= 0 && b < 3
- a >= 0 || a < 3 || b >= 0 || b < 3
42、④处应填（）
{{ select(42) }}
- d.find(t)!=d.end()
- d.count(t)
- t==end
- !d.count(t)
43、⑤处应填（ ）
{{ select(43) }}
- break;
- swap(t[k], t[a * 3 + b]);
- swap(t[k * 3 + b], t[b]);
- continue;
相关
在以下作业中: