2023-CSP-S(提高组)认证第一轮试题详细解析.pdfVIP

2023-CSP-S(提高组)认证第一轮试题详细解析

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

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

A.newdirB.mkdirC.createD.mkfolder

答案：B，Linux常用目录操作命令：cd切换目录，mkdir创建目录rm删除目

录mv和cp目录修改find有哪些信誉好的足球投注网站目录等

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

位数是1000,最大的四位数是9999。)

A.96B.18C.120D.84

答案：A千位有4种选择，百位4种，十位3种，个位2种，乘法原理，4*4*3*296。

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

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

的渐近时间复杂度最小。

A.O(mlogn·loglogn)B.O(n²+m)

C.O(n²/logm+mlogn)D.O(m+nlogn)

答案：Am和n同一数量级，loglognlogn，所以A＜D＜C＜B。

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

每根柱子的底部固定，顶部可以放入圆环；每次从柱子顶部放入圆环时，需要保

证任何两个相邻圆环的编号之和是一个完全平方数。请计算当有4根柱子时，最

多可以放置（）个圆环

A.7B.9C.11D.5

答案：C，模拟整个过程，我们发现，每次放圆环都只有一个选择，假设柱子为

ABCD，则A1B2C3D4D5C6B7A8B9C10D11。

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

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

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

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

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

答案：B，哈夫曼树用贪心思想构造，通常用来编码压缩，和图的深度优先有哪些信誉好的足球投注网站

没有关系。

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

A.完全三叉树B.平面图C.边双连通图D.欧拉图

答案：A，染色问题是同一条边的两个点用不用的颜色。树是一种二分图（两种

颜色即可），最简单的办法就是每一层用不同的颜色。

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

个序列X{x1,x2,x3,…,xm}和Y{y1,y2,y3,…,yn},最长公共子序列(LCS)问题

的目标是找到一个最长的新序列Z{z1,z2,z3,…,zk},使得序列Z既是序列X的

子序列，又是序列Y的子序列，且序列Z的长度k在满足上述条件的序列里是最

大的。(注：序列A是序列B的子序列，当且仅当在保持序列B元素顺序的情况

下，从序列B中删除若干个元素，可以使得剩余的元素构成序列A。)则序列

“ABCAAAABA”和“ABABCBABA”的最长公共子序列长度为（）

A.4B.5C.6D.7

答案：C，简单的动态规划问题，先匹配头尾的AB和ABA，长度为5，剩下CAAA

和ABCB只有一个可取。

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

规则如下：玩家第一次掷出x点，得到2x元；第二次掷出y点，当yx时玩家

会失去之前得到的2x元，而当y≠x时，玩家能保住第一次获得的2x元。上述

x,y∈{1,2,3,4,5,6}。例如：玩家第一次掷出3点得到6元后，但第二次再次掷

出3点，会失去之前得到的6元，玩家最终收益为0元；如果玩家第一次掷出3

点、第二次掷出4点，则最终收益是6元。假设骰子掷出任意一点的概率均为

1/6，玩家连续掷两次骰子后，所有可能情形下收益的平均值是多少?（）

A.7元B.35/6C.16/3D.19/3

答案：B，假设第一次是a，则5/6的可能性获得2a，1/6的可能性获得0，期望

收益是2a*5/65a/