CCF非专业级别软件能力认证第一轮
中山市认证点：中山市纪念中学
（CSP-J）入门级C++语言试题
认证时间：年9月19日14:30-16:30
一、单项选择题（共15题，每题2分，共计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.N^2
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条边的无向联通图（mn）,需要删掉（D）条边才能使其成为一棵树。
A.n-1
B.m-n
C.m-n-1
D.m-n+1
7.二进制数.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
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这五个数字组成不同的三位数有（A）种。
A.18
B.15
C.12
D.24
13.考虑如下递归算法
solve(n)
ifn=1return1
elseifn=5returnn*solve(n-2)
elsereturnn*solve(n-1)
则调用solve(7)得到的返回结果为（C）。
A.
B.
C.
D.
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
二、阅读程序（程序输入不超过数组或字符串定义的范围；判断题正确填√，错误填X；除特殊说明外，判断题1.5分，选择题3分，共计40分）
(1)
判断题
16.输入的n等于时，程序不会发生下标越界。（X）
17.输入的a[i]必须全为正整数，否则程序将陷入死循环。（X）
18.当输入””时，输出为””。（X）
19.当输入为”“时，输出为”18”。（√）
20.将源代码中g函数的定义（13-16行）移到main函数的后面，程序可以正常编译运行。（X）
单选题
21.当输入为”2-”时，输出为（B）。
A."”
B.""
C.""
D.""
(2)
判断题
22.输出的第二行一定是由小写字母、大写字母、数字和“+”、“/”、“=”构成的字符串。（X）
23.可能存在输入不同，但输出的第二行相同的情形。（√）
24.输出的第一行为“-1”。（√）
单选题
25.设输入字符串长度为n，decode函数的时间复杂度为（B）。
A.θ(√n)
B.θ(n)
C.θ(nlogn)
D.θ(n^2)
26.当输入为“Y3Nx”时，输出的第二行为（B）。
A.“csp”
B.“csq”
C.“CSP”
D.“Csp”
27.（3.5分）当输入为“Y2NmIDIwMjE=”时，输出的第二行为（C）。
A.“ccf”
B.“ccf”
C.“ccf”
D.“ccf”
(3)
假设输入的x是不超过的自然数，完成下面的判断题和单选题：
判断题
28.若输入不为"1"，把第12行删去不会影响输出的结果。（√）
29.（2分）第24行的"f[i]/c[i*k]"可能存在无法整除而向下取整的情况。（X）
30.（2分）在执行完init()后，f数组不是单调递增的，但g数组是单调递增的。（X）
单选题
31.init函数的时间复杂度为（A）。
A.θ(n)
B.θ(nlogn)
C.θ(n√n)
D.θ(n^2)
32.在执行完init()后，f[1],f[2],f[3]......f[]中有（C）个等于2。
A.23
B.24
C.25
D.26
33.（4分）当输入""时，输出为（C）。
A.""
B.""
C.""
D.""
三、完善程序（单选题，每小题3分，共计30分）
(1)（Josephus问题）有n个人围城一个圈，依次标号0至n-1。从0号开始，依次0,1,0,1,...交替报数，报到1的人会离开，直至圈中只剩下一个人。求最后剩下人的编号。
试补全模拟程序。
34.①处应填（D）
A.in
B.cn
C.in-1
D.cn-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.xb.x:a.idb.id
B.a.x!=b.x?a.xb.x:a.yb.y
C.equals(a,b)?a.idb.id:a.xb.x
D.equals(a,b)?a.idb.id:(a.x!=b.x?a.xb.x:a.yb.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].idA[j].id
C.A[i].x==A[j].xA[i].idA[j].id
D.A[i].xA[j].xA[i].yA[j].y
（CSP-S）提高级C++语言试题
认证时间：年9月19日09:30-11:30