该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

请输出答案

判断题请用A代表对B代表错

题目

(1)

01 #include <iostream>
02 using namespace std;
03
04 int n;
05 int a[1000];
06
07 int f(int x)
08 {
09 int ret = 0;
10 for (; x; x &= x - 1) ret++;
11 return ret;
12 }
13
14 int g(int x)
15 {
16 return x & -x;
17 }
18
19 int main()
20 {
21 cin >> n;
22 for (int i = 0; i < n; i++) cin >> a[i];
23 for (int i = 0; i < n; i++)
24 cout << f(a[i]) + g(a[i]) << ' ';
25 cout << endl;
26 return 0;
27 }

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 #include <string>
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 }

l 判断题
22. 输出的第二行一定是由小写字母、大写字母、数字和“+”、“/”、“=”构成的
字符串。（ ）
23. 可能存在输入不同，但输出的第二行相同的情形。（ ）
24. 输出的第一行为“-1”。（ ）
l 单选题
25. 设输入字符串长度为n，decode函数的时间复杂度为（ ）。
A. Θ(√𝑛) B. Θ(𝑛) C. Θ(𝑛 log 𝑛) D. Θ(𝑛!)
26. 当输入为“Y3Nx”时，输出的第二行为（ ）。
A. “csp” B. “csq” C. “CSP” D. “Csp”
27. （3.5 分）当输入为“Y2NmIDIwMjE=”时，输出的第二行为（ ）。
A. “ccf2021” B. “ccf2022” C. “ccf 2021” D. “ccf 2022”
（3）

01 #include <iostream>
02 using namespace std;
03
04 const int n = 100000;
05 const int N = n + 1;
06
07 int m;
08 int a[N], b[N], c[N], d[N];
09 int f[N], g[N];
10
11 void init()
12 {
13 f[1] = g[1] = 1;
14 for (int i = 2; i <= n; i++) {
15 if (!a[i]) {
16 b[m++] = i;
17 c[i] = 1, f[i] = 2;
18 d[i] = 1, g[i] = i + 1;
19 }
20 for (int j = 0; j < m && b[j] * i <= n; j++) {
21 int k = b[j];
22 a[i * k] = 1;
23 if (i % k == 0) {
24 c[i * k] = c[i] + 1;
25 f[i * k] = f[i] / c[i * k] * (c[i * k] + 1);
26 d[i * k] = d[i];
27 g[i * k] = g[i] * k + d[i];
28 break;
29 }
30 else {
31 c[i * k] = 1;
32 f[i * k] = 2 * f[i];
33 d[i * k] = g[i];
34 g[i * k] = g[i] * (k + 1);
35 }
36 }
37 }
38 }
39
40 int main()
41 {
42 init();
43
44 int x;
45 cin >> x;
46 cout << f[x] << ' ' << g[x] << endl;
47 return 0;
48 }

假设输入的x是不超过1000 的自然数，完成下面的判断题和单选题：
l 判断题
28. 若输入不为“1”，把第13行删去不会影响输出的结果。（ ）
29. （2 分）第25行的“f[i] / c[i * k]”可能存在无法整除而向下取整的情况。
（ ）
30. （2 分）在执行完init()后，f数组不是单调递增的，但g数组是单调递增的。
（ ）
l 单选题
31. init函数的时间复杂度为（ ）。
A. Θ(𝑛) B. Θ(𝑛 log 𝑛) C. Θ)𝑛√𝑛* D. Θ(𝑛!)
32. 在执行完init()后，f[1], f[2], f[3] …… f[100]中有（ ）个等于2。
A. 23 B. 24 C. 25 D. 26
33. （4 分）当输入为“1000”时，输出为（ ）。
A. “15 1340” B. “15 2340” C. “16 2340” D. “16 1340”