2023年（初赛S）CCF非专业级别软件能力认证全国卷真题（附详细答案解析）

2023CCF非专业级别软件能力认证第一轮 (CSP-S1)提高级C++语言试题 认证时间:2023年9月16日14:30~16:30 一、单项选择题(共15题,每题2分,共计30分:每题有且仅有一个正确选项) 1.在Linux系统终端中,以下哪个命令用于创建一个新的目录?( ) A. newdir B. mkdir C. create D. mkfolder 答案B Linux中mkdir创建新文件夹 2.,1,2,3,4中选取4个数字,能组成( )个不同四位数。(注:最小 的四位数是10,最大的四位数是9999。) A.96 B.18 C.120 D.84 答案A 选千位有四种选择,其余三个数从剩下四个数里面选择,故答案为Cl·A}=96 3.假设n是图的顶点的个数,m是图的边的个数,为求解某一问题有下面 四种不同时间复杂度的算法。对于m=(n)的稀疏图而言,下面的四个选 项,哪一项的渐近时间复杂度最小。 A.o(mlogn:loglogn B.O(n2+m) D.o(m+nlogn) 答案:A 稀疏图边数量较少,故要选以m为主的式子,选A 4.假设有n根柱子,需要按照以下规则依次放置编号为1、2、3、...的 圆环:每根杜子的底部固定,顶部可以放入圆环;每次从柱子顶部放入 圆环时,需要保证任何两个相邻圆环的编号之和是一个完全平方数。请 计算当有4根柱子时,最多可以放置( )个圆环。 A.7 B.9 C.11 D.5 答案:C 四个柱子分别为abcd. 按照以下顺序放 a1 b2 c3 d4 d5 c6 b7 a8 b9 c10 d11 一共能放下11个圆环 5.以下对数据结构的表述不恰当的一项是; )。 A.队列是一种先进先出(FIFO)的线性结构 B.哈夫曼树的构造过程主要是为了实现图的深度优先搜索 C.散列表是一种通过散列函数将关键字映射到存储位置的数据结构 D.二叉树是一种每个结点最多有两个子结点的树结构 答案:B 哈夫曼树的构造主要是为了压缩字符串,运用的贪心思想,和深度优先搜索无关 6.以下连通无向图中, )一定可以用不超过两种颜色进行染色。 A. 完全三叉树 B.平面图 C.边双连通图 D.欧拉图 答案:A 只有树结构无环,无环图可以用两种颜色染色 7.最长公共子序列长度常常用来衡量两个序列的相似度。其定义如下:给定两 个序列X=fx1.x2.x3....xml和Y=fy1.y2.y3...yn),最长公共子序列(LCS)问题的目 标是找到一个最长的新序列7-{z1.z2.23...-2x),使得序列z既是序列x的子序列 又是序列Y的子序列,且序列z的长度k在满足上述条件的序列里是最大的。(注 序列A是序列B的子序列,当且仅当在保持序列B元素顺序的情况下,从序列B中 删除若干个元素,可以使得剩余的元素构成序列A。)则序列“ABCAAAABA”和 “ABABCBABA”的最长公共子序列长度为( )。 A.4 B.5 C6 D.7 答案:C 第一个字符丰选ABCAAAABA. 第二个字符串选ABABCBABA 最长公共子序列为ABCABA 8.一位玩家正在玩一个特殊的掷毂子的游戏,游戏要求连续掷两次毂子,收益 规则如下:玩家第一次掷出x点,得到2x元:第二次掷出v点,当y=x时玩家会失 去之前得到的2x元,而当y*x时玩家能保住第一次获得的2x元。上述x,y (1,2,3,4,5,6)。例如:玩家第一次掷出3点得到6元后,但第二次再次挪出3 点,会失去之前得到的6元,玩家最终收益为元;如果玩家第一次挪出3点、第 二次掷出4点,则最终收益是6元。假设毂子掷出任意一点的概率均为1/6,玩家 连续掷两次毂子后,所有可能情形下收益的平均值是多少?() A.7元 答案:B 因为每次获得钱的概率为 根据期望公式计算出 5 5 5 +8. +6. 2. 士.4. 410. 36 36 3 3 答案等于3 9. 假设我们有以下的C++代码 Int a=5,b=3,c=4; bool res=a& b IIc ^b&& a Ic; 请问,res的值是什么?() 提示:在C++中,逻辑运算的优先级从高到低依次为:逻辑非(!)、逻辑与(88)、 逻辑或(1)。位运算的优先级从高到低依次为:位非(~)、位与(&)、位 异或()、位或()。同时,双目位运算的优先级高于双目逻辑运算:逻辑非 和位非优先级相同,且高于所有双目运算符。 A.true B.false C.1 D.0 答案:A 按照优先级计算即可,值为true,若输出则为1 19.假设快速排序算法的输入是一个长度为n的已排序数组,且该快速排序算法 在分治过程总是选择第一个元素作为基准元素。以下哪个选项描述的是在这利 情况下的快速排序行为? ) ) A.快速排序对于此类输入的表现最