#1848. 2023CSP-S1

2023CSP-S1

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

1 在Linux系统终端中，以下那个命令用于创建一个新的目录( ) {{ select(1) }}

  • newdir
  • mkdir
  • create
  • mkfold

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

  • 96
  • 18
  • 120
  • 84

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

  • O(m*sqrt(logn)*loglogn)
  • O(n2+m)O(n^2+m)
  • O(n2/logm+mlogn)O(n^2/logm+mlogn)
  • O(m+nlogn)O(m+nlogn)

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

  • 7
  • 9
  • 11
  • 5

5 以下对数据结构的表述不恰当的一项是( ) {{ select(5) }}

  • 队列是一种先进先出(FIFO)的线性结构
  • 哈夫曼树的构造过程主要是为了实现图的深度优先搜索
  • 散列表是一种通过散列函数将关键字映射到存储位置的数据结构
  • 二又树是一种每个结点最多有两个子结点的树结构

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

  • 完全三叉树
  • 平面图
  • 边双连通图
  • 欧拉图

7 最长公共子序列长度常常用来衡量两个序列的相似度。其定义如下:给定两个序列X={x1,x2,x3,...xm}和Y={y1,y2,y3...yn},最长公共子序列(LCS)问题的目标是找到一个最长的新序列Z= {z1,z2,z3...zk},使得序列 既是序列X 的子序列，又是序列Y的子序列，且序列Z的长度k 在满足上述条件的序列里是最大的。(注:序列A 是序列B 的子序列，当且仅当在保持序列B 元素顺序的情况下，从序列B中删除若千个元素，可以使得剩余的元素构成序列A。测序列“ABCAAAABA”和“ABABCBABA”的最长公共子序列长度为( ) {{ select(7) }}

  • 4
  • 5
  • 6
  • 7

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,玩家连续掷两次般子后所有可能情形下收益的平均值是多少? {{ select(8) }}

  • 7
  • 35/6
  • 16/3
  • 19/3

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

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

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

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

  • true
  • false
  • 1
  • 0

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

  • 快速排序对于此类输入的表现最好因为数组已经排序
  • 快速排序对于此类输入的时间复杂度是O(nlogn)。
  • 快速排序对于此类输入的时间复杂度是O(n2)O(n^2)
  • 快速排序无法对此类数组进行排序因为数组已经排序

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

  • g++ -o main main.cpp
  • g++ -o main.cpp main
  • g++ main -o main.cpp
  • g++ main.cpp -o main.cpp

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

  • 4个结点的树
  • 6个结点的树
  • 7个结点的树
  • 8个结点的树

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

  • 1
  • 2
  • 3
  • 4

image

{{ select(14) }}

  • 10
  • 11
  • 12
  • 13

15 现在用如下代码来计算x^n，其时间复杂度为( )

double quick_power(double x,unsigned int 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);

}

{{ select(15) }}

  • O(n)
  • O(1)
  • O(logn)
  • O(nlogn)

二、 阅读程序（程序输入不超过数组成字符串定义的范围：判断题正确填√，错误填×；除特殊说明外，判断题1.5分，选择题3分，共计40分）

1

01 #include

02 using namespace std;

03

04 unsigned short f(unsigned short x) {

05     x ^=x >> 6;

06      x ^=x >> 8;

07     return x;

08 }

09

10 int main() {

11    unsigned short x;

12    cin >> x;

13    unsigned short y = f(x);

14    cout<< y << endl;

15    return 0;

16 }

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

判断题

16 当输入非零时，输出一定不为零（ ） {{ select(16) }}

  • 正确√
  • 错误×

17 将f函数的输入参数的类型改为unsigned int，程序的输出不变（ ） {{ select(17) }}

  • 正确√
  • 错误×

18 当输入为“65535”时，输出为“63”（ ） {{ select(18) }}v

19 当输入为“1”时，输山为“64”。 {{ select(20) }}

  • 正确√
  • 错误×

单选题

20 当输入为“512”时，输出为() {{ select(20) }}

  • "33280"
  • "33410"
  • "33106"
  • "33346"

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

  • "8256”
  • “4130”
  • “4128”
  • “4160“

2

01 #include

02 #include

03 #include

04 #include

05 using namespace std;

06

07 long long solvel(int n) {

08     vector p(n+1，true);

09     vector f(n+1,0),g(n+1,0);

10     f[1] = 1;

11    for (int i= 2;i*i

12    if (p[i]) {

13 vector d;

14 for (int k=i;k

15 reverse(d.begin(),d.end());

16 for (int k :d){

17 for (int j= k;j

18 if (p[j]){

19 p[j] = false;

20 f[j] = i;

21 g[j] = k;

22 }

23}

24}

25 }

26 }

27 for (int i= sqrt(n) + 1;i

28if (p[i]){

29f[i] = i;

30g[i] = i;

31}

32}

33long long sum = 1;

34for (int i=2;i

35f[i]=f[i / g[i]]\*(g[i]\*f[i]-1) / (f[i]-1);

36sum += f[i];

37}

38return sum;

39}

40

41 long long solve2(int n){

42long 1ong sum = 0;

43for (int i= 1;i

44sum +=i\*(n /i);

45}

46return sum;

47}

48

49int main() {

50int n;

51cin >>n;

52cout

53cout

54return 0;

55}

判断题

22 将第15 行删去，输出不变（ ） {{ select(22) }}

答案 F

23 当输入为“10”时，输出的第一行大于第二行。（ ） {{ select(23) }}

答案 F

24 当输入为“1000”时，输出的第一行与第二行相等（ ） {{ select(24) }}

答案 T

单选题

25 solve1(n)的时间复杂度为（ ） {{ select(25) }}

A

B

C

D

答案 D

26 solve2(n)的时间复杂度为（ ） {{ select(26) }}

AO(n^2)BO(n)CO(nlogn)DO(nsqrt(n))

答案 B

27 输入为”5”时，输出的第二行为( ) {{ select(27) }}

A 20 B 21 C 22 D 23

答案 B

3

01 #include

02 #include

03 #include

04

05 using namespace std;

06

07 boo1 f0(vector& a, int m,int k) {

08 int s = 0;

09for (int i=0,j=0;i< a.size();i++) {

10while (a[i]- a[j]> m) j++;

11s+= i-j;

12}

13return s >= k;

14 }

15

16 int f(vector& a,int k) {

17sort(a.begin()，a.end());

18

19int g = 0;

20int h = a.back()- a[0];

21while (g

22intm=g+(h-g)/2;

23if(f0(a,m，k)){

24h=m;

25}else {

26g=m+1;

27}

28}

29

30return g;

31}

32

33 int main() {

34int n, k;

35cin >> n>> k;

36vector a(n,0);

37for (int i=0;i

38cin >>a[i];

39}

40cout

41return 0;

42 }

判断题

28 将第24行的“m”改为“m-1”，输出有可能不变，而剩下情况为少1。（ ） {{ select(28) }}

答案 T

29 将第22行的“g +(h-g)/2改为“(h+g)>>1”，输出不变。（ ） {{ select(29) }}

答案 T

30 当输入为“5 7 2 -4 5 1 -3”，输出为”5”。（ ） {{ select(30) }}

答案 T

单选题

31 设a数组中最大值减最小值加1为A，则f函数的时间复杂度为（ ） {{ select(31) }}

A

B

C

D

答案 C

32 将第10行中的”>”替换为”>=”，那么原输出与现输出的大小关系为（ ） {{ select(32) }}

A 一定小于 B 一定小于等于且不一定小于 C 一定大于等于且不一定大于 D 以上三种情况都不对

答案 B

33 当输入为“5 8 2 -5 3 8 -1 2”时，输出为（ ） {{ select(33) }}

A"13"B"14"C"8"D"15"

答案 B

三、完善程序(单选题，每小题3分，共计 3 分)

1第k小路径

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

试补全程序。

01 #include

02 #include

03 #incTude

04

05 const int MAXN = 100000;

06 const long long LIM =10000000000000000001l

07

08 int n,m,deg[MAXN];

09 std::vector E[MAXN];

10 long 1ong k，f[MAXN];

11

12 int next(std::vector cand, 1ong long &k) {

13std::sort(cand.begin0，cand.end());

14for (int u : cand) {

15if ( ) return u;

16k -= f[u];

17}

18return -1;

19 }

20

21 int main() {

22std::cin >>n>> m >> k;

23for (int i=0;i

24int u, v;

25std::cin >> u>> v;

26E[u].push_back(v);

27++deg[v];

28 }

29std::vector Q;

30for (int i= 0;i

31if (!deg[i]) Q.push_back(i);

32for (int i=0;i

33int u= Q[i];

34for (int v :E[u]){

35if ( ) Q.push_back(v);

36--deg[v];

37}

38}

39 std::reverse(Q.begin()，Q.end());

40for (int u:Q){

41f[u] = 1;

42for (int v : E[u]) f[u] =

43}

44int u= next(Q,k);

45std::cout

46while ( ) {

47;

48u= next(E[u]，k);

49std::cout

50}

51return 0;

52 }

34 处应该填写（ ） {{ select(34) }}

Ak>=f[u]BkCk>f[u]Dk

答案 B

35 处应该填写（ ） {{ select(35) }}

Adeg[v]==1Bdeg[v]==0Cdeg[v]>1Ddeg[v]>0

答案 A

36 处应该填写（ ） {{ select(36) }}

Astd::min(f[u]+f[v],LIM)

Bstd::min(f[u]+f[v]+1,LIM)

Cstd::min(f[u]*f[v],LIM)

Dstd::min(f[u]*(f[v]+1),LIM)

答案 A

37 处应该填写（ ） {{ select(37) }}

Au!=1B!E[u].empty()Ck>0Dk>1

答案 D

38 处应该填写（ ） {{ select(38) }}

Ak+=f[u]Bk-=f[u]C--kD++k

答案 C

2 最大值之和

给定整数序列 a0...an-1，求该序列所有非空连续子序列的最大值之和。上述参数满足1

一个序列的非空连续子序列可以用两个下标l和r(其中0

例如，当原序列为[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]和[2,2] 虽然是原序列的子序列，但不是连续子序列，所以不应该被计算。另外，注意其中有一些值相同的子序列，但由于他们在原序列中的下标不同，属于不同的非空连续子序列，所以会被分别计算.解决该问题有许多算法，以下程序使用分治算法时间复杂度 O(nlogn)。

试补全程序

01 #include

02 #include

03 #include

04

05 const int MAXN = 100000;

06

07 int n;

08 int a[MAXN];

09 long 1ong ans;

10

11 void solve(int l, int r) [

12 if(l+1==r){

13ans += a[l];

14return;

15}

16int mid=(l+r)>>1;

17 std::vector pre(a + mid,a+r);

18for (int i=l;i

19std::vector sum(r - mid + 1);

20for (int i=0;i

21for (int i=mid-1,j=mid,max = 0;i>= l;--i){

22while (j

23max = std::max(max,a[i]);

24ans += ;

25ans += ;

26}

27solve(l，mid);

28solve(mid，r);

29 }

30

31 int main(){

32 std::cin >> n;

33 for (int i=0;i> a[i];

34

35std::cout

36return 0;

37 }

39 处应填（ ） {{ select(39) }}

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

Bpre[i + 1]= std::max(pre[il,pre[i+ 1])

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

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

答案 D

40 处应填（ ） {{ select(40) }}

Aa[j]< max

Ba[j]< a[i]

Cpre[j - mid]< max

Dpre[j - mid] > max

答案 B

41 处应填（ ） {{ select(41) }}

A(long long)(j - mid)* max

B(long long)(j - mid) * (i - l)* max

Csum[j - mid]

Dsum[j - mid]*(i- l)

答案 A

42 处应填（ ） {{ select(42) }}

A(long long)(r -j)* max

B(long long)(r -j)*i*(mid -i)*max

Csum[r - mid] - sum[j - mid]

D(sum[r - mid] - sum[j - mid])* (mid - i)

答案 C

43处应填（ ） {{ select(43) }}

Asolve(0,n)Bsolve(0,n - 1)

Csolve(1,1)Dsolve(1,n - 1)

答案 A

Statistics

  1. About
  2. Contact Us
  3. Privacy
  4. Terms of Service
  5. Copyright Complaint
  6. Language
  7. Legacy mode
  8. Theme
  2. 粤ICP备2023010009号-2

  4. 粤公网安备 44011102003332号
  • Worker 0, 22ms
  • Powered by Hydro v4.9.17 Community