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

1. 十六进制数 1A2B3C 转换成八进制数字是（）。{{ select(1) }}

• 6425474
• 6621254
• 1715004
• 2510014

2. 数字 189 和 273 的最大公因数是（）{{ select(2) }}

• 13
• 17
• 29
• 21

3. 定义只有一个节点的二叉树深度为1，深度为5的二叉树上最多的节点数和最少的节点数之间的差值为（）{{ select(3) }}

• 15
• 16
• 26
• 31

4. 一个连通的无重边的无向图中有5个节点，图中最多可以有（）条不同的边。{{ select(4) }}

• 10
• 20
• 8
• 16

5. 顺序控制结构的程序执行过程是（）依次执行的。{{ select(5) }}

• 自上而下
• 自下而上
• 自内而外
• 自外而内

6. 一棵树的前序遍历为 ABDEFCGH，中序遍历为 DFEBAGCH，此树的后序遍历为（）。{{ select(6) }}

• FEBGDHCA
• FEDBGHCA
• FDEBGHCA
• FEDBGCHA

7. 现有一个三位数字，不包含数字0，相邻的两个数位上的数字不能相同。符合这个要求的数字共有（）个。{{ select(7) }}

• 890
• 881
• 729
• 576

8. 四个歌手争论谁的歌唱的最好听，每个人可以投票给一位唱的最好听的人，允许投票给自己。假定每个人投票给所有人的概率都是相同的，求有多大可能四个歌手一人一票。（）{{ select(8) }}

• 3/32
• 1/16
• 1/4
• 5/16

9. 对下列代码说法正确的是（）

   int func(int x, int y) {
       if(x > y) return x;
       else return func(x / y, x * y);
   }
   

   {{ select(9) }}

• 对于传入的两个 int 范围下的正整数，只要保证 x 和 y 不相等，该函数就可以正常返回值。
• 该函数传入两个 int 范围下的负整数，一定无法正常返回值。
• 该函数调用中 x 和 y 任意一个只要传入0，一定无法正常返回值。
• 对于传入的两个 int 范围下的整数 x 和 y，若 x =-y，存在方案使得函数正常返回值。

10. 四个有标号的节点之间连线，要求两个节点之间不能重复连线，连两条线的不同方法有（）种{{ select(10) }}

• 10
• 20
• 15
• 30

11. 对下列代码，正确的输出是（）

    #include <iostream>
    using namespace std;
    
    void func(int a, int& b) {
        a += 10;
        b += 10;
    }
    
    int main() {
        int x = 5, y = 5;
        func(x, y);
        cout << x << " " << y;
        return 0;
    }
    

    {{ select(11) }}

• 5 5
• 15 5
• 5 15
• 15 15

12. 已知一个机器人需要从网格的左上角 (0, 0) 移动到右下角（终点），每次只能向右或向下移动一格。若网格有 m 行 n 列，定义 dp[i][j] 为从起点到位置 (i,j) 的不同路径数，则状态转移方程正确的是？{{ select(12) }}

• dp[i][j] = dp[i-1][j] + dp[i][j-1]
• dp[i][j] = dp[i-1][j]- dp[i][j-1]
• dp[i][j] = dp[i-1][j] × dp[i][j-1]
• dp[i][j] = dp[i-1][j] + dp[i][j-1] + 1

13. 下列是一个合法的电子邮件的是？{{ select(13) }}

• www.ccf.com
• ftp://ccf.com
• ccf@ccf.com
• CCF#www.ccf.com

14. 给定一个栈的初始状态为空，执行以下操作序列：

    入栈 3
    入栈 1
    入栈 4
    出栈
    入栈 2
    出栈
    出栈
    入栈 5
    出栈
    

    操作结束后，栈顶元素是（） {{ select(14) }}

• 3
• 1
• 4
• 2

15. 双向链表中有2个指针域 llink 和 rlink，分别指向该结点的前驱和后继。设 p 指向链表中的一个结点，它的左右结点均非空。现要求删除结点 p，则下面语句序列中错误的是（）。{{ select(15) }}

• p->llink->rlink=p->rlink;p->rlink->llink=p->llink;delete(p)
• p->rlink->llink=p->rlink;p->llink->rlink=p->llink;delete(p)
• p->rlink->llink=p->llink;p->rlink->llink->rlink=p->rlink;delete(p)
• p->llink->rlink=p->rlink;p->llink->rlink->llink=p->llink;delete(p)

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

（一）阅读下列程序，回答问题。

1  #include <iostream>
2  using namespace std;
3  
4  int main() {
5  int n, sum = 0;
6  cin >> n;
7  for (int i = 1; i <= n; i++) 
8      for(int j = i;j <= n; j *= 2)
9          sum++;
10  cout << sum << endl;
11  return 0;
12 }

判断题 16. 当输入$n = 10$时，程序输出的结果为18。（）{{ select(16) }}

• 正确
• 错误

17. （3分）若输入的$n = 0$，程序会陷入死循环。（）{{ select(17) }}

• 正确
• 错误

单选题 18. 当输入$n = 100$时，程序输出的结果为（）{{ select(18) }}

• 97
• 100
• 197
• 200

19. （4分）输出答案在$[10,15]$之间的对应合法输入有（）种{{ select(19) }}

• 1
• 2
• 3
• 4

（二）阅读下列程序，回答问题。

1  #include <bits/stdc++.h>
2  using namespace std;
3  using ll = long long;
4  const int S = 1 << 26;
5
6  ll n, res, dp;
7  ll f[S];
8  string s;
9
10 int main() {
11 cin >> s;
12 n = s.size();
13 for (int i = 0; i < n; i++) {
14   dp ^= (1 << (s[i] - 'a'));
15   if (dp == 0) res++;
16   res += f[dp];
17   f[dp]++;
18 }
19  cout << res << '\n';
20  return 0;
21 }

合法的输入为一个长度不超过$10^5$的仅含有小写字母的字符串。

判断题 20. 输入字符串 "aabb" 时，程序输出 "4"。（）{{ select(20) }}

• 正确
• 错误

21. 对于任意长度为1的小写字母构成的字符串，程序均会输出 "0"。（）{{ select(21) }}

• 正确
• 错误

22. （3分）对于任意长度为2的小写字母构成的字符串，程序输出 "1"的不同字符串共有26种。（）{{ select(22) }}

• 正确
• 错误

选择题 23. 选出下列字符串中执行结果和其他不同的一项（）{{ select(23) }}

• ggbcdc
• efaafb
• baacba
• cdcdab

24. （4分）该程序段的功能为（）{{ select(24) }}

• 计数所有非空的字母出现次数均为偶数的允许不连续的子序列数量。
• 计数所有可以为空的字母出现次数均为偶数的允许不连续的子序列数量。
• 计数所有非空的字母出现次数均为偶数的连续的子序列数量。
• 计数所有可以为空的字母出现次数均为偶数的连续的子序列数量。

（三）阅读下列程序，回答问题

1  #include<iostream>
2  using namespace std;
3  int a, b, x, y; 
4  int main(){
5      cin >> a >> b; 
6      while(1){
7           x = a ^ b; 
8           y = a & b;
9           if(y == 0) break; 
10         a = x;
11         b = y << 1;
12     }
13     cout << x << endl; 
14     return 0;
15 }

其中输入保证$0 \leq a,b \leq 10^9$

判断题 25. 第11行的 << 和第13行的 << 意义相同。（）{{ select(25) }}

• 正确
• 错误

26. 第7行计算得到的 x 每次比上一次计算得到的大。（）{{ select(26) }}

• 正确
• 错误

27. （3分）存在一组满足输入限制下的 a,b 使程序会陷入死循环。（）{{ select(27) }}

• 正确
• 错误

单选题 28. 如果输入的$a = 155, b = 229$，那么第10行的代码会执行（）次。{{ select(28) }}

• 7
• 8
• 9
• 10

29. （4分）设$n = max(a,b)$，最坏情况下，此程序的时间复杂度是（）{{ select(29) }}

• $O(n)$
• $O(\log n)$
• $O(n \log n)$
• $O(\sqrt{n})$

三、完善程序（单选题，每小题3分，共计30分）

（一）完善程序第一题

现在有$n$个岛屿，每个岛屿上有一个权值。若两个岛屿的权值之差的绝对值小于等于$maxK$，则两个岛屿之间具有一条双向边。现在，给定所有岛屿的权值，一共有$q$次询问，你的任务是对于每次询问求出两个岛屿能否经过双向边互相抵达，能给出 Yes，不能给出 No。其中$1 \leq n,q \leq 5000$。

1  #include <bits/stdc++.h>
2  using namespace std;
3  const int N = 5005;
4  struct node {
5  int index, value;
6  bool operator < (const node &tmp) const {
7      _______30_______
8      };
9  };
10
11 node nodes[N]; int n, maxK, p[N];
12
13 int main() {
14 cin >> n >> maxK;
15 for(int i = 1; i <= n; ++i) {
16    cin >> nodes[i].value;
17    nodes[i].index = i;
18  }
19
20  _______31_______ 
21 for(int i = 1;i <= n; ++i)
22      _______32_______ 
23  int q; cin >> q;
24  for(int i = 1;i <= q; ++i) {
25    int u, v;
26    cin >> u >> v;
27    _______33_______
28    if(u > v) swap(u, v); 
29    bool flag = 1; 
30    for(int j = u + 1;j <= v; ++j)
31        if(_______34_______) 
32            flag = 0;
33    cout << (flag ? "Yes" : "No") << endl;
34   }
35   return 0;
36 }

30. 30处应填入（）{{ select(30) }}

• return value < tmp.value;
• return index < tmp.index;
• return value > tmp.value;
• return abs(value- tmp.value) <= maxK;

31. 31处应填入（）{{ select(31) }}

• sort(nodes, nodes + n);
• sort(nodes + 1, nodes + n);
• sort(nodes, nodes + n + 1);
• sort(nodes + 1, nodes + n + 1);

32. 32处应填入（）{{ select(32) }}

• p[i] = nodes[i].index;
• p[nodes[i].index] = i;
• p[i] = nodes[i].value;
• p[nodes[i].value] = i;

33. 33处应填入（）{{ select(33) }}

• u = nodes[u].value, v = nodes[v].value;
• u = nodes[u].index, v = nodes[v].index;
• swap(u, v);
• u = p[u], v = p[v];

34. 34处应填入（）{{ select(34) }}

• nodes[j].value- nodes[u].value > maxK
• nodes[v].value- nodes[j].value > maxK
• nodes[j].value- nodes[j- 1].value > maxK
• nodes[j- 1].value- nodes[j].value > maxK

（二）完善程序第二题

给定一个仅有大写字母的字符串，现在可以对字符串中的字符进行$m$次操作，每次操作为下列三种之一：

• 修改一个位置上的字符
• 在任意位置（包括串头和串尾）插入一个字符
• 删去一个字符

求字符串中最多的 ABB 串数。其中，$1 \leq m \leq 10^9$。

1  #include <bits/stdc++.h>
2  using namespace std;
3
4  int solution(string &s, int m)
5  {
6  int n = s.size();
7  int ans = 0;
8  vector<int> vis(n, 0);
9  for (int i = 2; i < n; ++i)
10 {
11    if (s[i] != 'A' && s[i] != 'B')
12        _______35_______
13    if (s[i - 2] == 'A' && s[i - 1] == 'B' && s[i] == 'B')
14        _______36_______
15 }
16 for (int i = 1; i < n; ++i)
17 {
18    if (m && !vis[i] && !vis[i - 1] &&
19        ((s[i - 1] == 'A' && s[i] == 'B') || (_______37_______)))
20        vis[i] = vis[i - 1] = 1, ans++, m--;
21 }
22
23  for (int i = 2; i < n; ++i)
24 {
25    if (m && !vis[i] && !vis[i - 1] && !vis[i - 2] &&
26        ((s[i - 2] == 'A' && s[i - 1] == 'T' && s[i] == 'B')))
27        vis[i] = vis[i - 1] = vis[i - 2] = 1, ans++, m--;
28 }
29
30 for (int i = 0; i < n; ++i)
31 {
32     if (_______38_______ && !vis[i] && (s[i] == 'A' || s[i] == 'B'))
33         vis[i] = 1, ans++, m -= 2;
34 }
35
36 if (m)
37     _______39_______
38
39 return ans;
40 }
41
42 int main()
43 {
44 int n, m;
45 string s;
46 cin >> n >> m >> s;
47 cout << solution(s, m);
48 return 0;
49 }

35. 35处应填入（）{{ select(35) }}

• s[i] = 'A';
• s[i] = 'B';
• vis[i] = 1;
• s[i] = 'T';

36. 36处应填入（）{{ select(36) }}

• vis[i] = 1, ans++;
• vis[i- 1] = vis[i] = 1, ans++;
• vis[i- 2] = vis[i- 1] = vis[i] = 1, ans++;
• ans++;

37. 37处应填入（）{{ select(37) }}

• s[i- 1] == 'B' && s[i] == 'B'
• s[i- 1] == 'A' && s[i] == 'A'
• s[i- 1] == 'B' && s[i] == 'A'
• s[i- 1] == 'T' && s[i] == 'B'

38. 38处应填入（）{{ select(38) }}

• m >= 1
• m > 0
• m >= 2
• i < n- 2

39. 39处应填入（）{{ select(39) }}

• ans += m;
• ans += m / 3;
• ans += m * 3;
• ans += m % 3;