普及组CSP-J2024初赛模拟卷5

*
您的姓名：
一、单项选择题（共 15 题，每题 2 分，共计 30 分；每题有且仅有一个正确选项）
1.
十进制数 2024 的八进制表示是（）。
A. 3749
B. 3750
C. 3751
D. 3752
2.
以下关于计算机协会竞赛的描述正确的是（）。
A.NOI国家集训队每年产生 4 名选手代表中国参加IOI
B.CSP-J/CSP-S是 2018 年开始举办的
C.USACO晋级白金的选手可以直接参加NOIP
D.ACSL和NOIP都是CCF旗下的程序设计赛事
3.
以下哪个可以用作C++程序中的变量名？（）
A. public
B. loops
C. new
D. delete
4.
以下哪个数据结构不属于线性结构？（）
A.栈
B.数组
C.树
D.链表
5.
以下哪个属于STL函数？（）
A. main
B. sort
C. freopen
D. scanf
6.
小明用递归的方法写了一个斐波那契数列的程序，在这里递归函数经常用到的数据结构是（）。
A.树
B.栈
C.链表
D.队列
7.
堆排序程序运行的时间复杂度是（）。
A. O(logn)
B. O(n)
C. O(n^2)
D. O(nlogn)
8.
在下列排序算法中，（）是稳定的排序算法。
A.归并排序
B.快速排序
C.选择排序
D.拓扑排序
9.
一台 32 位操作系统的计算机运行C++，下面哪个说法是正确的？（）
A. C++语言中的一个int类型的变量占 8 字节
B. C++语言中的一个指针类型的变量占 4 字节
C. C++语言中的一个bool类型的变量占 2 字节
D. C++语言中的一个double类型的变量占 4 字节
10.
设全集I={a,b,c,d,e,f,g,h}，集合B∪A={a,b,c,d,e,f}，C∩A={c,d,e}，~B∩A={a,d}，那么集合C∩B∩A为（）。
A. {c,e}
B. {d,e}
C. {e}
D. {c,d,e}
11.
在不大于 19000 的正整数中，与 19000 互质的正整数有（）个。
A. 7118
B. 7119
C. 7200
D. 7201
12.
假设P=true，Q=false，R=true，S=true，逻辑运算表达式PΛQVRΛS的值是（）。
A. true
B. false
C. null
D. NIL
13.
对于二叉树T，已知其前序遍历序列为 1 2 4 3 5 7 6，中序遍历序列为 4 2 1 5 7 3 6，则其后序遍历序列为（）。
A. 4 2 5 7 6 3 1
B. 4 2 7 5 6 3 1
C.4 2 7 5 3 6 1
D.4 7 2 3 5 6 1
14.
一个口袋内装有大小相同的 7 个白球和 2 个黑球，从口袋中取出 3 个球，使其中不含黑球，有多少种取法？（）
A. 32
B. 35
C. 24
D. 56
15.
在下图中，从顶点（）出发存在一条路径可以遍历图中的每条边一次，而且仅遍历一次。

A. B点
B. A点
C. E点
D. C点
二、阅读程序（程序输入不超过数组或字符串定义的范围；判断题正确填对，错误填错；除特殊说明外，判断题每题 1.5 分，选择题每题 3 分，共计 40 分）
（1）
01 #include<bits/stdc++.h>
02 using namespace std;
03 int a[100005];
04 bool judge(int x)
05 {
06     int i=2;
07     if(x==0 || x==1)
08         return false;
09     while(i <= floor(sqrt(x)) && (x%i != 0))
10         i++;
11     if(i > floor(sqrt(x)))
12         return true;
13     return false;
14 }
15 int inverted(int n)
16 {
17     int sum;
18     sum = 0;
19     while(n > 0)
20     {
21         sum = sum*10 + n%10;
22         n /= 10;
23     }
24     return sum;
25 }
26 int main()
27 {
28     int m,n,k;
29     bool flag;
30     k = 0;
31     flag = false;
32     cin >> m >> n;
33     for(int i=m; i<=n; i++)
34         if(judge(i) && judge(inverted(i)))
35         {
36             k++;
37             a[k] = i;
38             flag = true;
39         }
40     if(flag)
41     {
42         for(int i=1; i<k; i++)
43             cout << a[i] << ",";
44         cout << a[k] << endl;
45     }
46     else
47         cout << "No" << endl;
48     return 0;
49 }
判断题
16.
将第 6 行中的 i=2 改为 i=1，程序的运行结果不会改变。（）
A. 对
B. 错
17.
将第 9 行中的 x％i != 0去掉，程序的运行结果不会改变。（）
A. 对
B. 错
18.
将第 18 行删除，程序的运行结果不会改变。（）
A. 对
B. 错
19.
将第 31 行删除，程序的运行结果不会改变。（）
A. 对
B. 错
选择题
20.
若输入数据为 1949 2024，则输出为（）。
A. 1949,1987
B. 1949,1979
C. 1951,1979
D. 1951,1987
21.
若输出为NO，则输入可能为（）。
A. 168 180
B. 785 792
C. 999 1020
D. 2024 2050
（2）
01 #include<bits/stdc++.h>
02 using namespace std;
03 int main()
04 {
05     string s;
06     int len,pos,i,j,sum;
07     sum = 0;
08     getline(cin,s);
09     len = s.size();
10     s[len] = ' ';
11     for(i=0; i<=len; i++)
12     {
13         if(s[i] != ' ')
14             sum++;
15         else
16         {
17             pos = i;
18             for(j=1; j<=sum; j++)
19                 cout << s[--pos];
20             sum = 0;
21             if(i != len)
22                 cout<<" ";
23         }
24     }
25     cout<<endl;
26     return 0;
27 }
判断题
22.
将第 7 行删除，程序的运行结果不会改变。（）
A. 对
B. 错
23.
将第 9 行中的 s.size() 改为 s.length() ，程序的运行结果不会改变。（）
A. 对
B. 错
24.
将第 10 行 s[len]　= ＇ ＇　改为　s[len] = 32，程序的运行结果不会改变。 （）
A. 对
B. 错
25.
将第 20 行删除，程序的运行结果不会改变。（）
A. 对
B. 错
选择题
26.
若输入 CCF CSP，则输出为（）。
A. FCC PSC
B. CCF CSP
C. PSC FCC
D. PSC FCC
27.
将第 19 行中的 --pos 改为 pos--，输入 CCF CSP，则输出为（）。
A. PS FC
B. CF SP
C. FC PS
D. CC SC
（3）
01 #include<bits/stdc++.h>
02 #define N 1000010
03 using namespace std;
04 int x,tot,a[N];
05 void calculate(int n,int step)
06 {
07     int ans;
08     ans = 1;
09     for(int i=1; i<=step-1; i++)
10         ans *= a[i];
11     if(ans > x)
12         return;
13     if(ans == x)
14     {
15         tot++;
16         return;
17     }
18     for(int i=a[step-1]; i<=x; i++)
19         if(n%i == 0)
20         {
21             n /= i;
22             a[step] = i;
23             calculate(n,step+1);
24             n *= i;
25         }
26 }
27 int main()
28 {
29     int n;
30     cin >> n;
31     while(n--)
32     {
33         tot = 0;
34         cin >> x;
35         a[0] = 2;
36         calculate(x,1);
37         cout << tot << endl;
38     }
39     return 0;
40 }
判断题
28.
若将第 2 行替换为 const int N =1000010；，程序的运行结果不会改变。 （）
A. 对
B. 错
29.
若将第 8 行删除，程序的运行结果不会改变。（）
A. 对
B. 错
30.
若将第 15 行中的 tot++ 替换为 ++tot，程序的运行结果不会改变。（）
A. 对
B. 错
31.
将第 21 行和第 22 行交换，程序的运行结果不会改变。（）
A. 对
B. 错
选择题
32.
本程序中的算法用到了（）的思想。
A.贪心
B.搜索回溯
C.二分
D.动态规划
33.
若输入2 24 36，那么输出结果是（）。
A. 7 9
B. 7 8
C. 8 9
D. 8 8
34.
（4分）若输入2 96 2024，那么输出结果是（）。
A. 18 20
B. 18 21
C. 19 20
D. 19 21

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

（1）

给定两个正整数 l 和 r，求区间 [1，r] 内素数的个数。如下代码是一个经典的计算过程，请将程序补充完整。

输入格式：

    第 1 行有两个整数，分别代表询问次数 n 和给定区间的右端点最大值 m。接下来 n 行，每行两个整数 l 和 r ，代表一次查询。

输出格式：

    对于每次查询输出一行，若 l，r∈[1,m]，则输出区间内素数的个数，否则输出 Crossing the line。

输入样例：

    2 5

    1 3

    1 6

输出样例:

    2

    Crossing the line


01 #include<bits/stdc++.h>
02 using namespace std;
03 const int MAXN = 1e6 + 5;
04 bool is_prime[MAXN];
05 int sum[MAXN];
06 void get_sum(int m)
07 {
08     memset(is_prime,true,sizeof(is_prime));
09     is_prime[0] = false;
10     is_prime[1] = false;
11     for(int i = 2; ①; ++i)
12     {
13         if(is_prime[i])
14         {
15             for(②; j <= m; j += i)
16                 ③;
17         }
18     }
19     for(int i = 1; i <= m; ++i)
20     {
21         if(is_prime[i])
22             ④;
23         else
24             sum[i] = sum[i - 1];
25     }
26 }
27 int main()
28 {
29     int n,m,l,r;
30     cin>>n>>m;
31     get_sum(m);
32     while(n--)
33     {
34         cin>>l>>r;
35         if(l >= 1 && r <= m)
36             cout<<⑤<<endl;
37         else
38             cout<<"Crossing the line"<<endl;
39     }
40     return 0;
41 }

35.
①处应填（）。
A. i ＜= m
B. i * i ＜= m
C. i ＜= n
D. i * i ＜= n
36.
②处应填（）。
A. int j = 1
B. int j = 2
C. int j = i
D. int j= i * i
37.
③处应填（）。
A. is_prime[j] = true
B. is_prime[i] = true
C. is_prime[j] = false
D. is_prime[i] = false
38.
④处应填（）。
A. sum[i]++
B. sum[i] += sum[i – 1]
C. sum[i] = sum[i – 1]
D. sum[i] = sum[i － 1] + 1
39.
⑤处应填（）。
A. sum[r+1] - sum[l]
B. sum[r+1] – sum[l-1]
C. sum[r] – sum[l-1]
D. sum[r] – sum[l]

（2）

N 位同学站成一排，音乐老师要请其中的（N-K）位同学出列，使得剩下的K位同学排成合唱队形。合唱队形是指这样的一种队形：设 K 位同学从左到右依次编号为1,2,·· · ·,K，他们的身高分别为T1 ,T2,· · ·,TK，则他们的身高满足T1<··· · ·<Ti>Ti+1>·· · ·>TK（1≤i≤K）。

你的任务是，已知所有N位同学的身高，计算最少需要几位同学出列，可以使得剩下的同学排成合唱队形。

输入格式：

    输入的第 1 行是一个整数 N，表示同学的总数。第 2 行有 N 个整数，用空格分隔，第 i 个整数 Ti  是第 i 位同学的身高（厘米）。

输出格式：

    输出包括一行，这一行只包含一个整数，就是最少需要几位同学出列。

数据范围：

    2≤N≤100，130≤Ti ≤230。

输入样例：

    8

    186 186 150 200 160 130 197 220

输出样例:

    4


01 #include<bits/stdc++.h>
02 using namespace std;
03 const int MAXN = 2024;
04 int n,ans=0;
05 int h[MAXN],f[MAXN],g[MAXN];
06 int main()
07 {
08     scanf("%d",&n);
09     for(int i = 1; i <= n; i++)
10         scanf("%d",&h[i]);
11     for(int i = 1; i <= n; i++)
12     {
13         ①;
14         for(int j = 1; j < i; j++)
15             if(②)
16                 f[i] = max(f[i],f[j] + 1);
17     }
18     for(int i = n; i; i--)
19     {
20         g[i] = 1;
21         for(int j = n; ③; j--)
22             if(h[j] < h[i])
23                 ④;
24     }
25     for(int i = 1; i <= n; i++)
26         ⑤;
27     printf("%d\n",n - ans);
28     return 0;
29 }

40.
①处应填（）。
A. f[i] = 1
B. f[i] = 0
C. g[i] = 1
D.g[i] = 0
41.
②处应填（）。
A. h[j] ＜= h[i]
B. h[j] ＜ h[i]
C. h[j] >= h[i]
D. h[j] > h[i]
42.
③处应填（）。
A. j >= i
B. j >= 0
C. j > i
D. j > 0
43.
④处应填（）。
A. g[i]=max(f[i], f[j]+1)
B. g[i]=max(f[i], g[j]+1)
C.g[i]=max(g[i], f[j]+1)
D. g[i]=max(g[i], g[j]+1)
44.
⑤处应填（）。
A. ans=max(ans, f[i]+g[i]-1)
B. ans=max(f[i], g[i]-1)
C. ans=max(ans, f[i]+g[i])
D. ans=max(g[i], f[i]-1)
问卷星提供技术支持
举报