2021 CCF 非专业级别软件能力认证第一轮
(CSP-J1) 入门级 C 语言试题
认证时间：2021年9月19日 14:30 -- 16:30
试卷分析：青城雪 英文：Edviv
一.单项选择题(共15题，每题两分，共计30分)
1.以下不属于面向对象的程序设计语言的是( D ) 【原题】
A.C++ B.Python C.Java D.C
2.以下奖项与计算机领域最相关的是 ( B ) 【原题】
A.奥斯卡奖 B.图灵奖 C.诺贝尔奖 D.普利策奖
3.目前主流的计算机存储数据最终都是转换成 ( A ) 【原题】
A.二进制 B.十进制 C.八进制 D.十六进制
4.以比较作为基本运算，在 N 个数中找出最大值，最坏情况下所需要的最少的比较次数为 ( C ) 【原题】
A.N2 B.N C.N-1 D.N+1
5.对于入栈顺序为 a,b,c,d,e 的序列，下列 ( D ) 不是合法的出栈顺序。
A.a,b,c,d,e B.e,d,c,b,a C.b,a,c,d,e D.c,d,a,e,b【原题】
6.对于有 n 个顶点、m 条边的无向连通图(m > n)，则需要删掉( D )边才能使其成为一棵树。【原题】
A.n-1 B.m-n C.m-n-1 D.m-n+1
7.二进制数 101.11 对应的十进制数是( C ) 【进制转换】
A.6.5 B.5.5 C.5.75 D.5.25
8.如果一棵二叉树只有根结点，那么这棵二叉树高度为 1，请问高度为 5 的完全二叉树有( A )种不同的形态？【数据结构】
A.16 B.15 C.17 D.32
【解析】完全二叉树最后一层最少有1个结点，至多 2h-1 个结点
9.表达式 a*(b+c)*d 的后缀表达式为 ( B ),其中 “*” 和 “+” 是运算符。【栈】
A.**a+bcd B.abc+*d* C.abc+d** D.*a*+bcd
10.6个人，两个人组一队，总共组成三队，不区分队伍的编号。不同的组队情况有( B ) 【排列组合】
A.10 B.15 C.30 D.20
11.在数据压缩编码中的哈夫曼编码方法，在本质上是一种 ( B ) 的策略。
A.枚举 B.贪心 C.递归 D.动态规划 【贪心】
12.由1,1,2,2,3 这 5 个数字组成不同的三位数有 ( A ) 种。【枚举法】
A.18 B.15 C.12 D.24
13.考虑如下递归算法
solve(n)
if n <= 1 return 1
else if n >= 5 return n*solve(n-2)
else return n*solve(n-1)
则调用solve(7) 得到的返回结果为 ( C ) 【递归】
A.105 B.840 C.210 D.420
14.以 a 为起点，对右边的无向图进行深度优先遍历，则 b,c,d,e 四个点中可能作为最后一个遍历到的点的个数为( B ) 【搜索】
A.1 B.2 C.3 D.4
15.有四个人要从 A 点坐一条船过河到 B 点，船一开始在 A 点。该船一次最多可坐两个人。已知这四个人中每个人独自坐船的过河时间分别为1,2,4,8,且两个人坐船的过河时间为两个人独自过河时间的较大者。则最短 ( B ) 时间可以让四个人都过河到 B 点(包括从 B 点把船开回 A 点的时间)。
A.14 B.15 C.16 D.17
【解析】贪心策略：(1,2）过河耗时 2 分钟，划船回到 A 点 1分钟，总计 3 分钟；(4,8)过河 8 分钟，划船回到 A 点 2 分钟，总计 10分钟;最后(1,2)过河耗费时间 2 分钟，最后总计花费 15 分钟。
二、程序阅读题
(1)
01 #include
02
03 int n;
04 int a[1000];
05
06 int f(int x) // x 的二进制位 1 的个数
07 {
08 int ret = 0;
09 for( ; x; x &= x - 1) ret++;
10 return ret;
11 }
12
13 int g(int x) //lowbit运算
14 {
15 return x&-x;
16 }
17
18 int main()
19 {
20 scanf("%d",&n);
21 for(int i = 0; i < n; i++) scanf("%d",&a[i]);
22 for(int i = 0; i < n; i++)
23 printf("%d ",f(a[i]) + g(a[i]));
24 printf("\n");
25 return 0;
26 }
判断题
16.输入的 n 等于 1001时，程序不会发生下标越界。 ( F )
17.输入的 a[i] 必须全为正整数，否则程序将陷入死循环。 ( F )
18.当输入为 “5 2 11 9 16 10”时，输出为 “3 4 3 17 5”。 ( F )
3 4 3 17 4
19.当输入“1 511998”时，输出为“18”。 ( T )
20.将源代码中 g 函数的定义 (13 - 16行) 移到 main 函数的后面，程序可以正常编译运行。 ( F )
单选题
21.当输入为 “2 -65536 2147483647”时，输出为 ( B )【排除法】
A.“65532 33” B.“65552 32"
C.“65535 34” D.“65554 33”
【考点】位运算
(2)
01 #include
02 #include
03
04 char base[64];
05 char table[256];
06 char str[256];
07 char ans[256];
08
09 void init()
10 {
11 for(int i = 0; i < 26; i++) base[i] = 'A' + i; //大写字母
12 for(int i = 0; i < 26; i++) base[26+i] = 'a' + i; //小写字母
13 for(int i = 0; i < 10; i++) base[52+i] = '0' + i; //数字
14 base[62] = '+', base[63] = '/';
15
16 for(int i = 0; i < 256; i++) table[i] = 0xff; // -1
17 for(int i = 0; i < 64; i++) table[base[i]] = i;
18 table['='] = 0;
19 }
20
21 void decode(char *str)
22 {
23 char *ret = ans;
24 int i, len = strlen(str); //字符串长度
25 for(i = 0; i < len; i += 4){
26 (*ret++) = table[str[i]] << 2 | table[str[i+1]] >> 4;
27 if(str[i + 2] != '=')
28 (*ret++) = (table[str[i+1]] & 0x0f) << 4 | table[str[i+2]]>>2;
29 if(str[i+3] != '=')
30 (*ret++) = table[str[i+2]] << 6 | table[str[i+3]];
31 }
32 }
33
34 int main()
35 {
36 init();
37 printf("%d\n",(int)table[0]);
38
39 scanf("%s",str);
40 decode(str);
41 printf("%s\n",ans);
42 return 0;
43 }
判断题
22.输出的第二行一定是由小写字母、大写字母、数字和“+”、“/”、“=”构成的字符串。 ( F )
23.可能存在输入不同，但输出的第二行相同的情形。 ( T )
24.输出的第一行为 “-1”。 ( T )
单选题
25.设输入字符串长度为 n，decode 函数的时间复杂度为 ( B )
A.O(sqrt(n)) B.O(n) C.O(nlogn) D.O(n*n)
26.当输入为 “Y3Nx”时，输出的第二行为 ( B )
A.“csp” B.“csq” C.“CSP” D.“Csp”
27.(3.5分) 当输入为 “Y2NmIDIwMjE=”时，输出的第二行为 ( C )
A.“ccf2021” B.“ccf2022” C.“ccf 2021” D.“ccf 2022”
【考点】字符串、数据溢出的处理
(3)
01 #include
02
03 #define n 100000
04 #define N n+1
05
06 int m;
07 int a[N], b[N], c[N], d[N];
08 int f[N], g[N];
09
10 void init()
11 {
12 f[1] = g[1] = 1;
13 for(int i = 2; i <= n; i++){
14 if(!a[i]){
15 b[m++] = i;
16 c[i] = 1; f[i] = 2;
17 d[i] = 1; g[i] = i + 1;
18 }
19 for(int j = 0; j < m && b[j]*i <= n; j++){
20 int k = b[j];
21 a[i*k] = 1;
22 if(i%k == 0){
23 c[i*k] = c[i] + 1;
24 f[i*k] = f[i]/c[i*k]*(c[i*k] + 1);
25 d[i*k] = d[i];
26 g[i*k] = g[i]*k + d[i];
27 break;
28 }
29 else{
30 c[i*k] = 1;
31 f[i*k] = 2*f[i];
32 d[i*k] = g[i];
33 g[i*k] = g[i]*(k+1);
34 }
35 }
36 }
37 }
38
39 int main()
40 {
41 init();
42
43 int x;
44 scanf("%d", &x);
45 printf("%d %d\n",f[x],g[x]);
46 return 0;
47 }
判断题
28.若输入不为 “1”，把第 12 行删去不会影响输出的结果。 (T)
29.(2分)第 24 行的“f[i]/c[i*k]”可能存在无法整除而向下取整的情况。(F)
30.(2分)在执行完init()后,f数组不是单调递增的，但g数组是单调递增的。(F)
单选题
31.init( ) 函数的时间复杂度为 ( A )
A.O(n) B.O(nlogn) C.O(n) D.O(n*n)
32.在执行完 init( ) 后, f[1],f[2],f[3] ...... f[100] 中有 ( C ) 个等于2。
A.23 B.24 C.25 D.26
33.(4分)当输入为 “1000” 时，输出为 ( C )
A.”15 1340” B.”15 2340” C.”16 2340” D.”16 1340”
【解析】质数筛线性筛法改编的代码, f[i] == 2, i 一定是质因数
三、完善程序题
(1) (Josephus 问题) 有 n 个人围成一个圈，依次标号 0 至 n - 1。从 0 号开始，依次 0,1,0,1,...,交替报数,报到 1 的人会离开，直至圈中只剩下一个人。求最后剩下人的编号。试补全模拟程序。
34 ①处应该填 ( D )
A.i < n B. c < n C. i < n - 1 D. c < n - 1
35. ②处应该填 ( C )
A.i%2 == 0 B.i%2 == 1 C.p D.!p
36. ③处应填 ( C )
A.i++ B. i = (i+1)%n C.c++ D.p^=1
37.④处应填 ( D )
A.i++ B.i =(i+1)%n C.c++ D.p^=1
38.⑤处应填 ( B )
A.i++ B.i=(i+1)%n C.c++ D.p^=1
【解析】约瑟夫环问题
(2) (矩阵计数) 平面上有 n 个关键点，求有多少个四条边都和 x 轴或者 y 轴平行的矩形，满足四个顶点都是关键点。给出的关键点可能有重复，但完全重合的矩形只计一次。试补全枚举算法。
39. ①处应该填 ( B )
A.a.x |= b.x ? a.x < b.x : a.id < b.id
B.a.x |= b.x ? a.x < b.x : a.y < b.y
C.equals(a, b) ? a.id < b.id : a.x < b.x
D.equals(a, b) ? a.id < b.id :(a.x |= b.x ? a.x < b.x : a.y < b.y)
40. ②处应该填 ( D )
A.i == 0 || cmp(A[i], A[i - 1])
B.t == 0 || equals(A[i], A[t - 1])
C.i == 0 || !cmp(A[i], A[i - 1])
D.t == 0 || !equals(A[i], A[t - 1])
41. ③处应该填 ( C )
A.b - (b - a)/2 + 1 B.(a + b + 1) >> 1
C.(a + b)>>1 D.a+(b - a + 1)/2
42. ④处应该填 ( B )
A.!cmp(A[mid], p) B.cmp(A[mid], p)
C.cmp(p, A[mid]) D.!cmp(p, A[mid])
43. ⑤处应该填 ( D )
A.A[i].x == A[j].x
B.A[i].id < A[j].id
C.A[i].x == A[j].x && A[i].id < A[j].id
D.A[i].x < A[j].x && A[i].y < A[j].y
【解析】函数化编程、二分、排序的综合
学习建议
“工欲善其事必先利其器”，准备参加信息学竞赛首先要把语言基础打牢，俗话说”基础不牢，地动山摇“。有同学提问了，是学习英语吗？还是学习中文呢？其实都不是，我们这里学的语言基础就是 C 语言或者 C++，二者任选其一。我相信看我这篇文章的同学已经学过了 C/C++ 语言，但是请同学们想想是否在学习的阶段自己动手敲代码，光听老师讲课，敲代码不落实，一段时间没看就忘得一干二净，考级或者接下来的学习也会受到影响，导致学习效果不理想，所以我们学习的时候一定要动手敲代码！敲代码！敲代码！请注意这不是抄代码！不是抄代码！不是抄代码！
不同年龄阶段的同学在接受能力、学习能力等方面都不相同，所以在学习的时候不要气馁。“学习如逆水行舟，不进则退”，学习快的同学学习一年的时间即可学习算法入门基础，学习慢的同学则需要学习两年左右的时间才能学习算法入门基础。这里需要强调一下，学习语言基础的时候不仅仅是单纯的学习C/C++，在学习语言基础的时候数学基础差及时补基础，同时学习的过程中培养同学的逻辑思维能力。第一阶段基础打牢的同学刷题量在 100 题左右，这个时候你的基础掌握已经很好了，这个时候参加 CSP-J 初赛大概能得 50 分左右，在竞争比较弱的省已经晋级复赛了，但是不同的省份晋级线不同，所以同学们不管初赛考好或是考差，都需要保持一颗谦虚好学的心。
信息学奥赛之所含金量高，是因为它很考察学生的学习能力，逻辑思维与学习态度。学习态度不好，不管你学信奥赛还是学习语文数学英语都不会取得很大的成就。天赋固然重要，但是踏实勤奋才是王道。这里作个假设：把学校的文化课学习完了，同学把自己打游戏、刷剧、刷微博和QQ的时间拿出来学习信奥赛，一年之后你会发现自己收获颇多。即使老师没上课的时候，每天抽出 45 分钟学习，一年就比平常人多学了 273 个小时多的时间，那个时候进步都是巨大的，即使第一年 CSP-J 未能晋级成功，但是你要相信认真付出后第二年一定能晋级成功，复赛也会取得一个令自己满意的成绩。基础巩固好过后，我建议学习经典算法例题，初赛的程序完善题目必是经典例题改编，剩下一道题目就是考察同学们的代码能力。复赛前 200 分容易满分，然后一道数据结构上机题目，一道动态规划的上机题目，这两道题目初学者骗分为主。
最后的最后，都希望信奥能够帮助更多的同学进击名校，对未来的生活与学习带来诸多帮助，受益终生。欢迎有想法的同学或家长随时私聊