本文主要是介绍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++ 中小学初级组 第一轮真题-阅读程序题解析的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
