CSP-J模拟卷（三）总结
参考答案：
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
错题：
第2题
知识点：操作系统（英语：Operating System，缩写：OS）是一种内置的程序，用来协作计算机的各种硬件，以与用户进行交互。常见有Windows，macOS 和开源的 Linux、华为鸿蒙系统。根据运行的环境，操作系统可以分为桌面操作系统，手机操作系统，服务器操作系统，嵌入式操作系统等。操作系统是人与计算机之间的接口，也是计算机的灵魂。
第10题
知识点：前、中、后序遍历。
思路：通过后序遍历来确定根节点，通过中序遍历来确定左右子树，得出题目中所说的二叉树：
可以看出左子树有4个数。
第13题
知识点：排列、组合
思路：因为其要每个项目都有人，因此一定有两个人在一个项目里，故应有C（4，2） * A（3，3）=4!/(2!*2!)*3!=6*6=36种可能。
第15题
知识点：双链接链表头和尾是连接的，可以很方便的在头和尾插入或删除一个元素（有头指针的）
阅读程序第一题
代码：
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.}
这是快速幂代码，
阅读程序第二题
代码：
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.}
这里的代码就是排列数字。
阅读程序第三题
代码：
1.#include <bits/stdc++.h>
2.using namespace std;
3.const int N = 1e5 + 10;
4.int n;
5.int arr[N], reg[N];
6.void sort(int start, int end) {
7. if (start >= end)
8. return;
9. int len = end - start, mid = (len >> 1) + start;
10. int start1 = start, end1 = mid;
11. int start2 = mid + 1, end2 = end;
12. sort(start1, end1);
13. sort(start2, end2);
14. int k = start;
15. while (start1 <= end1 && start2 <= end2)
16. reg[k++] = arr[start1] < arr[start2] ? arr[start1++] : arr[start2++];
17. while (start1 <= end1)
18. reg[k++] = arr[start1++];
19. while (start2 <= end2)
20. reg[k++] = arr[start2++];
21. for (k = start; k <= end; k++)
22. arr[k] = reg[k];
23.}
24.int main() {
25. cin >> n;
26. for (int i=0; i<n; ++i) cin >> arr[i];
27. sort(0, n-1);
28. for (int i=0; i<n; ++i) cout << arr[i] << " ";
29. return 0;
30.}
这份代码时一个简单的归并排序。
完善程序第一题
代码：
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 (l>n||r>n||r>l) return;
8. if (l==n&&r==n) {
9. cout << s << endl;
10. return;
11. }
12. s[l]='(';
13. solve(l+1, r);
14. s[l+r] = ')';
15. solve(l,r+1);
16.}
17.int main() {
18. scanf("%d", &n);
19. solve(0,0);
20. return 0;
21.}
（这里的代码已补全）
这个代码时通过递归来生成括号的。
完善程序第二题
代码：
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. g[a].push_back(b),g[b].push_back(a);
14. degree[a]++,degree[b]++;
15. }
16. for (int i = 1; i <= n; ++i)
17. if (degree[i] < 2)
18. q[tt++]=i,del[i]=true;
19. while (!g[hh].empty()) {
20. int u = q[hh++];
21. for (int v: g[u])
22. if (!del[v]&&--degree[v]<2)
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.}
（这里的代码已补全）
这段代码的作用是通过拓补排序的思想来对一个无向图的环上顶点。
THE END
