参考答案
A D C B D
A D B C C
B B A A C
A B B A D
A A A B A
B D B A A
A D B C D
C C A C D
C A B
单选题
1.将4名北京冬奥会志愿者分配到短道速滑、冰球和冰壶3个项目进行培训，每名志愿者只分配到1个项目，每个项目至少分配1名志愿者，则不同的分配方案共有（ ）
[A]36
[B]72
[C]108
[D]144
解析过程
由于需分成3组（每组至少一人），且总共有4人，因此分组方式只能是一组2人、其余两组各1人。计算从4人中选出2人作为一组的方法数，使用组合公式种。将分好的3组分配到3个不同的项目，由于项目有区别，需考虑排列顺序，分配方法数为种。总方案数：基于乘法原理，分组与分配的步骤相乘，即种。
程序题
1.
1.#include <bits/stdc++.h>
2.using namespace std;
3.const int mod = 1024;
4.int fastmi(int a, int b) {
5.int res = 1;
6.while (b) {
7.if (b%2==1) res = (res*a)%mod;
8. a = (a*a)%mod;
9. b = b / 2;
10.}
11. return res % mod;
12.}
13.int main() {
14. int a, b;
15. cin >> a >> b;
16. cout << fastmi(a, b);
17. return 0;
18.}
- 将第11行”res%mod”改为”res”程序运行结果不变。
[A]√
[B]×
- 当输入是”10 10”是输出为（ ）
[A]0
[B]10
[C]100
[D]1000
快速幂核心思想
2.
1.#include <bits/stdc++.h>
2.using namespace std;
3.const int maxn = 20;
4.int a[maxn];
5.bool vis[maxn];
6.int n;
7.void dfs(int cur) {
8. if (cur == n) {
9. for (int i = 0; i < n; ++i) cout << a[i] << " ";
10. cout << endl;
11. return;
12. }
13. for (int i = 1; i <= n; i++) {
14. if (!vis[i]) {
15. a[cur] = i;
16. vis[i] = true;
17. dfs(cur+1);
18. vis[i] = false;
19. }
20. }
21.}
22.int main() {
23. cin >> n;
24. dfs(0);
25. return 0;
26.}
- 将第8行”cur == n”改为”cur >= n”程序运行结果不变。（ ）
[A]√
[B]×
原程序第8行是if (cur == n)，当cur等于n时输出排列。若改为cur > n，由于cur从1开始递增，当cur达到n+1时才会触发条件，但此时递归早已结束，无法生成有效排列，运行结果会改变，所以该说法错误。
- 当输入n为负数时，程序会运行错误。（ ）
[A]√
[B]×
for (int i = 1; i n）循环体不执行，无任何输出程序正常结束无崩溃。
- 删除第11行，程序结果不变。（ ）
[A]√
[B]×
填空题
（1）括号生成 输入n输出所有由n对小括号组成有效括号字符串。 例如输入3，输出：
((())) (()()) (())() ()(()) ()()()
1.#include <bits/stdc++.h>
2.using namespace std;
3.const int N = 110;
4.char s[N];
5.int n;
6.void solve(int l, int r) {
7. if ( ① ) return;
8. if ( ② ) {
9. cout << s << endl;
10. return;
11. }
12. s[l+r] = '(';
13. solve(l+1, r);
14. s[l+r] = ')';
15. solve(l, r+1);
16.}
17.int main() {
18. scanf("%d", &n);
19. solve( ⑤ );
20. return 0;
21.}
①:l>n||r>n||r>l
这是递归终止条件，当左括号数量超过n、右括号数量超过n或右括号数量多于左括号时，说明不是合法组合，需要返回②:l==n&&r==n
当左右括号数量都达到n时，说明找到一个合法组合，可以输出结果⑤:0, 0
初始调用时，左右括号数量都从0开始
(2) 发现环 给定一个无向图，其中有n个顶点和n条边，顶点的编号为1-n，请你找出环上顶点。
1.#include <bits/stdc++.h>
2.using namespace std;
3.const int N = 1e5 + 10;
4.vector<int> g[N];
5.int q[N], hh, tt;
6.int degree[N];
7.int del[N];
8.int main() {
9. int n, a, b;
10. scanf("%d", &n);
11. for (int i = 1; i <= n; ++i) {
12. scanf("%d%d", &a, &b);
13. ① ;
14. ② ;
15. }
16. for (int i = 1; i <= n; ++i)
17. if (degree[i] < 2)
18. ③ ;
19. while ( ④ ) {
20. int u = q[hh++];
21. for (int v: g[u])
22. if (--degree[v] < 2 && !del[v])
23. q[tt++] = v, del[v] = true;
24. }
25. for (int i = 1; i <= n; ++i)
26. if (!del[i]) printf("%d ", i);
27. return 0;
28.}
①:g[a].push_back(b),g[b].push_back(a)
②:degree[a]++,degree[b]++
错因:没看到能两个并成一行的...③:--degree[v] < 2 && !del[v]
度<2的顶点入队并标记删除④:hh<tt
hh＜tt表示队列非空，是终止条件
拓补排序思想
