信息学奥赛
万卷网> 信息学奥赛 >CSP-S/提高级 > 2023年CCF非专业级别软件能力认证第一轮CSP_S/提高级

2023年CCF非专业级别软件能力认证第一轮CSP_S/提高级
2023 第一轮 2023-09-18 15:17:20 125次

一、单选题

1．

②处应填()

A．

a[j]< max

 B．

a[j]<a[i]
C．

pre[j-mid]<max

 D．

pre[j- mid]> max
答案 详情
2．

③处应填()

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)
答案 详情
3．

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

A．

一定小于

 B．

一定小于等于且不一定小于
C．

一定大于等于且不一定大于

 D．

以上三种情况都不对
答案 详情
4．

以下哪个命令，能将一个名为"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
答案 详情
5．

①处应填()

A．

pre[i]= std::max(pre[i- 1],a[i-1])

 B．

pre[i+1]= std:max(pre[i],pre[i+1])
C．

pre[i]= std;:max(pre[i-1],a[i])

 D．

pre[i]= std:max(pre[i], pre[i- 1])
答案 详情
6．

①处应填()

A．

k>= f[u]

 B．

k <= f[u]
C．

k>f[u]

 D．

k<f[u]
答案 详情
7．

一位玩家正在玩一个特殊的掷骰子的游戏，游戏要求连续掷两次骰子，收益规则如下：玩家第一次掷出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元
答案 详情
8．

最长公共子序列长度常常用来衡量两个序列的相似度。其定义如下：给定两个序列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
答案 详情
9．

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

A．

"20"

 B．

"21"
C．

"22"

 D．

"23"
答案 详情
10．

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

A．

4个结点的树

 B．

6个结点的树
C．

7个结点的树

 D．

8个结点的树
答案 详情
11．

若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
答案 详情
12．

④处应填()

A．

(long long)(r-j)*max

 B．

(long long)(r-j)*(mid -i)*max
C．

sum[r- mid]- sum[-mid]

 D．

(sum[r-mid]- sum[j-mid])*(mid-i)
答案 详情
13．

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

A．

newdir

 B．

mkdir
C．

create

 D．

mkfold
答案 详情
14．

④处应填()

A．

u!=-1

 B．

!E[u].empty()
C．

k>0

 D．

k>1
答案 详情
15．

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

A．

快速排序对于此类输入的表现最好，因为数组已经排序。

 B．

快速排序对于此类输入的时间复杂度是0(nlogn)。
C．

快速排序对于此类输入的时间复杂度是0(n2)。

 D．

快速排序无法对此类数组进行排序，因为数组已经排序。
答案 详情
16．

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

A．

0(n log2 n)

 B．

0(n)
C．

0(n logn)

 D．

0(nloglogn)
答案 详情
17．

假设我们有一下的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
答案 详情
18．

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

A．

"13"

 B．

"14"
C．

"8"

 D．

"15"
答案 详情
19．

②处应填()

A．

deg[v]== 1

 B．

deg[v]== 0
C．

deg[v]> 1

 D．

deg[v]>0
答案 详情
20．

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

A．

O(m√logn·loglogn)

 B．

O(n2+m)
C．

O(n2/logm+mlogn)

 D．

O(m+nlogn)
答案 详情
21．

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

A．

"33280"

 B．

"33410"
C．

"33106"

 D．

"33346"
答案 详情
22．

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

A．

0(n2)

 B．

0(n)
C．

0(n logn)

 D．

0(n√n)
答案 详情
23．

③处应填()

A．

(long long)(j -mid)* max

 B．

(long long)(j- mid)*(i-1)*max
C．

sum[j- mid]

 D．

sum[j-mid]*(i-1)
答案 详情
24．

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

A．

1

 B．

2
C．

3

 D．

4
答案 详情
25．

现在用如下代码来计算下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)
答案 详情
26．

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

A．

96

 B．

18
C．

120

 D．

84
答案 详情
27．

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

A．

"8256"

 B．

"4130"
C．

"4128"

 D．

"4160"
答案 详情
28．

以下对数据结构的表述不恰当的一项是：

A．

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

 B．

哈夫曼树的构造过程主要是为了实现图的深度优先搜索
C．

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

 D．

二叉树是一种每个结点最多有两个子结点的树结构
答案 详情
29．

以下连通无向图中，(  )一定可以用不超过两种颜色进行染色


A．

完全三叉树

 B．

平面图
C．

边双连通图

 D．

欧拉图
答案 详情
30．

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

A．

0(n logA)

 B．

0(n2logA)
C．

0(n log(nA))

 D．

0(nlogn)
答案 详情
31．

⑤处应填()

A．

k += f[u]

 B．

k-= f[u]
C．

--k

 D．

++k
答案 详情
32．

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

A．

7

 B．

9
C．

11

 D．

5
答案 详情
33．

⑤处应填()

A．

solve(0,n)

 B．

solve(0, n-1)
C．

solve(1,n)

 D．

solve(1, n-1)
答案 详情

二、判断题

1．

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

A．正确 B．错误
答案 详情
2．

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

A．正确 B．错误
答案 详情
3．

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

A．正确 B．错误
答案 详情
4．

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

A．正确 B．错误
答案 详情
5．

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

A．正确 B．错误
答案 详情
6．

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

A．正确 B．错误
答案 详情
7．

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

A．正确 B．错误
答案 详情
8．

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

A．正确 B．错误
答案 详情
9．

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

A．正确 B．错误
答案 详情
10．

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

A．正确 B．错误
答案 详情

三、组合题

1．

阅读程序

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

(1)．

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

A．

"20"

 B．

"21"
C．

"22"

 D．

"23"
(2)．

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

A．

0(n log2 n)

 B．

0(n)
C．

0(n logn)

 D．

0(nloglogn)
(3)．

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

A．正确 B．错误
(4)．

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

A．

0(n2)

 B．

0(n)
C．

0(n logn)

 D．

0(n√n)
(5)．

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

A．正确 B．错误
(6)．

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

A．正确 B．错误
答案 详情
2．

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

(1)．

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

A．正确 B．错误
(2)．

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

A．正确 B．错误
(3)．

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

A．正确 B．错误
(4)．

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

A．

"33280"

 B．

"33410"
C．

"33106"

 D．

"33346"
(5)．

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

A．正确 B．错误
(6)．

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

A．

"8256"

 B．

"4130"
C．

"4128"

 D．

"4160"
答案 详情
3．

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

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

试补全程序。

(1)．

③处应填()

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)
(2)．

①处应填()

A．

k>= f[u]

 B．

k <= f[u]
C．

k>f[u]

 D．

k<f[u]
(3)．

④处应填()

A．

u!=-1

 B．

!E[u].empty()
C．

k>0

 D．

k>1
(4)．

②处应填()

A．

deg[v]== 1

 B．

deg[v]== 0
C．

deg[v]> 1

 D．

deg[v]>0
(5)．

⑤处应填()

A．

k += f[u]

 B．

k-= f[u]
C．

--k

 D．

++k
答案 详情
4．

(最大值之和)给定整数序列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)。

试补全程序。

(1)．

②处应填()

A．

a[j]< max

 B．

a[j]<a[i]
C．

pre[j-mid]<max

 D．

pre[j- mid]> max
(2)．

①处应填()

A．

pre[i]= std::max(pre[i- 1],a[i-1])

 B．

pre[i+1]= std:max(pre[i],pre[i+1])
C．

pre[i]= std;:max(pre[i-1],a[i])

 D．

pre[i]= std:max(pre[i], pre[i- 1])
(3)．

④处应填()

A．

(long long)(r-j)*max

 B．

(long long)(r-j)*(mid -i)*max
C．

sum[r- mid]- sum[-mid]

 D．

(sum[r-mid]- sum[j-mid])*(mid-i)
(4)．

③处应填()

A．

(long long)(j -mid)* max

 B．

(long long)(j- mid)*(i-1)*max
C．

sum[j- mid]

 D．

sum[j-mid]*(i-1)
(5)．

⑤处应填()

A．

solve(0,n)

 B．

solve(0, n-1)
C．

solve(1,n)

 D．

solve(1, n-1)
答案 详情
5．

阅读程序

(1)．

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

A．正确 B．错误
(2)．

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

A．

一定小于

 B．

一定小于等于且不一定小于
C．

一定大于等于且不一定大于

 D．

以上三种情况都不对
(3)．

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

A．

"13"

 B．

"14"
C．

"8"

 D．

"15"
(4)．

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

A．正确 B．错误
(5)．

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

A．正确 B．错误
(6)．

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

A．

0(n logA)

 B．

0(n2logA)
C．

0(n log(nA))

 D．

0(nlogn)
答案 详情
万卷网 版权所有 蒙ICP备2025029916号-1

蒙公网安备15040202200102号
由于万卷网是一个信息共享平台，不保证部分用户上传资料的来源及知识产权归属。如您发现相关资料侵犯您的合法权益，请联系万卷网，我们核实后将及时进行处理。
公众号
客服 反馈
顶部