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

一、单项选择题（每题 2 分，共 30 分）

1、若有定义：int a=7; float x=2.5, y=4.7; 则表达式 x+a%3*(int)(x+y)%2 的值是： {{ select(1) }}

• 0.000000
• 2.750000
• 2.500000
• 3.500000

2、下列属于图像文件格式的有： {{ select(2) }}

• WMV
• MPEG
• JPEG
• AVI

3、二进制数 11 1011 1001 0111 和 01 0110 1110 1011 进行逻辑或运算的结果是： {{ select(3) }}

• 11 1111 1101
• 11 1111 1111 1101
• 10 1111 1111 1111
• 11 1111 1111 1111

4、编译器的功能是： {{ select(4) }}

• 将源程序重新组合
• 将一种语言（通常是高级语言）翻译成另一种语言（通常是低级语言）
• 将低级语言翻译成高级语言
• 将一种编程语言翻译成自然语言

5、设变量 x 为 float 型且已赋值，则以下语句中能将 x 中的数值保留到小数点后两位，并将第三位四舍五入的是： {{ select(5) }}

• x=(x*100+0.5)/100.0
• x=(int)(x*100+0.5)/100.0
• x=(x/100+0.5)*100.0
• x=x*100+0.5/100.0

6、由数字 1, 1, 2, 4, 8, 8 所组成的不同的4位数的个数是： {{ select(6) }}

• 104
• 102
• 98
• 100

7、排序的算法很多，若按排序的稳定性和不稳定性分类，则（ ）是不稳定排序。 {{ select(7) }}

• 冒泡排序
• 直接插入排序
• 快速排序
• 归并排序

8、G 是一个非连通无向图（没有重边和自环），共有28条边，则该图至少有（ ）个顶点。 {{ select(8) }}

• 10
• 9
• 11
• 8

9、一些数字可以颠倒过来看，例如 0、1、8 颠倒过来看还是本身，6 颠倒过来是 9，9 颠倒过来看还是 6，其他数字颠倒过来都不构成数字。类似的，一些多位数也可以颠倒过来看，比如 106 颠倒过来是 901。假设某个城市的车牌只有5位数字，每一位都可以取 0 到 9。请问这个城市有多少个车牌倒过来恰好还是原来的车牌，并且车牌上的5位数能被3整除？ {{ select(9) }}

• 40
• 25
• 30
• 20

10、一次期末考试，某班有15人数学得满分，有12人语文得满分，并且有4人语、数都是满分，那么这个班至少有一门得满分的同学有多少人？ {{ select(10) }}

• 23
• 21
• 20
• 22

11、设 A 和 B 是两个长为 n 的有序数组，现在需要将 A 和 B 合并成一个排好序的数组，请问任何以元素比较作为基本运算的归并算法，在最坏情况下至少要做多少次比较？ {{ select(11) }}

• $n^{2}$
• $n log n$
• $2n$
• $2n-1$

12、以下哪个结构可以用来存储图？ {{ select(12) }}

• 栈
• 二叉树
• 队列
• 邻接矩阵

13、以下哪些算法不属于贪心算法？ {{ select(13) }}

• Dijkstra算法
• Floyd算法
• Prim算法
• Kruskal算法

14、有一个等比数列，共有奇数项，其中第一项和最后一项分别是 2 和 118098，中间一项是 486，请问以下哪个数是可能的公比？ {{ select(14) }}

• 5
• 3
• 4
• 2

15、有正实数构成的数字三角形排列形式如图所示。第一行的数为 a1,1；第二行的数从左到右依次为 a2,1, a2,2，第 n 行的数为 an,1，an,2，…，an,n。从 a1,1 开始，每一行的数 ai,j 只有两条边可以分别通向下一行的两个数 ai+1,j 和 ai+1,j+1。用动态规划算法找出一条从 a1,1 向下通道 an,1，an,2，…，an,n 中某个数的路径，使得该路径上的数之和最大。 令 C[i][j] 是从 a1,1 到 ai,j 的路径上的数的最大和，并且 C[i][0] = C[0][j] = 0，则 C[i][j] =（ ）

{{ select(15) }}

• $max{C[i-1][j-1],C[i-1][j]}+ a_{i,j}$
• $C[i-1][j-1]+C[i-1][j]$
• $max{C[i-1][j-1],c[i-1][j]}+1$
• $max{C[i][j-1],C[i-1][j]}+ a_{i,j}$ 二、阅读程序（程序输入不超过数组或字符串定义的范围；判断题正确填√错误填X；除特殊说明外，判断题 1.5 分，选择题 4分，共计40 分）

阅读程序,完成16-21题。

01 #include <cstdio>
02 using namespace std;
03 int n;
04 int a[100];
05 
06 int main() {
07     scanf("%d", &n);
08     for (int i = 1; i <= n; ++i)
09         scanf("%d", &a[i]);
10     int ans = 1;
11     for (int i = 1; i <= n; ++i) {
12         if (i > 1 && a[i] < a[i - 1])
13             ans = i;
14         while (ans < n && a[i] >= a[ans + 1])
15             ++ans;
16         printf("%d\n", ans);
17     }
18     return 0;
19 }

16、 第16行输出ans时，ans的值一定大于i。 {{ select(16) }}

• 正确
• 错误

17、程序输出的ans小于等于n。 {{ select(17) }}

• 正确
• 错误

18、若将第12行的<改为!=，程序输出的结果不会改变。 {{ select(18) }}

• 正确
• 错误

19、当程序执行到第16行时，若ans-i>2，则a[i+1]≦a[i]。 {{ select(19) }}

• 正确
• 错误

20、若输入的a数组是一个严格单调递增的数列，此程序的时间复杂度是（ ）。 {{ select(20) }}

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

21、最坏情况下，此程序的时间复杂度是（ ）。 {{ select(21) }}

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

阅读程序，完成22 - 27 题。

01 #include <iostream>
02 using namespace std;
03 
04 const int maxn = 1000;
05 int n;
06 int fa[maxn], cnt[maxn];
07 
08 int getRoot(int v) {
09     if (fa[v] == v) return v;
10     return getRoot(fa[v]);
11 }
12 
13 int main() {
14     cin >> n;
15     for (int i = 0; i < n; ++i) {
16         fa[i] = i;
17         cnt[i] = 1;
18     }
19     int ans = 0;
20     for (int i = 0; i < n - 1; ++i) {
21         int a, b, x, y;
22         cin >> a >> b;
23         x = getRoot(a);
24         y = getRoot(b);
25         ans += cnt[x] * cnt[y];
26         fa[x] = y;
27         cnt[y] += cnt[x];
28     }
29     cout << ans << endl;
30     return 0;
31 }

22、输入的a和b值应在[0, n-1]的范围内。 {{ select(22) }}

• 正确
• 错误

23、第16行改成fa[i] = 0;，不影响程序运行结果。 {{ select(23) }}

• 正确
• 错误

24、若输入的a和b值均在[0, n-1]的范围内，则对于任意0≤i＜n，都有0≤fa[i]＜n。 {{ select(24) }}

• 正确
• 错误

25、若输入的a和b值均在[0, n-1]的范围内，则对于任意0≤i＜n，都有1≤cnt[i] ≤n。 {{ select(25) }}

• 正确
• 错误

26、当n等于50时，若a、b的值都在[0,49]的范围内，且在第25行时x总是不等于y，那么输出为（ ） {{ select(26) }}

• 1276
• 1176
• 1225
• 1250

27、此程序的时间复杂度是（ ） {{ select(27) }}

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

阅读程序，完成28-33题。 提示: $t[0...pre[i] - 1]$ 是 $s[0...i]$ 的子序列; $t[suf[i] + 1...tlen - 1]$ 是 $s[i...slen - 1]$ 的子序列。

01 #include <iostream>
02 #include <string>
03 using namespace std;
04 const int max1 = 202;
05 string s, t;
06 int pre[max1], suf[max1];
07 
08 int main() {
09     cin >> s >> t;
10     int slen = s.length(), tlen = t.length();
11 
12     for (int i = 0, j = 0; i < slen; ++i) {
13         if (j < tlen && s[i] == t[j]) ++j;
14         pre[i] = j; // t[0..j - 1] 是 s[0..i] 的子序列
15     }
16 
17     for (int i = slen - 1, j = tlen - 1; i >= 0; --i) {
18         if(j >= 0 && s[i] == t[j]) --j;
19         suf[i] = j; // t[j + 1..tlen - 1] 是 s[i..slen - 1] 的子序列
20     }
21 
22     suf[slen] = tlen - 1;
23     int ans = 0;
24     for (int i = 0, j = 0, tmp = 0; i <= slen; ++i) {
25         while(j <= slen && tmp >= suf[j] + 1) ++j;
26         ans = max(ans, j - i - 1);
27         tmp = pre[i];
28     }
29     cout << ans << endl;
30     return 0;
31 }

28、程序输出时，suf数组满足：对任意0≤i＜slen，suf[i] ≤ suf[i+1]。 {{ select(28) }}

• 正确
• 错误

29、当t是s的子序列时，输出一定不为0。 {{ select(29) }}

• 正确
• 错误

30、程序运行到第23行时，j-i-1一定不小于0。 {{ select(30) }}

• 正确
• 错误

31、当t是s的子序列时，pre数组和suf数组满足：对任意0≤i＜slen，pre[i] > suf[i+1]+1。 {{ select(31) }}

• 正确
• 错误

32、若tlen=10，输出为0，则slen最小为（ ） {{ select(32) }}

• 10
• 12
• 0
• 1

33、若tlen=10，输出为2，则slen最小为（ ） {{ select(33) }}

• 0
• 10
• 12
• 1

三、完善程序（每题 5 分，共 40 分） 1.(匠人的自我修养) 一个匠人决定要学习 n 个新技术。要想成功学习一个新技术，他不仅要拥有一定的经验值，而且还必须要先学会若干个相关的技术。学会一个新技术之后，他的经验值会增加一个对应的值。给定每个技术的学习条件和习得后获得的经验值，给定他已有的经验值，请问他最多能学会多少个新技术。 输入第一行有两个数，分别为新技术个数 n (1 ≤ n ≤ 10³), 以及已有经验值 (≤ 10⁷)。 接下来 n 行。第 i 行的两个正整数，分别表示学习第 i 个技术所需的最低经验值 (≤ 10⁷), 以及学会第 i 个技术后可获得的经验值 (≤ 10⁷)。 接下来 n 行。第 i 行的第一个数 mi (0 ≤ mi < n)，表示第 i 个技术的相关技术数量。紧跟着 m 个两两不同的数，表示第 i 个技术的相关技术编号。输出最多能学会的新技术个数。 下面的程序以 O (n²) 的时间复杂度完成这个问题，试补全程序。

01 #include<cstdio>
02 using namespace std;
03 const int maxn = 1001;
04 
05 int n;
06 int cnt[maxn];
07 int child [maxn][maxn];
08 int unlock[maxn];
09 int threshold[maxn], bonus[maxn];
10 int points;
11 bool find() {
12     int target = -1;
13     for (int i = 1; i <= n; ++i)
14         if(① && ②){
15             target = i;
16             break;
17         }
18     if(target == -1)
19         return false;
20     unlock[target] = -1;
21     ③
22     for (int i = 0; i < cnt[target]; ++i)
23         ④
24     return true;
25 }
26 
27 int main() {
28     scanf("%d%d", &n, &points);
29     for (int i = 1; i <= n; ++i){
30         cnt[i] = 0;
31         scanf("%d%d", &threshold[i], &bonus[i]);
32     }
33     for (int i = 1; i <= n; ++i){
34         int m;
35         scanf("%d", &m);
36         ⑤
37         for (int j = 0; j < m; ++j){
38             int fa;
39             scanf("%d", &fa);
40             child[fa][cnt[fa]] = i;
41             ++cnt[fa];
42         }
43     }
44 
45     int ans = 0;
46     while(find())
47         ++ans;
48     printf("%d\n", ans);
49     return 0;
50 }

34、①处应填（ ） {{ select(34) }}

• unlock[i] <= 0
• unlock[i] >= 0
• unlock[i] == 0
• unlock[i] == -1

35、②处应填（ ） {{ select(35) }}

• threshold[i] > points
• threshold[i] >= points
• points > threshold[i]
• points >= threshold[i]

36、③处应填（ ） {{ select(36) }}

• target = -1
• --cnt[target]
• bonus[target] = 0
• points += bonus[target]

37、④处应填（ ） {{ select(37) }}

• cnt[child[target][i]] -= 1
• cnt[child[target][i]] = 0
• unlock[child[target][i]] -= 1
• unlock[child[target][i]] = 0

38、⑤处应填（ ） {{ select(38) }}

• unlock[i] = cnt[i]
• unlock[i] = m
• unlock[i] = 0
• unlock[i] = -1

2.（取石子） Alice和Bob两个人在玩取石子游戏。他们制定了n条取石子的规则，第i条规则为：如果剩余石子的个数大于等于a[i]且大于等于b[i]，那么他们可以取走b[i]个石子。他们轮流取石子。如果轮到某个人取石子，而他无法按照任何规则取走石子，那么他就输了。一开始石子有m个。请问先取石子的人是否有必胜的方法？

输入第一行有两个正整数，分别为规则个数n(1 < n < 64),以及石子个数m(≤ 10⁷)。 接下来n行。第i行有两个正整数a[i]和b[i]。(1 ≤ a[i] ≤ 10⁷,1 ≤ b[i] ≤ 64)。

如果先取石子的人必胜，那么输出Win，否则输出Loss。

提示： 可以使用动态规划解决这个问题。由于b[i]不超过64,所以可以使用64位无符号整数去压缩必要的状态。

status是胜负状态的二进制压缩，trans是状态转移的二进制压缩。

试补全程序。

代码说明： ~ 表示二进制补码运算符，它将每个二进制位的 0 变为 1、1 变为 0; 而 ^ 表示二进制异或运算符，它将两个参与运算的数中的每个对应的二进制位一一进行比较，若两个二进制位相同，则运算结果的对应二进制位为 0,反之为 1。 ull 标识符表示它前面的数字是 unsigned long long 类型

01 #include <cstdio>
02 #include<algorithm>
03 using namespace std;
04 const int maxn = 64;
05 int n, m;
06 int a[maxn], b[maxn];
07 unsigned long long status, trans;
08 bool win;
09 int main() {
10     scanf("%d%d", &n, &m);
11     for (int i = 0; i < n; ++i)
12         scanf("%d%d", &a[i], &b[i]);
13     for(int i = 0; i < n; ++i)
14         for(int j = i + 1; j < n; ++j)
15             if (a[i] > a[j]){
16                 swap(a[i], a[j]);
17                 swap(b[i], b[j]);
18             }
19     status = ①;
20     trans = 0;
21     for(int i = 1, j = 0; i <= m; ++i){
22         while (j < n && ②){
23             ③;
24             ++j;
25         }
26         win = ④;
27         ⑤;
28     }
29     puts(win? "Win" : "Loss");
30     return 0;
31 }

39、①处应填（ ） {{ select(39) }}

• 0
• ~0u11
• ~0u11 ^ 1
• 1

40、②处应填（ ） {{ select(40) }}

• a[j] < i
• a[j] == i
• a[j] != i
• a[j] > i

41、③处应填（ ） {{ select(41) }}

• trans |= 1ULL << (b[j] - 1)
• status |= 1ULL << (b[j] - 1)
• status += 1ULL << (b[j] - 1)
• trans += 1ULL << (b[j] - 1)

42、④处应填（ ） {{ select(42) }}

• ~status | trans
• status & trans
• status | trans
• ~status & trans

43、⑤处应填（ ） {{ select(43) }}

• trans = status | trans ^ win
• status = trans >> 1 ^ win
• trans = status ^ trans | win
• status = status << 1 ^ win