電子學(xué)會(huì)青少年軟件編程(C語(yǔ)言五級(jí))等級(jí)考試真題試卷(2022年3月)-附答案

青少年軟件編程（C語(yǔ)言五級(jí)）等級(jí)考試真題試卷（2022年3月）

題目總數(shù)：4

總分?jǐn)?shù)：100

時(shí)間：不限時(shí)

第1題

數(shù)字變換

問答題

給定一個(gè)包含5個(gè)數(shù)字（0-9）的字符串，例如"02943"，請(qǐng)將"12345"變換到它。你可以采取3種操作進(jìn)行

變換

1.交換相鄰的兩個(gè)數(shù)字

2.將一個(gè)數(shù)字加1。如果加1后大于9，則變?yōu)?

3.將一個(gè)數(shù)字加倍。如果加倍后大于9,則將其變?yōu)榧颖逗蟮慕Y(jié)果除以10的余數(shù)。

最多只能用第2種操作3次，第3種操作2次求最少經(jīng)過多少次操作可以完成變換。

時(shí)間限制：1000

內(nèi)存限制：65536

輸入

有最多100,000組數(shù)據(jù)每組數(shù)據(jù)就是包含5個(gè)數(shù)字的字符串

輸出

對(duì)每組數(shù)據(jù)，輸出將"12345"變換到給定字符串所需要的最少操作步數(shù)。如果無法變換成功，輸出-1

樣例輸入

12435

99999

12374

樣例輸出

1

-1

3

提示

由于測(cè)試數(shù)據(jù)太多，如果對(duì)每組數(shù)據(jù)都從頭進(jìn)行搜索，就會(huì)超時(shí)。建議先做預(yù)處理，即以"12345"作為初始

狀態(tài)做一遍徹底的廣搜，找出"12345"經(jīng)合法變換能夠到達(dá)的所有字符串，并記錄到達(dá)這些字符串各需要多

少步操作。然后對(duì)讀入的每組數(shù)據(jù)，在上述預(yù)處理記錄的結(jié)果中進(jìn)行查詢即可。

答案

參考答案1

#include<iostream>

#include<algorithm>

#include<cstring>

#include<queue>

usingnamespacestd;

#define_init(x,v)memset(x,v,sizeof(x))

intrcd[100000];

boolvis[100000][5][5];

structnode{

inta[5],d,o2,o3;

};

queue<node>q;

voidin(){

_init(rcd,-1);

nodes={1,2,3,4,5,0,3,2};

q.push(s);

vis[12345][3][2]=1;

rcd[12345]=0;

}

inttoNum(node&n){

intt=0;

for(inti=0;i<5;++i){

t*=10;

t+=n.a[i];

}

returnt;

}

voidbfs(){

while(!q.empty()){

nodes=q.front();

intt=toNum(s);

if(rcd[t]==-1||rcd[t]>s.d)rcd[t]=s.d;

//printf("n=%d,d=%d,o2=%d,o3=%d\n",toNum(s),s.d,s.o2,s.o3);

++s.d;

q.pop();

for(inti=0;i<5;++i){

//o1

if(i<4&&s.a[i]!=s.a[i+1]){

swap(s.a[i],s.a[i+1]);

if(!vis[toNum(s)][s.o2][s.o3]){

vis[toNum(s)][s.o2][s.o3]=1;

q.push(s);

第2題

尋找邊緣

問答題

給定一張R*C的地圖，由"X"和"O"組成。

現(xiàn)在需要重新處理這張地圖，找到地圖邊緣的那些"O"。你需要將這些地圖邊緣上的"O"保留下來，然后將

其他的"O"全部替換為"X"。

地圖邊緣的"O"指的是那些處于第一行/列或最后一行/列上的"O"，以及從這些"O"的相鄰位置（上下左右）

延伸出去的"O"。

時(shí)間限制：1000

內(nèi)存限制：65536

輸入

第一行是一個(gè)正整數(shù)T，表示一共有T組數(shù)據(jù)。對(duì)于每組數(shù)據(jù)，其第一行是兩個(gè)正整數(shù)R和C，表示地圖

的大小，用一個(gè)空格分開。接下來的R行，每行包含了C個(gè)字符，分別是"X"或"O"。其中，0<T<=

10，0<R,C<=500。

輸出

對(duì)于每組數(shù)據(jù)，輸出R行，每行包含了C個(gè)字符，分別是"X"或"O"。每組數(shù)據(jù)之間需要額外輸出一個(gè)空

行。

樣例輸入

2

23

OXX

XXO

55

XXXOX

XXXOX

XOOXX

XXOXX

XOXXX

樣例輸出

OXX

XXO

XXXOX

XXXOX

XXXXX

XXXXX

XOXXX

答案

#include<iostream>

#include<cstring>

usingnamespacestd;

intr,c;

chara[505][505];

intdirx[4]={0,0,1,-1};

intdiry[4]={1,-1,0,0};

voiddfs(intx,inty){

for(inti=0;i<4;i++){

intnx=x+dirx[i];

intny=y+diry[i];

if(a[nx][ny]=='O'){

a[nx][ny]='?';

dfs(nx,ny);

}

}

}

intmain(){

intt;

cin>>t;

while(t--){

memset(a,0,sizeof(a));

cin>>r>>c;

inti,j;

for(i=1;i<=r;i++)

for(j=1;j<=c;j++)

cin>>a[i][j];

for(i=1;i<=r;i++){

if(a[i][1]=='O'){

a[i][1]='?';

dfs(i,1);

}

if(a[i][c]=='O'){

a[i][c]='?';

dfs(i,c);

}

}

for(i=1;i<=c;i++){

if(a[1][i]=='O'){

a[1][i]

第3題

42點(diǎn)

42是：

問答題

?組合數(shù)學(xué)上的第5個(gè)卡特蘭數(shù)

?字符'*'的ASCII碼

?鉬的原子序數(shù)

?6與9的乘積結(jié)果的13進(jìn)制表示

?生命、宇宙以及任何事情的終極答案

?以及表達(dá)式(1+5)/2*(6-4)*7的值

因此，小機(jī)器人Marvin發(fā)明了這個(gè)叫42點(diǎn)的小游戲。在這個(gè)游戲中，玩家會(huì)獲得n個(gè)數(shù)。玩家需要使

用'+'、'-'、'*'、'/'、'('、')'以及這n個(gè)數(shù)構(gòu)成一個(gè)合法的中綴表達(dá)式，并使得該表達(dá)式的值為42。n個(gè)數(shù)

之間的順序可以改變。表達(dá)式運(yùn)算過程中只能出現(xiàn)整數(shù)。

由于過于抑郁，Marvin無力完成這個(gè)游戲，于是來找你幫忙。你的任務(wù)是對(duì)于給定的n個(gè)數(shù)，判斷他們是

否能根據(jù)上述游戲規(guī)則算出42。

時(shí)間限制：1000

內(nèi)存限制：65536

輸入

第一行為一個(gè)數(shù)n，1<=n<=6。第二行為n個(gè)數(shù)，每個(gè)數(shù)均為[1,13]范圍內(nèi)的整數(shù)。

輸出

輸出一行，若可以算出42則輸出"YES"，否則輸出"NO"（注意大小寫）。

樣例輸入

6

152647

樣例輸出

YES

答案

#include<iostream>

usingnamespacestd;

booldfs(inta[],intn){

if(n==1){

returna[0]==42;

}

for(inti=0;i<n;++i){

for(intj=i+1;j<n;++j){

intb[10];

intm=0;

for(intk=0;k<n;++k){

if(k==i||k==j)continue;

b[m++]=a[k];

}

++m;

b[m-1]=a[i]+a[j];if(dfs(b,m))return1;

b[m-1]=a[i]-a[j];if(dfs(b,m))return1;

b[m-1]=a[j]-a[i];if(dfs(b,m))return1;

b[m-1]=a[i]*a[j];if(dfs(b,m))return1;

if(a[j]!=0)b[m-1]=a[i]/a[j];if(dfs(b,m))return1;

if(a[i]!=0)b[m-1]=a[j]/a[i];if(dfs(b,m))return1;

}

}

return0;

}

intmain(){

intn;

inta[10];

cin>>n;

for(inti=0;i<n;++i)cin>>a[i];

if(dfs(a,n))cout<<"YES"<<endl;

elsecout<<"NO"<<endl;

system("pause");

return0;

}

第4題

問答題

ProjectSummer游戲

小I和小B最近沉迷一款叫做《ProjectSummer》的游戲，小I扮演這個(gè)游戲中需要逃生的無辜者

（Innocent)，小B扮演這個(gè)游戲中抓住無辜者，阻止其逃生的背叛者（Betrayer）。

這個(gè)游戲的地圖是一個(gè)N行M列的矩形，每個(gè)格點(diǎn)表示一個(gè)位置。

'#'表示地圖中的障礙物，'.'表示地圖中的空地，此外，地圖中還有只有背叛者才能使用的傳送門，用小寫

字母'a'-'z'標(biāo)記，它們?cè)诘貓D上成對(duì)出現(xiàn)。

角色可以花費(fèi)1單位的時(shí)間從一個(gè)格子走到上下左右相鄰的4個(gè)空地中的另一個(gè)格子（不可以走出地圖邊界或

者走到障礙物上）。此外，當(dāng)小B扮演的背叛者走到一個(gè)傳送門上時(shí)，他可以花費(fèi)1單位的時(shí)間從當(dāng)前格子

傳送到與當(dāng)前格子相同字母的另一個(gè)傳送門處（他也可以選擇不傳送，此時(shí)沒有花費(fèi)任何時(shí)間，待在原地不

動(dòng)）。

傳送是雙向的。比如，現(xiàn)在小B走到了標(biāo)記為'a'的格子上，那么他可以選擇花費(fèi)一單位的時(shí)間傳送到另一

個(gè)標(biāo)記為'a'的格子上，也可以選擇不傳送，那么他就待在原地不動(dòng)。

現(xiàn)在，小I被小B的陷阱困住了，無法移動(dòng)。給出地圖上小B和小I所在的格子（他們都站在空地上），

求小B最少需要花費(fèi)多少時(shí)間才能走到小I所在的格子抓住他。如果小I無法抓住小B，輸出-1

時(shí)間限制：1000

內(nèi)存限制：65536

輸入

第一行一個(gè)數(shù)字T,表示數(shù)據(jù)組數(shù)。接下來描述T組數(shù)據(jù)，每組數(shù)據(jù)最開始是兩個(gè)正整數(shù)N,M表示地圖是

N行M列的矩形。接下來N行，每行M個(gè)字符，表示地圖。在地圖上，用'.'表示空地，'#'表示障礙

物，'a'-'z'表示傳送門，'B'表示小B的初始位置，'I'表示小I的初始位置。對(duì)于每組數(shù)據(jù)，保證在地圖上

標(biāo)記相同的傳送

門恰好出現(xiàn)兩次。T,N,M<=100

輸出

T行，第i行輸出'Case#i:t',表示第i組數(shù)據(jù)的答案是t.小B最少需要t單位時(shí)間才能走到小I所在的格

子。如果小I無法抓住小B，輸出-1

樣例輸入

3

55

Bx#..

#a.#.

.....

##..#

.x.aI

55

BIa.a

x#.x.

.#.##

.....

#####

22

B#

#I

樣例輸出

Case#1:4

Case#2:1

Case#3:-1

提示

對(duì)于第一組數(shù)據(jù)，假設(shè)行從上到下標(biāo)號(hào)1到5，列從左到右標(biāo)號(hào)1到5，小B初始在(1,1)。小B的最優(yōu)

路線是：(1,1)->(1,2)->(2,2)->(5,4)->(5,5)

。也就是走到標(biāo)記為x的傳送門時(shí)忽略傳送門，走到標(biāo)

記為a的傳送門時(shí)使用傳送門。對(duì)于第二組數(shù)據(jù)，小B直接花費(fèi)1單位時(shí)間向右走一格就可以抓住小I,故

輸出1。對(duì)于第三組數(shù)據(jù)，小B無法走到小I所在的位置上，故輸出-1。

答案

#include<iostream>

#include<cstring>

#include<queue>

usingnamespacestd;

intT,N,M;

int