CSP-J/S初赛域 CSP-J模拟卷（三）
选择部分
3 某算法的部分流程图如下图所示。执行这部分流程，若依次输入x的值为6,10,15,20,28，则输出结果分别为(C)?
A.0,1,0,1,0
B.1,0,1,0,1
C.1,0,0,0,1
D.0,0,1,0,1
将6,10,15,20,28分别带入流程图算即可
4 以下能用作C++变量名（B）
A.3student (数字不能作为变量开头）
B.hospital (正确)
C.true (关键字不能作为变量）
D.bmp#3 (#不能放入变量)
5 机房里某台计算机无法访问互联网，检查发现，是TCP/IP属性设置有错误，如下图。修正方法是（D）
A.参数3改为255,255,255,0,其它不变
B.参数2改为192,168,10,1,其它不变
C.参数1与参数3交换
D.参数1与参数2交换
6 若网络带宽为100M bit/s，相当于网速为(10010241024/8 Byte/s)
原因：1Byte=8bit
1Kbps = 1024bps = 128 Bps
1Mbps = 1024Kbps = 128 KBps
1Gbps = 1024Mbps = 128 MBps
7 与单链表相比,双链表的优点之一是(访问前后节点更灵活)
数学常识
13 将4名北京冬奥会志愿者分配到短道速滑、冰球和冰壶3个项目进行培训，每名志愿者只分配到1个项目，每个项目至少分配1名志愿者，则不同的分配方案共有（36）种
根据题目可得知，必有一人在多出，这个人选有4种情况，他有3种选择去哪个项目，其他人选择总情况共3种（2+1），所以结果=3x3x4=36
程序阅读部分
（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.}
1.将第8行中的括号去掉，程序运行结果不变(T)
第8行代码为a=(a*a)%mod; 因为乘法与取余优先级相等所以去掉（）程序运行结果不变
2.将第7行”b%2==1”改为”b&1”,程序运行结果可能改变（F）
b%2==1是判断奇数的，b&1也是判断奇数的，所以程序运行结果不会改变
3.将第9行改为”b >>=2”程序运行结果不变（F）
b>>是将b2进制右移2位相当于b/4向下取整，与b/2不一样，所以程序运行结果会改变
4.将第11行”res%mod”改为”res”程序运行结果不变(T)
因为在第7行的唯一的一行res赋值程序中res已经%mod过了，mod的值也一直保持1024，所以将第11行”res%mod”改为”res”程序运行结果不变
5.当输入是”2 5”时输出为（32）
代入模拟
6.当输入是”10 10”是输出为（0）
代入模拟
（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.}
1.删除第11行，程序结果不变。（T）
2.程序运行结束时，vis数组里所有值都为false。（T）
在第18行所有变成true的vis都会再变成false
3.将第8行”cur == n”改为”cur >= n”程序运行结果不变。（T）
不变因为cur变量每次只+1,(dfs(cur+1);)所以cur不会>n,>=的>没用也就是==
4.当输入n为负数时，程序会运行错误。（F）
n为负数时循环无法进行但是不会运行错误、
程序输入4时，输出的最后一行为（4 3 2 1）
代入模拟
（3）
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.第7行的”>=”改为”>”不会影响程序运行结果(F)
有时候会正好=它，若将=删去有些样例会错
2.第9行改为”int mid=(start+end)/2;”不会影响程序运行结果。（T）
第9行代码：int len = end - start, mid = (len >> 1) + start;改完后其实就是省去一个变量len，不会影响程序运行结果
3.调换12行和13行代码不会影响程序的运行结果。（）
第12行代码：sort(start1, end1);第13行代码：sort(start2, end2); 代码之间并没有联系，12行与13行间没有代码，所以可以调换
4.将16行”<”改为”>”与将28行”i=1;i<n;++i”改为”i=n-1;i>=0;--i”的效果是一些的。（T）
调换的效果是从从小到大改为从大到小，输出不变
5.上述代码用的是哪种排序思想？（归并排序）
理解代码
6.程序时间复杂度为（nlogn）。
根据第5题，归并排序时间复杂度为nlogn
