2020年CCF非专业级别软件能力认证第一轮 （CSP-S）提高级C++语言试题

一、单项选择题（每题 2 分，共 30 分） 1、请选出以下最大的数： {{ select(1) }}

• $(550)_{10}$
• $(777)_{8}$
• $2^{10}$
• $(22F)_{16}$

2、操作系统的功能是： {{ select(2) }}

• 负责外设与主机之间的信息交换
• 控制和管理计算机系统的各种硬件和软件资源的使用
• 负责诊断机器的故障
• 将源程序编译成目标程序

3、现有一段8分钟的视频文件，它的播放速度是每秒24帧图像，每帧图像是 一幅分辨率为2048x1024像素的32位真彩色图像。请问要存储这段原始无压缩视频，需要多大的存储空间？ {{ select(3) }}

• 30G
• 90G
• 150G
• 450G

4、今有一空栈S，对下列待进栈的数据元素序列a, b, c, d, e, f依次进行：进栈，进栈，出栈，进栈，进栈，出栈的操作，则此操作完成后，栈底元素为： {{ select(4) }}

• b
• a
• d
• c

5、将(2, 7, 10, 18)分别存储到某个地址区间为0~10的哈希表中，如果哈希函数h(x) =（），将不会产生冲突，其中a mod b表示a除以b的余数。 {{ select(5) }}

• $x^2 \quad mod \quad 11$
• $2x \quad mod \quad 11$
• $x \quad mod \quad 11$
• $\left \lfloor \frac{x}{2} \right \rfloor$ mod 11,其中$\left \lfloor \frac{x}{2} \right \rfloor$表示$\frac{x}{2}$向下取整

6、下列哪些问题不能用贪心法精确求解？ {{ select(6) }}

• 霍夫曼编码问题
• 0-1背包问题
• 最小生成树问题
• 单源最短路径问题

7、具有n个顶点，e条边的图采用邻接表存储结构，进行深度优先遍历运算的时间复杂度为： {{ select(7) }}

• $O(n+e)$
• $O(n^2)$
• $O(e^2)$
• $O(n)$

8、二分图是指能将顶点划分成两个部分，每一部分内的顶点间没有边相连的简单无向图。那么，24个顶点的二分图至多有（）条边。 {{ select(8) }}

• 144
• 100
• 48
• 122

9、广度优先搜索时，一定需要用到的数据结构是： {{ select(9) }}

• 栈
• 二叉树
• 队列
• 哈希表

10、一个班学生分组做游戏，如果每组三人就多两人，每组五人就多三人，每组七人就多四人，问这个班的学生人数n在以下哪个区间？已知n < 60。 {{ select(10) }}

• 30 < n < 40
• 40 < n < 50
• 50 < n < 60
• 20 < n < 30

11、小明想通过走楼梯来锻炼身体，假设从第1层走到第2层消耗10卡热量，接着从第2层走到第3层消耗20卡热量，再从第3层走到第4层消耗30卡热量，依此类推，从第k层走到第k+1层消耗10k卡热量（k > 1）。如果小明想从1层开始，通过连续向上爬楼梯消耗1000卡热量，至少要爬到第几层楼？ {{ select(11) }}

• 14
• 16
• 15
• 13

12、表达式a*(b+c)-d的后缀表达形式为： {{ select(12) }}

• abc*+d-
• -+*abcd
• abcd*+-
• abc+*d-

13、从一个4x4的棋盘中选取不在同一行也不在同一列上的两个方格，共有（）种方法。 {{ select(13) }}

• 60
• 72
• 86
• 64

第 14、 题 对一个n个顶点、m条边的带权有向简单图用Dijkstra算法计算单源最短路时，如果不使用堆或其它优先队列进行优化，则其时间复杂度为： {{ select(14) }}

• $O((m + n^2) log n)$
• $O(mn + n^3)$
• $O((m + n) log n)$
• $O(n^2)$

15、1948年，（）将热力学中的熵引入信息通信领域，标志着信息论研究的开端。 {{ select(15) }}

• 欧拉(Leonhard Euler)
• 冯•诺伊曼(John von Neumann)
• 克劳德•香农(Claude Shannon)
• 图灵(Alan Turing)

二、阅读程序（程序输入不超过数组或字符串定义的范围；判断题正确填 √，错误填 ×；除特殊说明外，判断题 1.5 分，选择题 3 分，共计 40 分）

阅读程序，完成16 - 21 题。 假设输入的n和d[i]都是不超过10000的正整数。

01 #include <iostream>
02 using namespace std;
03 
04 int n;
05 int d[1000];
06 
07 int main() {
08     cin >> n;
09     for (int i = 0; i < n; ++i)
10         cin >> d[i];
11     int ans = -1;
12     for (int i = 0; i < n; ++i)
13         for (int j = 0; j < n; ++j)
14             if (d[i] < d[j])
15                 ans = max(ans, d[i] + d[j] - (d[i] & d[j]));
16     cout << ans;
17     return 0;
18 }

16、n必须小于1000，否则程序可能会发生运行错误。 {{ select(16) }}

• 正确
• 错误

17、输出一定大于等于0。 {{ select(17) }}

• 正确
• 错误

18、若将第13行的j = 0改为j = i + 1，程序输出可能会改变。 {{ select(18) }}

• 正确
• 错误

19、将第14行的d[i] < d[j]改为d[i] != d[j]，程序输出不会改变。 {{ select(19) }}

• 正确
• 错误

20、若输入n = 100，且输出为127，则输入的d[i]中不可能有： {{ select(20) }}

• 127
• 126
• 128
• 125

21、若输出的数大于0，则下面说法正确的是： {{ select(21) }}

• 若输出为偶数，则输入的d[i]中最多有两个偶数
• 若输出为奇数，则输入的d[i]中至少有两个奇数
• 若输出为偶数，则输入的d[i]中至少有两个偶数
• 若输出为奇数，则输入的d[i]中最多有两个奇数

阅读程序，完成22 - 27题。 假设输入的n、k和d[i]都是不超过10000的正整数，且k不超过n，并假设rand()函数产生的是均匀的随机数。

01 #include <iostream>
02 #include <cstdlib>
03 using namespace std;
04 
05 int n;
06 int d[10000];
07 
08 int find(int L, int R, int k) {
09     int x = rand() % (R - L + 1) + L;
10     swap(d[L], d[x]);
11     int a = L + 1, b = R;
12     while (a < b) {
13         while (a < b && d[a] < d[L])
14             ++a;
15         while (a < b && d[b] >= d[L])
16             --b;
17         swap(d[a], d[b]);
18     }
19     if (d[a] < d[L])
20         ++a;
21     if (a - L == k)
22         return d[L];
23     if (a - L < k)
24         return find(a, R, k - (a - L));
25     return find(L + 1, a - 1, k);
26 }
27 
28 int main() {
29     int k;
30     cin >> n;
31     cin >> k;
32     for (int i = 0; i < n; ++i)
33         cin >> d[i];
34     cout << find(0, n - 1, k);
35     return 0;
36 }

22、第9行的x的数值范围是L+1到R，即[L+1, R]。 {{ select(22) }}

• 正确
• 错误

23、将第19行的d[a]改为d[b]，程序不会发生运行错误。 {{ select(23) }}

• 正确
• 错误

24、当输入的d[i]是严格单调递增序列时，第17行的swap平均执行次数是： {{ select(24) }}

• $O(n log n)$
• $O(n)$
• $O(log n)$
• $O(n^2)$

25、当输入的d[i]是严格单调递减序列时，第17行的swap平均执行次数是： {{ select(25) }}

• $O(n^2)$
• $O(n)$
• $O(n log n)$
• $O(log n)$

26、若输入的d[i]为i，此程序①平均的时间复杂度和②最坏情况下的时间复杂度分别是： {{ select(26) }}

• $O(n), O(n^2)$
• $O(n), O(n log n)$
• $O(n log n), O(n^2)$
• $O(n log n), O(n log n)$

27、若输入的d[i]都为同一个数，此程序平均的时间复杂度是： {{ select(27) }}

• $O(n)$
• $O(log n)$
• $O(n log n)$
• $O(n^2)$

阅读程序，完成28 - 33 题。

01 #include <iostream>
02 #include <queue>
03 using namespace std;
04 
05 const int maxl = 2000000;
06 
07 class Map {
08     struct item {
09         string key; int value;
10     } d[maxl];
11     int cnt;
12 public:
13     int find(string x) {
14         for (int i = 0; i < cnt; ++i)
15             if (d[i].key == x)
16                 return d[i].value;
17         return -1;
18     }
19     static int end() { return -1; }
20     void insert(string k, int v) {
21         d[cnt].key = k; d[cnt++].value = v;
22     }
23 } s[2];
24 
25 class Queue {
26     string q[maxl];
27     int head, tail;
28 public:
29     void pop() { ++head; }
30     string front() { return q[head + 1]; }
31     bool empty() { return head == tail; }
32     void push(string x) { q[++tail] = x; }
33 } q[2];
34 
35 string st0, st1;
36 int m;
37 
38 string LtoR(string s, int L, int R) {
39     string t = s;
40     char tmp = t[L];
41     for (int i = L; i < R; ++i)
42         t[i] = t[i + 1];
43     t[R] = tmp;
44     return t;
45 }
46 
47 string RtoL(string s, int L, int R) {
48     string t = s;
49     char tmp = t[R];
50     for (int i = R; i > L; --i)
51         t[i] = t[i - 1];
52     t[L] = tmp;
53     return t;
54 }
55 
56 bool check(string st, int p, int step) {
57     if (s[p].find(st) != s[p].end())
58         return false;
59     ++step;
60     if (s[p ^ 1].find(st) == s[p].end()) {
61         s[p].insert(st, step);
62         q[p].push(st);
63         return false;
64     }
65     cout << s[p ^ 1].find(st) + step << endl;
66     return true;
67 }
68 
69 int main() {
70     cin >> st0 >> st1;
71     int len = st0.length();
72     if (len != st1.length()) {
73         cout << -1 << endl;
74         return 0;
75     }
76     if (st0 == st1) {
77         cout << 0 << endl;
78         return 0;
79     }
80     cin >> m;
81     s[0].insert(st0, 0); s[1].insert(st1, 0);
82     q[0].push(st0); q[1].push(st1);
83     for (int p = 0;
84          !(q[0].empty() && q[1].empty());
85          p ^= 1) {
86         string st = q[p].front(); q[p].pop();
87         int step = s[p].find(st);
88         if ((p == 0 &&
89              (check(LtoR(st, m, len - 1), p, step) ||
90               check(RtoL(st, 0, m), p, step)))
91             ||
92             (p == 1 &&
93              (check(LtoR(st, 0, m), p, step) ||
94               check(RtoL(st, m, len - 1), p, step))))
95             return 0;
96     }
97     cout << -1 << endl;
98     return 0;
99 }

28、输出可能为0。 {{ select(28) }}

• 正确
• 错误

29、若输入的两个字符串长度均为101时，则m=0时的输出，m=100时的输出是一样的。 {{ select(29) }}

• 正确
• 错误

30、若两个字符串的长度均为n，则最坏情况下，此程序的时间复杂度为$O(n!)$。 {{ select(30) }}

• 正确
• 错误

31、若输入的第一个字符串长度由100个不同的字符构成，第二个字符串是第一个字符串的倒序，输入的m为0，则输出为： {{ select(31) }}

• 49
• 50
• 100
• -1

32、已知当输入为"0123\n3210\n1"时输出为4，当输入为"012345\n543210\n1"时输出为14，当输入为"01234567\n76543210\n1"时输出为28，则当输入为"0123456789ab\nba9876543210\n1"时输出为： {{ select(32) }}

• 56
• 84
• 102
• 68

33、若两个字符串的长度均为n，且0 < m < n-1，且两个字符串的构成相同（即任何一个字符在两个字符串中出现的次数均相同），则下列说法正确的是： {{ select(33) }}

• 若$n、m$均为奇数，则输出可能小于0
• 若$n、m$均为偶数，则输出可能小于0
• 若$n$为奇数、$m$为偶数，则输出可能小于0
• 若$n$为偶数、$m$为奇数，则输出可能小于0

三、完善程序（每题 5 分，共 40 分）

1.（分数背包）小S有n块蛋糕，编号从1到n，第i块蛋糕的价值是wi，体积是vi。他有一个大小为B的盒子来装这些蛋糕，也就是说装入盒子的蛋糕的体积总和不能超过B。他打算选择一些蛋糕装入盒子，他希望盒子里装的蛋糕的价值之和尽量大。 为了使盒子里的蛋糕价值之和更大，他可以任意切割蛋糕。具体来说，他可以选择一个a（0 < a < 1），并将一块价值是w，体积为v的蛋糕切割成两块。其中一块的价值是$a\times w$，体积是$a\times v$，另一块的价值是$(1-a)\times w$，体积是$(1-a)\times v$。他可以重复无限次切割操作。

现要求编程输出最大可能的价值，以分数的形式输出。比如n=3, B=8，三块蛋糕的价值分别是4、4、2，体积分别是5、3、2。那么最优的方案就是将体积为5的蛋糕切成两份，一份体积是3，价值是2.4，另一份体积是2，价值是1.6，然后把体积是3的那部分和后两块蛋糕打包进盒子。最优的价值之和是8.4，故程序输出 $\frac{42}{5}$。 输入的数据范围为：$1≤n≤1000, 1≤B≤10^5; 1≤wi, vi≤100$。 提示：将所有的蛋糕按照性价比$\frac{wi}{vi}$从大到小排序后进行贪心选择。 试补全程序。

01 #include <cstdio>
02 using namespace std;
03 
04 const int maxn = 1005;
05 int n, B, w[maxn], v[maxn];
06 
07 int gcd(int u, int v) {
08     if (v == 0)
09         return u;
10     return gcd(v, u % v);
11 }
12 
13 void print(int w, int v) {
14     int d = gcd(w, v);
15     w = w / d;
16     v = v / d;
17     if (v == 1)
18         printf("%d\n", w);
19     else
20         printf("%d/%d\n", w, v);
21 }
22 void swap(int &x, int &y) {
23     int t = x; x = y; y = t;
24 }
25 
26 int main() {
27     scanf("%d %d", &n, &B);
28     for (int i = 1; i <= n; i++) {
29         scanf("%d %d", &w[i], &v[i]);
30     }
31     for (int i = 1; i < n; i++)
32         for (int j = 1; j < n; j++)
33             if (①) {
34                 swap(w[j], w[j + 1]);
35                 swap(v[j], v[j + 1]);
36             }
37     int curV, curW;
38     if (②) {
39         ③
40     } else {
41         print(B * w[1], v[1]);
42         return 0;
43     }
44     for (int i = 2; i <= n; i++)
45         if (curV + v[i] <= B) {
46             curV += v[i];
47             curW += w[i];
48         } else {
49             print(④);
50             return 0;
51         }
52     print(⑤);
53     return 0;
54 }

34、①处应填： {{ select(34) }}

• $w[j] / v[j] < w[j+1] / v[j+1]$
• $w[j] / v[j] > w[j+1] / v[j+1]$
• $v[j] * w[j+1] < v[j+1] * w[j]$
• $w[j] * v[j+1] < w[j+1] * v[j]$

35、②处应填： {{ select(35) }}

• $w[1] <= B$
• $v[1] <= B$
• $w[1] >= B$
• $v[1] >= B$

36、③处应填： {{ select(36) }}

• $print(v[1] * w[1]); return 0;$
• $curV = 0; curW = 0;$
• $print(w[1],v[1]); return 0;$
• $curV = v[1]; curW = w[1];$

37、④处应填： {{ select(37) }}

• $curW * v[i] + curV * w[i], v[i]$
• $(curW - w[i]) * v[i] + (B - curV) * w[i], v[i]$
• $curW + v[i], w[i]$
• $curW * v[i] * (B - curV) * w[i], v[i]$

38、⑤处应填： {{ select(38) }}

• $curW, curV$
• $curW, 1$
• $curV, curW$
• $curV, 1$

2.（最优子序列）取m=6，给出长度为n的整数序列$a_{1}, a_{2}, ..., a_{n}（0 ≤ ai < 2^m）$。对于一个二进制数x，定义其分值$w(x)为x + popcnt(x)$，其中$popcnt(x)$表示x二进制表示中1的个数。

对于一个子序列$b_{1}, b_{2}, ..., b_{k}$，定义其子序列分值S为$w(b_{1} ⊕ b_{2}) + w(b_{2} ⊕ b_{3}) + ... + w(b_{k-1} ⊕ b_{k})$。其中⊕表示按位异或。对于空子序列，规定其子序列分值为0。求一个子序列使得其子序列分值最大，输出这个最大值。

输入第一行包含一个整数$n（1 ≤ n ≤ 40000）$。接下来一行包含n个整数$a_{1}, a_{2}, ..., a_{n}$。 提示：考虑优化朴素的动态规划算法，将前$\frac{m}{2}$位和后$\frac{m}{2}$位分开计算。 $Max[x][y]$表示当前的子序列下一个位置的高8位是X、最后一个位置的低8位是y时的最大价值。 试补全程序。

01 #include <iostream>
02 using namespace std;
03 
04 typedef long long LL;
05 
06 const int MAXN = 40000, M = 16, B = M >> 1, MS = (1 << B) - 1;
07 const LL INF = 10000000000000LL;
08 LL Max[MS + 4][MS + 4];
09 
10 int w(int x)
11 {
12     int s = x;
13     while(x)
14     {
15         ①;
16         s++;
17     }
18     return s;
19 }
20 
21 void to_max(LL &x, LL y)
22 {
23     if(x < y)
24         x = y;
25 }
26 
27 int main()
28 {
29     int n;
30     LL ans = 0;
31     cin >> n;
32     for(int x = 0; x <= MS; x++)
33         for(int y = 0; y <= MS; y++)
34             Max[x][y] = -INF;
35     for(int i = 1; i <= n ; i++)
36     {
37         LL a;
38         cin >> a;
39         int x = ②, y = a & MS;
40         LL v = ③;
41         for(int z = 0; z <= MS; z++)
42             to_max(v, ④);
43         for(int z = 0; z <= MS; z++)
44             ⑤;
45         to_max(ans, v);
46     }
47     cout << ans << endl;
48     return 0;
49 }

39、①处应填： {{ select(39) }}

• $X$ >>= $1$
• $X$ ^= $X$ & $(X$ ^ $(X + 1))$
• $X$ -= $X$ | $-X$
• $X$ ^= $X$ & $(X$ ^ $(X - 1))$

40、②处应填： {{ select(40) }}

• $(a$ & $MS)$ << $B$
• $a$ >>$B$
• $a$ & $(1 << B)$
• $a$ & $(MS << B)$

41、③处应填： {{ select(41) }}

• $-INF$
• $Max[y][x]$
• $0$
• $Max[x][y]$

42、④处应填： {{ select(42) }}

• $Max[x][z] + w(y ^ z)$
• $Max[x][z] + w(a ^ z)$
• $Max[x][z] + w(x$^$(z << B))$
• $Max[x][z] + w(x ^ z)$

43、⑤处应填： {{ select(43) }}

• to_max(Max[y][z], v + w(a ^ (z << B)))
• to_max(Max[z][y], v + w((x ^ z) << B))
• to_max(Max[z][y], v + w(a ^ (z << B)))
• to_max(Max[x][z], v + w(y ^ z))$