CSP-J 初赛模拟卷09

一、单项选择题（共 15 题，每题 2 分，共计 30 分；每题有且仅有一个正确选项）

1. 二进制 $(1110110101101111)_2$ 转化为 8 进制的结果为？

{{ select(1) }}

• $(732671)_8$
• $(166557)_8$
• $(60703)_8$
• $(ED6F)_{16}$

2. 根据“冯·诺依曼计算机”模型，以下哪一个不属于计算机结构中的一部分？

{{ select(2) }}

• 运算器
• 输入设备
• 打印机
• 控制器

3. TCP/IP 结构的最上面一层是：

{{ select(3) }}

• 网络层
• 数据链路层
• 应用层
• 传输层

4. 中国计算机协会的英文缩写是：

{{ select(4) }}

• CSP
• NOI
• CCF
• IOI

5. 十进制 $(0.75)_{10}$ 转化为二进制为：

{{ select(5) }}

• $(0.101)_2$
• $(0.11)_2$
• $(0.111)_2$
• $(0.011)_2$

6. 马路上有编号为 1,2,3,4,5,6,7,8,9 的九盏路灯，现要关闭其中的 3 盏灯，但不能关掉相邻的 2 盏或 3 盏灯，也不能关掉两端的任意一盏灯，求满足条件的关灯方法有多少种？

{{ select(6) }}

• 10
• 15
• 20
• 25

7. 12 个顶点的连通图的最大生成树，其边数为( )

最大生成树的概念：保持一个图中点与点之间的联通性，删除若干条边后使图形成一棵树，使得树的两点间距离尽可能的远。

{{ select(7) }}

• 132
• 11
• 66
• 110

8. 以下哪种行为不会有网络安全风险：

{{ select(8) }}

• 连接公共场所的免费 WI-FI
• 使用“下载之家”网站下载游戏《红色警戒》
• 将自己的文件上传到“百度网盘”或“腾讯网盘”中
• 自定义的密码和账号相同，或为 123456 等简单密码

9. 一棵深度为 K 的完全二叉树最少有（ ）个结点：

{{ select(9) }}

• $2^K$
• $2^K-1$
• $2^{K-1}$
• $2×K-1$

10. 有 如 下 说 明 语 句 char str1[80]="abce",str2[80]="1234",str3[80]="ABCD"; 执 行 strcat(str1,strcat(str3,str2));后，下面说法正确的是？

{{ select(10) }}

• str1="abceABCD1234" str2="1234" str3="ABCD1234"
• str1="abce" str2="1234ABCD" str3="1234ABCDabce"
• str1="abceABCD" str2="1234" str3="ABCD1234"
• str1="abcd" str2="1234abceABCD" str3="ABCD"

11. 下面的故事与（ ）算法有着异曲同工之妙。

从前有座山，山里有座庙，庙里有个老和尚在给小和尚讲故事：“从前有座山，山里有座庙，庙里有个老和尚  在给小和尚讲故事：‘从前有座山，山里有座庙，庙里有个老和尚给小和尚讲故事……’”

{{ select(11) }}

• 枚举
• 递归
• 贪心
• 分治

12. 在 10000 以内，不能被 3 整除也不能被 2 整除的数有（ ）个

{{ select(12) }}

• 6667
• 5000
• 8334
• 3333

13. 在一个含有 10 个元素的集合里，其非空子集的数量是：

{{ select(13) }}

• 1024
• 1025
• 1023
• 512

14. 有 10 个运动员名额，分给 7 个班，每班至少一个，有 ( ) 种分配方案

{{ select(14) }}

• 252
• 90
• 80
• 84

15. 下面哪一种设备属于输入设备？

{{ select(15) }}

• 扫描仪
• 投影仪
• 显示器
• 打印机

二、阅读程序(程序输入不超过数组或字符串定义的范围，判断题正确填√，错误 填x;除特殊说明外，判断题1.5分，选择题3分，共计40分)

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

01    #include <bits/stdc++.h>
02    using namespace std;
03    int main(){
04        string s;
05        cin >> s;
06        int cnt = 0;
07        s = " " + s;
08        for(int i = 1; i < s.size(); i++){
09            if(s[i] != s[i-1])
10                cnt++;
11        }
12        cout << cnt << endl;
13    }

判断题(1.5*2=3)

16. 若将第 6 行改为 int cnt;，程序运行结果不变。

{{ select(16) }}

• 正确
• 错误

17. 由于 string 是从 0 计数的，所以第 8 行中 i 的初始化应该改为 $\text {i = 0}$，程序的运行结果才能符合期望。

{{ select(17) }}

• 正确
• 错误

选择题(3*2=6)

18. 当输入为 aabbcc 时，输出为

{{ select(18) }}

• 3
• 2
• 4
• 程序无法正常运行

19. 若删去第 7 行，当输入为 aabeeb 时，输出为

{{ select(19) }}

• 3
• 5
• 4
• 程序无法正常运行

程序阅读第二题（共 13 分）

01    #include <bits/stdc++.h>
02    using namespace std;
03    const int maxn = 1e5 + 5;
04    struct student{
05        int id, rank, num;
06    }stu[maxn];
07    bool cmp1(student a, student b){
08        return a.num > b.num;
09    }
10    bool cmp2(student a, student b){
11        return a.id < b.id;
12    }
13    int main(){
14        int n;
15        cin >> n;
16        for(int i = 1; i <= n; i++){
17            cin >> stu[i].num;
18            stu[i].id = i;
19        }
20        sort(stu+1, stu+1+n, cmp1);
21        for(int i = 1; i <= n; i++){
22            stu[i].rank = i;
23        }
24        sort(stu+1, stu+1+n, cmp2);
25        for(int i = 1; i <= n; i++){
26            cout << stu[i].rank << " ";
27        }
28    }

判断题(1*5=5)

20. （1分）第 20 行的排序是按照 num 从小到大进行排序。

{{ select(20) }}

• 正确
• 错误

21. （1分）第 24 行排序过后，stu[i] 数组中 num 的顺序和输入的顺序完全一样。

{{ select(21) }}

• 正确
• 错误

22. （1分）若将第 11 行改为 return a.id > b.id;，不会影响每一个 id 对应的 rank 值。

{{ select(22) }}

• 正确
• 错误

23. （1分）若在第 14 行后加一句 student stu[maxn];，程序依然能够编译通过。

{{ select(23) }}

• 正确
• 错误

24. （1分）若将第 04 行到第 06 行移动到第 13 行的上面，程序依然能够编译通过。

{{ select(24) }}

• 正确
• 错误

选择题(4*2=8)

25. （4分）若输入为 4 40 10 20 30（其中 4 是 $n$ 的值），则输出为

{{ select(25) }}

• 1 4 3 2
• 40 10 20 30
• 40 30 20 10
• 1 2 3 4

26. （4分）该代码的时间复杂度为

{{ select(26) }}

• $O(n)$
• $O(\text {n log n})$
• $O(\text {n log n log n})$
• $O(n^2)$

程序阅读第三题(共 18 分)

01    #include <iostream>
02    using namespace std;
03    int main(){
04        int n = 5, now = 1, a;
05        for(int i = 1; i <= n; i++){
06            cin >> a; // a 为正整数
07            int y = now;
08            now *= a;
09            if(now != 1){
10                if(a < y)	swap(a, y);
11                while(y != 0){
12                    int temp = y;
13                    y = a % y;
14                    a = temp;
15                }
16                now = now / a;
17            }
18        } 
19        cout << now << endl;
20    }

判断题（2*5=10）

27. （2分）若删除第 10 行，则程序运行结果一定不变。

{{ select(27) }}

• 正确
• 错误

28. （2分）若将第 16 行改为 now /= a;， 则程序运行结果一定不变。

{{ select(28) }}

• 正确
• 错误

29. （2分）若将第 9 行改为 if(true){，则程序运行结果一定不变。

{{ select(29) }}

• 正确
• 错误

30. （2分）如果不保证 a 为正整数，则程序一定可以运行出结果，但是结果可能不理想。

{{ select(30) }}

• 正确
• 错误

31. （2分）如果输入的所有 a 都相等，则就算没有 11-15 行的循环，程序运行结果也不会改变。

{{ select(31) }}

• 正确
• 错误

选择题(4*2=8)

32. （4分）若程序的输入为 1 1 3 6 7，则输出为

{{ select(32) }}

• 3
• 18
• 126
• 42

33. （4分）若将输入数字个数为 n，每个数字 a 的大小为 m，则该程序的时间复杂度为

{{ select(33) }}

• $O(nm)$
• $O(n)$
• $O(\text {n log n})$
• $O(\text {n log m})$

三、完善程序（单选题，每小题 3 分，共计 30 分）

1.(最长回文子串)给出一个长度为 n 的字符串，输出它最长的回文子串。

回文串的定义：正着读和反着读是一样的字符串。例如 aba，abba，a 等。

01    #include <bits/stdc++.h>
02    using namespace std;
03    string s;
04    int check(int l, int r){
05        for(; ; l--, r++){
06            if(r >= s.size() || l < 0 || s[l] != s[r])
07                break;
08        }
09        return ____①____; // 返回最长回文子串的长度
10    }
11    int main(){
12        cin >> s;
13        int maxx = 0, l, r;// 用 l r 保存最终回文串的左右端点
14        for(int i = 0; i < s.size(); i++){
15            int len = max(check(i, i), check(i, i+1));
16            if(len > maxx){
17                maxx = len;
18                if(len % 2 == 1){
19                    ____②____; // 记录最长回文子串的左端点
20                    ____③____; // 记录最长回文子串的右端点
21                }else{
22                    l = i - len / 2 + 1;
23                    r = i + len / 2;
24                }
25            }
26        }
27        cout << ____④____ << endl; // 根据 l r 的位置输出最终的回文子串
28    }

34. ①处应填

{{ select(34) }}

• r - l
• r - l + 1
• r - l - 1
• r

35. ②处应填

{{ select(35) }}

• l = i - len / 2
• l = i - len + 1
• l = i - len
• l = i - len / 2 + 1

36. ③处应填

{{ select(36) }}

• r = i + len / 2
• r = i + len - 1
• r = i + len
• r = i + len / 2 - 1

37. ④处应填

{{ select(37) }}

• s.substr(l)
• s.substr(l,r)
• s.substr(l,r - l + 1)
• s.substr(l,r - l)

38. 该代码的时间复杂度为

{{ select(38) }}

• $O(n)$
• $O(n^2)$
• $O(\text {n log n})$
• $O(n^3)$

2.(矩阵螺旋输出)现在给出一个二维数组，要求按照顺时针螺旋的方式输出这个二维数组（详见样例）。输入第一行给定 n,m 表示二维数组的行数和列数，然后每行依次给出这个二维数组的具体内容

样例输入

3 3
1 2 3
4 5 6
7 8 9

样例输出

1 2 3 6 9 8 7 4 5

01    #include <iostream>
02    #include <string.h>
03    using namespace std;
04    int n, m, cnt = 0; // cnt 表示现在输出的数字的个数
05    int a[105][105];
06    int vis[105][105];
07    void print(int x, int y, int flag){// x, y 是当前坐标，flag 表示方向，0 向右，1 向下，2 向左，3 向上
08        if(____①____){
09            return;
10        }
11        if(!vis[x][y]){
12            cout << a[x][y] << " ";
13            ____②____;
14            cnt++;
15        }
16        int nxt_x = x, nxt_y = y; // nxt_x nxt_y 表示下一个要输出的位置的坐标
17        if(flag == 0 && y != m){
18            ____③____;
19        }else if(flag == 1 && x != n){
20            nxt_x++;
21        }else if(flag == 2 && y != 1){
22            nxt_y--;
23        }else if(flag == 3 && x != 1){
24            nxt_x--;
25        }
26        if(____④____){
27            print(x, y, (flag + 1) % 4);
28        }else{
29            print(nxt_x, nxt_y, flag);
30        }
31    }
32    int main(){
33        cin >> n >> m;
34        memset(vis, 0x3f, sizeof vis);
35        for(int i = 1; i <= n; i++){
36            for(int j = 1; j <= m; j++){
37                cin >> a[i][j];
38                vis[i][j] = 0;
39            }
40        }
41        ____⑤____;
42    }

39. ①处应填

{{ select(39) }}

• vis[x][y] == 1
• cnt == n * m
• flag == 4
• x > n || y > m

40. ②处应填

{{ select(40) }}

• vis[x][y] = 1
• print(x,y,flag + 1)
• print(x,y + 1,flag)
• vis[x][y] = 0

41. ③处应填

{{ select(41) }}

• nxt_y++
• y++
• y--
• nxt_y--

42. ④处应填

{{ select(42) }}

• vis[x][y] == 1
• vis[x][y] == 0
• vis[nxt_x][nxt_y] == 0
• vis[nxt_x][nxt_y] == 1

43. ⑤处应填

{{ select(43) }}

• print(1, 1, 0)
• print(0, 0, 0)
• print(1, 1, 1)
• print(0, 0, 1)