請點(diǎn)擊↑關(guān)注、收藏，本博客免費(fèi)為你獲取精彩知識分享！有驚喜喲??！?

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

1.以下關(guān)于CSP-J/S的描述錯誤的是（）

A.參加CSP-S/J兩組兩輪認(rèn)證均須在網(wǎng)上注冊報(bào)名。未注冊者，無認(rèn)證成績

B.CSP-J/S是中國計(jì)算機(jī)學(xué)會舉辦的程序設(shè)計(jì)競賽

C.CSP-JS第二輪實(shí)行網(wǎng)上注冊、報(bào)名，未通過網(wǎng)上報(bào)名的認(rèn)證者可向所在省份特派員申請獲得第二輪參加認(rèn)證的資格

D.CSP-J/S認(rèn)證成績優(yōu)異者，可參加NOI省級選拔，省級選拔成績優(yōu)異者可參加NOI

2.在8位二進(jìn)制補(bǔ)碼中，10110110表示的是十進(jìn)制下的()??

A.202??????B.74??????C.-202??????D.-74

3.2019年10月14日是星期一，1978年10月14日是()

A.星期日?????????B.星期五?????????C.星期一??????D.星期六

4.圖G是一棵n節(jié)點(diǎn)的樹，G上有（）條邊

A.n????????????B.2*n????????????C.n-1?????????D.n+1

5.由五個(gè)不同的節(jié)點(diǎn)構(gòu)成的樹有（）種

A. 3125????B. 125???C.32???D.1024

6.有一個(gè)長為6的A序列：{3,20,4,6,1}，現(xiàn)通過進(jìn)行交換其中相鄰兩個(gè)數(shù)字的操作進(jìn)行排序，要將A序列排成從小到大的遞增序列最少要進(jìn)行多少次交換操作（）

A.5????????B.6????????????C.7????????????D.15

7.某算法計(jì)算時(shí)間表示為遞推關(guān)系式：??T(N)=N+T(N/2) ,則該算法時(shí)間復(fù)雜度為( )。

A.O(N*N)??????B.O(NlogN)??????C.O(N)??????D.O(1)

8.一棵6節(jié)點(diǎn)二叉樹的中序遍歷為DBAGECF,先序遍歷為ABDCEGF，后序遍歷為（）

A.??DGBEFAC?????????????????????B.??GBEACFD?????????????????????C.??DBGEFCA??????????????D.?ABCDEFG

9.一張有9個(gè)節(jié)點(diǎn)的無向圖最多有()條邊

A.40?????????B.81?????????C.72??????D.36

10.下列不屬于面向?qū)ο蟪绦蛟O(shè)計(jì)語言的是( )

A.C++?????????B.?C?????????C.JAVA??????D.C#

11.G是一張有n個(gè)點(diǎn)m條邊的連通圖，必須刪去（）條邊才能將其變成一棵n節(jié)點(diǎn)的樹

A.1?????????B.m-n-1??????C.m+n-1??????D.m-n+1

12.字符串”abcab”本質(zhì)不同的子串個(gè)數(shù)（）,不考慮空串

A.15? ? ?B.14? ? ? C.13? ? ? ?D.12

13.十進(jìn)制小數(shù)13.375對應(yīng)的二進(jìn)制數(shù)是()：??

A.1101.011????B.1011.011????C.1101.101???D.1010.01

14.若某算法的計(jì)算時(shí)間表示為遞推關(guān)系：

則該算法的復(fù)雜度為()

15.?一家三口人，恰好僅有兩個(gè)人生日在同一天的概率是（）???【假設(shè)每年都是365天】

A．1/365?????????B.365/（364*365）???????????????C.（3*364）/（365*365）????????????D.1/12

二、閱讀程序?qū)懡Y(jié)果(共8小題，每小題5分，共計(jì)40分)

第一題

#include

using namespace std;

int a,b,c;

int main()

{

???cin>>a>>b>>c;

???int t=b;

???b=a,a=t;

???c=a;

???cout<<a<<" "<<b<<" "<<c;< span=""></c;<>

}

16.?若輸入3 9 1，則輸出9 3 3

A.正確

B.錯誤

17.?若輸入12300400000 3 7，將一定能輸出3 12300400000 3

A.正確

B.錯誤

18.該程序中，頭文件#include可以改成#include

A.正確

B.錯誤

19.若輸入3 6 9，輸出()

A. 6 3 6

B. 9 3 3

C. 6 9 3

D. 6 3 3

20.若將c=a改成c=t,則若輸入3 6 9，輸出()

A. 6 3 6

B. 9 3 3

C. 6 9 3

D. 6 3 3

21.若將c=a改成c=b,則若輸入3 6 9，輸出()

A. 6 3 6

B. 6 3 9

C. 6 3 3

D. 3 6 3

第二題

#include

#include

#include

using namespace std;

int w[35000],d[35000],dp[35000];

int main()

{

????int?n,m;

????scanf("%d%d",&n,&m);

????for(int?i=1;i<=n;i++)< span="">

???????scanf("%d%d",&w[i],&d[i]);

????for(int?i=1;i<=n;i++)< span="">

????{

????????for(int?j=m;j>=w[i];j--)

????????{

????????????dp[j]=max(dp[j],dp[j-w[i]]+d[i]);

????????}

????}

????printf("%d\n",dp[m]);

????return?0;

}

22. 上述代碼中，雙重循環(huán)里循環(huán)變量j的枚舉順序改為從w[i]到m，輸出結(jié)果一定不變

A.正確

B.錯誤

23. 上述代碼中，雙重循環(huán)中變量i的枚舉順序改為從n到1，輸出結(jié)果一定不變

A.正確

B.錯誤

24.?當(dāng)輸入為：

?? 4 6

?? 1 4

?? 2 6

?? 3 12

?? 2 7

輸出為()

A.17

B.28

C.29

D.23

25.若輸入數(shù)據(jù)中，1<=n<=30000,1<=m<=30000,1<=w[i]<=30000,1<=d[i]<=30000,則所求答案一定沒有溢出()< span="">

A.正確

B.錯誤

26.若輸入數(shù)據(jù)中，1<=n<=30000,1<=m<=30000,1<=w[i]<=30000,1<=d[i]<=1000000000,則所求答案一定沒有溢出()< span="">

A.正確

B.錯誤

27.上述代碼的時(shí)間復(fù)雜度為()

A.O(n)

B.O(n*n*m)

C.O(n*m)

D.O(n*m*m)

第三題

#include

#include

#include

#define N 500+10

using namespace std;

int a[N],n;

int main()

{

?cin>>n;

?for(int i=1;i<=n;i++)cin>>a[i];

?for(int i=1;i<n;i++)< span=""></n;i++)<>

?{

?int tmp=i;

?for(int j=i+1;j<=n;j++)< span="">

?if(a[j]<a[tmp])tmp=j;< span=""></a[tmp])tmp=j;<>

?swap(a[i],a[tmp]);

?}

?for(int i=1;i<=n;i++)cout<<a[i]<<" ";

?cout<<endl;< span=""></endl;<>

?return 0;

}

28. 上述代碼實(shí)現(xiàn)了對一個(gè)長度為n的序列進(jìn)行排序（）

A.正確

B.錯誤

29. 我們將上述算法稱為（）

A. KMP

B. 冒泡排序

C. 選擇排序

D. 歸并排序

30.上述代碼的時(shí)間復(fù)雜度為()

A. O(n)??B. O(nlogn)??C. O(n*n)???D. O(n*n*n)

31.若輸入數(shù)據(jù)為：

5

3 2 1 5 4

則if(a[j]<a[tmp])這句話中的條件會成立多少次（即后面的tmp=j會被執(zhí)行多少次)? </a[tmp])這句話中的條件會成立多少次（即后面的tmp=j會被執(zhí)行多少次)()

A. 5????B. 7????C.3???D.4

32.去掉頭文件#include后程序仍能正常編譯運(yùn)行()

A.正確

B.錯誤

33.去掉using namespace std;后程序仍能正常編譯運(yùn)行()

A.正確

B.錯誤

五、完善程序(每題15分，共計(jì)30分)

1.?請完善下面的程序，使用BFS統(tǒng)計(jì)一張邊權(quán)都為1的圖中，從給定起點(diǎn)到所有點(diǎn)的距離：

#include

#include

#include

#define N 200020

using namespace std;

int n,m;

vectorG[N];

int q[N],hd,tl;

int dis[N];

void BFS(___（1）_____)

{

???hd=1,tl=0;

???for(int i=1;i<=n;i++)dis[i]=-1;< span="">

???q[++tl]=st,dis[st]=0;

???while(____(2)_____)

???{

??????int u=q[hd++];

??????for(int i=0;i<g[u].size();i++)< span=""></g[u].size();i++)<>

??????{

?????????int v=G[u][i];

?????????if(____(3)____)continue;

?????????dis[v]=dis[u]+1;

?????????q[++tl]=v;

??????}

???}

}

int main()

{

???scanf("%d%d",&n,&m);

???for(int i=1;i<=m;i++)< span="">

???{

??????int x,y;

??????scanf("%d%d",&x,&y);

??????G[x].push_back(y);

??????______(4)________;

???}

???int st;

???scanf("%d",&st);

???BFS(st);

???for(_____(5)_____)printf("%d ",dis[i]);

}

34.上述程序___(1)___中應(yīng)該填寫（）

A.int u;

B.int st;

C.int &st;

D.int st

35.上述程序___(2)___中應(yīng)該填寫（）

A.hd<tl< span=""></tl<>

B.hd>tl

C.hd<=tl< span="">

D.hd>=tl

36.上述程序___(3)___中應(yīng)該填寫（）

A.vis[v]==true

B.dis[v]<=dis[u]< span="">

C.dis[v]!=-1

D.dis[v]>dis[u]

37.?上述程序___(4)___中應(yīng)該填寫（）

A.G[y].push_back(x)

B.G[y].insert(x)

C.G[y][x]=1

D.G[y].push(x)

38.?上述程序___5___中應(yīng)該填寫（）

A.?int j=1;j<=n;j++< span="">

B.?int i=1;i<=n;i++< span="">

C.?int i=0;i<n;i++< span=""></n;i++<>

D.?int i=1,i<=n,i++< span="">

2.(拓?fù)渑判?給出一張n節(jié)點(diǎn)m條邊的有向圖，求出該圖的一個(gè)拓?fù)渑判?，若無拓?fù)渑判蜉敵?1

輸入：

第一行兩個(gè)正整數(shù)?n,m?表示點(diǎn)數(shù)和邊數(shù)。
接下來?m?行，每行三個(gè)正整數(shù)?x,y表示節(jié)點(diǎn)?x->y之間有一條邊。

輸出：

一個(gè)拓?fù)湫颍喊赐負(fù)湫蜉敵鳇c(diǎn)的編號。若拓?fù)湫虿晃ㄒ?，輸出任意一個(gè)均可。若無拓?fù)湫颍敵?-1.

#include

#include

#include

#define N 200020

using namespace std;

int n,m;

vectorG[N];

int q[N],hd,tl;

int du[N];

int ans[N],tot;

void topo()

{

?? hd=1,tl=0;

?? for(int i=1;i<=n;i++)if(___(1)____)q[++tl]=i;< span="">

?? while(hd<=tl)< span="">

?? {

?? ?? int u=q[hd++];

?? ?? ans[++tot]=u;

?? ?? for(int i=0;____(2)____;i++)

?? ?? {

?? ?? ?? int v=G[u][i];

?? ?? ?? du[v]--;

?? ?? ?? if(!du[v])____(3)____;

?? ?? }

?? }

?? if(tot!=n)puts("-1");

?? else

?? {

?? ?? for(int i=1;i<=n;i++)< span="">

?? ?? ?? printf("%d ",ans[i]);

?? }

}

int main()

{

?? scanf("%d%d",&n,&m);

?? for(int i=1;i<=m;i++)< span="">

?? {

?? ?? int x,y;

?? ?? scanf("%d%d",&x,&y);

?? ?? _____(4)___________;

?? ?? _____(5)___________;

?? }

?? topo();

}

39.?上述程序___1___中應(yīng)該填寫（）

A.?du[i]

B.?q[i]

C.?hd<=tl< span="">

D.?!du[i]

40.?上述程序___2___中應(yīng)該填寫（）

A.?i<=n< span="">

B.?i<n< span=""></n<>

C.?i<g[u].size()< span=""></g[u].size()<>

D.?i<=g[u].size()< span="">

41.?上述程序___3___中應(yīng)該填寫（）

A.?q[++tl]=v

B.?q[tl++]=v

C.?q[++hd]=v

D.?q[hd++]=v

42.?上述程序___4___中應(yīng)該填寫（）

A.G[y].push_back(x)

B.G[x].push_back(y)

C.G[x].push(y)

D.G[y].push(x)

43.?上述程序___5___中應(yīng)該填寫（）

A.G[y].push_back(x)

B.G[y].push(x)

C.du[y]++

D.du[x]++

CSP-S模擬卷參考答案

?2021年CSP-S提高級第一輪試題

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

1.?以下不屬于面向?qū)ο蟪绦蛟O(shè)計(jì)語言的是（D）。

A. C++

B. Python

C. Java

D. C

2.?以下獎頊與計(jì)算機(jī)領(lǐng)域最相關(guān)的是（B）。

A.?奧斯卡獎

B.?圖靈獎

C.?諾貝爾獎

D.?普利策獎

3.?目前主流的計(jì)算機(jī)儲存數(shù)據(jù)最終都是轉(zhuǎn)換成（A）數(shù)據(jù)進(jìn)行存儲。

A.?二進(jìn)制

B.?十進(jìn)制

C.?八進(jìn)制

D.?十六進(jìn)制

4.?以比較作為基本運(yùn)算，在N個(gè)數(shù)中找出最大數(shù)，最壞情況下所需要的最少的比較次數(shù)為（C）。

A. N^2

B. N

C. N-1

D. N+1

5.??對于入棧順序?yàn)閍,b,c,d,e的序列，下列（D）不是合法的出棧序列。

A. a,b,c,d,e

B. e,d,c,b,a

C. b,a,c,d,e

D. c,d,a,e,b

6.?對于有n個(gè)頂點(diǎn)、m條邊的無向聯(lián)通圖（m>n）,需要刪掉（D）條邊才能使其成為一棵樹。

A. n-1

B. m-n

C. m-n-1

D. m-n+1

7.?二進(jìn)制數(shù)101.11對應(yīng)的十進(jìn)制數(shù)是（C）。

A. 6.5

B. 5.5

C. 5.75

D. 5.25

8.?如果一棵二叉樹只有根結(jié)點(diǎn)，那么這棵二叉樹高度為1。請問高度為5的完全二叉樹有（A）種不同形態(tài)？

A. 16

B. 15

C. 17

D. 32

9.?表達(dá)式a*(b+c)*d的后綴表達(dá)式為（B），,其中”*”和”+”是運(yùn)算符。

A. **a+bcd

B. abc+*d*

C. abc+d**

D. *a*+bcd

10. 6個(gè)人，兩個(gè)人組一隊(duì)，總共組成三只，不區(qū)分隊(duì)伍的編號，不同的組隊(duì)情況有（B）種。

A. 10

B. 15

C. 30

D. 20

11.?在數(shù)據(jù)壓縮編碼中的哈夫曼編碼方法，在本質(zhì)是一種（B）的策略。

A.?枚舉

B.?貪心

C.?遞歸

D.?動態(tài)規(guī)劃

12.?由1, 1, 2, 2, 3這五個(gè)數(shù)字組成不同的三位數(shù)有（A）種。

A. 18

B. 15

C. 12

D. 24

13.?考慮如下遞歸算法

solve(n)

if n<=1 return 1

else if n>=5 return n*solve(n-2)

else return n*solve(n-1)

則調(diào)用solve(7)得到的返回結(jié)果為（C）。

A. 105

B. 840

C. 210

D. 420

14.?以a為起點(diǎn)，對右邊的無向圖進(jìn)行深度優(yōu)先遍歷，則b、c、d、e四個(gè)點(diǎn)中有可能作為最后一個(gè)遍歷到的點(diǎn)個(gè)數(shù)為（B）。

A. 1

B. 2

C. 3

D. 4

15.?有四個(gè)人要從A點(diǎn)做一條船過河到B點(diǎn)，船一開始在A點(diǎn)。該船一次最多可坐兩個(gè)人。已知這四個(gè)人中每個(gè)人獨(dú)自坐船的過河時(shí)間分別為1, 2, 4, 8,?且兩個(gè)人坐船的過河時(shí)間為兩人獨(dú)自過河時(shí)間的較大者。則最短（B）時(shí)間可以讓四個(gè)人都過河到B點(diǎn)（包括從B點(diǎn)把船開回A點(diǎn)時(shí)間）。

A. 14

B. 15

C. 16

D. 17?

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

(1)

判斷題

16.?輸入的n等于1001時(shí)，程序不會發(fā)生下標(biāo)越界。（X）

17.?輸入的a[i]必須全為正整數(shù)，否則程序?qū)⑾萑胨姥h(huán)。（X）

18.?當(dāng)輸入”5 2 11 9 16 10”時(shí)，輸出為”3 4 3 17 5”?。（X）

19.?當(dāng)輸入為”1 511998“時(shí)，輸出為”18”?。（√）

20.?將源代碼中g(shù)函數(shù)的定義（13-16行）移到main函數(shù)的后面，程序可以正常編譯運(yùn)行。（X）

單選題

21.?當(dāng)輸入為”2 -65536 2147483647”時(shí)，輸出為（B）。

A. "65532 33”

B. "65552 32"

C. "65535 34"

D. "65554 33"?

(2)

判斷題

22.?輸出的第二行一定是由小寫字母、大寫字母、數(shù)字和“+”、“/”、“=”構(gòu)成的字符串。（X）

23.?可能存在輸入不同，但輸出的第二行相同的情形。（√）

24.?輸出的第一行為“-1”。（?√）

單選題

25.?設(shè)輸入字符串長度為n，decode函數(shù)的時(shí)間復(fù)雜度為（B）。

A. θ(√n)

B. θ(n)

C. θ(nlogn)

D. θ(n^2)

26.?當(dāng)輸入為“Y3Nx”時(shí)，輸出的第二行為（B）。

A. “csp”

B. “csq”

C. “CSP”

D. “Csp”

27.?（3.5分）當(dāng)輸入為“Y2NmIDIwMjE=”時(shí)，輸出的第二行為（C）。

A. “ccf2021”

B. “ccf2022”

C. “ccf 2021”

D. “ccf 2022”?

(3)

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

判斷題

28.?若輸入不為"1"，把第12行刪去不會影響輸出的結(jié)果。（√）

29.?（2分）第24行的" f[i]/c[i*k]"可能存在無法整除而向下取整的情況。（X）

30.?（2分）在執(zhí)行完init()后，f數(shù)組不是單調(diào)遞增的，但g數(shù)組是單調(diào)遞增的。（X）

單選題

31. init函數(shù)的時(shí)間復(fù)雜度為（A）。

A. θ(n)

B. θ(nlogn)

C. θ(n√n)

D. θ(n^2)

32.?在執(zhí)行完init()后，f[1], f[2], f[3] ...... f[100]中有（C）個(gè)等于2。

A. 23

B. 24

C. 25

D. 26

33.?（4分）當(dāng)輸入"1000"時(shí)，輸出為（C）。

A. "15 1340"

B. "15 2340"

C. "16 2340"

D. "16 1340"

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

?(1)（Josephus?問題）有?n?個(gè)人圍城一個(gè)圈，依次標(biāo)號?0?至?n-1。從?0?號開始，依次?0, 1, 0, 1, ...?交替報(bào)數(shù)，報(bào)到?1?的人會離開，直至圈中只剩下一個(gè)人。求最后剩下人的編號。

試補(bǔ)全模擬程序。

34. ①處應(yīng)填（D）

A. i < n

B. c < n

C. i < n - 1

D. c < n - 1

35. ②處應(yīng)填（C）

A. i % 2 == 0

B. i % 2 == 1

C. p

D. !p

36. ③處應(yīng)填（C）

A. i++

B. i = (i + 1) % n

C. c++

D. p ^= 1

37. ④處應(yīng)填（D）

A. i++

B. i = (i + 1) % n

C. c++

D. p ^= 1

38. ⑤處應(yīng)填（B）

A. i++

B. i = (i + 1) % n

C. c++

D. p ^= 1?

(2)（矩形計(jì)數(shù)）平面上有n個(gè)關(guān)鍵點(diǎn)，求有多少個(gè)四條邊都和x軸或者y軸平行的矩形，滿足四個(gè)頂點(diǎn)都是關(guān)鍵點(diǎn)。給出的關(guān)鍵點(diǎn)可能有重復(fù)，但完全重合的矩形只計(jì)一次。

試補(bǔ)全枚舉算法。

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

A. a.x != b.x ? a.x < b.x : a.id < b.id

B. a.x != b.x ? a.x < b.x : a.y < b.y

C. equals(a,b) ? a.id < b.id : a.x < b.x

D. equals(a,b) ? a.id < b.id : (a.x != b.x ? a.x < b.x : a.y < b.y)

40. ②處應(yīng)填（D）

A. i == 0 || cmp(A[i], A[i - 1])

B. t == 0 || equals(A[i], A[t - 1])

C. i == 0 || !cmp(A[i], A[i - 1])

D. t == 0 || !equals(A[i], A[t - 1])

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

A. b - (b - a) / 2 + 1

B. (a + b + 1) >> 1

C. (a + b) >> 1

D. a + (b - a + 1) / 2

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

A. !cmp(A[mid], p)

B. cmp(A[mid], p)

C. cmp(p, A[mid])

D. !cmp(p, A[mid])

43. ⑤處應(yīng)填（D）

A. A[i].x == A[j].x

B. A[i].id < A[j].id

C. A[i].x == A[j].x && A[i].id < A[j].id

D. A[i].x < A[j].x && A[i].y < A[j].y

2021年CSP-S提高級第一輪試題? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?

文章來源地址http://www.zghlxwxcb.cn/news/detail-409361.html

到了這里，關(guān)于CSP-J初賽模擬試題及答案的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！