首页 › 试卷 › 信息学奥赛 › 信息学奥赛-提高级 › 2023年CCF非专业级别软件能力认证第一轮 (CSP-S)提高级C++语言试题

2023年CCF非专业级别软件能力认证第一轮 (CSP-S)提高级C++语言试题 VIP

信息学奥赛-提高级 共 43 题 2023 年 含标准答案与解析
返回试卷列表
本页为整卷浏览:先自己做一遍,再展开「查看答案与解析」核对。

一、单选题

1. 单选题

在Linux系统终端中,以下哪个命令用于创建一个新的目录?

  • A newdir
  • B mkdir
  • C create
  • D mkfold
查看答案与解析
答案:B
解析:

考察基本的Linux命令,mk是make的缩写,dir是Directory file(目录文件)的缩写。

2. 单选题

0,1,2,3,4中选取4个数字,能组成(  )个不同四位数。(注:最小的四位数是1000最大的四位数是9999)

  • A 96
  • B 18
  • C 120
  • D 84
查看答案与解析
答案:A
解析:

因为0不能做最高位,首先从1,2,3,4中选出一个数字做最高位,接下来百位有4种选择,十位有3种选择,个位有2种选择,按照乘法原理4×4×3×2=96。

3. 单选题

假设n是图的顶点的个数,m是图的边的个数,为求解某一问题有下面四种不同时间复杂度的算法。对于m=θ(n)的稀疏图而言,下面的四个选项,哪一项的渐近时间复杂度最小

  • A O(m√logn·loglogn)
  • B O(n2+m)
  • C O(n2/logm+mlogn)
  • D O(m+nlogn)
查看答案与解析
答案:A
解析:

由于图片,m和n的增长速度完全相同,可以认为图片,C为常数。把所有m替换成n后很容易排除B、C选项。考虑另外两个选项,当x比较大时,一定有图片,同理图片,两边同乘图片得到图片,而常数不影响渐进时间复杂度,说明A比D小。

4. 单选题

假设有n根柱子,需要按照以下规则依次放置编号为1、2、3、…的圆环:每根柱子的底部固定,顶部可以放入圆环;每次从柱子顶部放入圆环时,需要保证任何两个相邻圆环的编号之和是一个完全平方数。请计算当有4根柱子时,最多可以放置(  )个圆环

  • A 7
  • B 9
  • C 11
  • D 5
查看答案与解析
答案:C
解析:

在4根柱子的时候每个圆环只有一种放置方法,直接模拟就可以得到答案了。

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 4
  • B 5
  • C 6
  • D 7
查看答案与解析
答案:C
解析:

可以使用经典的动态规划算法,可以看出最长公共子序列是“ABAABA”。

8. 单选题

一位玩家正在玩一个特殊的掷骰子的游戏,游戏要求连续掷两次骰子,收益规则如下:玩家第一次掷出x点,得到2x元;第二次掷出y点,当y=x时玩家会失去之前得到的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/6元

  • C

    16/3元

  • D

    19/3元

查看答案与解析
答案:B
解析:

可以算出每种收益的出现概率乘以对应的收益:获得2元的概率是1/6×5/6=5/36,获得4元、6元、8元、10元、12元同理,获得0元的概率是1-5/36*6=1/6,所以收益的平均值是:(2+4+6+8+10+12)×5/36=35/6元。

9. 单选题

假设我们有一下的C++代码:

int a = 5, b = 3, c = 4;

bool res = a &b || c ^ b && a  | c;

请问res的值是什么?()

提示:在C++中,逻辑运算的优先级从高到低依次为:逻辑非(!),逻辑与(&&),逻辑或(||)。位运算的优先级从高到低依次为:位非(~),位与(&),位异或(^),位或(|)。同时,双目位运算的优先级高于双目逻辑运算:逻辑非和位非优先级相同,且高于所有双目运算符。

  • A true
  • B false
  • C 1
  • D 0
查看答案与解析
答案:A
解析:

首先把位运算算出来,得到res = 1 || 7 && 5,然后执行逻辑运算(非0的数字在逻辑运算中都视为true)得到true。

10. 单选题

假设快速排序算法的输入是一个长度为n的已排序数组,且该快速排序算法在分治过程总是选择第一个元素作为基准元素。以下哪个选项描述的是在这种情况下的快速排序行为?

  • A 快速排序对于此类输入的表现最好,因为数组已经排序。
  • B 快速排序对于此类输入的时间复杂度是0(nlogn)。
  • C 快速排序对于此类输入的时间复杂度是0(n2)。
  • D 快速排序无法对此类数组进行排序,因为数组已经排序。
查看答案与解析
答案:C
解析:

如果数组已经排序,并且每次都取第一个元素作为基准元素。那么每次递归时,待排序区间都只会减少一个数,所以深度会达到n层,总复杂度是O(n2)。

11. 单选题

以下哪个命令,能将一个名为"main.cpp"的C++源文件,编译并生成一个名为"main"的可执行文件?(  )

  • A g++-o main main,cpp
  • B g++-0 main.cpp main
  • C g++  main -o main.cpp
  • D g++  main.cpp  -o main.cpp
查看答案与解析
答案:A
解析:

基础编译命令,-o后面是需要生成的可执行文件的名字(Linux中可执行文件不需要后缀名),然后接上需要被编译的C++文件名。

12. 单选题

在图论中,树的重心是树上的一个结点,以该结点为根时,使得其所有的子树中结点数最多的子树的结点数最少。一棵树可能有多个重心。请问下面哪种树一定只有一个重心?(  )

  • A 4个结点的树
  • B 6个结点的树
  • C 7个结点的树
  • D 8个结点的树
查看答案与解析
答案:C
解析:

考虑一条链的情况下,如果树的结点是偶数个数,那么中间的两个点都可以是重心,所以必须是奇数个结点的树。

13. 单选题

如图是一张包含6个顶点的有向图,但顶点间不存在拓扑序。如果要删除其中一条边,使这6个顶点能进行拓扑排序,请问总共有多少条边可以作为候选的被删除边?

  • A 1
  • B 2
  • C 3
  • D 4
查看答案与解析
答案:C
解析:

拓扑排序的前提条件是有向无环图,图中存在一个1→3→4→1的环,删除环上任意一条边就可以了。

14. 单选题

若n = ∑ki=016i·xi,定义f(n) = ∑ki=0xi;其中x∈{0,1,…,15},对于给定自然数n0,存在序列n0, n1, n2, …, nm,其中对于1≤i≤m都有nm=nm-1,称nm为n0关于f的不动点。问在10016至1A016中,关于f的不动点为9的自然数个数为()。

  • A

    10

  • B

    11

  • C

    12

  • D

    13

查看答案与解析
答案:B
解析:

题目大意:n是一个16进制的数字,f(n)表示n的16进制状态下各位之和,如果不断计算n=f(n),最终n会停在某个数字不再改变。询问(100)16到(1A0)16中有多少个数字会停在数字9。

考虑位数只有3位,并且最高位是1,第二位最多是A,第一次的f(n)只能是9或者(18)16,f(n) = 9一共9种方案(均为16进制):108, 117, 126, 135, 145, 154, 163, 171, 180。f(n) = 9一共2种方案(均为16进制):18F, 19E。

15. 单选题

现在用如下代码来计算下xn,其时间复杂度为()

double quick_power(double x, unsigned n){

        If(n  == 0) return 1;

        If(n  == 1) return x;

        return  quick_power(x, n/2)

* quick_power(x, n/2)

* ((n & 1) ? x : 1);

}
  • A 0(n)
  • B 0(1)
  • C 0(logn)
  • D 0(nlogn)
查看答案与解析
答案:A
解析:

虽然看上去使用了快速幂,但是每次分治后程序把quick_power运行了两次,没能真正实现分治法,复杂度仍然是O(n)。

21. 单选题

当输入为”512”时,输出为()。

  • A "33280"
  • B "33410"
  • C "33106"
  • D "33346"
查看答案与解析
答案:B
这道题暂未补解析。
22. 单选题

当输入为“64”时,执行完第5行后x的值为()。

  • A "8256"
  • B "4130"
  • C "4128"
  • D "4160"
查看答案与解析
答案:D
这道题暂未补解析。
27. 单选题

.solve1(n)的时间复杂度为()。

  • A 0(n log2 n)
  • B 0(n)
  • C 0(n logn)
  • D 0(nloglogn)
查看答案与解析
答案:D
这道题暂未补解析。
28. 单选题

solve2(n)的时间复杂度为()。

  • A 0(n2)
  • B 0(n)
  • C 0(n logn)
  • D 0(n√n)
查看答案与解析
答案:B
这道题暂未补解析。
29. 单选题

输入为“5”时,输出的第二行为().

  • A "20"
  • B "21"
  • C "22"
  • D "23"
查看答案与解析
答案:B
这道题暂未补解析。
34. 单选题

设a数组中最大值减最小值加1为A,则f函数的时间复杂度为()。

  • A 0(n logA)
  • B 0(n2logA)
  • C 0(n log(nA))
  • D 0(nlogn)
查看答案与解析
答案:C
这道题暂未补解析。
35. 单选题

.将第10行中的">"替换为">=",那么原输出与现输出的大小关系为()

  • A 一定小于
  • B 一定小于等于且不一定小于
  • C 一定大于等于且不一定大于
  • D 以上三种情况都不对
查看答案与解析
答案:B
这道题暂未补解析。
36. 单选题

当输入为”582-538-12”时,输出为()

  • A "13"
  • B "14"
  • C "8"
  • D "15"
查看答案与解析
答案:B
这道题暂未补解析。
38. 单选题

①处应填()

  • A k>= f[u]
  • B k <= f[u]
  • C k>f[u]
  • D k<f[u]
查看答案与解析
答案:B
这道题暂未补解析。
39. 单选题

②处应填()

  • A deg[v]== 1
  • B deg[v]== 0
  • C deg[v]> 1
  • D deg[v]>0
查看答案与解析
答案:A
这道题暂未补解析。
40. 单选题

③处应填()

  • A std::min(f[u]+ f[v],LIM)
  • B std::min(f[u]+ f[v]+1,LIM)
  • C std::min(f[u]* f[v],LIM)
  • D std::min(f[u]*(f[v]+ 1),LIM)
查看答案与解析
答案:A
这道题暂未补解析。
41. 单选题

④处应填()

  • A u!=-1
  • B !E[u].empty()
  • C k>0
  • D k>1
查看答案与解析
答案:D
这道题暂未补解析。
42. 单选题

⑤处应填()

  • A k += f[u]
  • B k-= f[u]
  • C --k
  • D ++k
查看答案与解析
答案:C
这道题暂未补解析。

二、简答题

16. 简答题

假设输入的x是不超过65535的自然数,完成下面的判断题和单选题:

查看答案与解析
答案:(缺答案,待补录)
这道题暂未补解析。
23. 简答题

阅读程序

假设输入的n是不超过1000000的自然数,完成下面的判断题和单选题:

查看答案与解析
答案:(缺答案,待补录)
这道题暂未补解析。
30. 简答题

阅读程序

查看答案与解析
答案:(缺答案,待补录)
这道题暂未补解析。
37. 简答题

(第k小路径)给定一张n个点m条边的有向无环图,顶点编号从0到n-1对于一条路径,我们定义"路径序列"为该路径从起点出发依次经过的顶点编号构成的序列。求所有至少包含一个点的简单路径中,“路径序列”字典序第k小的路径。保证存在至少k条路径。上述参数满足1≤n,m≤105和1≤k≤1018。

在程序中,我们求出从每个点出发的路径数量。超过1018的数都用1018表示。然后我们根据k的值和每个顶点的路径数量,确定路径的起点,然后可以类似地依次求出路径中的每个点。

试补全程序。

查看答案与解析
答案:(缺答案,待补录)
这道题暂未补解析。
43. 简答题

(最大值之和)给定整数序列a0,… an-1,求该序列所有非空连续子序列的最大值之和。上述参数满足1≤n≤105和1≤a;≤108。

一个序列的非空连续子序列可以用两个下标l和r(其中0≤l≤r<n)表示,对应的序列为alal+1… ar。两个非空连续子序列不同,当且仅当下标不同。

例如,当原序列为[1,2,1,2]时,要计算子序列[1]、[2]、[1]、[2]、[1,2]、[2,1]、[1,2]、[1,2,1]、[2,1,2]、[1,2,1,2]的最大值之和,答案为18。注意[1,1]和[22]虽然是原序列的子序列,但不是连续子序列,所以不应该被计算。另外,注意其中有一些值相同的子序列,但由于他们在原序列中的下标不同,属于不同的非空连续子序列,所以会被分别计算。解决该问题有许多算法,以下程序使用分治算法,时间复杂度0(nlogn)。

试补全程序。

查看答案与解析
答案:(缺答案,待补录)
这道题暂未补解析。

三、判断题

17. 判断题

当输入非零时,输出一定不为零。()

  • A对
  • B错
查看答案与解析
答案:对
这道题暂未补解析。
18. 判断题

将f函数的输入参数的类型改为unsignedint,程序的输出不变。()

  • A对
  • B错
查看答案与解析
答案:错
这道题暂未补解析。
19. 判断题

当输入为“65535”时,输出为”63”。()

  • A对
  • B错
查看答案与解析
答案:对
这道题暂未补解析。
20. 判断题

当输入为”1“时,输山为"64”。()

  • A对
  • B错
查看答案与解析
答案:错
这道题暂未补解析。
24. 判断题

将第15行删去,输出不变。()

  • A对
  • B错
查看答案与解析
答案:错
这道题暂未补解析。
25. 判断题

当输入为"10"时,输出的第一行大于第二行。()

  • A对
  • B错
查看答案与解析
答案:错
这道题暂未补解析。
26. 判断题

当输入为"1000"时,输出的第一行与第二行相等。()

  • A对
  • B错
查看答案与解析
答案:对
这道题暂未补解析。
31. 判断题

将第24行的"m"改为"m-1",输出有可能不变,而剩下情况为少1。()

  • A对
  • B错
查看答案与解析
答案:对
这道题暂未补解析。
32. 判断题

将第22行的“g +(h-g)/2”改为"(h+g)>>1",输出不变。()

  • A对
  • B错
查看答案与解析
答案:对
这道题暂未补解析。
33. 判断题

当输入为“572-451-3",输出为"5”。()

  • A对
  • B错
查看答案与解析
答案:对
这道题暂未补解析。