CSP-J 初赛模拟卷02

一、单选题（每题 2 分，共 30 分）

1. 以下哪个编码不能表示数字 0 {{ select(1) }}

• $[00000000]_反$
• $[11111111]_反$
• $[10000000]_补$
• $[10000000]_原$

2. 人工智能之父是： {{ select(2) }}

• 图灵
• 姚期智
• 周志华
• 冯 • 诺依曼

3. 以下哪种操作系统不是基于 unix 或其分支改造而成的操作系统 {{ select(3) }}

• 安卓
• linux
• ios
• windows

4. 以下编程语言中，哪种语言的效率最高 {{ select(4) }}

• C 语言
• python
• 汇编语言
• 机器语言

5. 以下哪种电子元件的产生，直接推动了个人计算机的问世？ {{ select(5) }}

• 电子管
• 晶体管
• 集成电路
• 超大规模集成电路

6. 以下哪种硬件的 CPU 读取效率最高 {{ select(6) }}

• 缓存
• RAM
• ROM
• 光盘

7. 0,1,2,3,4,5 可以组成 ( ) 个没有重复数字和前导零的五位奇数。 {{ select(7) }}

• 288
• 320
• 144
• 224

8. 以下哪种行为可以有效防止电脑被计算机病毒侵害 {{ select(8) }}

• 定期对计算机进行备份。
• 对自己的各种账号设置较为复杂且各不相同的密码。
• 不下载非官方的软件，不点击未知链接。
• 购买电脑时选购 CPU 更好，硬盘更高级的电脑。

9. 以下对于算法的描述中，完全正确的是： {{ select(9) }}

• 二分法是指将问题一分为二，二分为四，四分为八，再逐一解决分解出的小问题，最终解决整个问题。
• 枚举法是将可能的答案一一枚举并尝试，枚举法可能会借助 for 循环，递归等方法进行。
• 一个算法可以没有输出，但是必须要有输入。
• 选择排序、冒泡排序、插入排序是稳定的排序算法。

10. 三个男生和三个女生站成一排，要求恰好有两个女生相邻，问有多少种方案？ {{ select(10) }}

• 432
• 576
• 192
• 72

11. 以下关于编辑、编译和解释的哪个说法是正确的？ {{ select(11) }}

• dev C++ 软件是 C++ 的编译器。
• dev C++ 软件是 C++ 的编辑器.
• C 语言和 C++ 语言是两种语言，一种是编译型语言，一种是解释型语言。
• C 语言和 C++ 语言是一种语言，它们完全相同。

12. 以下关于变量的定义，命名的说法哪个是正确的？ {{ select(12) }}

• 变量名可以以数字开头，例如 0a
• 变量名只能由字母组成
• 一个程序里可以定义多个 int a;，只要这些变量的作用域不同即可
• 变量的名字可以是系统中已经有的关键词

13. 以下关于计算机语言中表达式的说法，哪个说法是正确的？ {{ select(13) }}

• 一个只包含逻辑运算符和关系运算符的表达式的值只可能为 true 或者 false
• a = b 这一表达式的含义是判断 a 和 b 是否相等
• a > b 这一表达式的含义是 a 这个数字比 b 要大
• a >= b 这个表达式的值一定和表达式 a <= b 的值相反

14. 一个链表中，每一个结点有一个 next 指针指向下一个结点，现在想要删除链表中结点 p 的下一个结点，正确的操作是？ {{ select(14) }}

• free(p->next);
• temp = p->next; p->next = temp->next; free(temp);
• temp = p->next; temp->next = p->next; free(temp);
• temp = p->next; free(temp);

15. 入栈顺序为 1，2，3，4，5，则不可能的出栈顺序为： {{ select(15) }}

• 1 2 3 4 5
• 5 4 3 2 1
• 3 2 1 5 4
• 3 1 2 4 5

二、阅读程序（共 40 分，除特殊标注外，判断题每题 1.5 分，选择题每题 3 分）

阅读程序第一题(共 10 分)

01    #include <iostream>
02    using namespace std;
03    int main(){
04        int a, b; 
05        cin >> a >> b;
06        a = a ^ b;
07        b = a ^ b;
08        a = a ^ b;
09        cout << a << endl;
10    }

判断题(3 分)

1. （1 分）第 6 行的意思是使得 a 等于 a 的 b 次方。 {{ select(16) }}

• 对
• 错

2. （1 分）第 7 行中 = 的含义是判断左右两边相等。 {{ select(17) }}

• 对
• 错

3. （1 分）若输入为 3 5，则经过第 5 行的语句之后，a 的值为 3，b 的值为 5。 {{ select(18) }}

• 对
• 错

选择题(7 分)

1. 若输入为 10 3，则经过第 6 行之后，a 的值为 {{ select(19) }}

• 13
• 7
• 9
• 11

2. （4 分）若输入为 126 82，则最终输出的值为 {{ select(20) }}

• 44
• 82
• 208
• 126

阅读程序第二题(15 分)

01    #include <iostream>
02    using namespace std;
03    const int maxn = 1e5 + 5;
04    int arr[maxn];
05    void reverseArr(int left, int right) {
06        while(left < right) {
07            int temp = arr[left];
08            arr[left] = arr[right];
09            arr[right] = temp;
10            left++;
11            right--;
12        }
13    }
14    void leftShift(int n, int k) {
15        k %= n;
16        reverseArr(0, k-1);
17        reverseArr(k, n-1);
18        reverseArr(0, n-1);
19    }
20    int main() {
21        int n, k;
22        cin >> k >> n;
23        for(int i = 0; i < n; i++)
24            cin >> arr[i];
25        leftShift(n, k);
26        for(int i = 0; i < n; i++) {
27            cout << arr[i] << " ";
28        }
29    }

判断题(8 分)

1. （1 分）若将第 15 行替换为 k % n，程序的运行结果一定不变。 {{ select(21) }}

• 对
• 错

2. （1 分）在 leftShift 函数中，经过 16、17 行的函数调用后，n，k 的值仍然和第 15 行时一样，不发生变化。 {{ select(22) }}

• 对
• 错

3. （2 分）若将第 23、26 行的 for 循环都改为 for(int i = 1; i <= n; i++)，则程序的运行结果一定不变。 {{ select(23) }}

• 对
• 错

4. （2 分）若将第 25 行改为 cout << leftShift(n, k);，则程序可以运行，但是不会输出多余内容。 {{ select(24) }}

• 对
• 错

5. （2 分）第 7 行到第 9 行的作用是交换 arr[left] 和 arr[right]。 {{ select(25) }}

• 对
• 错

选择题(7 分)

1. 若输入为 5 5 1 2 3 4 5，则经过第 16 行之后，arr 数组的前五个元素会变为： {{ select(26) }}

• 1 2 3 4 5
• 5 4 3 2 1
• 2 1 3 5 4
• 4 5 3 1 2

2. （4 分）若输入为 2 5 1 2 3 4 5，则最终的输出为： {{ select(27) }}

• 3 4 5 1 2
• 4 5 1 2 3
• 3 4 5 2 1
• 5 4 1 2 3

阅读程序第三题(15 分)

01    #include <iostream>
02    using namespace std;
03    int main(){
04        int l, r, mod = 10;
05        cin >> l >> r;
06        int ans = 0;
07        for(int i = l; i <= r; i++){
08            int temp = i;
09            int last = -1;
10            bool flag = true;
11            while(temp){ 
12                int now = temp % mod;
13                if(last == 2 && now == 6){
14                    flag = false;
15                }
16                last = now;
17                temp /= mod;
18            }
19            if(flag)
20                ans++;
21        }
22        cout << ans << endl;
23    }

判断题(1.5*4=6 分)

1. 若取消第 8 行，并将所有 temp 全部替换成 i，程序一定可以运行出结果，但是结果可能会错。 {{ select(28) }}

• 对
• 错

2. 若将第 9 行 last 的初始值改为 2，则程序运行结果一定不变。 {{ select(29) }}

• 对
• 错

3. 最终输出的值不可能大于 r-l。 {{ select(30) }}

• 对
• 错

4. 若将第 7 行改为 for(int i = r; i >= l; i--){，则程序运行结果一定不变。 {{ select(31) }}

• 对
• 错

选择题(3*3=9 分)

1. 如果输入为 100 300，则运行结果为 {{ select(32) }}

• 200
• 199
• 198
• 201

2. 如果输入为 1 10000，则运行结果为 {{ select(33) }}

• 9700
• 9701
• 7000
• 7001

3. 若将第 4 行中 mod 改为 6，输入为 1 100000，则运行结果为 {{ select(34) }}

• 0
• 66666
• 97000
• 100000

三、程序填空（每题 3 分，共 30 分）

（大整数加法）给出两个很大的整数，大小超过 long long，求这两个整数相加之后的结果。

提示：用 string 存储两个数字，先将两个数字右对齐，然后像手算加法一样逐位相加，同时在需要的时候向高位进位。

01    #include <iostream>
02    using namespace std;
03    int main(){
04        string s1, s2;
05        cin >> s1 >> s2;
06        if(**1**)	swap(s1, s2);
07        int diff = s1.size() - s2.size();
08        string temp(diff, '0');
09        string ans = s1;
10        s2 = temp + s2;
11        int up = 0; // 保存之前的进位
12        **2**{ // 枚举每一个位置，用于之后的相加
13            int now = s1[i] + s2[i];
14            ans[i] = **3**; // 计算当前位加法之后的结果
15            if(**4**)	up = 1; // 判断下一位进位
16            else	up = 0;
17        }
18        if(up == 1)
19            ans = **5**;
20        for(int i = 0; i < ans.size(); i++)
21            cout << ans[i];
22    }

1. 1 处应填 {{ select(35) }}

• s1 > s2
• s2 > s1
• s1.size() > s2.size()
• s2.size() > s1.size()

2. 2 处应填 {{ select(36) }}

• for(int i = 0; i < s1.size(); i++)
• for(int i = 1; i <= s1.size(); i++)
• for(int i = s1.size(); i >= 1; i--)
• for(int i = s2.size() - 1; i >= 0; i--)

3. 3 处应填 {{ select(37) }}

• now + up
• now % 10 + up
• (now - 2 * '0' + up) % 10
• (now - 2 * '0' + up) % 10 + '0'

4. 4 处应填 {{ select(38) }}

• now >= 10
• now + up >= 10
• now + up >= 2 * '0' + 10
• now >= 2 * '0' + 10

5. 5 处应填 {{ select(39) }}

• 1 + ans
• "1" + ans
• s1[0] + ans
• ans

（数组选数）给定一个大小为 n 的数组和一个数字 k，问能否从这些数字中取到一些数字使得其和为 k。若能，输出 YES，否则输出 NO。

输入第一行包含两个正整数 n，k，接下来一行包含 n 个正整数，表示数组的内容。

提示：使用分治的思想来做，将数组切割成多段子数组。对于每一段子数组，都新建一个 bool 类型的 ans 数组用于保存每个数字能否被取到，再合并多段子数组算出的 ans 数组，最终合并成一个总的 ans 数组，判断 ans[k] 是否为 1，则可以得到答案。

01     #include <iostream>
02     #include <vector>
03     using namespace std;
04     int a[25], n, k;
05     vector<bool> dfs(int l, int r){
06         vector<bool>ans(k + 1);
07  	   int mid = (l + r) / 2;
08         **1**;
09         if(l > r)	return ans;
10         if(l == r){
11             if(a[l] <= k)
12                 **2**;
13             return ans;
14         }
15         vector<bool>lans = dfs(l, mid);
16         vector<bool>rans = dfs(mid + 1, r);
17         **3**{ // 将 lans 和 rans 的内容合并成一个 ans 数组并返回
18             if(lans[i] == 0)	continue;
19             ans[i] = 1;
20             for(int j = 0; j <= k; j++){
21                 if(rans[j] == 0)	continue;
22                 **4**;
23             }
24         } 
25         return ans;
26     }
27     int main(){
28         cin >> n >> k;
29         for(int i = 1; i <= n; i++){
30             cin >> a[i];
31         }
32         vector<bool>ans = **5**;
33         if(ans[k]){
34             cout << "YES" << endl;
35         }else{
36             cout << "NO" << endl;
37         }
38     }

1. 1 处应填 {{ select(40) }}

• ans[0] = 1
• ans[l] = 1
• ans[mid] = 1
• ans[r] = 1

1. 2 处应填 {{ select(41) }}

• return
• ans[a[l]] = 1
• ans[l] = 1
• return ans

3. 3 处应填 {{ select(42) }}

• for(int i = 1; i <= n; i++)
• for(int i = l; i <= r; i++)
• for(int i = 0; i <= k; i++)
• for(int i = a[l]; i <= a[r]; i++)

1. 4 处应填 {{ select(43) }}

• ans[j] = 1
• ans[a[j]] = 1
• ans[i+j] = 1
• ans[i+a[j]] = 1

5. 5 处应填 {{ select(44) }}

• dfs(n, k)
• dfs(0, n)
• dfs(1, n)
• dfs(0, n-1)