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++真题