CSP-J 练习E卷

4．—个两位十进制正整数n转换为二进制数m，下列说法正确的是( )。

A. m的位数最多是8位

B．删除m的最右边两位后转换为十进制数x，则x=n/4

C. m乘以2的值可能是(11000111)2

D．如果n的个位数字是3，则m的最低位数字可能是0

5．机房里某台计算机无法访问互联网，检查发现，是TCP/IP属性设置有错误，如下图。修正方法是（）

A．参数③改为255、255、255、0 , 其它不变

B．参数②改为192、168、10、1 ,其它不变

C．参数①与参数③交换

D．参数①与参数②交换

第II卷（阅读程序题）
总共3道大题，每道大题含6道小题，判断题和单项选择题。判断题正确填“✓”，错误填“x”。除特殊说明外，每道判断题1.5分，每道单项选择的3分。总共40分。
一、
1. #include <bits/stdc++.h>
2. using namespace std;
3. bool is_prime(int x) {
4. for (int i = 2; i < x; ++i)
5. if (x % i == 0) return false;
6. return true;
7. }
8. int main() {
9. int n;
10. cin >> n;
11. for (int i = 2, cnt = 0; true; i++) {
12. if (is_prime(i)) cnt++;
13. if (cnt == n) {
14. cout << i << endl;
15. break;
16. }
17. }
18. return 0;
19. }

二、
1. #include <iostream>
2. using namespace std;
3. int main() {
4. int n, x;
5. scanf("%d", &n);
6. int a[10];
7. for (int i = 0; i < 10; ++i) a[i] = n;
8. bool ok = true;
9. for (x = 1; ok; ++x) {
10. int y = x;
11. while (y > 0) {
12. if (--a[y % 10] < 0) {cout << x - 1<< endl; ok = false;}
13. y /= 10;
14. }
15. }
16. return 0;
17. }

三、
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. }

第III卷（完善程序题）
总共2道大题，每道大题含5道小题，全部为单项选择题。每道单项选择的3分。总共30分。代码中需要完善的部分都是由数字并且有下划线组成。
一、（验证栈序列）给出两个长度都为n的序列 pushed 和序列poped ，其取值从 1 到 n 。已知入栈序列是 pushed，如果出栈序列有可能是 poped，则输出 Yes，否则输出 No。

1. #include <bits/stdc++.h>
2. using namespace std;
3. const int N = 100010;
4. int n;
5. int instk[N], outstk[N], intop, outtop;
6. int stk[N], top;
7. int main() {
8. scanf("%d", &n);
9. for (int i = 0; i < n; i++) scanf("%d", &instk[i]);
10. for (int i = 0; i < n; i++) scanf("%d", &outstk[i]);
11. intop = 0;
12. 1 ;
13. bool ok = true;
14. for (int i = 0; i < n; ++i) {
15. int x = outstk[i];
16. if (top >= 0 && stk[top] == x) 2 ;
17. else {
18. while ( 3 ) stk[++top] = instk[intop++];
19. if ( 4 ) {ok = false; break;}
20. else 5 ;
21. }
22. }
23. if (ok) puts("Yes");
24. else puts("No");
25. return 0;
26. }

二、（滑动窗口）给定一个长度为N的整数数组，有一个大小为K的滑动窗口从数组的最左侧移动到数组的最右侧。每次滑动窗口值向右移动一位，输出每个窗口内的最大值。例如8个元素分别为1 3 -1 -3 5 3 6 7，在大小为3的滑动窗口中的最大值分别为3 3 5 5 6 7.
滑动窗口的位置最大值
--------------- -----
[1 3 -1] -3 5 3 6 7 3
1 [3 -1 -3] 5 3 6 7 3
1 3 [-1 -3 5] 3 6 7 5
1 3 -1 [-3 5 3] 6 7 5
1 3 -1 -3 [5 3 6] 7 6
1 3 -1 -3 5 [3 6 7] 7
提示：通过单调队列来实现，当元素滑入窗口时检查当前元素是否大于等于队尾元素，如果大于等于队尾元素，则队尾元素出队，直到队空或者队尾元素大于当前元素为止，这样队列元素单调递减，最大值就在队头元素，同时每次滑动窗口要检查队头元素是否已经不在窗口里，如果不在，需要队头元素出队。

1. #include <bits/stdc++.h>
2. using namespace std;
3. const int N = 1e5 + 10;
4. int arr[N];
5. int q[N], head = 0, tail = 0;
6. int n, k;
7. int main() {
8. scanf("%d%d", &n, &k);
9. for (int i = 0; i < n; ++i) scanf("%d", &arr[i]);
10. for (int i = 0; 1 ; ++i) {
11. if ( 2 ) head++;
12. while (head < tail && 3 ) tail--;
13. 4 ;
14. if ( 5 ) printf("%d ", arr[q[head]]);
15. }
16. return 0;
17. }