Description

一、单项选择题（共 15 题，每题 2 分，共计 30 分；每题有且仅有一个正确选项）
1. 以下不属于面向对象程序设计语言的是（ ）。 
A. C++ B. Python C. Java D. C 
2. 以下奖项与计算机领域最相关的是（ ）。 
A. 奥斯卡奖 B. 图灵奖 C. 诺贝尔奖 D. 普利策奖 
3. 目前主流的计算机储存数据最终都是转换成（ ）数据进行储存。
 A. 二进制 B. 十进制 C. 八进制 D. 十六进制 
4. 以比较作为基本运算，在 N 个数中找出最大数，最坏情况下所需要的最少的比较次数为 （ ）。 
A. N²  B. N C. N-1 D. N+1 
5. 对于入栈顺序为 a, b, c, d, e 的序列，下列（ ）不是合法的出栈序列。
 A. a, b, c, d, e B. e, d, c, b, a C. b, a, c, d, e D. c, d, a, e, b 
6. 对于有 n 个顶点、m 条边的无向连通图 (m>n)，需要删掉（ ）条边才能使其成为一棵 树。 
A. n-1 B. m-n C. m-n-1 D. m-n+1 
7. 二进制数 101.11 对应的十进制数是（ ）。 
A. 6.5 B. 5.5 C. 5.75 D. 5.25 
8. 如果一棵二叉树只有根结点，那么这棵二叉树高度为 1。请问高度为 5 的完全二叉树有 （ ）种不同的形态？ 
A. 16 B. 15 C. 17 D. 32
9. 表达式 a*(b+c)*d 的后缀表达式为( )，其中“*”和“+”是运算符。
 A. **a+bcd B. abc+*d* C. abc+d** D. *a*+bcd 
10.6 个人，两个人组一队，总共组成三队，不区分队伍的编号。不同的组队情况有（ ） 种。 
A. 10 B. 15 C. 30 D. 20 
11.在数据压缩编码中的哈夫曼编码方法，在本质上是一种（ ）的策略。
 A. 枚举 B. 贪心 C. 递归 D. 动态规划 
12.由 1，1，2，2，3 这五个数字组成不同的三位数有（ ）种。
 A. 18 B. 15 C. 12 D. 24
 13.考虑如下递归算法
 solve(n) 
   if n<=1 return 1
   else if n>=5 return n*solve(n-2) 
   else return n*solve(n-1) 
则调用 solve(7)得到的返回结果为（ ）。 
A. 105 B. 840 C. 210 D. 420
14.以 a 为起点，对右边的无向图进行深度优先遍历，则 b、 c、 d、 e 四个点中有可能作 为最后一个遍历到的点的个数为（ ）。
 A. 1 B. 2 C. 3 D. 4
15.有四个人要从 A 点坐一条船过河到 B 点，船一开始在 A 点。该船一次最多可坐两个人。 已知这四个人中每个人独自坐船的过河时间分别为 1, 2, 4, 8, 且两个人坐船的过河时 间为两人独自过河时间的较大者。则最短（ ）时间可以让四个人都过河到 B 点（包括从 B 点把船开回 A 点的时间）。
 A. 14 B. 15 C. 16 D. 17
二、阅读程序（程序输入不超过数组或字符串定义的范围；判断题正确填√，错误填×；除特 殊说明外，判断题 1.5 分，选择题 3 分，共计 40 分）
(1)
 
l 判断题 
16. 输入的 n 等于 1001 时，程序不会发生下标越界。（ ） 
17. 输入的 a[i] 必须全为正整数，否则程序将陷入死循环。（ ） 
18. 当输入为“5 2 11 9 16 10”时，输出为“3 4 3 17 5”。（ ） 
19. 当输入为“1 511998”时，输出为“18”。（ ） 
20. 将源代码中 g 函数的定义（14-17 行）移到 main 函数的后面，程序可以正常编译运 行。（ ）
 l 单选题
 21. 当输入为“2 -65536 2147483647”时，输出为（ ）。 
A. “65532 33” B. “65552 32” C. “65535 34” D. “65554 33”
(2)

01 #include <iostream>
02 
03 using namespace std;
04
05 char base[64];
06 char table[256];
07
08 void init()
09 {
10 for (int i = 0; i < 26; i++) base[i] = 'A' + i;
11 for (int i = 0; i < 26; i++) base[26 + i] = 'a' + i;
12 for (int i = 0; i < 10; i++) base[52 + i] = '0' + i;
13 base[62] = '+', base[63] = '/';
14
15 for (int i = 0; i < 256; i++) table[i] = 0xff;
16 for (int i = 0; i < 64; i++) table[base[i]] = i;
17 table['='] = 0;
18 }
19
20 string decode(string str)
21 {
22 string ret;
23 int i;
24 for (i = 0; i < str.size(); i += 4) {
25 ret += table[str[i]] << 2 | table[str[i + 1]] >> 4;
26 if (str[i + 2] != '=')
27 ret += (table[str[i + 1]] & 0x0f) << 4 | table[str[i + 
2]] >> 2;
28 if (str[i + 3] != '=')
29 ret += table[str[i + 2]] << 6 | table[str[i + 3]];
30 }
31 return ret;
32 }
33
34 int main()
35 {
36 init();
37 cout << int(table[0]) << endl;
38
39 string str;
40 cin >> str;
41 cout << decode(str) << endl;
42 return 0;
43 }</pre>
l 判断题<br />
22. 输出的第二行一定是由小写字母、大写字母、数字和“+”、“/”、“=”构成的
字符串。（ ）<br />
23.可能存在输入不同，但输出的第二行相同的情形。（ ）<br />
24.输出的第一行为“-1”。（ ）<br />
l 单选题<br />
25.设输入字符串长度为 n，decode 函数的时间复杂度为（ ）。<br />
A. Θ(√n) B. Θ(n) C. Θ( n log n) D. Θ(n^2)<br />
26.当输入为“Y3Nx”时，输出的第二行为（ ）。<br />
A. “csp” B. “csq” C. “CSP” D. “Csp”<br />
27.（3.5 分）当输入为“Y2NmIDIwMjE=”时，输出的第二行为（ ）。<br />
A. “ccf2021” B. “ccf2022” C. “ccf 2021” D. “ccf 2022”<br />
<img src="../upload/121.199.20.253/20221030//1642_2_20221030183659_24531.png" width="500" alt="" /><br />
<img src="../upload/121.199.20.253/20221030//1642_3_20221030183659_73805.png" width="500" alt="" /> <br />
假设输入的 x 是不超过 1000 的自然数，完成下面的判断题和单选题：  <br />
l 判断题  <br />
28.若输入不为“1”，把第 13 行删去不会影响输出的结果。（ ）  <br />
29.（2 分）第 25 行的“f[i] / c[i * k]”可能存在无法整除而向下取整的情况。
（ ）  <br />
30.（2 分）在执行完 init()后，f 数组不是单调递增的，但 g 数组是单调递增的。
（ ）  <br />
l 单选题  <br />
31.init 函数的时间复杂度为（ ）。  <br />
A. Θ(n) B. Θ(n log n) C. Θ（n√n） D. Θ(n^2) <br />
32.在执行完 init()后，f[1], f[2], f[3] …… f[100]中有（ ）个等于 2。 <br />
 A. 23 B. 24 C. 25 D. 26  <br />
33.（4 分）当输入为“1000”时，输出为（ ）。 <br />
 A. “15 1340” B. “15 2340” C. “16 2340” D. “16 1340” <br />
三、完善程序（单选题，每小题 3 分，共计 30 分） <br />
 （1）（Josephus 问题）有 n个人围成一个圈，依次标号 0 至 n − 1。从 0 号开
始，依次 0, 1, 0, 1, … 交替报数，报到 1 的人会离开，直至圈中只剩下一个人。求最后
剩下人的编号。 <br />
 试补全模拟程序。 <br />
<pre>01 #include<iostream>
02 
03 using namespace std;
04 
05 const int MAXN = 1000000;
06 int F[MAXN];
07 
08 int main() {
09 int n;
10 cin >> n;
11 int i = 0, p = 0, c = 0;
12 while (①) {
13 if (F[i] == 0) {
14 if (②) {
15 F[i] = 1;
16 ③;
17 }
18 ④;
19 }
20 ⑤;
21 }
22 int ans = -1;
23 for (i = 0; i < n; i++) 
24 if (F[i] == 0) 
25 ans = i; 
26 cout << ans << endl;
 27 return 0; 
28 } </pre>
34.①处应填（ ）<br />
A. i < n B. c < n C. i < n - 1 D. c < n - 1<br />
35.②处应填（ ）<br />
A. i % 2 == 0 B. i % 2 == 1 C. p D. !p<br />
36.③处应填（ ）<br />
A. i++ B. i = (i + 1) % n
C. c++ D. p ^= 1<br />
37.④处应填（ ）<br />
A. i++ B. i = (i + 1) % n
C. c++ D. p ^= 1<br />
38.⑤处应填（ ）<br />
A. i++ B. i = (i + 1) % n
C. c++ D. p ^= 1<br />
（2） （矩形计数）平面上有 n 个关键点，求有多少个四条边都和 x 轴或者 y 轴平行的矩
形，满足四个顶点都是关键点。给出的关键点可能有重复，但完全重合的矩形只计一
次。<br />
试补全枚举算法。<br />
<img src="https://ipic.luogu.com.cn/v7s04.webp" width="500" alt="" /><br />
39.①处应填（ ）<br />
A. a.x != b.x ? a.x < b.x : a.id < b.id<br />
B. a.x != b.x ? a.x < b.x : a.y < b.y<br />
C. equals(a, b) ? a.id < b.id : a.x < b.x<br />
D. equals(a, b) ? a.id < b.id : (a.x != b.x ? a.x < b.x : a.y < b.y)<br />
40.②处应填（ ）<br />
A. i == 0 || cmp(A[i], A[i - 1])<br />
B. t == 0 || equals(A[i], A[t - 1])<br />
C. i == 0 || !cmp(A[i], A[i - 1])<br />
D. t == 0 || !equals(A[i], A[t - 1])<br />
41.③处应填（ ）<br />
A. b - (b - a) / 2 + 1 B. (a + b + 1) >> 1<br />
C. (a + b) >> 1 D. a + (b - a + 1) / 2<br />
42.④处应填（ ）<br />
A. !cmp(A[mid], p) B. cmp(A[mid], p)<br />
C. cmp(p, A[mid]) D. !cmp(p, A[mid])<br />
43.⑤处应填（ ）<br />
A. A[i].x == A[j].x<br />
B. A[i].id < A[j].id<br />
C. A[i].x == A[j].x && A[i].id < A[j].id<br />
D. A[i].x < A[j].x && A[i].y < A[j].y<br />
<h2>Input Format</h2>
无<br />
<h2>Output Format</h2>
提交方法见提示<br />
<pre><code class="language-input1">

</code></pre><pre><code class="language-output1">

</code></pre>
<h2>Hint</h2>
答题模板<br />
<pre>1 X
2 X
3 X
4 X
5 X
6 X
7 X
8 X
9 X
10 X
11 X
12 X
13 X
14 X
15 X
16 X
17 X
18 X
19 X
20 X
21 X
22 X
23 X
24 X
25 X
26 X
27 X
28 X
29 X
30 X
31 X
32 X
33 X
34 X
35 X
36 X
37 X
38 X
39 X
40 X
41 X
42 X
43 X
</pre>
将X替换为你的答案，然后复制到代码框中提交，选C++语言<br />
<h2>Source</h2>
CSP-J 2021 初赛