a--5：2023年CSP-J初赛原创模考大赛（6月赛）

2023年CSP-J初赛原创模考大赛(6月赛)

（C++语言    满分：100分    考试时间：120分钟）

一、 单项选择题（每题只有一个正确选项，每题2分，共30分）

1. 计算机基本存储单位是     ，计算机最小的存储单位是     （     ）。

A. Byte bit    B. bit Byte    C. KB Byte    D. Byte KB

2. 下列软件中不是计算机操作系统的是（    ）。

A. Windows    B. Linux    C. OS/2    D. WPS

3. 以下选项能够求得ab的是（    ）。注：选项中 a^b 表示 ab

A. pow(a,b)    B. ceil(a^b)    C. sqrt(a^b)    D. log10(exp(a^b))

4. 下列数中最大的是（    ）。注：选项中 (a) b 表示 a这个数是b进制

A. (237) 8    B. (1BF) 16    C. (10101101) 2    D. (789) 10

5.  3 ^ 9 、 3 | 9 和 3 & 9 运算之后的结果是（    ）。

A. 1010  0001  1110    B. 0101  0100  1110    

C. 0101  1011  0001    D. 1010  1011  0001

6. 以下程序段执行之后的结果为（    ）。

A. 12    B. 3    C. 5    D. 13

7. 表达式 a + (b - c) * d 的后缀形式是（    ）。

A. a b c - + d *    B. a b c – d * +    C. a + b c - * d    D. b – c + a * d

8. 已知小明的生日是在8月28号，已知2010年的8月28号是星期六，从2011到2020的十年中小明共有（    ）个生日在周末。

A. 1    B. 2    C. 3    D. 4

9. 结点数量超过300的满二叉树至少有（    ）层。

A. 7    B. 8    C. 9    D. 10

10. 设栈S和队列Q的初始状态为空，元素1,2,3,4,5,6依次通过栈S，一个元素出栈后即进入队列Q。若出队的顺序为1,4,6,5,3,2，则栈S的容量至少应该为（    ）。

A. 2    B. 3    C. 4    D. 5

11. 假如输入3，输出结果是（    ）

A. 33    B. 50    C. 43    D. 100

12. 某省有四个市，人口总和为129万人。其中A市7万人口，B市30万人口，C市人口比D市人口多，并且A市与C市人口之和

比其余两市人口之和多5万人。问C市和D市分别有多少万人？

A. 50 22    B. 60 32    C. 90 62    D. 70 22

13. 以下哈夫曼编码中，合法并且完整的是（    ）。

A. 000,001,010,011,10    B. 000,001,01,10,1

C. 00,01,10,110,111    D. 00,100,101,110,111

14. 假设一棵二叉树的前序遍历序列为ABDGKEHCFIJ，中序遍历序列为GKDBHEACIFJ，则其后序遍历序列为（    ）。

A. KGDHEBFJICA    

B. KGDHEBIJFCA    

C. KGDEHBIJFCA    

D. GKDHEBIJFCA

15. 把10个同样的西瓜装在4个同样的袋子里，袋子不能为空，问共有多少种不同的分法？（    ）。

A. 9    B. 24    C. 210    D. 5040

二、程序阅读理解题（共3大题，共计40分）

1. （12.5分）

01 #include <bits/stdc++.h>

02 using namespace std;

03 char mp[105];

04 int trans(char c) {

05 if (c >= '0' && c <= '9') return c - '0';

06 else return c - 'a' + 10;

07 }

08 int main() {

09 int n;

10 scanf("%d", &n);

11 for (int i = 0; i < n; i++) {

12 scanf("%s", mp);

13 int len = strlen(mp);

14 for (int j = 0; j < len; j++) {

15 for (int k = 3; k >= 0; k--) {

16 printf((trans(mp[j]) >> k) & 1 ? "*" : " ");

17 }

18 }

19 printf("\n");

20 }

21 return 0;

22 }

函数trans()实现了将十六进制字符串中某一字符转化成十进制数字的作用，例如字符'd'换转化成13。

在主函数中会循环输入n个字符串，字符串中的每一位都会通过trans()函数转化成十进制数，然后再通过左移和位运算会生成4位二进制数，最后将每一位2进制数按照1输出*，0输出' '（一个空格）的规则进行输出。

例如输入：

1

ff

先将'f'转化成15，再将15转化成二进制下的1111，再按照规则输出"****"，最终输出为********

 判断题

（1）若输入的字符串中某一字符为'c'，trans()函数对应返回值为13。（    ）（1.5分）

（2）若输入字符串为f0f，则对应的那一行输出仅包含一个空格。（    ）（1.5分）

（3）字符串"70"和字符串"n0"对应的那一行输出是一样的。（    ）（1.5分）

 选择题

（4）若输入字符串为xtl，则输出为（    ）。（2分）

（5）如果想要输出下列的图案，则输入应为（    ）。（3分）

A. 

8

ff 02 04 08 08 02 04 ff

B. 

8

ff 02 04 08 80 20 40 ff

C. 

8

ff 02 04 08 10 20 40 ff

D. 

8

ff 20 40 80 08 02 04 ff

（6）下列哪项输入字符串对应的那一行输出字符串为回文字符串（即从前往后和从后往前均为同一字符串）（    ）。（3分）

A. c56a3    B. h72c9    C. j8ui7    D. a76d5

2. （13.5分，判断题1.5分，选择题3分）

数据范围：1≤n≤2×105, 0≤k≤109

请阅读程序，完成下面的判断题和单选题。 

（提示：230 = 1073741824，231 = 2147483648）

01 #include <bits/stdc++.h>

02 using namespace std;

03 int main() {

04 int n, k;

05 cin >> n >> k;

06 vector<int> cnt(31, 0), a(n);

07 for(int i = 0;i < n; ++i) {

08 cin >> a[i];

09 for(int j = 30; j >= 0; --j) {

10 if(a[i] & (1 << j)) +cnt[j];

11 }

12 }

13 int ans = 0;

14 for(int i = 30; i >= 0; --i) {

15 int need = n - cnt[i];

16 if(need <= k) {

17 k -= need;

18 ans += (1 << i);

19 }

20 }

21 cout << ans << "\n"; 

22 }

 判断题

（1）k必须<=30，否则程序会报错。（    ）

（2）第 16 行，当need=0，k=0时，若把的<=改成<，程序输出不变。（    ）

（3）第14行，若改成从for(int i = 0; i <= 30; ++i) ，程序输出不变。（    ）

 选择题

（4）输入以下数据后:  3 2 2 1 1 。输出的数据为（    ）

A. 1

B. 2

C. 1073741824

D. 2147483647

（5）输入以下数据后：4 4 3 1 3 1。输出的数据为（    ）

A. 1073741824

B. 1073741825

C. 2147483646

D. 2147483647

（6）输入以下数据后：1  30  0。输出的数据为（    ）

A. 0

B. 1

C. 2147483646

D. 2147483647

3. （13.5分）

01 #include <bits/stdc++.h>

02 using namespace std;

03 int a[1000005], b[1000005];

04 int cnta[1000005] = {le9}, cntb[1000005] = {le9};

05 int nowa[1000005], nowb[1000005];

06 int main() {

07 int n, m, x, now = 0;

08 scanf("%d%d%d", &n, &m, &x);

09 for (int i = 0; i < n; i++) {

10 scanf("%d", &a[i]);

11 if(!i || a[i] == a[i-1]) now++; 

12 else cnta[now]++, now = 1; 

13 }

14 cnta[now]++, now = 0;

15 for(int i = 0; i < m; i++) {

16 scanf("%d", &b[i]);

17 if(!i || b[i] == b[i-1]) now++;

18 else cntb[now]++, now = 1;

19 }

20 cntb[now]++;

21 int ans = 0, nowans = 0, pa = n, pb = m;

22 for (int i = 0; i < x; i++) {

23 while (nowa[pa] == cnta[pa]) pa--;

24 nowa[pa]++; nowans += pa;

25 }

26 ans = nowans;

27 for (int i = 1; i <= x; i++) {

28 while (!nowa[pa]) pa++;

29 nowa[pa]--; nowans -= pa;

30 while (nowb[pb] == cntb[pb]) pb--;

31 nowb[pb]++; nowans += pb;

32 ans = max(ans, nowans);

33 }

34 printf("%d\n", ans);

35 return 0;

36 }

输入数据范围如下：

1<=n,m<=106,1<=x<=n+m，且a[1....n],b[1....m]中的数字在int范围内，且均为非降序列。

请完成以下判断题和选择题。

 判断题

（1）给定任意合法输入，数组不会越界。（       ）（1.5分）

（2）第23行代码的while更换成if不会对结果产生影响。（       ）（1.5分）

 选择题

（3）若输入以下数据，则输出为（       ）。（2分）

3 5 1 

1 1 1 

2 2 2 2 2

A. 5    B. 3    C. 8    D. 2

（4）若输入以下数据，则输出为(      )。（3分）

10 20 6 

1 1 1 2 2 8 9 10 10000 1000000 

4 4 4 4 4 5 8 8 8 8 10000 10000 10000 10000 10000 1000000 1000000 1000000 1000000 1000000

A. 23    B. 24    C. 25    D. 26

（5）本题复杂度为（      ）。（3分）

  A.  Ο(n*m+x)

B.  Ο(n*m*x)   

C.  Ο(n+m+x)    

D.  Ο((n+m)*x)

（6）对于任意合法输入，ans最大可达到（      ）。（3分）

  A. 2*106    B. 106    C. 231 - 1    D. 109

三、程序完善题（共2大题，每个选择题3分，共计30分）

1.

01 #include <bits/stdc++.h>

02 using namespace std;

03 int main() {

04 int t;

05 cin >> t;

06 while (t--) {

07 long long p, q;

08 cin >> p >> q;

09 if (①) {

10 printf("%lld\n", p);

11 continue;

12 }

13 vector <long long> a;

14 long long tp = p, tq = q;

15 for (int i = 2; ②; i++) {

16 ③ {

17 a.push_back(i);

18 tq /= i;

19 }

20 }

21 if (tq > 1) a.push_back(tq);

22 long long nmax = -1;

23 for (int i = 0; i < a.size(); i++) {

24 tp = p;

25 ④ {

26 ⑤;

27 }

28 nmax = max(nmax, tp);

29 }

30 printf("%lld\n",nmax);

31 }

32 return 0;

33 }

题意：给定 long long 范围内正整数 p 和 int 范围内正整数 q(q<p) 。求能整除 p ，不能被 q 整除的最大整数 x。共询问 t 次。

（1）①处应填（    ）

A. p % q != 0      B. p == q      C. p % q == 0      D. p > q

（2）②处应填（    ）

A. i * i < tq      B. i < tq – 1      C. i <= tq      D. i <= tq / i

（3）③处应填（    ）

A. while (tq % i == 0)      B. if (tq % i == 0)

C. while (i % tq == 0)      D. if (i % 2 == 0)

（4）④处应填（    ）

A. while (tp % q == 0)      B. if (tp % q == 0)

C. while (tp % i == 0)      D. if (tp % i == 0)

（5）⑤处应填（    ）

A. tp /= a[i]      B. tp /= q      C. tp /= i      D. tp = q * i

2.

有一棵结点数为n(n<=1000)的严格二叉树，n称作这棵二叉树的大小，且二叉树的每个非叶子结点都恰好有两个子结点。为每个结点分配一个权值来表示以这个结点为根的子树的大小，然后按照先序遍历的思想把结点的权值列出作为它的特征序列。为了简化，只列出根节点和所有左子结点权值作为特征序列。经过观察，通过这样构造出的特征序列可以唯一确定一棵二叉树。现在给定一棵二叉树的特征序列，请还原出完整的二叉树的先序遍历结果，输入的特征序列保证题目有解。

输入样例：

7

13 7 1 3 1 1 1

输出样例：

13 7 1 5 3 1 1 1 5 1 3 1 1

01 #include <iostream>

02 #include <cstdio>

03 using namespace std;

04 const int MAXN = le3 + 5;

05 int length, trid;

06 int sign[MAXN], tree[2*MAXN];

07

08 void build(){

09 int s[MAXN];

10 int i, top = 0;

11 for( ①;i++) {

12 if((tree[trid] - sign[i] - 1) > 0) {

13 top ++;

14 s[top] = ②;

15 }

16 trid ++;

17 tree[trid] = sign[i];

18 while( ③== 1)

19 ④;

20 }

21 }

22 int main() {

23 int i;

24 scanf("%d", &length);

25 for(i = 1; i <= length; i++)

26 scanf("%d", &sign[i]);

27 tree[1] = sign[1];

28 trid = 1;

29 build();

30 for( ⑤; i++)

31 printf("%d ", tree[i]);

32 return 0;

33 }

（1）①处应填写（    ）

A. i = 0; i < length      B. i = 1; i < length

C. i = 1; i <= length     D. i = 2; i <= length

（2）②处应填写（    ）

A. tree[trid] - sign[i] – 1      B. tree[trid] - sign[i]

C. sign[i] - tree[trid] – 1      D. sign[i] - tree[trid]

（3）③处应填写（    ）

A. s[top]      B. tree[trid]      C. sign[i]      D. tree[trid] - sign[i]

（4）④处应填写（    ）

A. tree[trid++] = s[top--]      B. tree[++trid] = s[top--]

C. s[++top] = tree[--trid]      D. s[top++] = tree[trid--]

（5）⑤处应填写（    ）

A. i = 0; i <= trid – 1      B. i = 0; i <= trid

C. i = 1; i <= trid – 1      D. i = 1; i <= trid

答案：----->E:\csp\初赛集训模拟题试题包\23年有道小图灵\2023J组6月赛