CCF 非专业级别软件能力认证第一轮
(CSP-J1) 入门级 C 语言试题
认证时间：年9月日 : -- :
试卷分析：青城雪 英文：Edviv
一.单项选择题(共题，每题两分，共计分)
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.二进制数 对应的十进制数是( C ) 【进制转换】
A. B. C. D.
8.如果一棵二叉树只有根结点，那么这棵二叉树高度为 1，请问高度为 5 的完全二叉树有( A )种不同的形态？【数据结构】
A. B. C. D.
【解析】完全二叉树最后一层最少有1个结点，至多 2h-1 个结点
9.表达式 a*(b+c)*d 的后缀表达式为 ( B ),其中 “*” 和 “+” 是运算符。【栈】
A.**a+bcd B.abc+*d* C.abc+d** D.*a*+bcd
个人，两个人组一队，总共组成三队，不区分队伍的编号。不同的组队情况有( B ) 【排列组合】
A. B. C. D.
.在数据压缩编码中的哈夫曼编码方法，在本质上是一种 ( B ) 的策略。
A.枚举 B.贪心 C.递归 D.动态规划 【贪心】
.由1,1,2,2,3 这 5 个数字组成不同的三位数有 ( A ) 种。【枚举法】
A. B. C. D.
.考虑如下递归算法
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. B. C. D.
.以 a 为起点，对右边的无向图进行深度优先遍历，则 b,c,d,e 四个点中可能作为最后一个遍历到的点的个数为( B ) 【搜索】
A.1 B.2 C.3 D.4
.有四个人要从 A 点坐一条船过河到 B 点，船一开始在 A 点。该船一次最多可坐两个人。已知这四个人中每个人独自坐船的过河时间分别为1,2,4,8,且两个人坐船的过河时间为两个人独自过河时间的较大者。则最短 ( B ) 时间可以让四个人都过河到 B 点(包括从 B 点把船开回 A 点的时间)。
A. B. C. D.
【解析】贪心策略：(1,2）过河耗时 2 分钟，划船回到 A 点 1分钟，总计 3 分钟；(4,8)过河 8 分钟，划船回到 A 点 2 分钟，总计 分钟;最后(1,2)过河耗费时间 2 分钟，最后总计花费 分钟。
二、程序阅读题
(1)
#include
int n;
int a[];
int f(int x) // x 的二进制位 1 的个数
{
int ret = 0;
for( ; x; x &= x - 1) ret++;
return ret;
}
int g(int x) //lowbit运算
{
return x&-x;
}
int main()
{
scanf("%d",&n);
for(int i = 0; i < n; i++) scanf("%d",&a[i]);
for(int i = 0; i < n; i++)
printf("%d ",f(a[i]) + g(a[i]));
printf("\n");
return 0;
}
判断题
.输入的 n 等于 时，程序不会发生下标越界。 ( F )
.输入的 a[i] 必须全为正整数，否则程序将陷入死循环。 ( F )
.当输入为 “ ”时，输出为 “ 5”。 ( F )
4
.当输入“”时，输出为“”。 ( T )
.将源代码中 g 函数的定义 ( - 行) 移到 main 函数的后面，程序可以正常编译运行。 ( F )
单选题
.当输入为 “2 -”时，输出为 ( B )【排除法】
A.“” B.“"
C.“” D.“”
【考点】位运算
(2)
#include
#include
char base[];
char table[];
char str[];
char ans[];
void init()
{
for(int i = 0; i < ; i++) base[i] = 'A' + i; //大写字母
for(int i = 0; i < ; i++) base[+i] = 'a' + i; //小写字母
for(int i = 0; i < ; i++) base[+i] = '0' + i; //数字
base[] = '+', base[] = '/';
for(int i = 0; i < ; i++) table[i] = 0xff; // -1
for(int i = 0; i < ; i++) table[base[i]] = i;
table['='] = 0;
}
void decode(char *str)
{
char *ret = ans;
int i, len = strlen(str); //字符串长度
for(i = 0; i < len; i += 4){
(*ret++) = table[str[i]] << 2 | table[str[i+1]] >> 4;
if(str[i + 2] != '=')
(*ret++) = (table[str[i+1]] & 0x0f) << 4 | table[str[i+2]]>>2;
if(str[i+3] != '=')
(*ret++) = table[str[i+2]] << 6 | table[str[i+3]];
}
}
int main()
{
init();
printf("%d\n",(int)table[0]);
scanf("%s",str);
decode(str);
printf("%s\n",ans);
return 0;
}
判断题
.输出的第二行一定是由小写字母、大写字母、数字和“+”、“/”、“=”构成的字符串。 ( F )
.可能存在输入不同，但输出的第二行相同的情形。 ( T )
.输出的第一行为 “-1”。 ( T )
单选题
.设输入字符串长度为 n，decode 函数的时间复杂度为 ( B )
A.O(sqrt(n)) B.O(n) C.O(nlogn) D.O(n*n)
.当输入为 “Y3Nx”时，输出的第二行为 ( B )
A.“csp” B.“csq” C.“CSP” D.“Csp”
.(分) 当输入为 “Y2NmIDIwMjE=”时，输出的第二行为 ( C )
A.“ccf2021” B.“ccf2022” C.“ccf ” D.“ccf ”
【考点】字符串、数据溢出的处理
(3)
#include
#define n
#define N n+1
int m;
int a[N], b[N], c[N], d[N];
int f[N], g[N];
void init()
{
f[1] = g[1] = 1;
for(int i = 2; i <= n; i++){
if(!a[i]){
b[m++] = i;
c[i] = 1; f[i] = 2;
d[i] = 1; g[i] = i + 1;
}
for(int j = 0; j < m && b[j]*i <= n; j++){
int k = b[j];
a[i*k] = 1;
if(i%k == 0){
c[i*k] = c[i] + 1;
f[i*k] = f[i]/c[i*k]*(c[i*k] + 1);
d[i*k] = d[i];
g[i*k] = g[i]*k + d[i];
break;
}
else{
c[i*k] = 1;
f[i*k] = 2*f[i];
d[i*k] = g[i];
g[i*k] = g[i]*(k+1);
}
}
}
}
int main()
{
init();
int x;
scanf("%d", &x);
printf("%d %d\n",f[x],g[x]);
return 0;
}
判断题
.若输入不为 “1”，把第 行删去不会影响输出的结果。 (T)
.(2分)第 行的“f[i]/c[i*k]”可能存在无法整除而向下取整的情况。(F)
.(2分)在执行完init()后,f数组不是单调递增的，但g数组是单调递增的。(F)
单选题
.init( ) 函数的时间复杂度为 ( A )
A.O(n) B.O(nlogn) C.O(n) D.O(n*n)
.在执行完 init( ) 后, f[1],f[2],f[3] ...... f[] 中有 ( C ) 个等于2。
A. B. C. D.
.(4分)当输入为 “” 时，输出为 ( C )
A.”” B.”” C.”” D.””
【解析】质数筛线性筛法改编的代码, f[i] == 2, i 一定是质因数
三、完善程序题
(1) (Josephus 问题) 有 n 个人围成一个圈，依次标号 0 至 n - 1。从 0 号开始，依次 0,1,0,1,...,交替报数,报到 1 的人会离开，直至圈中只剩下一个人。求最后剩下人的编号。试补全模拟程序。
①处应该填 ( D )
A.i < n B. c < n C. i < n - 1 D. c < n - 1
. ②处应该填 ( C )
A.i%2 == 0 B.i%2 == 1 C.p D.!p
. ③处应填 ( C )
A.i++ B. i = (i+1)%n C.c++ D.p^=1
.④处应填 ( D )
A.i++ B.i =(i+1)%n C.c++ D.p^=1
.⑤处应填 ( B )
A.i++ B.i=(i+1)%n C.c++ D.p^=1
【解析】约瑟夫环问题
(2) (矩阵计数) 平面上有 n 个关键点，求有多少个四条边都和 x 轴或者 y 轴平行的矩形，满足四个顶点都是关键点。给出的关键点可能有重复，但完全重合的矩形只计一次。试补全枚举算法。
. ①处应该填 ( 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)
. ②处应该填 ( 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])
. ③处应该填 ( C )
A.b - (b - a)/2 + 1 B.(a + b + 1) >> 1
C.(a + b)>>1 D.a+(b - a + 1)/2
. ④处应该填 ( B )
A.!cmp(A[mid], p) B.cmp(A[mid], p)
C.cmp(p, A[mid]) D.!cmp(p, A[mid])
. ⑤处应该填 ( 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++，在学习语言基础的时候数学基础差及时补基础，同时学习的过程中培养同学的逻辑思维能力。第一阶段基础打牢的同学刷题量在 题左右，这个时候你的基础掌握已经很好了，这个时候参加 CSP-J 初赛大概能得 分左右，在竞争比较弱的省已经晋级复赛了，但是不同的省份晋级线不同，所以同学们不管初赛考好或是考差，都需要保持一颗谦虚好学的心。
信息学奥赛之所含金量高，是因为它很考察学生的学习能力，逻辑思维与学习态度。学习态度不好，不管你学信奥赛还是学习语文数学英语都不会取得很大的成就。天赋固然重要，但是踏实勤奋才是王道。这里作个假设：把学校的文化课学习完了，同学把自己打游戏、刷剧、刷微博和QQ的时间拿出来学习信奥赛，一年之后你会发现自己收获颇多。即使老师没上课的时候，每天抽出 分钟学习，一年就比平常人多学了 个小时多的时间，那个时候进步都是巨大的，即使第一年 CSP-J 未能晋级成功，但是你要相信认真付出后第二年一定能晋级成功，复赛也会取得一个令自己满意的成绩。基础巩固好过后，我建议学习经典算法例题，初赛的程序完善题目必是经典例题改编，剩下一道题目就是考察同学们的代码能力。复赛前 分容易满分，然后一道数据结构上机题目，一道动态规划的上机题目，这两道题目初学者骗分为主。
最后的最后，都希望信奥能够帮助更多的同学进击名校，对未来的生活与学习带来诸多帮助，受益终生。欢迎有想法的同学或家长随时私聊