2023年信息學(xué)CSP-S組初賽真題及參考答案

2023-09-20 13:52|編輯: 常老師|閱讀: 2102

摘要

2023信息學(xué)CSP-J/S初賽已經(jīng)結(jié)束，本文整理了2023年信息學(xué)CSP-S組初賽真題及參考答案，供考生參考。

2023信息學(xué)CSP-J/S認(rèn)證，分別舉行第一輪認(rèn)證、第二輪認(rèn)證。CSP-J/S認(rèn)證分入門級和提高級兩個組別，難度不同。CSP-J/S第一輪為集中筆試；第二輪為現(xiàn)場集中上機(jī)認(rèn)證。2023年9月16日上午11:30，CSP-J 2023第一輪認(rèn)證結(jié)束，以下為本次比賽真題及參考答案

2023年信息學(xué)CSP-S組初賽真題及參考答案

一、單項選擇題（共15題，每題2分，共計30分：每題有且僅有一個正確選項）

1 在Linux系統(tǒng)終端中，以下那個命令用于創(chuàng)建一個新的目錄（）

A newdir

B mkdir

C create

D mkfold

答案 B

2 由0,1,2,3,4中選取4個數(shù)字，能組成（）個不同四位數(shù)注:最小的四位數(shù)是1000最大的四位數(shù)是9999

A 96

B 18

C 120

D 84

答案 A

3 假設(shè)n 是圖的頂點(diǎn)的個數(shù),m 是圖的邊的個數(shù)，為求解某一問題有下面四種不同時間復(fù)雜度的算法,對于m=O（n）的稀疏圖而言下面的四個選項，哪一項的漸近時間復(fù)雜度最小

A O（m*sqrt（logn）*loglogn）

B O（n^2+m）

C O（n^2/logm+mlogn）

D O（m+nlogn）

答案 A

4 假設(shè)有n 根柱子，需要按照以下規(guī)則依次放置編號為1、2、3、...的圓環(huán):每根柱子的底部固定，頂部可以放入圓環(huán)，每次從柱子頂部放入圓環(huán)時，需要保證任何兩個相鄰圓環(huán)的編號之和是一個完全平方數(shù)。請計算當(dāng)有4根柱子時，最多可以放置（）個圓環(huán)

A 7

B 9

C 11

D 5

答案 C

5 以下對數(shù)據(jù)結(jié)構(gòu)的表述不恰當(dāng)?shù)囊豁検?/p>

A 隊列是一種先進(jìn)先出（FIFO）的線性結(jié)構(gòu)

B 哈夫曼樹的構(gòu)造過程主要是為了實(shí)現(xiàn)圖的深度優(yōu)先搜索

C 散列表是一種通過散列函數(shù)將關(guān)鍵字映射到存儲位置的數(shù)據(jù)結(jié)構(gòu)

D 二又樹是一種每個結(jié)點(diǎn)最多有兩個子結(jié)點(diǎn)的樹結(jié)構(gòu)

答案 B

6 以下連通無向圖中，（）一定可以用不超過兩種顏色進(jìn)行染色

A 完全三叉樹

B 平面圖

C 邊雙連通圖

D歐拉圖

答案 A

7 最長公共子序列長度常常用來衡量兩個序列的相似度。其定義如下:給定兩個序列X={x1,x2,x3,...xm}和Y={y1,y2,y3...yn},最長公共子序列（LCS）問題的目標(biāo)是找到一個最長的新序列Z= {z1,z2,z3...zk},使得序列既是序列X 的子序列，又是序列Y的子序列，且序列Z的長度k 在滿足上述條件的序列里是最大的。（注:序列A 是序列B 的子序列，當(dāng)且僅當(dāng)在保持序列B 元素順序的情況下，從序列B中刪除若千個元素，可以使得剩余的元素構(gòu)成序列A。測序列“ABCAAAABA”和“ABABCBABA”的最長公共子序列長度為（）

A 4

B 5

C 6

D 7

答案 C

8 一位玩家正在玩一個特殊的擲骰子的游戲，游戲要求連續(xù)擲兩次骰子，收益規(guī)則如下:玩家第一次擲出x點(diǎn)，得到2x元;第二次擲出y點(diǎn)，當(dāng)y=x 時玩家會失去之前得到的2x元而當(dāng)y!=x時玩家能保住第一次獲得的2x元。上述x,y∈[1,2,3,4,5,6]。例如:玩家第一次擲出3點(diǎn)得到6元后，但第二次再次擲出3點(diǎn)，會失去之前得到的6元，玩家最終收益為0元:如果玩家第一次擲出3點(diǎn)第二次擲出4點(diǎn)，則最終收益是6元。假設(shè)骰子挑出任意一點(diǎn)的概率均為1/6,玩家連續(xù)擲兩次般子后所有可能情形下收益的平均值是多少?

A 7

B 35/6

C 16/3

D 19/3

答案 B

9 假設(shè)我們有以下的C++代碼:

inta=5,b=3,c=4;

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

提示:在 C++中，邏輯運(yùn)算的優(yōu)先級從高到低依次為: 邏輯非（!）邏輯與（&&）、邏輯或（||）。位運(yùn)算的優(yōu)先級從高到低依次為: 位非（~）、位與（&）、位異或（^）、位或（|）。同時，雙目位運(yùn)算的優(yōu)先級高于雙目邏輯運(yùn)算:邏輯非和位非優(yōu)先級相同，且高于所有雙目運(yùn)算符

A true

B false

C 1

D 0

答案 A

10 假設(shè)快速排序算法的輸入是一個長度為n的已排序數(shù)組，且該快速排序算法在分治過程總是選擇第1個元素作為基準(zhǔn)元素。以下哪個選項描述的是在這種情況下的快速排序行為?

A 快速排序?qū)τ诖祟愝斎氲谋憩F(xiàn)最好因為數(shù)組已經(jīng)排序

B 快速排序?qū)τ诖祟愝斎氲臅r間復(fù)雜度是O（nlogn）。

C 快速排序?qū)τ诖祟愝斎氲臅r間復(fù)雜度是O（n^2）

D 快速排序無法對此類數(shù)組進(jìn)行排序因為數(shù)組已經(jīng)排序

答案 C

11 以下哪個命令，能將一個名為“main.cpp”的 C++源文件，編譯并生成一個名為"main“的可執(zhí)行文件? （）

A g++ -o main main.cpp

B g++ -o main.cpp main

Cg++main -o main.cpp

D g++ main.cpp -o main.cpp

**答案 A **

12 在圖論中，樹的重心是樹上的一個結(jié)點(diǎn)，以該結(jié)點(diǎn)為根時，使得其所有的子樹中結(jié)點(diǎn)數(shù)最多的子樹的結(jié)點(diǎn)數(shù)最少。一棵樹可能有多個重心。請問下面哪種樹一定只有一個重心（）

A 4個結(jié)點(diǎn)的樹

B 6個結(jié)點(diǎn)的樹

C 7個結(jié)點(diǎn)的樹

D 8個結(jié)點(diǎn)的樹

答案 C

13 如圖是一張包含6個頂點(diǎn)的有向圖，但頂點(diǎn)間不存在拓?fù)湫颉Ｈ绻獎h除其中一條邊，使這6個頂點(diǎn)能進(jìn)行拓?fù)渑判?，請問總共有多少條邊可以作為候選的被刪除邊?

A 1

B 2

C 3

D 4

答案 C

A 10

B 11

C 12

D 13

答案 B

15 現(xiàn)在用如下代碼來計算x^n，其時間復(fù)雜度為（）

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）;

}

A O（n）

B O（1）

C O（logn）

D O（nlogn）

答案 A

二、閱讀程序（程序輸入不超過數(shù)組成字符串定義的范圍：判斷題正確填√，錯誤填×；除特殊說明外，判斷題1.5分，選擇題3分，共計40分）

01 #incTude<iostream>

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 << end1;

15 return 0;

16 }

假設(shè)輸入的x是不超過65535的自然數(shù)，完成下面的判斷題和單選題

判斷題

16 當(dāng)輸入非零時，輸出一定不為零（）

答案 T

17 將f函數(shù)的輸入?yún)?shù)的類型改為unsigned int，程序的輸出不變（）

答案 F

18 當(dāng)輸入為“65535”時，輸出為“63”（）

答案 T

19 當(dāng)輸入為“1”時，輸山為“64”。

答案 F

單選題

20 當(dāng)輸入為“512”時，輸出為（）

A “33280” B “33410” C “33106” D “33346"

答案 B

21 當(dāng)輸入為“64”時，執(zhí)行完第5行后x的值為（）

A "8256” B “4130” C “4128” D “4160“

答案 D

判斷題

22 將第15 行刪去，輸出不變（）

答案 F

23 當(dāng)輸入為“10”時，輸出的第一行大于第二行。（）

答案 F

24 當(dāng)輸入為“1000”時，輸出的第一行與第二行相等（）

答案 T

單選題

25 solve1（n）的時間復(fù)雜度為（）

答案 D

26 solve2（n）的時間復(fù)雜度為（）

A O（n^2） B O（n） C O（nlogn） D O（nsqrt（n））

答案 B

27 輸入為”5”時，輸出的第二行為（）

A 20 B 21 C 22 D 23

答案 B

判斷題

28 將第24行的“m”改為“m-1”，輸出有可能不變，而剩下情況為少1。（）

答案 T

29 將第22行的“g +（h-g）/2改為“（h+g）>>1”，輸出不變。（）

答案 T

30 當(dāng)輸入為“5 7 2 -4 5 1 -3”，輸出為”5”。（）

答案 T

單選題

31 設(shè)a數(shù)組中最大值減最小值加1為A，則f函數(shù)的時間復(fù)雜度為（）

答案 C

32 將第10行中的”>”替換為”>=”，那么原輸出與現(xiàn)輸出的大小關(guān)系為（）

A 一定小于 B 一定小于等于且不一定小于 C 一定大于等于且不一定大于 D 以上三種情況都不對

答案 B

33 當(dāng)輸入為“5 8 2 -5 3 8 -1 2”時，輸出為（）

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

答案 B

三、完善程序（單選題，每小題3分，共計 3 分）

1第k小路徑

給定一張n個點(diǎn) m 條邊的有向無環(huán)圖，頂點(diǎn)編號從0到n-1。對于一條路徑，我們定義“路徑序列”為該路徑從起點(diǎn)出發(fā)依次經(jīng)過的頂點(diǎn)編號構(gòu)成的序列。求所有至少包含一個點(diǎn)的簡單路徑中，“路徑序列”字典序第k小的路徑。保證存在至少 k條路徑，上述參數(shù)滿足1<=n,m<=10^5 和1<=k<=10^18表示 .在程序中，我們求出從每個點(diǎn)出發(fā)的路徑數(shù)量。超過10^18的數(shù)都用 10^18表示。然后我們根據(jù)k的值和每個頂點(diǎn)的路徑數(shù)量，確定路徑的起點(diǎn)，然后可以類似地依次求出路徑中的每個點(diǎn)。

試補(bǔ)全程序。

34 ①處應(yīng)該填寫（）

Ak>=f[u]Bk<=f[u]Ck>f[u]Dk < p=""> <>

答案 B

35 ②處應(yīng)該填寫（）

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

答案 A

36 ③處應(yīng)該填寫（）

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 ④處應(yīng)該填寫（）

Au!=1B!E[u].empty（）Ck>0Dk>1

答案 D

38 ⑤處應(yīng)該填寫（）

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

答案 C

2 最大值之和

給定整數(shù)序列 a0...an-1，求該序列所有非空連續(xù)子序列的最大值之和。上述參數(shù)滿足1<=n<=10^5 和 1<=ai<=10^8

一個序列的非空連續(xù)子序列可以用兩個下標(biāo)l和r（其中0 <=l<=r<=n）表示，對應(yīng)的序列為al,al+1,...ar。兩個非空連續(xù)子序列不同，當(dāng)且僅當(dāng)下標(biāo)不同

例如，當(dāng)原序列為[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] 雖然是原序列的子序列，但不是連續(xù)子序列，所以不應(yīng)該被計算。另外，注意其中有一些值相同的子序列，但由于他們在原序列中的下標(biāo)不同，屬于不同的非空連續(xù)子序列，所以會被分別計算.解決該問題有許多算法，以下程序使用分治算法時間復(fù)雜度 O（nlogn）。

試補(bǔ)全程序