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

本文主要是介绍2022年CSP-J认证 CCF信息学奥赛C++ 中小学初级组 第一轮真题-阅读程序题解析,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

2022 CCF认证第一轮(CSP-J)真题

二、阅读程序题

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

第一题 位运算

1 #include <iostream>
2 
3 using namespace std;
4	
5 int main()
6 {
7	unsigned short x, y;
8	cin >> x >> y;
9	x=(x|x<< 2) & 0x33;
10	x= (x|x << 1) & 0x55;
11	y = (y|y << 2) & 0x33;
12	y =(y|y << 1)& 0x55;
13	unsigned short z=x|y << 1;
14	cout << z << endl;
15	return 0;
16 }

程序分析

主要考查小朋友们读写程序能力和逻辑思维能力,此程序实现了一个位运算的操作,输入两个无符号短整数x和y,经过一系列的位运算操作后,得到一个新的无符号短整数z,并将其输出。

  • 具体来说,程序中使用了以下位运算符和操作:
  • 位移运算符:<< 用于将一个数的二进制位向左移动指定的位数。
  • 位或运算符:| 用于对两个数的二进制位进行位或操作。
  • 位与运算符:& 用于对两个数的二进制位进行位与操作。
  • 程序的执行步骤如下: 从标准输入中读取两个无符号短整数x和y。
  • 对变量x进行位运算,将x左移2位并与0x33(也就是二进制00110011)进行位与操作,再将结果与x左移1位进行位或操作并与0x55(也就是二进制01010101)进行位与操作,得到的结果存入变量x中。
  • 对变量y进行位运算,将y左移2位并与0x33进行位与操作,再将结果与y左移1位进行位或操作并与0x55进行位与操作,得到的结果存入变量y中。
  • 将x与y左移1位进行位或操作,并将结果存入变量z中。 将变量z输出到标准输出。

假设输入的 x、y 均是不超过 15 的自然数,完成下面的判断题和单选题

判断题

1、删去第 7 行与第 13 行的 unsigned,程序行为不变

2、将第 7 行与第 13 行的 short 均改为 char,程序行为不变

3、程序总是输出一个整数“0”

4、当输入为“2 2”时,输出为“10“

5、当输入为“2 2”时,输出为“59

答案:1√ 2 × 3 × 4 × 5 ×

答案分析:

1、因为题目要求输入的数值为不超过15的自然数,所以删除无符号标记不影响

2、如果调整为char类型,最后输出z的时候会输出字符而不是整数

3、根据程序的分析可以得出输出结果会根据输入数字而发生变化

4、5、当输入为2 2的时候,二进制都是0010,运算后z的值为1100,对应输出的结果应该是12

单选题

6)、当输入为“13 8”时,输出为

A、"0"

B、"209"

C、"197"

D、"226"

答案:B

答案分析:根据程序分析,13对应二进制为:1101,8对应二进制为:1000,运行后z得到的值为11010001,转换成十进制为209,答案B

第二题 最小代价

1 #include <algorithm>
2 #include <iostream>
3 #include <limits>
4
5 using namespace std;
6
7 const int MAXN = 105;
8 const int MAXK = 105;
9
10 int h[MAXN][MAXK];
11
12 int f(int n, int m)
13 {
14	if(m == 1)return n;
15	if (n == 0) return 0;
16	
17	int ret = numeric_limits<int>::max();
18	for (int i= 1;i <= n; i++)
19		ret = min(ret, max(f(n-i,m),f(i-1,m-1))+ 1);
20	return ret;
21 }
22
23 int g(int n, int m)
24 {
25	for (int i= 1;i <= n; i++)
26		h[i][1] = i;
27	for (int j= 1;j<= m; j++)
28		h[0][j] = 0;
29
30	for (int i= 1;i<= n; i++){
31		for (int j= 2;j<= m; j++){
32			h[i][j]= numeric_limits<int>::max();
33			for (int k = 1; k <= i; k++)
34				h[i][j] = min(
35              h[i][j],
36              max(h[i-k][j], h[k-1][j-1])+ 1);
37		}
38	}
39	
40	return h[n][m];
41 }
42
43 int main()
44 {
45	int n, m;
46	cin >> n >> m;
47	cout << f(n, m) << endl << g(n, m) << endl;
48	return 0;
49 }

程序分析

主要考查小朋友们读写程序能力和逻辑思维能力,此程序是用来计算将n个元素分成m组的最小代价的问题。

  • 函数f是递归解法,用来计算将n个元素分成m组的最小代价
  • 当m=1时,表示将n个元素分成1组,直接返回n。当n=0时,表示没有元素可以分组,返回0
  • 否则,遍历分割点i,将左边的i个元素分成m-1组,右边的n-i个元素分成1组,取两种情况下的最大代价,然后加上当前的分割点的代价1,最后取所有情况的最小值
  •  函数g是动态规划解法,用来计算将n个元素分成m组的最小代价
  • 先初始化h数组,将h[i][1]设为i,表示将i个元素分成1组的最小代价。
  • 将h[0][j]设为0,表示将0个元素分成j组的最小代价。然后,利用递推关系式,遍历i和j,计算h[i][j],最后返回h[n][m]
  • 主函数中,从输入中读取n和m,然后分别调用f函数和g函数,将结果输出
  • 这个问题的解法是使用动态规划。通过将问题划分为子问题,然后进行递推计算,最终得到最优解。递归解法是通过递归调用来解决子问题,但是可能存在重复计算的问题,所以使用了动态规划的解法来避免重复计算。

假设输入的 n、m 均是不超过 100 的正整数,完成下面的判断题和单选题

判断题

1)、当输入为“7 3”时,第 19 行用来取最小值的 min 函数执行了 449 次

2)、输出的两行整数总是相同的

3)、当 m为1时,输出的第一行总为 n

答案:1× 2 √  3 √ 

答案分析:

1、本题执行起来由于是递归,要具体算确实会比较麻烦,小朋友们可以进行递归模拟,找出相应的规律,最多得到的规律是,当m=3的时候,执行min函数的次数为:(2^(n-1)) * n程序运行后的结果为:2^(7-1) * 7 = 2^6 * 7 = 64 * 7 = 448 

2、根据程序分析,可以看出输出的结果是一样的

3、这问再程序14行就有答案

单选题

4)、 算法 g(n,m)最为准确的时间复杂度分析结果为

A、O(n^3/2m)

B、O(nm)

C、O(n^2m)

D、O(nm^2)

答案:C

答案分析:从程序中就可以看出g函数里面有三层嵌套循环,次数分别为:n,m,n,答案C

5)、当输入为“20 2”时,输出的第一行为

A、"4"

B、"5"

C、"6"

D、"20"

答案:C

答案分析:从程序分析中可以得到,当m等于2的时候,输出的值变化为:1、2、2、3、3、3、4、4、4、4....,到n=20的时候,输出的值为6,答案C

6)、当输入为“100 100”时,输出的第一行为

A、"6"

B、"7"

C、"8"

D、"9"

答案:B

答案分析:本题还是稍微有点费手和费脑,有没有大佬可以评论区分享一下

第三题 平方根求解

1 #include <iostream>
2
3 using namespace std;
4
5 int n, k;
6
7 int solve1()
8 {
9	int l= 0,r= n;
10	while (l <= r) {
11		int mid =(l+ r)/ 2;
12		if(mid * mid <= n)l= mid + 1;
13		else r = mid - 1;
14	}
15	return l-1;
16 }
17
18 double solve2(double x)
19 {
20	if(x == 0) return x;
21	for (int i = 0;i < k; i++)
22		x = (x+n/x) / 2;
23	return x;
24 }
25
26 int main()
27 {
28	cin >> n >> k;
29	double ans = solve2(solve1());
30	cout << ans <<' '<<(ans * ans == n)<< endl;
31	return 0;
32 }

程序分析

主要考查小朋友们读写程序能力和逻辑思维能力,该程序使用了二分法和牛顿法来求解平方根。

  • 首先,我们来解析solve1()函数。该函数使用二分法来寻找平方根的整数部分
  • 在二分过程中,设定左边界l为0,右边界r为n
  • 然后每次取中间值mid,如果mid的平方小于等于n,则将左边界l更新为mid+1,否则将右边界r更新为mid-1。最终返回l-1
  • solve2()函数。该函数使用牛顿法来近似求解平方根
  • 牛顿法的迭代公式为x = (x + n/x) / 2,其中x为初始值,n为待求平方根的数值
  • 在迭代过程中,对x进行k次迭代。最终返回迭代后的x
  • 在主函数中,程序先读取输入的n和k值
  • 然后调用solve1()函数获取平方根的整数部分,再将该整数部分作为初始值调用solve2()函数进行近似求解
  • 最后输出迭代后的x值和判断该x值的平方是否等于n

假设 int 为 32 位有符号整数类型,输入的 n 是不超过 47000 的自然数、k 是不超过 int表示范围的自然数,完成下面的判断题和单选题

判断题

1) 该算法最准确的时间复杂度分析结果为0(log n+k)

2) 当输入为“9801 1”时,输出的第一个数为“99”

3) 对于任意输入的 n,随着所输入 k的增大,输出的第二个数会变成“1”

4) 该程序有存在缺陷。当输入的n过大时,第 12 行的乘法有可能溢出,因此应当将mid 强制转换为 64 位整数再计算

答案:1√ 2 √ 3  × 4  ×

答案分析:

1、从程序分析可以得出该程序的时间复杂度为二分法的logn加上牛顿法的k,正确

2、从程序分析可以看出,是求平方根,而9801是99的平方,正确

3、从程序分析可以看出,本题是求平方根,求平方根除了完全平方数不然都会有小数,错误

4、从程序分析可以看出,二分法的中间值最大为47000/2 = 23500,平方之后也没有超过int的取值范围,所以并不会溢出,错误

单选题

5) 当输入为“2 1”时,输出的第一个数最接近

A、1

B、1.414

C、1.5

D、2

答案:C

答案分析:从程序分析可以看出,2没有整数平方根,此时x=1,带入牛顿法得到x=(x+n/x)/2=(1+2/1)/2=1.5,答案C

6) 当输入为“3 10”时,输出的第一个数最接近

A、1.7

B、1.732

C、1.75

D、2

答案:B

答案分析:可以参考第五题进行求解最后答案B

7) 当输入为“256 11”时,输出的第一个数

A、等于 16

B、接近但小于 16

C、接近但大于 16

D、前三种情况都有可能

答案:A

答案分析:从程序分析可以看出,256是16的完全平方数,所以不管后面的k是多少都会输出16,答案A

这篇关于2022年CSP-J认证 CCF信息学奥赛C++ 中小学初级组 第一轮真题-阅读程序题解析的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/762247

相关文章

springboot security使用jwt认证方式

《springbootsecurity使用jwt认证方式》:本文主要介绍springbootsecurity使用jwt认证方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地... 目录前言代码示例依赖定义mapper定义用户信息的实体beansecurity相关的类提供登录接口测试提供一

Java的IO模型、Netty原理解析

《Java的IO模型、Netty原理解析》Java的I/O是以流的方式进行数据输入输出的,Java的类库涉及很多领域的IO内容:标准的输入输出,文件的操作、网络上的数据传输流、字符串流、对象流等,这篇... 目录1.什么是IO2.同步与异步、阻塞与非阻塞3.三种IO模型BIO(blocking I/O)NI

Python 中的异步与同步深度解析(实践记录)

《Python中的异步与同步深度解析(实践记录)》在Python编程世界里,异步和同步的概念是理解程序执行流程和性能优化的关键,这篇文章将带你深入了解它们的差异,以及阻塞和非阻塞的特性,同时通过实际... 目录python中的异步与同步:深度解析与实践异步与同步的定义异步同步阻塞与非阻塞的概念阻塞非阻塞同步

C++ 中的 if-constexpr语法和作用

《C++中的if-constexpr语法和作用》if-constexpr语法是C++17引入的新语法特性,也被称为常量if表达式或静态if(staticif),:本文主要介绍C++中的if-c... 目录1 if-constexpr 语法1.1 基本语法1.2 扩展说明1.2.1 条件表达式1.2.2 fa

C++中::SHCreateDirectoryEx函数使用方法

《C++中::SHCreateDirectoryEx函数使用方法》::SHCreateDirectoryEx用于创建多级目录,类似于mkdir-p命令,本文主要介绍了C++中::SHCreateDir... 目录1. 函数原型与依赖项2. 基本使用示例示例 1:创建单层目录示例 2:创建多级目录3. 关键注

C++从序列容器中删除元素的四种方法

《C++从序列容器中删除元素的四种方法》删除元素的方法在序列容器和关联容器之间是非常不同的,在序列容器中,vector和string是最常用的,但这里也会介绍deque和list以供全面了解,尽管在一... 目录一、简介二、移除给定位置的元素三、移除与某个值相等的元素3.1、序列容器vector、deque

C++常见容器获取头元素的方法大全

《C++常见容器获取头元素的方法大全》在C++编程中,容器是存储和管理数据集合的重要工具,不同的容器提供了不同的接口来访问和操作其中的元素,获取容器的头元素(即第一个元素)是常见的操作之一,本文将详细... 目录一、std::vector二、std::list三、std::deque四、std::forwa

Redis中高并发读写性能的深度解析与优化

《Redis中高并发读写性能的深度解析与优化》Redis作为一款高性能的内存数据库,广泛应用于缓存、消息队列、实时统计等场景,本文将深入探讨Redis的读写并发能力,感兴趣的小伙伴可以了解下... 目录引言一、Redis 并发能力概述1.1 Redis 的读写性能1.2 影响 Redis 并发能力的因素二、

C++字符串提取和分割的多种方法

《C++字符串提取和分割的多种方法》在C++编程中,字符串处理是一个常见的任务,尤其是在需要从字符串中提取特定数据时,本文将详细探讨如何使用C++标准库中的工具来提取和分割字符串,并分析不同方法的适用... 目录1. 字符串提取的基本方法1.1 使用 std::istringstream 和 >> 操作符示

C++原地删除有序数组重复项的N种方法

《C++原地删除有序数组重复项的N种方法》给定一个排序数组,你需要在原地删除重复出现的元素,使得每个元素只出现一次,返回移除后数组的新长度,不要使用额外的数组空间,你必须在原地修改输入数组并在使用O(... 目录一、问题二、问题分析三、算法实现四、问题变体:最多保留两次五、分析和代码实现5.1、问题分析5.