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

1. 运行如下代码的输出结果是（ ）。

char c = '0' + 'P';
cout << c << endl;

{{ select(1) }}

• 0
• P
• 48
• 80

2. 以下代码段的功能是（ ）。

#include <iostream>
using namespace std;
int Lowbit(int x) {
    return (x & -x);
}
int main() {
    int n, res = 0;
    cin >> n;
    while (n) {
        n -= Lowbit(n), res++;
    }
    cout << res;
    return 0;
}

{{ select(2) }}

• 求该数转为二进制数以后各位上1的总数
• 求该数转为二进制的反码
• 求该数转为二进制的补码
• 求该数转为二进制的原码

3. 前缀表达式-*+1345/567的后缀表达式为（ ）。 {{ select(3) }}

• 1 3 4 + 5 * 5 6 7 / -
• - * + 1 3 4 5 / 5 6 7
• 1 3 4 + 5 * 5 6 7 /
• 1 3 4 5 * + 5 6 7 /

4. 在数组$A[x]$中，若存在$(i < j) \&\& (A[i] > A[j])$，则称$(A[i], A[j])$为数组$A[x]$的一个逆序对。对于序列7,4,1,9,3,6,8,5，其中有（ ）个逆序对。 {{ select(4) }}

• 10
• 11
• 12
• 13

5. 以下哪个操作不属于STL中双端队列（deque）的操作函数？（ ） {{ select(5) }}

• front
• back
• top
• erase

6. KMP算法不属于下面哪位人士参与研究的算法？（ ） {{ select(6) }}

• Knuth
• McDonald
• Morris
• Pratt

7. 命题“$P \rightarrow Q$”可读作$P$蕴含$Q$，其中$P$、$Q$是两个独立的命题。只有当命题$P$成立而命题$Q$不成立时，命题“$P \rightarrow Q$”的值才为false，其他情况均为true。与命题“$P \rightarrow Q$”等价的逻辑关系式是（ ）。 {{ select(7) }}

• $\neg P \vee Q$
• $P \leftrightarrow Q$
• $\neg (P \vee Q)$
• $\neg (\neg Q \land P)$

8. 有一个5x5的棋盘，棋盘左下格有一枚棋子，我们每次可以将棋子向右移动一格，也可以向上移动一格，但棋盘的某些方格不可以放置棋子（如下图所示，画x的方格表示不可以放置棋子），则棋子从左下格到右上格一共存在（ ）条路径。 {{ select(8) }}

• 10
• 11
• 12
• 13

9. 关于图论，下面的说法哪个是正确的？（ ） {{ select(9) }}

• 欧拉路有一个奇点
• 欧拉回路有两个奇点
• 对于一个无向图，如果任意一对顶点都是连通的，则此图被称为连通图
• 不存在割点的无向图称为“2-边连通图”

10. 假设我们用$V = (p_1, p_2, \cdots, p_5)$来表示无向图$G$的5个顶点的度数，下面给出的哪组$V$值合理？（ ） {{ select(10) }}

• {5, 3, 3, 3, 1}
• {2, 2, 2, 1, 1}
• {3, 3, 3, 2, 2}
• {1, 4, 3, 2, 5}

11. 下述选项哪个不属于与典型图论有关的算法？（ ） {{ select(11) }}

• 线段树
• 次小生成树
• 最小生成树
• Bellman-Ford

12. 有如下递归代码，则solve(30, 30)的结果为（ ）。

int fun(int a, int b) {
    if (a == 1) return 1;
    return 9 * fun(a - 1, b) % b;
}

{{ select(12) }}

• 9
• 18
• 21
• 27

13. 甲乙两人参加校内“信奥”知识竞赛，其中有6道选择题和4道判断题，甲乙两人依次各抽1题。请问甲乙两人中至少有一人抽到选择题的概率是（ ）。 {{ select(13) }}

• 4/15
• 13/15
• 4/5
• 11/15

14. 如下图所示，用4种颜色给图中的$A$、$B$、$C$、$D$、$E$、$F$这6个点涂色，要求每个点涂一种颜色，且图中每条线段的两个端点涂不同颜色，则不同的涂色方法有（ ）种。 {{ select(14) }}

• 288
• 264
• 240
• 168

15. 1800的所有约数的和为（ ）。 {{ select(15) }}

• 6043
• 6044
• 6045
• 6046

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

(1)

01 #include <iostream>
02 using namespace std;
03 
04 const int N = 100500;
05 const int Mod = 1000000007;
06 int n, m, j, p[N], f[N];
07 char s[N], t[N];
08 
09 int main() {
10     scanf("%s", s + 1); scanf("%s", t + 1);
11     n = strlen(s + 1); m = strlen(t + 1);
12     j = 0; p[1] = 0;
13     for (int i = 1; i < m; ++i) {
14         while (j > 0 && t[j + 1] != t[i + 1]) j = p[j];
15         if (t[j + 1] == t[i + 1]) ++j;
16         p[i + 1] = j;
17     }
18     j = 0; f[0] = 1;
19     for (int i = 1; i <= n; ++i) {
20         f[i] = f[i - 1];
21         while (j > 0 && s[i] != t[j + 1]) j = p[j];
22         if (s[i] == t[j + 1]) ++j;
23         if (j == m) {
24             j = p[j];
25             (f[i] += f[i - m]) %= Mod;
26         }
27     }
28     printf("%d\n", f[n]);
29     return 0;
30 }

■ 判断题 16. 若输入数据导致$m > n$，则输出一定为1。（ ） {{ select(16) }}

• 正确
• 错误

17. 若输入数据导致$m = 1$，则输出一定为2的整次幂。（ ） {{ select(17) }}

• 正确
• 错误

18. 去掉第12行，不影响程序的输出结果。（ ） {{ select(18) }}

• 正确
• 错误

19. 若将本程序改为可读入多组数据，则并不用增加新的初始化代码。（ ） {{ select(19) }}

• 正确
• 错误

■ 选择题 20. 若输入为"xxxxxxxxx"，则输出为（ ）。 {{ select(20) }}

• 5
• 8
• 10
• 15

21. 输入数据的两个字符串长度分别为$N$、$M$，则本程序的时间复杂度为（ ）。 {{ select(21) }}

• $O(M)$
• $O(N)$
• $O(M + N)$
• $O(M \times N)$

(2)

01 #include <iostream>
02 
03 const int mod = 1e4;
04 int n;
05 int ans;
06 
07 inline int qpow(int a, int b) {
08     int res = 1;
09     for (; b; b >>= 1, a = 1LL * a * a % mod)
10         if (b & 1) res = 1LL * res * a % mod;
11     return res;
12 }
13 
14 inline void add(int &x, const int y) {
15     x += y;
16     if (x >= mod) x -= mod;
17 }
18 
19 inline int calc(int n) {
20     int res = 0;
21     int c = 1, x = 1;
22     for (; x * 10 - 1 <= n; ++c, x *= 10)
23         add(res, 9LL * x * c % mod);
24     add(res, 1LL * c * (n - x + 1) % mod);
25     return res;
26 }
27 
28 int main() {
29     std::cin >> n;
30     if (n == 1) return puts("4"), 0;
31     ans = n % mod;
32     add(ans, 1LL * qpow(2, n - 1) * n % mod);
33     add(ans, (calc(n) - 1 + mod) % mod);
34     add(ans, 1LL * qpow(2, n - 1) * calc(n) % mod);
35     add(ans, (qpow(2, n) - 1 + mod) % mod);
36     add(ans, 2 * (n - 1) % mod);
37     std::cout << ans << std::endl;
38     return 0;
39 }

■ 判断题 22. 第14行的两个&符号的作用一致。（ ） {{ select(22) }}

• 正确
• 错误

23. 第16行等价于把$x$对mod取模，只是更慢。（ ） {{ select(23) }}

• 正确
• 错误

24. 输入为5的时候，输出为209。（ ） {{ select(24) }}

• 正确
• 错误

25. 输入每增加1，输出扩大2倍以上。（ ） {{ select(25) }}

• 正确
• 错误

■ 选择题 26. 输入为0的时候，程序会（ ）。 {{ select(26) }}

• 输出乱码
• 死循环
• 输出"0"
• 输出"-1"

27. 本程序的时间复杂度为（ ）。 {{ select(27) }}

• $O(\log N)$
• $O(\log \log N)$
• $O(N)$
• $O(\log_2 N + \log N)$

(3)

01 #include <iostream>
02 using namespace std;
03 typedef long long i64;
04 
05 const int NN = 1e7 + 5;
06 i64 ans, l, r;
07 bool s[NN];
08 int p[NN], o[NN], cnt;
09 
10 inline void sss() {
11     o[1] = 1;
12     for (int i = 2; i <= r; ++i) {
13         if (!s[i])
14             o[p[++cnt] = i] = i;
15         for (int j = 1; j <= cnt && p[j] * i <= r; ++j) {
16             s[p[j] * i] = true;
17             o[p[j] * i] = p[j];
18             if (i % p[j] == 0) break;
19         }
20     }
21 }
22 
23 inline void answer() {
24     sss();
25     for (int i = l; i <= r; ++i)
26         if (s[i]) ans += i / o[i];
27     cout << ans << endl;
28 }
29 
30 int main() {
31     cin >> l >> r;
32     answer();
33 }

■ 判断题 28. （2分）本题使用了埃氏筛法。（ ） {{ select(28) }}

• 正确
• 错误

29. （2分）如果输入数据$l$比$r$大，那么程序会报错或者发生死循环。（ ） {{ select(29) }}

• 正确
• 错误

30. （2分）本程序可以处理的最大$r$是10000000。（ ） {{ select(30) }}

• 正确
• 错误

31. （2分）在确保$l < r$的前提下，$l$的大小不影响程序的运行速度。（ ） {{ select(31) }}

• 正确
• 错误

■ 选择题 32. （4分）当输入为"6 27"时，输出为（ ）。 {{ select(32) }}

• 115
• 116
• 117
• 118

33. （4分）本程序的时间复杂度为（ ）。 {{ select(33) }}

• $O(\log N)$
• $O(N)$
• $O(\log \log N)$
• $O(N \log \log N)$

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

(1) 输入一系列短棍的长度，它们是由一些等长的木棒截断得来的。请输出原始木棒的最小可能长度。截断后的短棍不超过64根，且长度不超过50。本程序使用搜索+剪枝的办法来解决该问题，共使用4个剪枝。

比如，输入数据为：

9
5 2 1 5 2 1 5 2 1

输出数据为：

6

拼凑方案为： 5+1, 5+1, 5+1, 2+2+2

01 #include <iostream>
02 using namespace std;
03 
04 int a[100], v[100], n, len, cnt;
05 bool dfs(int stick, int cab, int last) {
06     if (stick > cnt) return true;
07     if (cab == len) return dfs(stick + 1, 0, 1);
08     int fail = 0;
09     for (①) {
10        if (!v[i] && cab + a[i] <= len && fail != a[i]) {
11             v[i] = 1;
12             if (dfs(stick, cab + a[i], i + 1)) return true;
13             ②;
14             v[i] = 0;
15             if (③ || ④) return false;
16         }
17     }
18     return false;
19 }
20 
21 int main() {
22     while (cin >> n && n) {
23         int sum = 0, val = 0;
24         for (int i = 1; i <= n; i++) {
25             scanf("%d", &a[i]);
26             sum += a[i]; val = max(val, a[i]);
27         }
28         sort(a + 1, a + n + 1);
29         reverse(a + 1, a + n + 1);
30         for (len = val; len <= sum; len++) {
31             if (sum % len) continue;
32             cnt = sum / len;
33             memset(v, 0, sizeof(v));
34             if (⑤) break;
35         }
36         cout << len << endl;
37     }
38     return 0;
39 }

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

• int i = n; i >= last; i--
• int i = last; i <= n; i++
• int i = last + 1; i <= n; i++
• int i = n; i >= last + 1; i--

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

• fail += a[i]
• a[i] = fail
• fail = cab + a[i]
• fail = a[i]

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

• cab == 0
• cab == a[i]
• a[last] == fail
• last == 0

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

• cab + a[i] <= len
• a[i] == fail
• cab + a[i] == len
• a[i] > cab / 2

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

• dfs(0, 0, 1)
• dfs(1, 0, 1)
• dfs(0, 0, 0)
• dfs(1, 0, 0)

(2) 给定一个长度不超过17的字符串及整数$K$，字符串由0~9组成，且无前导0。求使用其中的数字排列成无前导0且能被17整除的第$K$小的数。$K \leq 17$。

比如，输入为22422232，输出为2242232。

01 #include <iostream>
02 using namespace std;
03 
04 typedef long long ll;
05 const int N = 20, M = 20005;
06 int cnt[N]; char s[N];
07 ll f[N][N][M], d[N], K;
08 
09 inline ll dfs(int k, int val, int sta) {
10     ①;
11     if (~f[k][val][sta]) return f[k][val][sta];
12     ll res = 0;
13     for (int i = 0; i <= 9; ++i) {
14         int lim = sta / d[i] % (cnt[i] + 1);
15         if (lim == cnt[i]) continue;
16         res += ②;
17     }
18     return f[k][val][sta] = res;
19 }
20 
21 int main() {
22     ③;
23     scanf("%s", s + 1); cin >> K;
24     int len = strlen(s + 1);
25     for (int i = 1; i <= len; ++i)
26         ++cnt[s[i] - '0'];
27     d[0] = 1;
28     for (int i = 1; i <= 9; ++i)
29         d[i] = ④;
30     int sta = 0, val = 0; ll now = 0;
31     for (int i = len; i >= 1; --i) {
32         for (int j = (i == len ? 1 : 0); j <= 9; ++j) {
33             int lim = ⑤;
34             if (lim == cnt[j]) continue;
35             ll tmp = dfs(i - 1, (val * 10 + j) % 17, sta + d[j]);
36             if (now + tmp >= K) {
37                 putchar(j + '0');
38                 val = (val * 10 + j) % 17;
39                 sta += d[j];
40                 break;
41             }
42             now += tmp;
43         }
44     }
45     cout << endl;
46     return 0;
47 }

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

• if (k) return !val
• if (!k) return !val
• if (!k) return val
• if (k) return val

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

• dfs(k + 1, (val - i * 10) % 17, sta + d[i])
• dfs(k - 1, (val * 10 + i) % 17, sta - d[i])
• dfs(k + 1, (val - i * 10) % 17, sta - d[i])
• dfs(k - 1, (val * 10 + i) % 17, sta + d[i])

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

• memset(f, 255, sizeof(f))
• memset(f, 0, sizeof(f))
• memset(f, 127, sizeof(f))
• memset(f, 128, sizeof(f))

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

• d[i - 1] * (cnt[i - 1])
• d[i - 1] * (cnt[i])
• d[i - 1] * (cnt[i - 1] + 1)
• d[i - 1] * (cnt[i] + 1)

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

• sta / d[j] % (cnt[j] + 1)
• sta / d[j - 1] % (cnt[j])
• sta / d[j - 1] % (cnt[j] + 1)
• sta / d[j] % (cnt[j])

---