CSP-J初赛模拟题

（C++语言 满分：100分 考试时间：120分钟）

一、单项选择题

1. 以下哪个选项不属于“外设”？ {{ select(1) }}

• 硬盘
• 鼠标
• 显示器
• CPU

2. CPU 处理速度“字长”的单位是什么？

{{ select(2) }}

• 字节
• 位
• KB
• TB

3. 在 C++ 中，表达式 12^6 的结果是多少？ {{ select(3) }}

• 4
• 6
• 10
• 14

4. 以下关于算法的描述中，哪一项是正确的？ {{ select(4) }}

• 对于同样的算法，使用递归实现的时间复杂度一定比使用循环实现的时间复杂度高。
• 递归就是一种深度优先搜索。
• 广度优先搜索需要借助栈才能实现。
• 二分查找只能在线性数据结构上才能够使用，例如数组、链表等。

5. 3 个男生和 3 个女生站成一排，要求每个男生的旁边都要有女生，且女生甲和女生乙必须相邻，求方案数 （ ） {{ select(5) }}

• 24
• 72
• 36
• 48

6. 字符串 abc 有 6 种全排列，字符串 ddd 有 1 种全排列，则字符串 abcddd 有几种全排列

   {{ select(6) }}

• 120
• 360
• 240
• 60

7. 假设 a = true, b = true, c = false，则逻辑运算表达式为真的是

{{ select(7) }}

• (a∧c)∨(b∧c)
• (a∨c)∧(b∧c)
• (a∧c)∨(b∧a)
• a ∧ (b ∨ c) ∧ c

8. 已知一棵二叉树的先序遍历序列为 ABDGCEFH， 中序遍历序列为 DGBAECHF，则后序遍历序列为 {{ select(8) }}

• GDBAEHFC
• GDBEHFCA
• GDBEFHCA
• GDBECHFA

9. 定义一个数组 long long a[10]，则运行此程序时，这个数组占用的系统空间大小为 {{ select(9) }}

• 80KB
• 80B
• 40KB
• 40B

10. 入栈顺序为 1、2、3、4、5，则出栈顺序不可能为

{{ select(10) }}

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

11. 以下哪种数据结构可以用于图的存储

{{ select(11) }}

• 队列
• 并查集
• 邻接表
• 栈

12.有多少个没有前导零的四位数，满足任意两个相邻的数位都不相同？

{{ select(12) }}

• 9990
• 9000
• 6561
• 7200

13. 对于同样的逻辑，以下哪种编程语言的执行效率最高

{{ select(13) }}

• python
• go 语言
• java
• C 语言

14. 用于预测和评估台风“烟花”的登陆时间以及气候影响，使用的计算机的类型是 {{ select(14) }}

• 微型计算机
• 小型计算机
• 大型计算机
• 超大型计算机

15. 一棵二叉树不具有的性质是 {{ select(15) }}

• 可能有结点没有孩子
• 一定没有环
• 每个结点最多两个孩子
• 每个节点都有父亲结点

二、程序阅读理解题（共3大题。程序输入不超过数组或字符串定义的范围，除特殊说明外，判断题1.5分，选择题3分，共计40分）

阅读程序第一题（12分）

01 #include<bits/stdc++.h>
02 
03 using namespace std;
04 struct p{
05     int l;
06     int r;
07 }a[1000000];
08 bool cmp(p xx,p yy){
09     return xx.l>yy.l;
10 }
11 int main(){
12     int n,h;
13     int c=0;
14     scanf("%d%d",&n,&h);
15     for(int i=1;i<=n;i++)
16     {
17         scanf("%d",&a[c++].l);
18         a[c].r=1;
19         scanf("%d",&a[c++].l);
20     }
21     sort(a,a+c,cmp);
22     int sum=0;
23     for(int i=0;i<c;i++)
24     {
25         if(a[i].r==1)
26         {
27             sum++;
28             h-=a[i].l;
29             if(h<=0)
30             {
31                 printf("%d",sum);
32                 return 0;
33             }
34         }
35         else if(a[i].r!=1)
36         {
37             if(h%a[i].l==0) sum+=h/a[i].l;
38             else sum+=h/a[i].l+1;
39             printf("%d",sum);
40             return 0;
41            
42         }
43     }
44 }

判断题

16. 若程序输入 n=600000，程序可能会发生运行时错误。（ ）

    {{ select(16) }}

• 正确
• 错误

17. 第23行的for循环总是只会运行一次就会因为return 0结束循环（ ） {{ select(17) }}

• 正确
• 错误

18. 如果输入的a[i].l>0变量sum必然会输出一次（ ） {{ select(18) }}

• 正确
• 错误

单选题

19. 若输入1 10 3 5 ，则输出是什么？（ ）

    {{ select(19) }}

• 1
• 3
• 2
• 4

20. 若输入2 10 3 5 2 6，则输出是什么？（ ）

    {{ select(20) }}

• 1
• 2
• 3
• 4

阅读程序第二题

01 #include<bits/stdc++.h>
02 using namespace std;
03 int n,cnt,a[233],f[1000010],p;
04 int main()
05 {
06 	   cin>>n;
07 	   a[++cnt]=1;
08	   p=1;
09	   for(int i=1;i<=8;i++)
10     {
11         p*=6;
12         a[++cnt]=p;
13     }
14     p=1;
15     for(int i=1;i<=6;i++)
16     {
17         p*=9;
18         a[++cnt]=p;
19     }
20     sort(a+1,a+cnt+1);
21     memset(f,0x3f,sizeof(f)); 
22     f[0]=0;
23     for(int i=1;i<=cnt;i++)
24         for(int j=a[i];j<=n;j++)
25             f[j]=min(f[j],f[j-a[i]]+1);
26     cout<<f[n];
27     return 0;
28 }

判断题

21. 该程序是用类似于01背包的思想设计算法（ ） {{ select(21) }}

• 正确
• 错误

22.第20行排序去掉并不会影响答案（ ） {{ select(22) }}

• 正确
• 错误

23. 第21行初始化去掉并不会影响答案（ ） {{ select(23) }}

• 正确
• 错误

24. 第22行更改为f[0]=-1;第26行更改为cout<<f[n]+1;结果不变 （ ）

    {{ select(24) }}

• 正确
• 错误

单选题

25. 若输入为3，则输出的结果为（ ）

    {{ select(25) }}

• 1
• 2
• 3
• 4

26. 若输入127，则输出是（ ）？

    {{ select(26) }}

• 1
• 2
• 3
• 4

阅读程序第三题

01 #include<bits/stdc++.h>
02 using namespace std;
03 const int N = 2e5 + 10, mod = 1e9 + 7;
04 int n, m, d[N], s[N];
05 vector<int> g[N];
06 void bfs() {
07     memset(d, 0x3f, sizeof(d));
08	   d[1] = 0; s[1] = 1;
09	   queue<int> q;
10	   q.push(1);
11	   while(!q.empty()) {
12         int u = q.front(); q.pop();
13         for(auto it : g[u]) {
14		       if(d[it] >= d[u] + 1) {
15                 if(d[it] > 1e8)  q.push(it);
16                 d[it] = d[u] + 1;
17                 s[it] = (s[it] + s[u]) % mod;
18             }
19         }
20     }
21 }
22 int main() {
23     cin >> n >> m;
24     for(int i = 1, u, v; i <= m; i++) {
25         cin >> u >> v;
26         g[u].push_back(v);
27         g[v].push_back(u);
28     }
29     bfs();
30     cout << s[n];
31     return 0;
32 }

判断题

27. 数组s,s[i]代表第i个点是否访问过（ ） {{ select(27) }}

• 正确
• 错误

28. 数组d,d[i]代表第i个点距离起点的最短距离多少（ ）

{{ select(28) }}

• 正确
• 错误

单选题

29. 如果输入如下，那么输出：（ ）

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

{{ select(29) }}

• 2
• 6
• 4
• 8

30. 如果输入如下，那么输出：（ ）

4 3
1 3
2 3
2 4

{{ select(30) }}

• 2
• 1
• 4
• 3

31. 如果输入如下，那么输出：（ ）

7 8
1 3
1 4
2 3
2 4
2 5
2 6
5 7
6 7

{{ select(31) }}

• 2
• 1
• 3
• 4

32. 如果第17行改成s[it] +=s[u]% mod;会发生哪些情况（ ）。（4分）

    {{ select(32) }}

• 程序无影响
• 答案错误
• 超时
• 运行时错误

三、程序完善题（共2大题，每个选择题3分，共计30分）

1.题目描述：有 n 个游乐设施，每次玩时满意度加上此设施的乐趣值，同时设施的乐趣值减一，直到变成 0。

一个设施可以玩多次，求一共玩 k 次后满意度的最大值。例如：

输入：

3 5
100 50 102

输出：

502

01 #include <bits/stdc++.h>
02 using namespace std;
03 long long a[100001], b[100001], n, k;
04 bool cmp(int x, int y)
05 {
06    ③
07
08 }
09 bool check(long long mid)
10 {
11     long long sum = 0;
12     for (int i = 1; i <= n; i++)
13     {
14         if (a[i] - mid > 0)
15         {
16             sum += (a[i] - mid);
17         }else break;
18     }
19     if (sum > k) return 1;
20     return 0;
21 }
22 int main()
23 {
24     ios::sync_with_stdio(0);
25     cin.tie(0); cout.tie(0);
26     cin >> n >> k;
27     for (int i = 1; i <= n; i++) cin >> a[i];
28     ①
29     long long l = 0, r = 2 * 1e9 + 1, mid;
30     while (l < r)
31     {
32        ②
33        mid = l + r >> 1;
34        if (check(mid)) l = mid + 1;
35        else r = mid;
36     }
37     long long ans = 0;
38     for (int i = 1; i <= n; i++)
39     {
40         if (a[i] <= l) continue;
41         k -= (a[i] - l);
42         if ((a[i] - l) * (a[i] + l + 1) / 2 > 0)
43
44         ans += ④；
45      }
46      cout << ⑤  ;
47
48 }

33. ①处应填（ ）

{{ select(33) }}

• sort(a + 1, a + n + 1, cmp);
• sort(a, a + n + 1, cmp);
• sort(a + 1, a + n, cmp);
• sort(a , a + n , cmp);

34. ②处应填（ ）

{{ select(34) }}

• mid =(l + r+1) / 1;
• mid = l + r >> 1;
• mid = l + r +1>> 1;
• mid = l + r /2;

35. ③处应填（ ）

{{ select(35) }}

• return x > y;
• return x < y;
• return x+y > y+x;
• return x != y;

36. ④处应填（ ）

{{ select(36) }}

• (a[i] - l) + (a[i] + l + 1) / 2
• (a[i] - l) - (a[i] + l + 1) / 2
• (a[i] - l) / (a[i] + l + 1) / 2
• (a[i] - l) * (a[i] + l + 1) / 2

37. ⑤处应填（ ）

{{ select(37) }}

• ans + l * k
• ans
• ans + l
• ans +k

2. 题目描述:

用十进制标记一次性地在纸上写了 1 ~ N 以下的所有整数。 在这项工作中，写了几个 1 这样的数字呢？即求从 1 ~ N 中数字 1 出现的次数。

01 #include<iostream>
02 #include<cstring>
03 using namespace std;
04 int a[101],t[10][100];
05 int dfs(int k,int sum,int ok)
06 {
07     ①
08         return sum;
09     int end=ok?a[k]:9;
10     int s=0;
11     if(!ok&&t[sum][k]!=0)return t[sum][k];
12     for(int i=0;i<=②;i++)
13     {
14         s+=dfs(k-1,sum+(i==1),③);
15     }
16     ④
17     return s;
18 }
19 int chai(int n)
20 {
21     memset(a,0,sizeof(a));
22     memset(t,0,sizeof(t));
23     int i=0;
24     while(n!=0)
25     {
26         i++;
27         ⑤
28         n/=10;
29     }
30     return dfs(i,0,1);
31 }
32 int main()
33 {
34     int n,m;
35     cin>>n;
36     cout<<chai(n)<<endl;
37     return 0;
38 }

38. ①处应填写（ ）

{{ select(38) }}

• if(k==0)
• if(ok==0)
• if(k==1)
• if(ok==1)

39. ②处应填写（ ）

{{ select(39) }}

• 0
• 9
• a[k]
• end

40. ③处应填写（ ） {{ select(40) }}

• ok
• end
• ok&&i
• ok&&i==end

41. ④处应填写（ ）

{{ select(41) }}

• t[t][sum]=s;
• t[sum][k]=s;
• s+=t[sum][t];
• s+=t[t][sum];

42. ⑤处应填写（ ） {{ select(42) }}

• a[i]=n;
• sum+=n%10;
• a[i]=n%10;
• sum+=n/10;