CSP-JS2023提高组一轮试题(山东) .pdf

2023CCF非专业级别软件能力认证第一轮

（CSP-S1）提高级C++语言试题

认证时间：2023年9月16日14:30~16:30

考生注意事项：

试题纸共有13页，答题纸共有1页，满分100分。请在答题纸上作答，写在试题纸上的

一律无效。

不得使用任何电子设备（如计算器、手机、电子词典等）或查阅任何书籍资料。

一、单项选择题（共15题，每题2分，共计30分；每题有且仅有一个正确选项）

1.在Linux系统终端中，以下哪个命令用于创建一个新的目录？（）

A.newdir

B.mkdir

C.create

D.mkfolder

2.0，1，2，3，4中选取4个数字，能组成（）个不同四位数。（注：最小的四位数是1000，

最大的四位数是9999。）

A.96

B.18

C.120

D.84

3.假设n是图的顶点的个数，m是图的边的个数，为求解某一问题有下面四种不同时间复杂

=Θ

度的算法。对于m(n)的稀疏图而言，下面的四个选项，哪一项的渐近时间复杂度最小。

（）

A.O(mlogn∙loglogn)

B.O(n2+m)

C.O(n2logm+mlogn)

O(+logn)

D.mn

4.假设有n根柱子，需要按照以下规则依次放置编号为1、2、3、...的圆环：每根柱子的底

部固定，顶部可以放入圆环；每次从柱子顶部放入圆环时，需要保证任何两个相邻圆环的

编号之和是一个完全平方数。请计算当有4根柱子时，最多可以放置（）个圆环。

CCFCSP-S2023第一轮C++语言试题

113

第页，共页

A.7

B.9

C.11

D.5

5.以下对数据结构的表述不恰当的一项是：（）。

A.队列是一种先进先出（FIFO）的线性结构

B.哈夫曼树的构造过程主要是为了实现图的深度优先有哪些信誉好的足球投注网站

C.散列表是一种通过散列函数将关键字映射到存储位置的数据结构

D.二叉树是一种每个结点最多有两个子结点的树结构

6.以下连通无向图中，（）一定可以用不超过两种颜色进行染色。

A.完全三叉树

B.平面图

C.边双连通图

D.欧拉图

7.最长公共子序列长度常常用来衡量两个序列的相似度。其定义如下：给定两个序列X=

{,,,⋯,}Y={,,,⋯,}

xxxx和yyyy，最长公共子序列（LCS）问题的目标是找到一个

123m123n

,,,⋯,}

最长的新序列Z={zzzz，使得序列Z既是序列X的子序列，又是序列Y的子序

123k

列，且序列Z的长度k在满足上述条件的序列里是最大的。（注：序列A是序列B的子序

列，当且仅当在保持序列B元素顺序的情况下，从序列B中删除若干个元素，可以使得剩

余的元素构成序列A。）则序列“ABCAAAABA”和“ABABCBABA”的最长公共子序列长度

为（）。

A.4

B.5

C.6

D.7

8.一位玩家正在玩一个特殊的掷骰子的游戏，游戏要求连续掷两次骰子，收益规则如下：玩

家第一次掷出x点，得到2x元；第二次掷出y点，当y=x时玩家会失去之前得到的2x元，

而当y≠x时玩家能保住第一次获得的2x元。上述x,y∈{1,2,3,4,5,6}。例如：玩家