2021
CCF
非专业级别软件能力认证第一轮
（
CSP-J1
）入门级
C++
语言试题
认证时间：
2021
年
9
月
19
日
14:30~16:30
考生注意事项
：
试题纸共有
12
页，答题纸共有
1
页，满分
100
分。请在答题纸上作答，写在试题纸上的一律无效。
不得使用任何电子设备（如计算器、手机、电子词典等）
或查阅任何书籍资料。
一、单项选择题（共
15
题，每题
2
分，共计
30
分；每题有且仅有一个正确选项
）
以下不属于面向对象程序设计语言的是
（
）
。
C++
Python
Java
C
以下奖项与计算机领域最相关的是
（
）
。
奥斯卡奖
图灵奖
诺贝尔奖
普利策奖
目前主流的计算机储存数据最终都是转换成
（
）数据进行储存
。
二进制
十进制
八进制
十六进制
以比较作为基本运算，在
N
个数中找出最大数，最坏情况下所需要的最少的比较次数为
（
）
。
N
2
N
N-
1
N+1
对于入栈顺序为
a, b, c, d, e
的序列，下列
（
）不是合法的出栈序列
。
a, b, c, d,
e
e, d, c, b,
a
b, a, c, d,
e
c, d, a, e,
b
对于有
n
个顶点、
m
条边的无向连通图
(m>n)
，需要删掉（
）条边才能使其成为一棵
树。
n-
1
m-
n
m-n-
1
m-
n+1
二进制数
101.11
对应的十进制数是
（
）
。
A.
6.5
B.
5.5
C.
5.75
D.
5.25
如果一棵二叉树只有根结点，那么这棵二叉树高度为
1
。请问高度为
5
的完全二叉树有
（
）
种不同的形态？
16
15
17
32
表达式
a*(b+c)*d
的后缀表达式为
(
)
，其中“
*
”和“
+
”是运算符。
**a+bcd
abc+*d*
abc+d**
*a*+bcd
10.
6
个人，两个人组一队，总共组成三队，不区分队伍的编号。不同的组队情况有（
）
种。
10
15
30
20
在数据压缩编码中的哈夫曼编码方法，在本质上是一种
（
）的策略
。
枚举
贪心
递归
动态规划
由
1
，
1
，
2
，
2
，
3
这五个数字组成不同的三位数有
（
）种
。
18
15
12
24
考虑如下递归算法
solve(n)
if n<=1 return
1
else
if
n>=5
return
n*solve(n-2) else return n*solve(n-1)
则调用
solve(7)
得到的返回结果为（
）
。
A.
105
B.
840
C.
210
D.
420
以
a
为起点，对右边的无向图进行深度优先遍历，则
b
、
c
、
d
、
e
四个点中有可能作
c
为最后一个遍历到的点的个数为
（
）
。
a
1
2
b
3
4
d
e
有四个人要从
A
点坐一条船过河到
B
点，船一开始在
A
点。该船一次最多可坐两个人。已知这四个人中每个人独自坐船的过河时间分别为
1, 2, 4, 8,
且两个人坐船的过河时
间为两人独自过河时间的较大者。则最短（
）时间可以让四个人都过河到
B
点（包括从
B
点把船开回
A
点的时间）。
14
15
16
17
二、阅读程序（程序输入不超过数组或字符串定义的范围；判断题正确填
√
，错误填
×
；除特殊说明外，判断题
1.5
分，选择题
3
分，共计
40
分）
(1)
01 #include <iostream> 02
using
namespace
std;
03
04 int
n;
05 int
a[1000];
06
07
int
f(int
x) 08 {
09
int ret =
0;
10
for
(; x; x &= x
- 1)
ret++;
11
return
ret;
12
}
13
14
int
g(int
x) 15 {
16
return
x
&
-x; 17 }
18
19
int
main() 20 {
cin >>
n;
for (int i = 0; i < n; i++) cin >>
a[i];
for (int i = 0; i < n;
i++)
24
cout << f(a[i]) + g(a[i]) << '
';
cout <<
endl;
return
0; 27 }
判断题
输入的
n
等于
1001
时，程序
不会
发生下标越界。
（
）
输入的
a[i]
必须全为正整数，否则程序将陷入死循环。
（
）
18.
当输入为“
5 2 11 9 16 10
”时，输出为“
3 4 3 17 5
”。
（
）
19.
当输入为“
1 511998
”时，输出为“
18
”。
（
）
将源代码中
g
函数的定义（
14-17
行）移到
main
函数的后面，程序可以正常编译运
行。（
）
单选题
21.
当输入为“
2 -65536 2147483647
”时，输出为
（
）
。
A.
“
65532
33
”
B.
“
65552
32
”
C.
“
65535
34
”
D.
“
65554
33
”
（
2
）
#include
<iostream>
#include
<string>
03
using namespace
std;
04
05
char
base[64];
06
char
table[256];
07
08
void
init()
09
{
10
for (int i = 0; i < 26; i++) base[i] = 'A' +
i;
11
for (int i = 0; i < 26; i++) base[26 + i] = 'a' +
i;
12
for (int i = 0; i < 10; i++) base[52 + i] = '0' +
i;
13
base[62] = '+', base[63] =
'/';
14
15
for (int i = 0; i
< 256; i++) table[i] =
0xff;
16
for (int i = 0; i < 64; i++) table[base[i]] =
i;
17
table['='] =
0;
18
}
19
20
string decode(string
str)
21
{
22
string
ret;
23
int
i;
24
for (i = 0; i < str.size(); i += 4)
{
25
ret += table[str[i]] << 2 | table[str[i + 1]] >>
4;
26
if (str[i + 2] !=
'=')
27
ret += (table[str[i + 1]] & 0x0f) << 4 | table[str[i
+
2]] >>
2;
2
2021年信息学奥赛CSP-J普及组初赛C++真题