第十五屆全國(guó)青少年信息學(xué)奧林匹克聯(lián)賽初賽試題

第十五屆全國(guó)青少年信息學(xué)奧林匹克聯(lián)賽初賽試題

(普及組C++語(yǔ)言二小時(shí)完成)

??全部試題答案均要求寫(xiě)在答卷紙上，寫(xiě)在試卷紙上一律無(wú)效??

一.單項(xiàng)選擇題(共20題，每題1.5分，共計(jì)30分。每題有且僅有一個(gè)正確答案。)

I、關(guān)于圖靈機(jī)下面的說(shuō)法哪個(gè)是正確的：

A)圖靈機(jī)是世界上最早的電子計(jì)算機(jī)。

B)由于大量運(yùn)用磁帶操作，圖靈機(jī)運(yùn)行速度很慢。

C)圖靈機(jī)是英國(guó)人圖靈獨(dú)創(chuàng)的，在二戰(zhàn)中為破譯德軍的密碼發(fā)揮J'重要作用。

D)圖靈機(jī)只是一個(gè)理論上的計(jì)算模型。

2、關(guān)于計(jì)算機(jī)內(nèi)存下面的說(shuō)法哪個(gè)是正確的：

A)隨機(jī)存儲(chǔ)器(RAM)的意思是當(dāng)程序運(yùn)行時(shí)，每次詳細(xì)安排給程序的內(nèi)存位置是隨

機(jī)而不確定的。

B)1MB內(nèi)存通常是指1024*1024字節(jié)大小的內(nèi)存。

C)計(jì)算機(jī)內(nèi)存嚴(yán)格說(shuō)來(lái)包括主存(memory)、高速緩存(cache)和寄存器(register)

三個(gè)部分。

D)一般內(nèi)存中的數(shù)據(jù)即使在斷電的狀況下也能保留2個(gè)小時(shí)以上。

3、關(guān)于BIOS下面說(shuō)法哪個(gè)是正確的：

A)BIOS是計(jì)算機(jī)基本輸入輸出系統(tǒng)軟件的簡(jiǎn)稱。

B)BIOS里包含了鍵盤、鼠標(biāo)、聲卡、顯卡、打印機(jī)等常用輸入輸出設(shè)備的驅(qū)動(dòng)程序。

C)BIOS一般由操作系統(tǒng)廠商來(lái)開(kāi)發(fā)完成。

D)BIOS能供應(yīng)各種文件拷貝、復(fù)制、刪除以及書(shū)目維護(hù)等文件管理功能。

4、關(guān)于CPU下面哪個(gè)說(shuō)法是正確的：

A)CPU全稱為中心處理器(或中心處理單元)。

B)CPU可以干脆運(yùn)行匯編語(yǔ)言。

C)同樣主頻下，32位的CPU比16位的CPU運(yùn)行速度快一倍。

D)CPU最早是由Intel公司獨(dú)創(chuàng)的。

5、關(guān)于ASCH,下面哪個(gè)說(shuō)法是正確的：

A)ASCII碼就是鍵盤上全部鍵的唯一編碼。

B)一個(gè)ASCH碼運(yùn)用一個(gè)字節(jié)的內(nèi)存空間就能夠存放。

C)最新擴(kuò)展的ASCII編碼方案包含了漢字和其他歐洲語(yǔ)言的編碼。

D)ASCII碼是英國(guó)人主持制定并推廣運(yùn)用的。

6、下列軟件中不是計(jì)算機(jī)操作系統(tǒng)的是：

A)WindowsB)LinuxC)OS/2D)WPS

7、關(guān)于互聯(lián)網(wǎng)，下面的說(shuō)法哪一個(gè)是正確的：

A)新一代互聯(lián)網(wǎng)運(yùn)用的IPv6標(biāo)準(zhǔn)是IPv5標(biāo)準(zhǔn)的升級(jí)與補(bǔ)充。

B)互聯(lián)網(wǎng)的入網(wǎng)8主機(jī)假如有了域名就不再須要IP地址。

C)互聯(lián)網(wǎng)的基礎(chǔ)協(xié)議為TCP/IP協(xié)議。

D)互聯(lián)網(wǎng)上全部可下載的軟件及數(shù)據(jù)資源都是可以合法免費(fèi)運(yùn)用的。

8、關(guān)于HTML下面哪種說(shuō)法是正確的：

A)HTML實(shí)現(xiàn)了文本、圖形、聲音乃至視頻信息的統(tǒng)一編碼。

B)HTML全稱為超文本標(biāo)記語(yǔ)言。

C)網(wǎng)上廣泛運(yùn)用的Flash動(dòng)畫(huà)都是由HTML編寫(xiě)的。

D)HTML也是一種高級(jí)程序設(shè)計(jì)語(yǔ)言。

9、關(guān)于程序設(shè)計(jì)語(yǔ)言，下面哪個(gè)說(shuō)法是正確的：

A)加了注釋的程序一般會(huì)比同樣的沒(méi)有加注釋的程序運(yùn)行速度慢。

D)高級(jí)語(yǔ)言開(kāi)發(fā)的程序不能運(yùn)用在低層次的硬件系統(tǒng)如：自控機(jī)床或低端手機(jī)上。

C)高級(jí)語(yǔ)言相對(duì)于低級(jí)語(yǔ)言更簡(jiǎn)潔實(shí)現(xiàn)跨平臺(tái)的移植。

D)以上說(shuō)法都不對(duì)。

10、已知大寫(xiě)字母A的ASCH編碼為65(10進(jìn)制)，則大寫(xiě)字母J的10進(jìn)制ASCH編碼為：

A)71B)72C)73D)以上都不是

11、十進(jìn)制小數(shù)125.125對(duì)應(yīng)的8進(jìn)制數(shù)是

A)100.1B)175.175C)175.1D)100.175

12、有六個(gè)元素FEDCBA從左至右依次依次進(jìn)棧，在進(jìn)棧過(guò)程中會(huì)有元素被彈出棧。問(wèn)下

列哪一個(gè)不行能是合法的出棧序列？

A)EDCFABB)DECABFC)CDFEBAD)BCDAEF

13、表達(dá)式a*(b+c)-d的后綴表達(dá)式是：

A)abcd*+-B)abc+*d-C)abc*+d-D)-+*abcd

14、一個(gè)包含n個(gè)分支結(jié)點(diǎn)(非葉結(jié)點(diǎn))的非空二叉樹(shù)，它的葉結(jié)點(diǎn)數(shù)目最多為：

A)2n+1B)2n-lC)n-1D)n+1

15、快速排序最壞狀況下的算法時(shí)間困難度為：

A)O(log2n)B)0(n)C)O(nlog2n)D)O(n2)

16.有一個(gè)由4000個(gè)整數(shù)構(gòu)成的依次表，假定表中的元素已經(jīng)按升序排列，采納二分查找

定位一個(gè)元素。則最多須要幾次比較就能確定是否存在所查找的元素：

A)ll次B)12次C)13次D)14次

17、排序算法是穩(wěn)定的意思是關(guān)鍵碼相同的記錄排序前后相對(duì)位置不發(fā)生變更，下列哪種排

序算法是不穩(wěn)定的：

A）冒泡排序B）插入排序C）歸并排序D）快速排序

18、已知n個(gè)頂點(diǎn)的有向圖，若該圖是強(qiáng)連通的（從全部頂點(diǎn)都存在路徑到達(dá)其他頂點(diǎn)），

則該圖中最少有多少條有向邊？

A）nB）n+IC）n-1D）n*（n-I）

19、全國(guó)信息學(xué)奧林匹克的官方網(wǎng)站為參與信息學(xué)競(jìng)賽的老師同學(xué)們供應(yīng)相關(guān)的信息和資

源，請(qǐng)問(wèn)全國(guó)信息學(xué)奧林匹克官方網(wǎng)站的網(wǎng)址是：

A）://noi/B）:///

C）://noi/D）://xinxixue/

20、在參與NOI系列競(jìng)賽過(guò)程中，下面哪一種行為是不被嚴(yán)格禁止的：

A）攜帶書(shū)寫(xiě)工具，手表和不具有通訊功能的電子詞典進(jìn)入賽場(chǎng)。

B）在聯(lián)機(jī)測(cè)試中通過(guò)手工計(jì)算出可能的答案并在程序里干脆輸出答案來(lái)獲得分?jǐn)?shù)。

C）通過(guò)互聯(lián)網(wǎng)搜尋取得解題思路。

D）在提交的程序中啟動(dòng)多個(gè)進(jìn)程以提高程序的執(zhí)行效率。

二.問(wèn)題求解（共2題，每空5分，共計(jì)10分）

1.小陳現(xiàn)有2個(gè)任務(wù)A,B要完成，每個(gè)任務(wù)分另J有若干步驟如下：A=al->a2->a3,

B=bl->b2->b3->b4->b5o在任何時(shí)候，小陳只能用心做某個(gè)任務(wù)的一個(gè)步驟。但是假如情愿,

他可以在做完手中任務(wù)的當(dāng)前步驟后，切換至另一個(gè)任務(wù)，從上次此任務(wù)第一個(gè)未做的步驟

接著。每個(gè)任務(wù)的步驟依次不能打亂，例如……a2->b2->a3->b3……是合法的，而……

a2->b3->a3->b2……是不合法的。小陳從B任務(wù)的bl步驟起先做，當(dāng)恰做完某個(gè)任務(wù)的某

個(gè)步驟后，就停工回家吃飯了。當(dāng)他回來(lái)時(shí)，只記得自己已經(jīng)完成了整個(gè)任務(wù)A,其他的都

忘了。試計(jì)算小陳飯前已做的可能的任務(wù)步驟序列共有種。

2.有如下的一段程序：

1.a=l;

2.b=a;

3.d=-a;

4.e=a+d;

5.c=2*d;

6.f=b+e-d;

7.g=a*f+c;

現(xiàn)在要把這段程序安排到若干臺(tái)（數(shù)量足夠）用電纜連接的PC上做并行執(zhí)行。每臺(tái)PC執(zhí)

行其中的某幾個(gè)語(yǔ)句，并可隨時(shí)通過(guò)電纜與其他PC通正，交換一些中間結(jié)果。假設(shè)每臺(tái)PC

每單位時(shí)間可以執(zhí)行一個(gè)語(yǔ)句，且通訊花費(fèi)的時(shí)間不計(jì)。則這段程序最快可以在單

位時(shí)間內(nèi)執(zhí)行完畢。留意：隨意中間結(jié)果只有在某臺(tái)PC上已經(jīng)得到，才可以被其他PC引

用。例如若語(yǔ)句4和6被分別安排到兩臺(tái)PC上執(zhí)行，則因?yàn)檎Z(yǔ)句6須要引用語(yǔ)句4的計(jì)算

結(jié)果，語(yǔ)句6必需在語(yǔ)句4之后執(zhí)行。

三.閱讀程序?qū)懡Y(jié)果(共4題，每題8分，共計(jì)32分)

I.

#include<iostrearr>

usingnamespacestd;

inta,b;

intwork(inta,intb){

if(a%b)

returnwork(b,a%b);

returnb;

)

intmain()(

cin?a?b;

cout<<work.(a,b)<<endl;

return0;

)

輸入：2012

輸出：_______

2.

#include<iostrearr>

usingnamespacestd;

intmain()

(

inta[3]zb[3];

intizj,tmp;

for(i=0;i<3;i++)

cin?b[i];

for(i=0;i<3;i++)

(

a[i]=0;

for(j=0;j<=i;j++)

(

a[i]+=b[j];

b[a[i]%3]+=a[j];

)

)

tmp=l;

for(i=0;i<3;i++)

(

a[i]%=10;

b[i]%=10;

tmp*=a[i]+b[L];

}

cout<<tmp?endl;

return0;

}

輸入：235

輸出：_______

3.

#include<iostrearr>

usingnamespacestd;

constintc=2024;

intmain()

intnzp,s,i,j,t;

cin?n?p;

s=0;t=l;

for(i=l;i<=n;i++)

(

t=t*p%c;

for(j=l;j<=i;j++)

s=(s+t)%c;

)

cout<<s<<endl;

return0;

)

輸入：112

輸出：________

4.

#include<iostrearr.>

usingnamespacestd;

constintmaxn=50;

voidgetnext(charstr[])

(

intl=strlen(str),i,j,k,temp;

k=l-2;

while(k>=0&istr[k]>str[k+1])k.--;

i=k+l;

while(i<l&&str[i]>str[k])i++;

temp=str[k];

str[k]=str[i-1];

str[i-l]=temp;

for(i=l-l;i>k;i——)

for(j=k+l;j<i;j++)

if(str[j]>str[j+1])

(

temp=str[j];

str[j：=str[j+l];

str[j-1]=temp;

)

return;

intmain()

(

chara[maxn];

intn;

cin?a?n;

while(n>0)

(

getnext(a);

n——;

)

cout<<a<<endl;

return0;

)

輸入：NOIP3

輸出：_________

四.完善程序(前8空，每空3分，后2空，每空2分，共28分)

1.(最大連續(xù)子段和)給出一個(gè)數(shù)列(元素個(gè)數(shù)不多于100),數(shù)列元素均為負(fù)整數(shù)、

正整數(shù)、0o請(qǐng)找出數(shù)列中的一個(gè)連續(xù)子數(shù)列，使得這個(gè)了?數(shù)列中包含的全部元素之和最大,

在和最大的前提下還要求該子數(shù)列包含的元素個(gè)數(shù)最多，并輸出這個(gè)最大和以及該連續(xù)子數(shù)

列中元素的個(gè)數(shù)。例如數(shù)列為4,-5,3,2,4時(shí)，輸出9和3;數(shù)列為123-5078

時(shí),輸出16和7。

#include<iostrearr.>

usingnamespacestd;

inta[101];

intn,i,ans,len,trr.p,beg;

intmain(){

cin>>n;

for(i=l;i<=n;i++)

cin?a[i];

tmp=O;

ans=O;

len=O;

beg=?;

for(i=l;i<=n;i++){

if(tmp+a[i]>ans){

ans=tmp+a[i];

len=i-beg;

)

elseif(&&i-beg>lem

len=i-beg;

if(tmp+a[i](3)){

beg=④;

tmp=0;

)

else

⑤；

}

cout<<ans<<'*"<<len<<endl;

return0;

)

2.(國(guó)王放置)在"m的棋盤上放置k個(gè)國(guó)王，要求k個(gè)國(guó)王相互不攻擊，有多少種

不同的放置方法。假設(shè)國(guó)王放置在第(x,y)格，國(guó)王的攻擊的區(qū)域是：(x-Lv-l),

(x-1,y)z(x-1,y+1),-：x,y-1),(xzy+1),(x+1,y-1),(x+lzy),(x+1,y+1)。讀入

三個(gè)數(shù)輸出答案。題目利用I可溯法求解。棋盤行標(biāo)號(hào)為列標(biāo)號(hào)為

#include<iostrearr>

usingnamespacestd;

intn,mzkzans;

inthash[5][5];

voidwork(intxzinty,inttot){

inti,j;

if(tot==k){

ans++;

return;

}

do{

while(hash[x][y]){

y++;

if(y==m){

x++;

y=?;

}

if(x==n)

return;

)

for(i=x-l;i<=x+l;i++)

if(i>=0&&i<n)

for(j=y-l;j<=y+1;j++)

if(j>=0&&j<m)

②

________?_________；

for(i=x-l;i<=x+l;i++)

if(i>=0&&i<n)

for(j=y-l;j<=y+l;j++)

if(j>=0&&j<m)

@；

y++;

if(y==m){

x++;

y=0;

)

if(x==n)

return;

}

while(1);

)

intmain(){

cin?n?m?k;

ans=0;

memset(hash,0,sizeof(hash));

________?________；

cout<<ans?endl;

return0;

答案部分

NO工P2024年普及組（C++語(yǔ)言）參考答案與評(píng)分標(biāo)準(zhǔn)

一、單項(xiàng)選擇題：（每題1.5分）

1.D2.B3.A4.A5.B

6.D7.C8.B9.C10.D

11.C12.C13.B14.D15.D

16.B17.D18.A19.C20.B

二、問(wèn)題求解：（共2題，每空5分,共計(jì)10分）

1.70

2.5

三、閱讀程序?qū)懡Y(jié)果（共4題，每題8分，共計(jì)32分）

1.4

2.416

3.782

4.NPOI

四.完善程序（前8空，每空3分，后2空，每空2分，共28分）

（說(shuō)明：以下各程序填空可能還有一些等價(jià)的寫(xiě)法，各省可請(qǐng)本省專家審定和

上機(jī)驗(yàn)證，不肯定上報(bào)科學(xué)委員會(huì)審查）

1.

①0

②tmp+a[i]==ans或者a[i]+tmp==ans或者ans==a[i]+tmp等

③<0

④i

⑤tmp+-a[i]或者tmp-tmp+a[i]

2.

①0

②hash[i][j]或者h(yuǎn)ash[i][j]=hash[i][j]+1或者

++hash[i][j]

③work（x,y,tot+l）

@hash[i][j]一或者h(yuǎn)ash[i][j]=hash[1][j]-1或者

—hash[i][j]

（5）work（0,0,0）

留意：②④兩空，不肯定要++或者--。也可以是④--，②++,也

可以是+=k，也可以-=k,甚至任何加標(biāo)記的操作（如位運(yùn)算）都可以，只

要相互撤銷。（所以答案特別多）。

第十六屆全國(guó)青少年信息學(xué)奧林匹克聯(lián)賽初賽試題

（普及組C++語(yǔ)言兩小時(shí)完成）

??全部試題答案均要求寫(xiě)在答卷紙上，寫(xiě)在試卷紙上一律無(wú)效??

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

1.2E+03表示（）o

A.2.03B.5C.8D.2000

2.一個(gè)字節(jié)（byte）由（）個(gè)二進(jìn)制位組成。

A.8B.16C.32D.以上都有可能

3.以下邏輯表達(dá)式的值恒為真的是(

A.PV(->P/\Q)V(「PA->Q)B.QV(IPAQ)V(PA-iQ)

C.PVQV(PA-.Q)V(-.PAQ)D.PV-iQV(PA^Q)V<-.PA-.Q)

4.Linux下可執(zhí)行文件的默認(rèn)擴(kuò)展名為（）。

A.exeB.comC.dllD.以上都不是

5.假如樹(shù)根算第1層，那么一棵n層的二叉樹(shù)最多有（）個(gè)結(jié)點(diǎn)。

A.2n-lB.2nC.2n+lD.2n+1

6.提出“存儲(chǔ)程序”的計(jì)算機(jī)工作原理的是（）。

A.克勞德?香農(nóng)B.戈登?摩爾C.查爾斯?巴比奇D.馮?諾依曼

7.設(shè)X、Y、Z分別代表三進(jìn)制下的一位數(shù)字，若等式XY+ZX=XYX在三進(jìn)制下成立,

那么同樣在三進(jìn)制下，等式XY*ZX=（）也成立。

A.YXZR.ZXYC.XYZD.XZY

8.Pascal語(yǔ)言、C語(yǔ)言和C++語(yǔ)言都屬于（）。

A.面對(duì)對(duì)象語(yǔ)言B.腳本語(yǔ)言C.說(shuō)明性語(yǔ)言D.編譯性語(yǔ)言

9.前綴表達(dá)式“+3*2+512”的值是（）。

A.23B.25C.37D.65

10.主存儲(chǔ)器的存取速度比中心處理器（CPU）的工作速度慢得多，從而使得后者的效率受

到影響。而依據(jù)局部性原理，CPU所訪問(wèn)的存儲(chǔ)單元通常都趨于聚集在一個(gè)較小的連續(xù)區(qū)域

中。于是，為了提高系統(tǒng)整體的執(zhí)行效率，在CPU中引入了（）。

A.寄存器E.高速緩存C.閃存D.外存

11.一個(gè)字長(zhǎng)為8位的整數(shù)的補(bǔ)碼是11111001,則它的原碼是（）。

A.00000111B.01111001C.11111001D.1000011L

12.基于比較的排序時(shí)間困難度的下限是（），其中n表示待排序的元素個(gè)數(shù)。

A.@（n）B.?（nlogn）C.0（logn）D.0（n2）

13.一個(gè)自然數(shù)在十進(jìn)制下有n位，則它在二進(jìn)制下的位數(shù)與（）最接近。

A.5nB.n*log210C.10*log2nD.10nlog2n

14.在下列HTML語(yǔ)句中，可以正確產(chǎn)生一個(gè)指向NO工官方網(wǎng)站的超鏈接的是（）。

A.<aurl=n://noi”歡迎訪問(wèn)NO工網(wǎng)站</a>

B.<ahref=n://noi”歡迎訪問(wèn)NO工網(wǎng)站</a>

C.<a>://noi</a>

D.<aname=H:i/noi”歡迎訪問(wèn)NO工網(wǎng)站</a>

15.元素RI、R2、R3、R4、R5入棧的依次為Rl、R2、R3、R4、R5。假如第1個(gè)出棧的

是R3,那么第5個(gè)出棧的不行能是（）。

A.RIB.R2C.R4D.R5

16.雙向鏈表中有兩個(gè)指針域llink和rlink,分別指向該結(jié)點(diǎn)的前驅(qū)及后繼。設(shè)p指向

鏈表中的一個(gè)結(jié)點(diǎn)，它的左右結(jié)點(diǎn)均非空?，F(xiàn)要求刪除結(jié)點(diǎn)p,則下面語(yǔ)句序列中錯(cuò)誤的是

（）O

A.p->rlink->llink=p->rlink;

p->llink->rlink=p->llink;deletep;

B.p->l1ink->rlink=p->rlink;

p->rlink->llink=p->llink;deletep;

C.p->rlink->llink=p->llink;

p->rlink->llink->rlink=p->rlink;deletep;

D.p->llink->rlink=p->rlink;

p->llink->rlink->llink=p->llink;deletep;

17.一棵二叉樹(shù)的前序遍歷序列是ABCDEFG,后序遍歷序列是CBFEGDA,則根結(jié)點(diǎn)的左

子樹(shù)的結(jié)點(diǎn)個(gè)數(shù)可能是（）。

A.2B.3C.4D.5

18.關(guān)于拓?fù)渑判?，下面說(shuō)法正確的是（）。

A.全部連通的有向圖都可以實(shí)現(xiàn)拓?fù)渑判?/p>

B.對(duì)同一個(gè)圖而言，拓?fù)渑判虻慕Y(jié)果是唯一的

C.拓?fù)渑判蛑腥攵葹?的結(jié)點(diǎn)總會(huì)排在入度大于0的結(jié)點(diǎn)的前面

D.拓?fù)渑判蚪Y(jié)果序列之的第一個(gè)結(jié)點(diǎn)肯定是入度為0的點(diǎn)

19.完全二叉樹(shù)的依次存儲(chǔ)方案，是指將完全二叉樹(shù)的結(jié)點(diǎn)從上至下、從左至右依次存放

到一個(gè)依次結(jié)構(gòu)的數(shù)組中,假定根結(jié)點(diǎn)存放在數(shù)組的1號(hào)位置，則第k號(hào)結(jié)點(diǎn)的父結(jié)點(diǎn)假

如存在的話，應(yīng)當(dāng)存放在數(shù)組的（）號(hào)位置。

A.2kB.2k+lC.k/2下取整D.（k+l）/2下取整

20.全國(guó)青少年信息學(xué)奧林匹克系列活動(dòng)的主辦單位是（）。

A.教化部B.科技部C.共青團(tuán)中心D.中國(guó)計(jì)算機(jī)學(xué)會(huì)

二、問(wèn)題求解（共2題，每題5分，共計(jì)10分）

1.LZW編碼是一種自適反詞典編碼。在編碼的過(guò)程中，起先時(shí)只有一部基礎(chǔ)構(gòu)造元素的編

碼詞典，假如在編碼的過(guò)程中遇到一個(gè)新的詞條，則該詞條及一個(gè)新的編碼會(huì)被追加到詞典

中，并用于后繼信息的編碼。

舉例說(shuō)明，考慮一個(gè)待編碼的信息串："xyxyyyyxyx%初始詞典只有3個(gè)條目，

第一個(gè)為x,編碼為1：其次個(gè)為y,編碼為2：第三個(gè)為空格，編碼為3：于是串“xyx”

的編碼為1-2-1（其中-為編碼分隔符），加上后面的一個(gè)空格就是"2-1-3。但由于有了

一個(gè)空格，我們就知道前面的“xyx”是一個(gè)單詞，而由于該單詞沒(méi)有在詞典中，我們就可以

自適應(yīng)的把這個(gè)詞條添加到詞典里，編碼為4,然后依據(jù)新的詞典對(duì)后繼信息進(jìn)行編碼，以

此類推。于是，最終得到編碼:1-2-1-3-2-2-3-5-3-4o

現(xiàn)在已知初始詞典的3個(gè)條目如上述，則信息串”yyxyxxyyxyxyxxxxyx”的

編碼是。

2.隊(duì)列快照是指在某一時(shí)刻隊(duì)列中的元素組成的有序序列。例如，當(dāng)元素1、2、3入隊(duì)，

元素1出隊(duì)后，此刻的隊(duì)列快照是“23”。當(dāng)元素2、3也出隊(duì)后，隊(duì)列快照是即為空。

現(xiàn)有3個(gè)正整數(shù)元素依次入隊(duì)、出隊(duì)。已知它們的和為8,則共有種可能的不

同的隊(duì)列快照（不同隊(duì)列的相同快照只計(jì)一次）。例如，“51“、“422“、都是可能

的隊(duì)列快照；而“7”不是可能的隊(duì)列快照，因?yàn)槭Ｏ碌?個(gè)正整數(shù)的和不行能是1。

三、閱讀程序?qū)懡Y(jié)果（共4題，每題8分，其中第4題（1）、（2）各4分，共計(jì)32分）

1.

#include<iostream>

usingnamespacestd;

voidswap(int&a,int&b)

(

intt;

t=a;

a=b;

b=t;

|

intmain()

intal,a2,a3,x

cin?al?a2?a3;

if(al>a2)

swap(al,a2)；

if(a2>a3)

swap(a2,a3);

if(al>a2)

swap(al,a2);

cin?x;

if(x<a2)

if(x<al)

cout<<x<<?al?,,?a2?',?a3?endl;

else

cout<<al<<*<<x<<?<<a2<<'*<<a3<<endl;

else

if(x<a3)

cout<<al<<''<<a2<<<<x<<'*<<a3<<endl;

else

cout<<al<<<<a2<<**<<a3<<11<<x<<endl;

return0;

}

輸入：

91220

77

輸出：___________

2.

#include<iostream>

usingnamespacestd;

intrSum(intj)

(

intsum=0;

while(j!=0){

sum=sum*10+(j%10);

j=j/10;

)

returnsum;

)

intmain()

(

intn,m,i;

cin>>n?m;

for(i=n;i<m;i++)

if(i==rSum(i))

cout<<i<<'1;

return0;

}

輸入：90120

輸出：___________

3.

#include<iostream>

#include<string>

usingnamespacestd;

intmain()

strings;

charml,m2;

inti;

getline(cin,s);

ml=?';

m2=*';

for(i=0;i<s.length();i++)

if(s[i]>ml){

m2=ml;

ml=s[i];

}

elseif(s[i]>m2)

m2=s[i];

cout?int(ml)<<**?int(m2)<<endl;

return0;

}

輸入：Expo2024ShanghaiChina

輸出：___________

提示：

字符”格'01'A,'a1

ASCII碼32486597

4.

#include<iostream>

usingnamespacestd;

constintNUM=5;

intr(intn)

(

inti;

if(n<=NUM)

returnn;

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

if(r(n-i)<0)

returni;

return-1;

)

intmain()

(

intn;

cin>>n;

cout<<r(n)<<endl;

return0;

}

(1)

輸入：7

輸出：(4分)

(2)

輸入：16

輸出：(4分)

四、完善程序(前4空，每空2.5分，后6空，每空3分，共計(jì)28分)

1.(哥德巴赫猜想)哥德巴赫猜想是指，任一大于2的偶數(shù)都可寫(xiě)成兩個(gè)質(zhì)數(shù)之和。迄今

為止，這仍舊是一個(gè)聞名的世界難題，被譽(yù)為數(shù)學(xué)王冠上的明珠。試編寫(xiě)程序，驗(yàn)證任一大

于2且不超過(guò)n的偶數(shù)都能寫(xiě)成兩個(gè)質(zhì)數(shù)之和。

#include<iostream>

usingnamespacestd;

intmain()

(

constintSIZE=1000;

intn,r,p[SIZZ],i,j,k,ans;

booltmp;

cin>>n;

r=1;

P[1]=2;

for(i=3;i<=n;i++){

?；

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

if(i%②==0){

tmp=false;

break;

)

if(tmp){

r++;

@;

}

)

ans-0;

for(i=2;i<=n/2;i++){

tmp=false;

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

for(k=j;k<=r;k++)

if(i+i==④){

tmp=true;

break;

}

if(tmp)

ans++;

)

cout<<ans<<endl;

return0;

)

若輸入n為2024,則輸巴⑤時(shí)表示驗(yàn)證勝利,即大于2且不超過(guò)2024的偶數(shù)都

滿意哥德巴赫猜想。

2.(過(guò)河問(wèn)題)在一個(gè)月黑風(fēng)高的夜晚，有一群人在河的右岸，想通過(guò)唯一的一根獨(dú)木橋

走到河的左岸。在這伸手不見(jiàn)五指的黑夜里，過(guò)橋時(shí)必需借助燈光來(lái)照明，很不幸的是，他

們只有一盞燈。另外，獨(dú)木橋上最多承受兩個(gè)人同時(shí)經(jīng)過(guò)，否則將會(huì)坍塌。每個(gè)人單獨(dú)過(guò)橋

都須要肯定的時(shí)間，不同的人須要的時(shí)間可能不同。兩個(gè)人一起過(guò)橋時(shí)，由于只有一盞燈，

所以須要的時(shí)間是較慢的那個(gè)人單獨(dú)過(guò)橋時(shí)所花的時(shí)間?，F(xiàn)輸入n(2^n<100)和這。個(gè)

人單獨(dú)過(guò)橋時(shí)須要的時(shí)間，請(qǐng)計(jì)算總共最少須要多少時(shí)間，他們才能全部到達(dá)河的左岸。

例如，有3個(gè)人甲、乙、丙，他們單獨(dú)過(guò)橋的時(shí)間分別為1、2、4,則總共最少須要

的時(shí)間為7。詳細(xì)方法是：甲、乙一起過(guò)橋到河的左岸，甲單獨(dú)回到河的右岸將燈帶叵，然

后甲、丙再一起過(guò)橋到河為左岸，總時(shí)間為2+1+4=7。

#include<iostream>

usingnamespacestd;

constintSIZE=100;

constintINFINITY=10000;

constboolLEFT=true;

constboolRIGHT=false;

constboolLEFT_TO_RIGHT=true;

constboolRIGHT_TO_LEFT=false;

intn,hour[SIZE];

boolpos[SIZE];

intmax(inta,intb)

(

if(a>b)

returna;

else

returnb;

intgo(boolstage)

(

inti,j,num,tmp,ans;

if(Stage==RIGHT_TO_LEFT){

num=0;

ans=0;

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

if(pos[i]==RIGHT){

num++;

if(hour(i]>ans)

ans=hour[i];

)

if(①)

returnans;

ans=INFINITY;

for(i=l;i<=n-l;i++)

if(pos[i]==RIGHT)

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

if(pos(j]==RIGHT){

pos[i]=LEFT;

pOS[j]=LEFT;

tmp=max(hour(i],hour[j])+②

if(tmp<ans)

ans=tmp;

pos[i]=RIGHT;

pos[j]=RIGHT;

}

returnans;

)

if(stage==LEFT_TO_RIGHT){

ans=INFINITY;

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

if(③){

pos[i]=RIGHT;

tmp=@；

if(tmp<ans)

ans=tmp;

@；

)

returnans;

)

return0;

)

intmain()

(

inti;

cin?n;

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

cin>>hour[i];

pos[i]=RIGHT;

）

cout<<go（RIGHT_TO_LEFT）<<endl;

return0;

}

NOIP2024年普及組（C++語(yǔ)言）參考答案與評(píng)分標(biāo)準(zhǔn)

一、單項(xiàng)選擇題：（每題1.5分）

12345678910

DAADADBDCB

11121314151617181920

DBBBBAADCD

二、問(wèn)題求解：（共2題，每空5分，共計(jì)1。分）

1.2-2-1-2-3-1-1-3-4-3-1-2-1-3-5-3-6（或）

2.49

三、閱讀程序?qū)懡Y(jié)果（共4題，每題8分，共計(jì)32分）

1.2207791

2.99101111

3.120112

4.（1）1（2）4

四、完善程序（前4空，每空2.5分,后6空，每空3分，共計(jì)28分）

（說(shuō)明：以下各程序填空可能還有一些等價(jià)的寫(xiě)法，各省可請(qǐng)本省專家審定和上

機(jī)驗(yàn)證，

不肯定上報(bào)科學(xué)委員會(huì)審查）

1.

①tmp=true

②p[j]

③p[r]=i

④p[j]+p[k]

⑤1004

本小題中，LEFT可月true代替，LEFT_TO_RIGHT可用true代替,

RlGHT_TO_LEFT

可用fdlse代替。

2.

①num<=2(或num<3或num=2)

②gO(LEFT_TO_RIGHT)

③pos[i]==LEFT(或LEFT=pos[i])

④hour[i]+go(RIGHT_TO_L￡FT)(或go(RGHT_TO_LEFT)+hour[i])

⑤pos[i]=LEFT

本小題中，LEFT可月true代替，LEFT_TO_RIGHT可用true代替,

RIGHT_TO_LEFT

可用false代替。

第十八屆全國(guó)青少年信息學(xué)奧林匹克聯(lián)賽初賽

（普及組C++語(yǔ)言試題）

競(jìng)賽時(shí)間：2024年10月13日14:30-16:30

選手留意：

?試題紙共有10頁(yè)，答題紙共有2頁(yè)，滿分100分。請(qǐng)?jiān)诖痤}紙上作答，寫(xiě)在試題紙上一律

無(wú)效。

?不得運(yùn)用任何電子設(shè)備（如計(jì)算器、手機(jī)、電子詞典等）或查閱任何書(shū)籍資料

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

1.計(jì)算機(jī)假如缺少（A）,將無(wú)法正常啟動(dòng)。

12345678910

ABABCCBCAA

11121314151617181920

BDBCCDCACB

A.內(nèi)存B.鼠標(biāo)C.U盤D.攝像頭

2.（B）是一種先進(jìn)先出的線性表。

A.棧B.隊(duì)列C.哈希表（散列表）D.二叉樹(shù)

3.目前計(jì)算機(jī)芯片（集成電路）制造的主要原料是（A）,它是一種可以在沙子中提煉出的物

質(zhì)。

A.硅B.銅C.錯(cuò)D.鋁

4.十六進(jìn)制數(shù)9A在（B）進(jìn)制下是232。

A.四B.八C.十D.十二

5.（C）不屬于操作系統(tǒng)。

A.WindowsB.DOSC.PhotoshopD.NOILinux

6.假如一棵二叉樹(shù)的中序遍歷是BAC,那么它的先序遍歷不行能是（C）o

A.ABCB.CBAC.ACBD.BAC

7.目前個(gè)人電腦的（B）市場(chǎng)占有率最靠前的廠商包括Intel、AMD等公司。

A.顯示器B.CPUC.內(nèi)存D.鼠標(biāo)

8.運(yùn)用冒泡排序?qū)π蛄羞M(jìn)行升序排列，每執(zhí)行一次交換操作系統(tǒng)將會(huì)削減1個(gè)逆序?qū)Γ虼诵?/p>

列5,4,3,2,1須要執(zhí)行（C）次操作，才能完成冒泡排序。

A.0B.5C.10D.15

9.1946年誕生于美國(guó)賓夕法尼亞高校的ENIAC屬于（A）計(jì)算機(jī)。

A.電子管B.晶體管C.集成電路D.超大規(guī)模集成電路

10.無(wú)論是TCP/IP模型還是0SI模型，都可以視為網(wǎng)絡(luò)的分層模型，每個(gè)網(wǎng)絡(luò)協(xié)議都會(huì)被歸

入某一層中。假如用現(xiàn)實(shí)生活中的例子來(lái)比方這些“層”，以下最恰當(dāng)?shù)氖牵ˋ）。

A.中國(guó)公司的經(jīng)理與波蘭公司的經(jīng)理交女商業(yè)文件

中國(guó)公司經(jīng)理波蘭公司經(jīng)理

第4層

t111

卜國(guó)公亙圣理斑書(shū)

第3層:反蘭公芝姿瑾受書(shū)

t111

第2層中國(guó)公巨打設(shè)波蘭公司翻譯

t111

第1層十五虻遞員—f波蘭郵遞員

B.軍隊(duì)發(fā)布吩咐

第4層司令

,1

第3層軍長(zhǎng)1軍長(zhǎng)2

11

第2層師長(zhǎng)1師長(zhǎng)2師長(zhǎng)3師長(zhǎng)4

111

第1層團(tuán)長(zhǎng)1團(tuán)長(zhǎng)2團(tuán)長(zhǎng)3團(tuán)長(zhǎng)4團(tuán)長(zhǎng)5團(tuán)長(zhǎng)6團(tuán)長(zhǎng)7團(tuán)長(zhǎng)8

C.國(guó)際會(huì)議中，每個(gè)人都與他國(guó)地位對(duì)等的人干脆進(jìn)行會(huì)談

第4層英國(guó)女王<—>瑞典國(guó)王

第3層英國(guó)首相瑞典首相

第2層英國(guó)外交大臣<--A瑞典外交大臣

第1層英田三瑞典大受<-A是其至美里大空

D.體育競(jìng)賽中，每一級(jí)競(jìng)賽的優(yōu)勝者晉級(jí)上一級(jí)競(jìng)賽

第4層奧運(yùn)會(huì)

t

第3層全運(yùn)金

t

第2層省運(yùn)會(huì)

t

第1層市運(yùn)會(huì)

11.矢量圖(VectoMmage)圖形文件所占的貯存空間比較小，并且無(wú)論如何放大、縮小或旋轉(zhuǎn)

等都不會(huì)失真，是因?yàn)樗糂).

A.記錄了大量像素塊的色調(diào)值來(lái)表示圖像

B.用點(diǎn)、宜線或者多邊形等基于數(shù)學(xué)方程的幾何圖元來(lái)表示圖像

C.每個(gè)像素點(diǎn)的顏色信息均用矢量表示

D.把文件保存在互聯(lián)網(wǎng)，采納在線閱讀的方式查看圖像

12.假如一個(gè)棧初始時(shí)為空，且當(dāng)前棧中的元素從棧頂?shù)綏５滓来螢閍,b,c,另有元素d已

經(jīng)出棧，則可能的入棧依次是（D）o

A.a,d,c,bB.b,a,c,dC.a,c,b,dD.d,a,b,c

13.（B）是主要用于顯示網(wǎng)頁(yè)服務(wù)器或者文件系統(tǒng)的HTML文件的內(nèi)容，并讓用戶與這些

文件交互的一種軟件。

A.資源管理器B.閱讀器C.電子部件D.編譯器

14.（C）是目前互聯(lián)網(wǎng)上常用的E-mail服務(wù)協(xié)議。

A.B.FTPC.POP3D.Telnet

15.（C）就是把一個(gè)困難的問(wèn)題分成兩個(gè)或更多的相同類似的子問(wèn)題，再把子問(wèn)題分解成

更小的子問(wèn)題……直到最終的子問(wèn)題可以簡(jiǎn)潔地干脆求解。而原問(wèn)題的解就是子問(wèn)^解的并。

A.動(dòng)態(tài)規(guī)劃B.貪心C.分治D.搜尋

16.地址總線的位數(shù)確定了CPU可干脆尋址的內(nèi)存空間大小，例如地址總線為16位，其最大的

可尋址空間為64KB。假如地址總線是32位，則理論上最大可尋址的內(nèi)存空間為（D）,

A.128KBB.1MBC.1GBD.4GB

17.藍(lán)牙和Wi-Fi都是（C）設(shè)備。

A.無(wú)線廣域網(wǎng)B.無(wú)線城域網(wǎng)C.無(wú)線局域網(wǎng)D.無(wú)線路由器

18.在程序運(yùn)行過(guò)程中，假如遞歸調(diào)用的層數(shù)過(guò)多，會(huì)因?yàn)椋ˋ）引發(fā)錯(cuò)誤。

A.系統(tǒng)安排的?？臻g溢出B.系統(tǒng)安排的堆空間溢出

C.系統(tǒng)安排的隊(duì)列空閏溢出D.系統(tǒng)安排的鏈表空間溢出

19.原字符串中隨意一段連續(xù)的字符所組成的新字符串稱為子串。則字符“AAABBBCCC”共

有（C）個(gè)不同的非空子串。

A.3B.12C.36D.45

20.仿生學(xué)的問(wèn)世開(kāi)拓了獨(dú)特的科學(xué)技術(shù)發(fā)展道路。人們探討生物體的結(jié)構(gòu)、功能和工作原理，

并將這些原理移植于新興的工程技術(shù)中。以下關(guān)于仿生學(xué)的敘述，錯(cuò)誤的是（B）

A.由探討蝙蝠，獨(dú)創(chuàng)雷達(dá)B.由探討蜘蛛網(wǎng)，獨(dú)創(chuàng)因特網(wǎng)

C.由探討海豚，獨(dú)創(chuàng)聲納D.由探討電魚(yú)，獨(dú)創(chuàng)伏特電池

二、問(wèn)題求解（共2題，每題5分，共計(jì)10分）

I.假如平面上任取n個(gè)整點(diǎn)（橫縱坐標(biāo)都是整數(shù)），其中肯定存在兩個(gè)點(diǎn)，它們連線的中點(diǎn)也

是整點(diǎn)，那么n至少是。

2.在NOI期間，主辦單位為了歡迎來(lái)自各國(guó)的選手，實(shí)行了盛大的晚宴。在第十八桌，有