2022年CSP-J认证 CCF信息学奥赛C++ 中小学初级组 第一轮真题-阅读程序题解析_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