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

相關(guān)推薦：2023年CSP-J/S報(bào)名、認(rèn)證試題及證書作用、NOI常見問(wèn)題匯總

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

一、 單項(xiàng)選擇題（共15題，每題2分，共計(jì)30分：每題有且僅有一個(gè)正確選項(xiàng)）

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

A newdir

B mkdir

C create

D mkfold

答案 B

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

A 96

B 18

C 120

D 84

答案 A

3 假設(shè)n 是圖的頂點(diǎn)的個(gè)數(shù),m 是圖的邊的個(gè)數(shù)，為求解某一問(wèn)題有下面四種不同時(shí)間復(fù)雜度的算法,對(duì)于m=O（n）的稀疏圖而言下面的四個(gè)選項(xiàng)，哪一項(xiàng)的漸近時(shí)間復(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ī)則依次放置編號(hào)為1、2、3、...的圓環(huán):每根柱子的底部固定，頂部可以放入圓環(huán)，每次從柱子頂部放入圓環(huán)時(shí)，需要保證任何兩個(gè)相鄰圓環(huán)的編號(hào)之和是一個(gè)完全平方數(shù)。請(qǐng)計(jì)算當(dāng)有4根柱子時(shí)，最多可以放置（ ）個(gè)圓環(huán)

A 7

B 9

C 11

D 5

答案 C

5 以下對(duì)數(shù)據(jù)結(jié)構(gòu)的表述不恰當(dāng)?shù)囊豁?xiàng)是

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

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

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

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

答案 B

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

A 完全三叉樹

B 平面圖

C 邊雙連通圖

D歐拉圖

答案 A

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

A 4

B 5

C 6

D 7

答案 C

8 一位玩家正在玩一個(gè)特殊的擲骰子的游戲，游戲要求連續(xù)擲兩次骰子，收益規(guī)則如下:玩家第一次擲出x點(diǎn)，得到2x元;第二次擲出y點(diǎn)，當(dāng)y=x 時(shí)玩家會(huì)失去之前得到的2x元而當(dāng)y!=x時(shí)玩家能保住第一次獲得的2x元。上述x,y∈[1,2,3,4,5,6]。例如:玩家第一次擲出3點(diǎn)得到6元后，但第二次再次擲出3點(diǎn)，會(huì)失去之前得到的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)先級(jí)從高到低依次為: 邏輯非（!）邏輯與（&&）、邏輯或（||）。位運(yùn)算的優(yōu)先級(jí)從高到低依次為: 位非（~）、位與（&）、位異或（^）、位或（|）。同時(shí)，雙目位運(yùn)算的優(yōu)先級(jí)高于雙目邏輯運(yùn)算:邏輯非和位非優(yōu)先級(jí)相同，且高于所有雙目運(yùn)算符

A true

B false

C 1

D 0

答案 A

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

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

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

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

D 快速排序無(wú)法對(duì)此類數(shù)組進(jìn)行排序因?yàn)閿?shù)組已經(jīng)排序

答案 C

11 以下哪個(gè)命令，能將一個(gè)名為“main.cpp”的 C++源文件，編譯并生成一個(gè)名為"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 在圖論中，樹的重心是樹上的一個(gè)結(jié)點(diǎn)，以該結(jié)點(diǎn)為根時(shí)，使得其所有的子樹中結(jié)點(diǎn)數(shù)最多的子樹的結(jié)點(diǎn)數(shù)最少。一棵樹可能有多個(gè)重心。請(qǐng)問(wèn)下面哪種樹一定只有一個(gè)重心（ ）

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

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

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

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

答案 C

13 如圖是一張包含6個(gè)頂點(diǎn)的有向圖，但頂點(diǎn)間不存在拓?fù)湫?。如果要?jiǎng)h除其中一條邊，使這6個(gè)頂點(diǎn)能進(jìn)行拓?fù)渑判?，?qǐng)問(wèn)總共有多少條邊可以作為候選的被刪除邊?

A 1

B 2

C 3

D 4

答案 C

14

A 10

B 11

C 12

D 13

答案 B

15 現(xiàn)在用如下代碼來(lái)計(jì)算x^n，其時(shí)間復(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

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

1

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是不超過(guò)65535的自然數(shù)，完成下面的判斷題和單選題

判斷題

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

答案 T

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

答案 F

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

答案 T

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

答案 F

單選題

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

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

答案 B

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

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

答案 D

2

判斷題

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

答案 F

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

答案 F

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

答案 T

單選題

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

答案 D

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

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

答案 B

27 輸入為”5”時(shí)，輸出的第二行為（ ）

A 20 B 21 C 22 D 23

答案 B

3

判斷題

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ù)的時(shí)間復(fù)雜度為（ ）

答案 C

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

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

答案 B

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

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

答案 B

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

1第k小路徑

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

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

例如，當(dāng)原序列為[1,2,1,2] 時(shí)，要計(jì)算子序列[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)該被計(jì)算。另外，注意其中有一些值相同的子序列，但由于他們?cè)谠蛄兄械南聵?biāo)不同，屬于不同的非空連續(xù)子序列，所以會(huì)被分別計(jì)算.解決該問(wèn)題有許多算法，以下程序使用分治算法時(shí)間復(fù)雜度 O（nlogn）。

試補(bǔ)全程序

39 ①處應(yīng)填（ ）

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

Aa[j]< max

Ba[j]< a[i]

Cpre[j - mid]< max

Dpre[j - mid] > max

答案 B

41 ③處應(yīng)填（ ）

A（long long）（j - mid）* max

B（long long）（j - mid） * （i - l）* max

Csum[j - mid]

Dsum[j - mid]*（i- l）

答案 A

42 ④處應(yīng)填（ ）

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

Asolve（0,n）Bsolve（0,n - 1）

Csolve（1,1）Dsolve（1,n - 1）

答案 A

聲明：本文由北京高考在線團(tuán)隊(duì)（微信公眾號(hào)：bjgkzx）排版編輯，內(nèi)容來(lái)源于信息學(xué)競(jìng)賽，如有侵權(quán)，請(qǐng)及時(shí)聯(lián)系管理員刪除。