2024CSPJ初赛模拟题(六)
一、单项选择题
1.被后人称为“现代计算机之父” 的是（）。 {{ select(1) }}
- 姚期智
- 艾伦·麦席森·图灵
- 约翰·冯·诺依曼
- 克劳德·艾尔伍德·香农
- 二进制
- 八进制
- 十进制
- 十六进制
3.以下关于数据结构的说明正确的是（）。 {{ select(3) }}
- 队列是一种“先进先出” 的线性表，其限制是只允许在表的一端进行插入和删除运 算。
- 链表是一种物理存储单元上非连续、顺序的存储结构。
- 二叉树特点是每个结点最多只能有两棵子树，且有左右之分。
- 哈希表是根据关键码值而间接进行访问的数据结构。 【答案】C
4.以下程序段最为准确的时间复杂度分析结果为（）。
int i = 1;
while (i <= n)
i = 2 * i;
{{ select(4) }}
- O(logn)
- O(n)
- O(n^2)
- O(2n)
5.闰年的计算方法是： 四年一闰，百年不闰，四百年再闰。一个人出生于 1896 年 2 月 29 日，于 2001 年 3 月 1 日去世，这个人一共可以过多少次生日？(出生那天不计算在 内) {{ select(5) }}
- 25
- 26
- 27
- 28
6.有 5 个元素，按照 4 、5 、3 、 1 、2 的顺序入栈，请问下面哪个出栈序列是非法的 ()。 {{ select(6) }}
- 5 4 3 2 1
- 2 1 3 5 4
- 5 3 2 1 4
- 1 2 3 4 5
7.前缀表达式 + 5 * - 4 3 2 的结果为（），其中+ 、- 、*是运算符。 {{ select(7) }}
- 3
- 5
- 7
- 9
8.以下代码段为实现两数交换，则①内要填入的语句是（）。
void sp(int &a, int &b)
{
a = a + b;
①;
a = a - b;
}
{{ select(8) }}
- b = b - a;
- b = a + b;
- b = a - b;
- a = a - b;
9.一个具有 10 个顶点，20 条边的简单无向图，其所有顶点的度数之和是（）。 {{ select(9) }}
- 10
- 20
- 40
- 90
10.一棵有 n 个结点的完全二叉树用数组进行存储和表示，已知根结点存储在数组的第1 个位置。那么存储在数组第 19 个位置的结点的父结点位置是（）。 {{ select(10) }}
- 8
- 9
- 18
- 38
11.当 a=7 ，b=2 时，表达式 a&(1<<b)的值为（）。 {{ select(11) }}
- 4
- 5
- 6
- 7
12.抽奖箱中装有 4 个完全相同的小球，小球上面依次有编号 1,2,3,4，随机摸出一个小 球后不放回，再随机摸出一个小球，则两次摸出的小球编号之和等于 5 的概率为() {{ select(12) }}
- 1
- 1/2
- 1/3
- 1/4
13.十进制数 163.25 ，转换为十六进制为（）。 {{ select(13) }}
- B3.4
- 3A.2
- A3.4
- 3A.4
14.假设一棵二叉树的前序遍历序列为ABDFCEG，中序遍历序列为 DFBACGE，则其 后序遍历序列为（）。 {{ select(14) }}
- FDBGECA
- DFBGECA
- FDBGCEA
- DFBCEGA
15.仅由数字 1,3,5 组成的四位数中，相邻数字均不相同的四位数的个数是（）。 {{ select(15) }}
- 12
- 18
- 24
- 32
二、阅读程序
（1）
01 #include <bits/stdc++.h>
02 using namespace std;
03 int main() 04 {
05 string a = "", b = "";
06 char s[101] = {};
07 cin.getline(s, 101);
08 int len = strlen(s), t;
09 for (int i = 0; i < len; i++)
10 if (s[i] >= 'A' && s[i] <= 'Z')
11 t = (s[i] - 'A' + 3) % 26, a += t + 'a';
12 else
13 t = (s[i] - 'a' + 23) % 26, b += t + 'A';
14 int lena = a.size(), lenb = b.size();
15 if (lena == lenb) reverse(b.begin(), b.end());
16 else
17 {
18 if (lenb < lena) swap(a, b), swap(lena, lenb);
19 a.insert(lena, b.substr(lena, lenb - lena));
20 reverse(a.begin(), a.end());
21 }
22 cout << a << " " << b << endl;
23 return 0;
24 }
输入保证只有大小写字母及空格，完成下面的判断题和单选题 l 判断题
16.当输入只有大小写字母和空格时，输出只有大小写字母( ) {{ select(16) }}
- 正确
- 错误
17.如果输入了大小写字母及空格之外的其他字符，运行会报错( ) {{ select(17) }}
- 正确
- 错误
18.将第 8 行变量 t 的类型修改为char 会影响结果( ) {{ select(18) }}
- 正确
- 错误
l 单选题
19.如果输出是 XYZYX XYZYX 时，那么输入为( ) {{ select(19) }}
- ABCBA
- ABcBA
- abcba
- abCba
20.当输入的是 ABCdef 时，输出为( ) {{ select(20) }}
- fed ABC
- ABC fed
- CBA def
- def CBA
（2）
01 #include<iostream>
02 #include<cstdio>
03 #include<cstring>
04 #include<cmath>
05 #include<cstdlib>
06 #include<algorithm>
07 #define LL long long
08 using namespace std;
09 LL n, k;
10 struct node{
11 LL a[105][105];
12 }p, q;
13 node array(node x, node y)
14 {
15 node t;
16 for (LL i = 1; i <= n; i++)
17 for (LL j = 1; j <= n; j++) t.a[i][j] = 0;
18 for (LL i = 1; i <= n; i++)
19 {
20 for (LL j = 1; j <= n; j++)
21 {
22 for (LL k = 1; k <= n; k++)
23 {
24 t.a[i][j] = (t.a[i][j] + (x.a[i][k] *
25 y.a[k][j]) % 1000000007) % 1000000007;
26 }
27 }
28 }
29 return t;
30 }
31 node Qpow(LL k)
32 {
33 node ans;
34 for (LL i = 1; i <= n; i++) ans.a[i][i] = 1;
35 while (k)
36 {
37 if (k & 1)
38 {
39 ans = array(ans, p);
40 }
41 k >>= 1;
42 p = array(p, p);
43 }
44 return ans;
45 }
46 int main()
47 {
48 cin >> n >> k;
49 for (LL i = 1; i <= n; i++)
50 {
51 for (LL j = 1; j <= n; j++)
52 {
53 cin >> p.a[i][j];
54 }
55 }
56 q = Qpow(k);
57 for (LL i = 1; i <= n; i++)
58 {
59 for (LL j = 1; j <= n; j++)
60 {
61 cout << q.a[i][j] << " ";
62 }
63 cout<<endl;
64 }
65 return 0;
66 }
输入保证： 1≤n≤100 ，0≤k≤10^12 ，-1000≤p.a[i][j]≤1000
l 判断题
21.算法 Qpow(LL k) 的时间复杂度为 O(nlogn)。 {{ select(21) }}
- 正确
- 错误
22.将第 37 行"k & 1"替换为"k % 2" ，程序结果不变。 {{ select(22) }}
- 正确
- 错误
23.输入的矩阵数字都相等时，输出必然全部相等。 {{ select(23) }}
- 正确
- 错误
l 单选题
24.当输入为"2 2 1 1 1 1"时，输出的所有数字之和为()。 {{ select(24) }}
- 2
- 4
- 8
- 16
25.当输入为"2 2 1 2 3 4"时，输出的第一行为()。 {{ select(25) }}
- 1 4
- 3 6
- 5 8
- 7 10
26.当输入为"3 3 1 -2 3 -4 5 -6 7 -8 9"时，输出包含以下哪个选项()。 {{ select(26) }}
- 470
- -1064
- -1548
- 2414
（3）
01 #include<bits/stdc++.h>
02 using namespace std;
03 typedef struct node
04 {
05 int value;
06 struct node *left, *right;
07 } Node, *root;
08 int search_tree(root T, int key, root f, root *p)
09 {
10 if (T == NULL)
11 {
12 *p = f;
13 return 0;
14 }
15 else if (key == T->value)
16 {
17 *p = T;
18 return 1;
19 }
20 else if (key < T->value) return search_tree(T->left, key, T, p);
21 else return search_tree(T->right, key, T, p); 22 }
23 void insert_tree(root *T, int num)
24 {
25 root p = 0;
26 if (!search_tree(*T, num, 0, &p))
27 {
28 root s = (root)malloc(sizeof(Node));
29 s->value = num;
30 s->left = s->right = NULL;
31 if (!p) *T = s;
32 else if (num < p->value) p->left = s;
33 else p->right = s;
34 }
35 }
36 void order_print(root t)
37 {
38 if (t == 0) return;
39 order_print(t->left);
40 cout << t->value << " ";
41 order_print(t->right);
42 }
43 int main()
44 {
45 int n, t;
46 cin >> n;
47 root T = 0;
48 for (int i = 1; i <= n; i++)
49 {
50 cin >> t;
51 insert_tree(&T, t);
52 }
53 order_print(T);
54 }
输入 n 个数（3<=n<=1024）,数字可能相同
l 判断题 27.当输入的 n 个数字都不同时，也会输出 n 个不同的数字（ ）。 {{ select(27) }}
- 正确
- 错误
28.第 10 行的 T==NULL 修改为!T 不会影响结果（ ）。 {{ select(28) }}
- 正确
- 错误
29.去掉第 30 行的初始化也不影响结果（ ）。 {{ select(29) }}
- 正确
- 错误
l 单选题
30.search_tree 函数的时间复杂度为（ ）。 {{ select(30) }}
- O(n^2)
- O(nlogn)
- O(logn)
- O(n)
31.当输入为 5 5 2 3 6 9 时，输出为（ ）。 {{ select(31) }}
- 2 3 5 6 9
- 5 2 3 6 9
- 9 6 5 3 2
- D.3 2 9 6 5
32.当输入为 6 2 1 3 5 3 6 时，输出为（ ）。 {{ select(32) }}
- 1 2 3 3 5 6
- 1 2 3 5 6
- 6 5 3 3 2 1
- 6 5 3 2 1
三、完善程序
（1）（反素数）对于任何正整数 x，其约数个数记做 f(x)，例如 f(2) = 2,f(8) = 4，如 果某个正整数 x 满足对任意的 i（0 < i < x）都有 f(i) < f(x)，则称 x 为反素数。
输入一个正整数 n（1 < n <= 5000），求[1,n]内的最大反素数。
提示： 反素数性质 1 ：一个反素数的所有质因子是从 2 开始连续的质数
反素数性质 2：如果反素数 x = 2^a1 * 3^a2 * 5^a3……，那么必有 a1≥a2≥a3 … …
#include <bits/stdc++.h>
using namespace std;
int main ()
{
int n, maxn = 0, ans = 0, tmp = 0, sum = 1;
cin >> n;
for (int i = 2; i <= n; i++) {
tmp = ①;
for (intj = 2; j <= i; j++) {
int cnt = 0;
②{
tmp /= j;
③;
}
sum *= ④; }
if(sum > maxn) ans = i, maxn = sum;
⑤;
}
cout << ans << endl; return 0 ;
}
33.①处应填（）。 {{ select(33) }}
- n
- 0
- i
- sum
34.②处应填（）。 {{ select(34) }}
- if(n % j == 0)
- if(tmp % j == 0)
- while(n % j == 0)
- while(tmp % j == 0)
35.③处应填（）。 {{ select(35) }}
- cnt = j
- cnt = tmp % j
- cnt += 1
- cnt += j
36.④处应填（）。 {{ select(36) }}
- cnt
- cnt + 1
- cnt++
- cnt + j
37.⑤处应填（）。 {{ select(37) }}
- sum = 1
- sum += tmp
- sum = 0
- ans += sum
（2）(单元最短路径) 给出一个有向图，计算从某一点出发到所有点的最短路径长度。 试补全程序。
#include <iostream>
#include <queue>
#define inf 2147483647;
using namespace std;
int head[1000005], dis[1000005], vis[1000005];
int n, m, id, u, v, w, cnt;
struct Edge{
int next, to, val;
}edge[1000005];
void add(int u, int v, int w) {
edge[①].next = head[u]; edge[cnt].to = v;
edge[cnt].val = w; head[u] = cnt;
}
int main() {
queue<int> q;
cin >> n >> m >> id;
for (int i = 1; i <= m; ++i) {
cin >> u >> v >> w; add(u, v, w);
}
for (int i = 1; i <= n; ++i) {
②;
vis[i] = 0;
}
q.push(id); dis[id] = 0; vis[id] = 1;
while (③) {
int x = q.front();
q.pop(); vis[x] = 0;
for (int i = head[x]; ④; i=edge[i].next) {
int y = edge[i].to;
if (dis[y] > dis[x] + edge[i].val) {
⑤;
if (vis[y] == 0) {
vis[y] = 1; q.push(y);
}
}
}
}
for (int i = 1; i <= n; ++i) {
cout << dis[i] << " ";
}
return 0;
}
38.①处应填（）。 {{ select(38) }}
- u
- cnt++
- ++cnt
- v
39.②处应填（）。 {{ select(39) }}
- dis[i] = 0
- head[i] = 0
- head[i] = inf
- dis[i] = inf
40.③处应填（）。 {{ select(40) }}
- !q.empty()
- q.empty()
- id<=n
- id<=m
41.④处应填（）。 {{ select(41) }}
- --i
- i!=0
- i==0
- ++i
42.⑤处应填（）。 {{ select(42) }}
- dis[y] = edge[i].val
- dis[y] = dis[x]
- dis[y] = dis[x] + edge[i].val
- dis[x] = dis[y] + edge[i].val