2022
CCF
非专业级别软件能力认证第一
轮
（
CSP-J1
）入门级
C++
语言试
题
认证时间：
2022
年
9
月
18
日
09:30~11:30
考生注意事
项：
试题纸共有
12
页，答题纸共有
1
页，满分
100
分。请在答题纸上作答，写在试题纸上的一律无效。
不得使用任何电子设备（如计算器、手机、电子词典等）
或查阅任何书籍资料。
一、单项选择题（共
15
题，每题
2
分，共计
30
分；每题有且仅有一个正确选项
）
以下哪种功能没有涉及
C++
语言的面向对象特性支持
：
（
）
。
C++
中调用
printf
函数
C++
中调用用户定义的类成员函数
C++
中构造一个
class
或
struct
C++
中构造来源于同一基类的多个派生类
有
6
个元素，按照
6
、
5
、
4
、
3
、
2
、
1
的顺序进入栈
S
，请问下列哪个出栈序列是非法的
（
）
。
A.
5
4
3
6
1
2
B.
4
5
3
1
2
6
C.
3
4
6
5
2
1
D.
2
3
4
1
5
6
运行以下代码片段的行为是
（
）
。
int
x
=
101; int
y
=
201; int
*p
=
&x; int *q =
&y;
p =
q;
将
x
的值赋为
201
将
y
的值赋为
101
将
q
指向
x
的地址
将
p
指向
y
的地址
链表和数组的区别包括
（
）
。
数组不能排序，链表可以
链表比数组能存储更多的信息
数组大小固定，链表大小可动态调整
以上均正确
对假设栈
S
和队列
Q
的初始状态为空。存在
e1~e6
六个互不相同的数据，每个数据按照进栈
S
、出栈
S
、进队列
Q
、出队列
Q
的顺序操作，不同数据间的操作可能会交错。已知
栈
S
中依次有数据
e1
、
e2
、
e3
、
e4
、
e5
和
e6
进栈，队列
Q
依次有数据
e2
、
e4
、
e3
、
e6
、
e5
和
e1
出队列。则栈
S
的容量至少是（
）个数据。
2
3
4
6
对表达式
a+(b-c)*d
的前缀表达式为
（
），其中
+
、
-
、
*
是运算符
。
*+a-
bcd
+a*-
bcd
abc-
d*+
abc-
+d
假设字母表
{a,
b,
c,
d,
e}
在字符串出现的频率分别为
10%,
15%,
30%,
16%, 29%
。若使用哈夫曼编码方式对字母进行不定长的二进制编码，字母
d
的编码长度为
（
）
位。
1
2
2
或
3
3
一棵有
n
个结点的完全二叉树用数组进行存储与表示，已知根结点存储在数组的第
1
个位
置。若存储在数组第
9
个位置的结点存在兄弟结点和两个子结点，则它的兄弟结点和右子结点的位置分别是（ ）。
8
、
18
B.
10
、
18
C.
8
、
19
D.
10
、
19
考虑由
N
个顶点构成的有向连通图，采用邻接矩阵的数据结构表示时，该矩阵中至少存在
（
）
个非零元素。
N-
1
N
N+1
N
2
以下对数据结构的表述不恰当的一项为
：（
）
。
图的深度优先遍历算法常使用的数据结构为栈。
栈的访问原则为后进先出，队列的访问原则是先进先出。
队列常常被用于广度优先搜索算法。
栈与队列存在本质不同，无法用栈实现队列。
以下哪组操作能完成在双向循环链表结点
p
之后插入结点
s
的效果（其中，
next
域为结
点的直接后继，
prev
域为结点的直接前驱）：（
）。
A.
p->next->prev=s;
s-
>prev=p;
p-
>next=s;
s->next=p-
>next;
B.
p->next->prev=s;
p-
>next=s;
s-
>prev=p;
s->next=p-
>next;
C.
s->prev=p;
s->next=p-
>next;
p-
>next=s;
p->next-
>prev=s;
D.
s->next=p->next;
p->next->prev=s;
s->prev=p;
p-
>next=s;
以下排序算法的常见实现中，哪个选项的说法是错误的
：（
）
。
冒泡排序算法是稳定的
简单选择排序是稳定的
简单插入排序是稳定的
归并排序算法是稳定的
八进制数
32.1
对应的十进制数是
（
）
。
A.
24.125
B.
24.250
C.
26.125
D.
26.250
一个字符串中任意个连续的字符组成的子序列称为该字符串的子串，则字符串
abcab
有
（
）
个内容互不相同的子串。
12
13
14
15
以下对递归方法的描述中，正确的是
：（
）
递归是允许使用多组参数调用函数的编程技术
递归是通过调用自身来求解问题的编程技术
递归是面向对象和数据而不是功能和逻辑的编程语言模型
递归是将用某种高级语言转换为机器代码的编程技术
二、阅读程序（程序输入不超过数组或字符串定义的范围；判断题正确填
√
，错误填
×
；除特
殊说明外，判断题
1.5
分，选择题
3
分，共计
40
分）
(1)
01
#include
<iostream>
02
03
using namespace
std;
04
05
int
main()
06
{
07
unsigned short x,
y;
08
cin >> x >>
y;
09
x = (x | x
<< 2) &
0x33;
10
x = (x | x << 1) &
0x55;
11
y = (y | y << 2) &
0x33;
12
y = (y | y << 1) &
0x55;
unsigned short z = x | y <<
1;
cout << z <<
endl;
return
0; 16 }
假设输入的
x
、
y
均是不超过
15
的自然数，完成下面的判断题和单选题
：
判断题
删去第
7
行与第
13
行的
unsigned
，程序行为不变。
（
）
将第
7
行与第
13
行的
short
均改为
char
，程序行为不变
2022年信息学奥赛CSP-J普及组初赛C++真题