a--7：2023年CSP-J初赛原创模考大赛（8月赛）
2023年CSP-J初赛原创模考大赛(8月赛)
（C++语言 满分：100分 考试时间：120分钟）
单项选择题（每题只有一个正确选项，每题2分，共30分）
1. 计算机的五大基本组成部分是什么？（ ）
A. 输入设备、输出设备、控制器、运算器、存储器
B. 处理器、硬盘、内存、网络接口、显卡
C. 电源、风扇、机箱、屏幕、键盘
D. 操作系统、应用软件、语言编译器、数据库、安全软件
2. 以下关于switch说法不正确的是：（ ）。
A. switch语句中的default语句可以放在任意位置
B. switch语句中case后的表达式只能是常量表达式
C. switch语句中case语句必须在default语句之前
D. switch语句中case表达式不要求顺序
3. 程序运行后输出的结果是（ ）。
#include <iostream>
using namespace std;
int main() {
int i = 0, j = 1;
do {
i += j;
j++;
} while (j <= 10);
cout << i << endl;
return 0;
}
A. 36 B. 45 C. 55 D. 66
4. 某进制数: (347)r=(3213)4, 则 r = （ ）。
A. 4 B. 8 C. 12 D. 16
5. 关于位运算，下列不正确的是（ ）。
A. x | (1 << n)，该运算可以将 x 的第 n 位设置为 1
B. x & ~(1 << n)，该运算可以将 x 的第 n 位设置为1
C. x ^ (1 << j)，该运算可以将 x 的第 j 位取反
D. a ^= b ^= a ^= b，该运算可以交换a和b的值
6. 参加合唱的5名同学已经排好顺序，老师决定临时增加2名同学一同合唱。要将这2名同学插到队伍中，但二者不能相邻，那么有多少种不同的插法？（ ）。
A. 12 B. 30 C. 15 D. 25
7. 5个人围着圆桌坐下，共有多少种坐法？（ ）。
A. 75 B. 48 C. 24 D. 120
8. 已知二叉树的中序遍历序列为ACBDEFHGI，后序遍历序列为ACDBHIGFE。那么前序遍历序列为？（ ）。
A. BCADFGHIE B. ABCDEFGHI C. EBDCAFGHI D. EBCADFGHI
9. 一棵 n 层的满二叉树，总结点的数量和叶子结点数量之差是多少？（ ）。
A. 2^(n-1)- 2^n-1 B. 2^(n-1)-2^n+1
C. 2^n-1-2^(n-1) D. 2^n- 1-2^(n-2)
10. 现有2个空栈A、B，存在5个互不相同的元素s1、s2、s3、s4、s5，每个元素分别按照进栈A、出栈A、进栈B、出栈B的顺序操作，进入栈A的先后顺序为s1、s2、s3、s4、s5。那么51342、53421、12345、34521这4种出栈B的元素编号顺序有几个是可行的？（ ）。
A. 1 B. 2 C. 3 D. 4
11. 以下代码在输入2 8时的结果是？（ ）。
#include <bits/stdc++.h>
using namespace std;
int f(int a, int b){
if (a == b) return 1;
else if (a < b) return f(a + 1, b) + 1;
return f(a, b * 2) + 1;
}
int main(){
int a, b;
cin >> a >> b;
cout << f(a, b);
return 0;
}
A. 4 B. 5 C. 7 D. 6
12. 以下代码在输入3时的结果是？（ ）。
#include <bits/stdc++.h>
using namespace std;
int main(){
int num[10] = {20, 3, 5, 12, 18, 6, 1, 0, 10, 35};
int n, ans = 0;
int *p = &num[0];
cin >> n;
while(p < &num[9]){
if (*p & 1) ans++;
if (ans == n) break;
p++;
}
cout << *p;
return 0;
}
A. 1 B. 5 C. 3 D. 35
13. 期末考试结束要对班级里的同学分别按照总分从大到小排序，若总分数相同，按照数学成绩从大到小排序，如果总分与数学成绩都相同，则按照名字字典序从小到大排序，排版成绩单。使用sort函数进行排序，以下能够排版正确的cmp函数是？（ ）。
struct stu{
int sum;//总分
int math;//数学成绩
string name;//名字
};
A. bool cmp(stu a, stu b){
if (a.sum != b.sum) return a.sum > b.sum;
else if (a.math != b.math) return a.math > b.math;
else return a.name < b.name;
}
B. bool cmp(stu a, stu b){
return a.sum > b.sum;
if (a.math < b.math) return 1;
else return a.name < b.name;
}
C. bool cmp(stu a, stu b){
return a.sum > b.sum;
if (a.math > b.math) return a.math > b.math;
else return a.name < b.name;
}
D. bool cmp(stu a, stu b){
if (a.sum > b.sum) return a.sum > b.sum;
else return a.math > b.math;
return a.name < b.name;
}
14. 对于数列{2, 16, 34(1), 71, 39, 34(2), 66, 77, 24}排序后，结果为{2, 16, 24, 34(2), 34(1), 39, 66, 71, 77}。以下说法正确的是？（ ）。
A. 使用的排序算法是稳定排序 B. 使用的排序算法是不稳定排序
C. 使用冒泡排序可以做到 D. 以上都不对
15. 若对如下无向图进行遍历，则下列选项中，不是广度优先遍历的是？（ ）。
A. bacdfe B. abfcde C. bafced D. facbed
二、程序阅读理解题（共3大题，共计40分）
1. （11分）
01 #include <iostream>
02 #include <cmath>
03 using namespace std;
04 unsigned long long k, len;
05 int n;
06 bool flag;
07 int main() {
08 cin >> n >> k;
09 len = pow(2, n - 1);
10 while(len) {
11 if(!flag) {
12 if(k < len) cout << "0";
13 else if(k >= len) {
14 cout << "1";
15 k -= len;
16 flag = true;
17 }
18 } else if(flag) {
19 if(k < len) {
20 cout << "1";
21 flag = false;
22 } else if(k >= len) {
23 cout<< "0";
24 k -= len;
25 }
26 }
27 len >>= 1;
28 }
29 return 0;
30 }
对于输入的数据，1≤n≤64，0≤k<2n。完成下面的判断题和单选题：
判断题
（1）第9行，把pow(2, n - 1)改为1 << (n - 1) 程序运行结果不变。（ ）（1分）
（2）第15行和第24行，k-=len改为 k^=len程序运行结果不变。（ ）（1分）
（3）若n=4,k=15 和 n=5,k=15, 如果输出数据最高位补0对齐，除了最高位不同，其余位相同。（ ）（1.5分）
（4）若n=4,k=15和n=5,k=16, 如果输出数据最高位补0对齐，除了最高位不同，其余位相同。（ ）（1.5分）
选择题
（5）当n,k为正确输入，输出结果为11001011时，k+1结果为（ ）（3分）
A. 138 B. 139 C. 140 D. 141
（6）输出结果 110110111， 问k是（ ）（3分）
A. 292 B. 293 C. 294 D. 295
2. （14分）
01 #include <bits/stdc++.h>
02 using namespace std;
03 vector<int> v[1005];
04 string s;
05 void dfs1(int x) {
06 printf("%d", x);
07 for(int i = 0; i < v[x].size(); i++) {
08 dfsl(v[x][i]);
09 }
10 }
11 void dfs2(int x) {
12 for(int i = 0; i< v[x].size(); i++) {
13 dfs2(v[x][i]);
14 }
15 printf("%d", x);
16 }
17 int main() {
18 cin >> s;
19 s = '(' + s + ')';
20 stack<int> stk;
21 int ans = 0, cnt = 0;
22 for(int i = 0; i < s.size(); i++) {
23 if (s[i] == '(') {
24 stk.push(++cnt);
25 ans += stk.size();
26 }
27 else{
28 int x = stk.top(); stk.pop();
29 if(!stk.empty()) {
30 v[stk.top()].push_back(x);
31 }
32 }
33 }
34 printf("%d\n", ans);
35 dfs1(1);
36 printf("\n");
37 dfs2(1);
38 return 0;
39 }
输入的字符串s是一个合法的圆括号匹配序列，长度不超过20002000。
判断题
（1）第29行的if语句只可能得到true。（ ）（1.5分）
（2）如果s的长度是2n，那么输出的第二行一定是1到n的自然数，按照从小到大的顺序输出。（ ）（1.5分）
选择题
（3）如果输入 ()()(()())，那么输出的第一行是：（ ）（2分）
A. 13 B. 14 C. 15 D. 16
（4）如果s的长度是20，那么输出的第一行的最大值是：（ ）（3分）
A. 45 B. 55 C. 66 D. 78
（5）如果s的长度为100，并且s有且仅有两个子串是"()"，那么输出的第一行的最小值是：（ ）。（3分）
A. 699 B. 701 C. 703 D. 705
（6）如果输出的第三行是4 5 3 6 2 7 1，那么输出的第一行可能是（ ）。（3分）
A. 17 B. 18 C. 19 D. 20
3. （13.5分，判断题1.5分，选择题3分）
01 #include <bits/stdc++.h>
02 using namespace std;
03 vector<int> v[1005];
04 int dis[1005], n;
05 ing bfs(int s) {
06 memset(dis, 0x3f, sizeof(dis));
07 queue<int> q;
08 q.push(s); dis[s] = 0;
09 int ans = 0;
10 while (!q.empty()) {
11 int x = q.front(); q.pop();
12 for (int i = 0; i < v[x].size(); i++) {
13 if (dis[v[x][i]] > dis[x] + 1) {
14 ans = dis[v[x][i]] = dis[x] + 1;
15 q.push(v[x][i]);
16 }
17 }
18 }
19 return ans;
20 }
21 int main() {
22 scanf("%d", &n);
23 for (int i = 1; i < n; i++) {
24 int a, b;
25 scanf("%d%d", &a, &b);
26 v[a].emplace_back(b);
27 v[b].emplace_back(a);
28 }
29 for (int i = 1; i <= n; i++) {
30 printf("%d", bfs(i));
31 }
32 return 0;
33 }
输入的n≤1000，(a,b)代表一条边，输入保证所有的边会组成一棵树。
判断题
（1）每次调用bfs()函数时，其返回值一定不会超过n－1。（ ）
（2）把代码中的emplace_back 替换成push_back，代码的输出不会改变。（ ）
选择题
（3）如果n=100，那么输出的所有数的总和的最大值是：（ ）。
A. 2475 B. 2525 C. 4925 D. 7450
（4）如果n=100，那么输出的所有数的总和的最小值是：（ ）
A. 99 B. 100 C. 199 D. 200
（5）如果n=1000，输入的所有(a,b) 都满足b / 2 == a，那么输出的所有数中出现次数最多的是：（ ）。
A. 17 B. 18 C. 19 D. 20
（6）如果输出的数中最大值是255255，那么输出的数中最小值的最小值是：（ ）。
A. 31 B. 32 C. 127 D. 128
程序完善题（共2大题，每个选择题3分，共计30分）
完善程序
输入两个只包含小写字符的字符串a, b，每次操作只能改变1个字母，请输出最少需要操作多少次可以使得两个字符串满足下列三个条件之一。
1、字符串a中的字符均小于字符串b中的字符；
2、字符串a中的字符均大于字符串b中的字符；
3、两个字符串变成同一个字母。
01 #include <bits/stdc++.h>
02 using namespace std;
03 string a, b;
04 int c1[26], c2[26], ans = INT_MAX;
05 int main() {
06 cin >> a >> b;
07 int n = a.size(), m = b.size();
08 for (int i = 0; i < n; i++) c1[①]++;
09 for (int i = 0; i < m; i++) c2[b[i] - 'a']++;
10 for (int i = 0; i < 26 && ans != 0; i++) {
11 int ca = n - c1[i], cb = m - c2[i];
12 ans = min(ans, ②);
13 if (③) continue;
14 int r1 = 0, r2 = 0;
15 for (int j = i; j < 26; j++) r1 += c1[j];
16 for (int j = 0; j < i; j++) r1 += c2[j];
17 for (int j = 0; j < i; j++) r2 += c1[j];
18 for (int j = i; j < 26; j++) ④;
19 ans = ⑤;
20 }
21 cout << ans;
22 return 0;
23 }
（1）①处应填（ ）。
A. a[i] - 'a' B. (int)a[i] C. a[i] D. a[i] - 'A'
（2）②处应填（ ）。
A. ca B. ca + cb C. cb D. abs(ca - cb)
（3）③处应填（ ）。
A. c1[i] == 0 B. i == 25 C. i == 0 D. c2[i] == 0
（4）④处应填（ ）。
A. r1 += c1[j] B. r1 += c2[j] C. r2 += c1[j] D. r2 += c2[j]
（5）⑤处应填（ ）。
A. max(ans, min(r1, r2)) B. min(ans, max(r1, r2))
C. min(ans, min(r1, r2)) D. min(r1, r2)
小 Z 最近玩了一个特殊的消消乐游戏，给定n个数字，c[1],c[2]...c[n]，如果其中的子串是回文的，那么小 Z 可以用1次机会销毁这个子串。请问小 Z 最少需要多少次才能销毁所有的数字。
注意：1.消完一次后剩下的数字会自动向开头补过来。2.回文的定义是正过来倒过来都一样。
输入描述：
第一行，一个正整数n。（1<=n<=500）
第二行，n个正整数，依次为c[1],c[2]...c[n]。(1<=c[i]<=n)
输出描述：
一个正整数，表示最少的次数。
样例1：
输入样例：
3
1 2 3
输出样例：
3
样例2：
输入样例：
7
1 4 4 2 3 2 1
输出样例：
2
样例解释：先消4 4，再消1 2 3 2 1，因此共2次。
01 #include <bits/stdc++.h>
02 using namespace std;
03 const int N = 510;
04 int n, c[N], f[N][N];
05 int main() {
06 scanf("%d", &n);
07 for(int i = 1; i <= n; i++) scanf("%d", &c[i]);
08 memset(f, 0x3f, sizeof f);
09 for(int len = 1; len <= n; len++)
10 for(int l = 1; l + len - 1 <= n; l++) {
11 int r = ①;
12 if (len == 1) f[l][r] = 1;
13 else if (len == 2) {
14 if (c[l] == c[r]) f[l][r] = ②;
15 else f[l][r] = ③;
16 }
17 else {
18 if (c[l] == c[r]) f[l][r] = ④;
19 for (int k = l; k < r; k++)
20 f[l][r] = min(f[l][r], ⑤);
21 }
22 }
23 printf("%d\n", f[1][n]);
24 return 0;
25 }
（1）①处应填写（ ）。
A. n B. len C. l + len – 1 D. l + len
（2）②处应填写（ ）。
A. 1 B. 2 C. f[l+1 ][r] D. f[l + 1][r - 1]
（3）③处应填写（ ）。
A. 1 B. 2 C. i == 0 D. c2[i] == 0
（4）④处应填写（ ）。
A. 1 B. 2 C. f[l+1 ][r] D. f[l + 1][r - 1]
（5）⑤处应填写（ ）。
A. f[l+1][k] + f[k + 1][r] B. f[l+1][k-1] + f[k][r]
C. f[l][k] + f[k + 1][r] D. f[l][k-1] + f[k][r]
答案：----->E:\csp\初赛集训模拟题试题包\23年有道小图灵\2023J组8月赛