当前位置：首页 > news >正文

2024年CSP-J认证 CCF信息学奥赛C++ 中小学初级组第一轮真题-阅读程序题解析

news 2024/9/25 7:33:48

2024 CCF认证第一轮（CSP-J）真题

二、阅读程序题

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

第一题

01 #include <iostream>
02 using namespace std;
03
04 bool isPrime(int n){
05 	 if (n <= 1){
06		 return false;
07	 }
08	 for (int i=2;i*i<= n; i++){
09		 if (n % i== 0){
10			 return false;
11		 }
12	 }
13	 return true;
14 }
15
16 int countPrimes(int n) {
17	 int count= 0;
18	 for (int i=2; i<= n; i++){
19		 if (isPrime(i)) {
20			 count++;
21		 }
22	 }
23	 return count;
24 }
25
26 int sumPrimes(int n) {
27	 int sum =0;
28	 for (int i= 2; i<= n; i++){
29		 if (isPrime(i)) {
30			 sum += i;
31		 }
32	 }
33	 return sum;
34 }
35
36 int main() {
37	 int x;
38	 cin >> x;
39	 cout << countPrimes(x)<<" "<< sumPrimes(x)<< endl;
40	 return 0;
41 }

程序分析

主要考查小朋友们读写程序能力和逻辑思维能力，此程序实现实现了判断一个数是否为质数，并计算小于等于给定数的所有质数的个数和。

函数isPrime判断一个数是否为质数。首先判断是否小于等于1，如果小于等于1，则不是质数，返回false。然后从2开始循环到该数平方根的整数部分（因为一个数可以分解成两个因数，其中一个必定小于等于它的平方根），判断是否存在能整除该数的因数，如果存在，则不是质数，返回false。如果循环结束后仍未找到能整除该数的因数，则该数是质数，返回true。
函数countPrimes计算小于等于给定数的所有质数的个数。从2开始循环到给定数，调用isPrime函数判断每个数是否为质数，如果是质数，则计数器加1。循环结束后，返回计数器的值。
函数sumPrimes计算小于等于给定数的所有质数的和。从2开始循环到给定数，调用isPrime函数判断每个数是否为质数，如果是质数，则累加到一个变量sum中。循环结束后，返回sum的值。
在主函数main中，程序首先读取一个整数x作为输入。然后调用countPrimes函数和sumPrimes函数计算小于等于x的所有质数的个数和，并将结果输出到标准输出流中，最后返回0表示程序执行结束

判断题

16、当输入为“10”时，程序的第一个输出为“4”，第二个输出为“17”

17、若将 isPrime(i)函数中for循环的条件改为 i<=n/2,输入“20”时，countPrimes(20)的输出将变为“6”

18、sumPrimes 函数计算的是从 2 到 n 之间的所有素数之和

答案：16√ 17 × 18 √

答案分析：

16、从程序分析可以得出输入10，总共质数有：2、3、5、7，4个，和是17，答案正确

17、isPrime(i)for循环改成i<=n/2，依然能够正确校验出n是否是质数，输入20时，输出的结果不变还是8个，答案错误

18、从程序分析得知sumPrimes是求质数和，答案正确

单选题

19、当输入为“50”时，sumPrimes(50)的输出为

A、1060

B、328

C、381

D、275

答案：B

答案分析：从程序分析可以得出，输入50求的是2-50的质数之和，而50以内的质数有15个，分别是：2、3、5、7、11、13、17、19、23、29、31、37、41、43、47，累加为328，所以答案B

20、如果将 for(int i=2;i*i<=n;i++)改为 for(int i=2;i<=n;i++),输入“10”时，程序的输出

A、将不能正确计算 10 以内素数个数及其和

B、仍然输出“4”和“17”

C、输出“3”和 10

D、输出结果不变，但余小宁时间更短

答案：A

答案分析：因冲程序分析可以得出for循环是用来遍历从2开始一直遍历所有的除数，如果加上i等于n，那么将不能判断出对应的素数，因为后面的程序if语句里面是n%i，如果i等于n，那么所有的数都符合条件，所以答案A

第二题

01 #include <iostream>
02 #include <vector>
03 using namespace std;
04
05 int compute(vector<int> &cost) {
06    int n = cost.size();
07    vector<int> dp(n + 1, 0);
08    dp[1]= cost[0];
09    for (int i= 2;i<= n; i++){
10	 	  dp[i] = min(dp[i- 1], dp[i -2]) + cost[i- 1];
11	  } 
12	  return min(dp[n], dp[n -1]);
13 }
14  
15 int main() {
16	 int n;
17	 cin >> n;
18	 vector<int> cost(n);
19	 for (int i=0;i<n; i++){
20		 cin >> cost[i];
21	 }
22	 cout << compute(cost)<<endl;
23	 return 0;
24 }

程序分析

主要考查小朋友们读写程序能力和逻辑思维能力，此程序是一个解决"爬楼梯"问题的动态规划算法。该算法的思路是：每次可以选择爬一层或者爬两层，每次爬楼的消耗是给定的cost数组中对应位置的值。我们要求的是到达楼顶的最小消耗。

程序中的compute函数接收一个cost数组作为参数，计算出到达楼顶的最小消耗。
首先，我们定义一个大小为n+1的dp数组，其中dp[i]表示爬到第i层所需的最小消耗。
然后，我们初始化dp[1]为cost[0]，因为爬到第一层的最小消耗就是cost[0]。
接下来，我们从第二层开始迭代计算dp数组。对于每一层i，我们有两种方式可以到达：从上一层爬一层到达：这种情况下，消耗为dp[i-1] + cost[i-1]，其中dp[i-1]表示到达上一层所需的最小消耗，cost[i-1]表示到达当前层的消耗。
从上两层直接跳过一层到达：这种情况下，消耗为dp[i-2] + cost[i-1]，其中dp[i-2]表示到达上两层所需的最小消耗，cost[i-1]表示到达当前层的消耗。
然后，我们取这两种方式中的较小值作为dp[i]的值。
最后，返回dp[n]和dp[n-1]中的较小值，即到达楼顶的最小消耗。
在main函数中，首先读取输入的楼层数n，然后创建一个大小为n的cost数组，用于存储每一层的消耗。
接下来，使用循环读取输入的cost数组。
最后，调用compute函数计算最小消耗并输出结果。
整个程序的时间复杂度为O(n)，空间复杂度为O(n)。

判断题

21、当输入的 cost 数组为{10，15，20}时，程序的输出为 15

22、如果将 dp[i-1]改为 dp[i-3]，程序可能会产生编译错误

23、程序总是输出 cost 数组中的最小的元素

答案：21√ 22 × 23 ×

答案分析：

21、从程序分析可以得出要爬到楼顶可以选择第一次爬2层，第二次再爬2层，消耗就是15，答案正确

22、编译只是检测语法是否出错，修改后语法并没有错；只是对应数组下标变为负数，这个是运行时才会报错，答案错误

23、从程序分析可以得出程序输出的并不一定是cost数组中的最小元素，而是到达楼顶的最小消耗，答案错误

单选题

24、当输入的 cost 数组为｛1,100,1,1,1,100,1,1,100,1｝时，程序的输出为

A、6

B、7

C、8

D、9

答案：A

答案分析：从程序分析可以得出，求的是最小消耗，所以可以选择的楼层为：1、3、5、7、9、10，而这6个楼层的消耗都是1，所以答案A

25、如果输入的 cost 数组为｛10,15,30,5,5,10,20｝，程序的输出为

A、25

B、30

C、35

D、40

答案：B

答案分析：从程序分析可以得出，求的是最小消耗，所以可以选择的楼层为：2、4、6，对应的消耗为：15+5+10=30，所以答案B

26、若将代码中的 min(dp[i-1],dp[i-2])+cost[i-1]修改为 dp[i-1]+cost[i-2]，输入 cost 数组为 {5,10,15}时，程序的输出为

A、10

B、15

C、20

D、25

答案：A

答案分析：从程序分析可以得出，如果修改之后对应的dp值为：[5,10,20]，而最后返回的值是倒数第一个和倒数第二个中的最小值，所以答案A

第三题

01 #include <iostream>
02 #include <cmath>
03 using namespace std;
04  
05 int customFunction(int a, int b){
06		if (b == 0){
07			return a;
08	  	}
09		return a + customFunction(a,b-1);
10 }
11  
12 int main() {
13 	  int x, y;
14	  cin >>x>>y;
15	  int result = customFunction(x, y);
16	  cout << pow(result, 2) << endl;
17	  return 0;
18 }