第十五屆全國青少年信息學奧林匹克聯賽初賽試題

第十五屆全國青少年信息學奧林匹克聯賽初賽試題

(普及組C++語言二小時完成)

??全部試題答案均要求寫在答卷紙上，寫在試卷紙上一律無效??

一.單項選擇題(共20題，每題1.5分，共計30分。每題有且僅有一個正確答案。)

I、關于圖靈機下面的說法哪個是正確的：

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

B)由于大量運用磁帶操作，圖靈機運行速度很慢。

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

D)圖靈機只是一個理論上的計算模型。

2、關于計算機內存下面的說法哪個是正確的：

A)隨機存儲器(RAM)的意思是當程序運行時，每次詳細安排給程序的內存位置是隨

機而不確定的。

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

C)計算機內存嚴格說來包括主存(memory)、高速緩存(cache)和寄存器(register)

三個部分。

D)一般內存中的數據即使在斷電的狀況下也能保留2個小時以上。

3、關于BIOS下面說法哪個是正確的：

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

B)BIOS里包含了鍵盤、鼠標、聲卡、顯卡、打印機等常用輸入輸出設備的驅動程序。

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

D)BIOS能供應各種文件拷貝、復制、刪除以及書目維護等文件管理功能。

4、關于CPU下面哪個說法是正確的：

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

B)CPU可以干脆運行匯編語言。

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

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

5、關于ASCH,下面哪個說法是正確的：

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

B)一個ASCH碼運用一個字節(jié)的內存空間就能夠存放。

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

D)ASCII碼是英國人主持制定并推廣運用的。

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

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

7、關于互聯網，下面的說法哪一個是正確的：

A)新一代互聯網運用的IPv6標準是IPv5標準的升級與補充。

B)互聯網的入網8主機假如有了域名就不再須要IP地址。

C)互聯網的基礎協(xié)議為TCP/IP協(xié)議。

D)互聯網上全部可下載的軟件及數據資源都是可以合法免費運用的。

8、關于HTML下面哪種說法是正確的：

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

B)HTML全稱為超文本標記語言。

C)網上廣泛運用的Flash動畫都是由HTML編寫的。

D)HTML也是一種高級程序設計語言。

9、關于程序設計語言，下面哪個說法是正確的：

A)加了注釋的程序一般會比同樣的沒有加注釋的程序運行速度慢。

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

C)高級語言相對于低級語言更簡潔實現跨平臺的移植。

D)以上說法都不對。

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

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

11、十進制小數125.125對應的8進制數是

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

12、有六個元素FEDCBA從左至右依次依次進棧，在進棧過程中會有元素被彈出棧。問下

列哪一個不行能是合法的出棧序列？

A)EDCFABB)DECABFC)CDFEBAD)BCDAEF

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

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

14、一個包含n個分支結點(非葉結點)的非空二叉樹，它的葉結點數目最多為：

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

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

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

16.有一個由4000個整數構成的依次表，假定表中的元素已經按升序排列，采納二分查找

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

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

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

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

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

18、已知n個頂點的有向圖，若該圖是強連通的（從全部頂點都存在路徑到達其他頂點），

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

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

19、全國信息學奧林匹克的官方網站為參與信息學競賽的老師同學們供應相關的信息和資

源，請問全國信息學奧林匹克官方網站的網址是：

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

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

20、在參與NOI系列競賽過程中，下面哪一種行為是不被嚴格禁止的：

A）攜帶書寫工具，手表和不具有通訊功能的電子詞典進入賽場。

B）在聯機測試中通過手工計算出可能的答案并在程序里干脆輸出答案來獲得分數。

C）通過互聯網搜尋取得解題思路。

D）在提交的程序中啟動多個進程以提高程序的執(zhí)行效率。

二.問題求解（共2題，每空5分，共計10分）

1.小陳現有2個任務A,B要完成，每個任務分另J有若干步驟如下：A=al->a2->a3,

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

他可以在做完手中任務的當前步驟后，切換至另一個任務，從上次此任務第一個未做的步驟

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

a2->b3->a3->b2……是不合法的。小陳從B任務的bl步驟起先做，當恰做完某個任務的某

個步驟后，就停工回家吃飯了。當他回來時，只記得自己已經完成了整個任務A,其他的都

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

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;

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

行其中的某幾個語句，并可隨時通過電纜與其他PC通正，交換一些中間結果。假設每臺PC

每單位時間可以執(zhí)行一個語句，且通訊花費的時間不計。則這段程序最快可以在單

位時間內執(zhí)行完畢。留意：隨意中間結果只有在某臺PC上已經得到，才可以被其他PC引

用。例如若語句4和6被分別安排到兩臺PC上執(zhí)行，則因為語句6須要引用語句4的計算

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

三.閱讀程序寫結果(共4題，每題8分，共計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ù)子段和)給出一個數列(元素個數不多于100),數列元素均為負整數、

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

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

列中元素的個數。例如數列為4,-5,3,2,4時，輸出9和3;數列為123-5078

時,輸出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.(國王放置)在"m的棋盤上放置k個國王，要求k個國王相互不攻擊，有多少種

不同的放置方法。假設國王放置在第(x,y)格，國王的攻擊的區(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)。讀入

三個數輸出答案。題目利用I可溯法求解。棋盤行標號為列標號為

#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++語言）參考答案與評分標準

一、單項選擇題：（每題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

二、問題求解：（共2題，每空5分,共計10分）

1.70

2.5

三、閱讀程序寫結果（共4題，每題8分，共計32分）

1.4

2.416

3.782

4.NPOI

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

（說明：以下各程序填空可能還有一些等價的寫法，各省可請本省專家審定和

上機驗證，不肯定上報科學委員會審查）

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]或者hash[i][j]=hash[i][j]+1或者

++hash[i][j]

③work（x,y,tot+l）

@hash[i][j]一或者hash[i][j]=hash[1][j]-1或者

—hash[i][j]

（5）work（0,0,0）

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

可以是+=k，也可以-=k,甚至任何加標記的操作（如位運算）都可以，只

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

第十六屆全國青少年信息學奧林匹克聯賽初賽試題

（普及組C++語言兩小時完成）

??全部試題答案均要求寫在答卷紙上，寫在試卷紙上一律無效??

一、單項選擇題（共20題,每題1.5分，共計30分。每題有且僅有一個正確選項。）

1.2E+03表示（）o

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

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

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

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

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í)行文件的默認擴展名為（）。

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

5.假如樹根算第1層，那么一棵n層的二叉樹最多有（）個結點。

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

6.提出“存儲程序”的計算機工作原理的是（）。

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

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

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

A.YXZR.ZXYC.XYZD.XZY

8.Pascal語言、C語言和C++語言都屬于（）。

A.面對對象語言B.腳本語言C.說明性語言D.編譯性語言

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

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

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

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

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

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

11.一個字長為8位的整數的補碼是11111001,則它的原碼是（）。

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

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

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

13.一個自然數在十進制下有n位，則它在二進制下的位數與（）最接近。

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

14.在下列HTML語句中，可以正確產生一個指向NO工官方網站的超鏈接的是（）。

A.<aurl=n://noi”歡迎訪問NO工網站</a>

B.<ahref=n://noi”歡迎訪問NO工網站</a>

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

D.<aname=H:i/noi”歡迎訪問NO工網站</a>

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

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

A.RIB.R2C.R4D.R5

16.雙向鏈表中有兩個指針域llink和rlink,分別指向該結點的前驅及后繼。設p指向

鏈表中的一個結點，它的左右結點均非空?，F要求刪除結點p,則下面語句序列中錯誤的是

（）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.一棵二叉樹的前序遍歷序列是ABCDEFG,后序遍歷序列是CBFEGDA,則根結點的左

子樹的結點個數可能是（）。

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

18.關于拓撲排序，下面說法正確的是（）。

A.全部連通的有向圖都可以實現拓撲排序

B.對同一個圖而言，拓撲排序的結果是唯一的

C.拓撲排序中入度為0的結點總會排在入度大于0的結點的前面

D.拓撲排序結果序列之的第一個結點肯定是入度為0的點

19.完全二叉樹的依次存儲方案，是指將完全二叉樹的結點從上至下、從左至右依次存放

到一個依次結構的數組中,假定根結點存放在數組的1號位置，則第k號結點的父結點假

如存在的話，應當存放在數組的（）號位置。

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

20.全國青少年信息學奧林匹克系列活動的主辦單位是（）。

A.教化部B.科技部C.共青團中心D.中國計算機學會

二、問題求解（共2題，每題5分，共計10分）

1.LZW編碼是一種自適反詞典編碼。在編碼的過程中，起先時只有一部基礎構造元素的編

碼詞典，假如在編碼的過程中遇到一個新的詞條，則該詞條及一個新的編碼會被追加到詞典

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

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

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

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

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

自適應的把這個詞條添加到詞典里，編碼為4,然后依據新的詞典對后繼信息進行編碼，以

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

現在已知初始詞典的3個條目如上述，則信息串”yyxyxxyyxyxyxxxxyx”的

編碼是。

2.隊列快照是指在某一時刻隊列中的元素組成的有序序列。例如，當元素1、2、3入隊，

元素1出隊后，此刻的隊列快照是“23”。當元素2、3也出隊后，隊列快照是即為空。

現有3個正整數元素依次入隊、出隊。已知它們的和為8,則共有種可能的不

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

的隊列快照；而“7”不是可能的隊列快照，因為剩下的2個正整數的和不行能是1。

三、閱讀程序寫結果（共4題，每題8分，其中第4題（1）、（2）各4分，共計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分，共計28分)

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

為止，這仍舊是一個聞名的世界難題，被譽為數學王冠上的明珠。試編寫程序，驗證任一大

于2且不超過n的偶數都能寫成兩個質數之和。

#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,則輸巴⑤時表示驗證勝利,即大于2且不超過2024的偶數都

滿意哥德巴赫猜想。

2.(過河問題)在一個月黑風高的夜晚，有一群人在河的右岸，想通過唯一的一根獨木橋

走到河的左岸。在這伸手不見五指的黑夜里，過橋時必需借助燈光來照明，很不幸的是，他

們只有一盞燈。另外，獨木橋上最多承受兩個人同時經過，否則將會坍塌。每個人單獨過橋

都須要肯定的時間，不同的人須要的時間可能不同。兩個人一起過橋時，由于只有一盞燈，

所以須要的時間是較慢的那個人單獨過橋時所花的時間?，F輸入n(2^n<100)和這。個

人單獨過橋時須要的時間，請計算總共最少須要多少時間，他們才能全部到達河的左岸。

例如，有3個人甲、乙、丙，他們單獨過橋的時間分別為1、2、4,則總共最少須要

的時間為7。詳細方法是：甲、乙一起過橋到河的左岸，甲單獨回到河的右岸將燈帶叵，然

后甲、丙再一起過橋到河為左岸，總時間為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++語言）參考答案與評分標準

一、單項選擇題：（每題1.5分）

12345678910

DAADADBDCB

11121314151617181920

DBBBBAADCD

二、問題求解：（共2題，每空5分，共計1。分）

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

2.49

三、閱讀程序寫結果（共4題，每題8分，共計32分）

1.2207791

2.99101111

3.120112

4.（1）1（2）4

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

（說明：以下各程序填空可能還有一些等價的寫法，各省可請本省專家審定和上

機驗證，

不肯定上報科學委員會審查）

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代替。

第十八屆全國青少年信息學奧林匹克聯賽初賽

（普及組C++語言試題）

競賽時間：2024年10月13日14:30-16:30

選手留意：

?試題紙共有10頁，答題紙共有2頁，滿分100分。請在答題紙上作答，寫在試題紙上一律

無效。

?不得運用任何電子設備（如計算器、手機、電子詞典等）或查閱任何書籍資料

一、單項選擇題（共20題.每題1.5分，共計30分；每題且僅有一個正確選項）

1.計算機假如缺少（A）,將無法正常啟動。

12345678910

ABABCCBCAA

11121314151617181920

BDBCCDCACB

A.內存B.鼠標C.U盤D.攝像頭

2.（B）是一種先進先出的線性表。

A.棧B.隊列C.哈希表（散列表）D.二叉樹

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

質。

A.硅B.銅C.錯D.鋁

4.十六進制數9A在（B）進制下是232。

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

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

A.WindowsB.DOSC.PhotoshopD.NOILinux

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

A.ABCB.CBAC.ACBD.BAC

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

A.顯示器B.CPUC.內存D.鼠標

8.運用冒泡排序對序列進行升序排列，每執(zhí)行一次交換操作系統(tǒng)將會削減1個逆序對，因此序

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

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

9.1946年誕生于美國賓夕法尼亞高校的ENIAC屬于（A）計算機。

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

10.無論是TCP/IP模型還是0SI模型，都可以視為網絡的分層模型，每個網絡協(xié)議都會被歸

入某一層中。假如用現實生活中的例子來比方這些“層”，以下最恰當的是（A）。

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

中國公司經理波蘭公司經理

第4層

t111

卜國公亙圣理斑書

第3層:反蘭公芝姿瑾受書

t111

第2層中國公巨打設波蘭公司翻譯

t111

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

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

第4層司令

,1

第3層軍長1軍長2

11

第2層師長1師長2師長3師長4

111

第1層團長1團長2團長3團長4團長5團長6團長7團長8

C.國際會議中，每個人都與他國地位對等的人干脆進行會談

第4層英國女王<—>瑞典國王

第3層英國首相瑞典首相

第2層英國外交大臣<--A瑞典外交大臣

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

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

第4層奧運會

t

第3層全運金

t

第2層省運會

t

第1層市運會

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

等都不會失真，是因為它＜B).

A.記錄了大量像素塊的色調值來表示圖像

B.用點、宜線或者多邊形等基于數學方程的幾何圖元來表示圖像

C.每個像素點的顏色信息均用矢量表示

D.把文件保存在互聯網，采納在線閱讀的方式查看圖像

12.假如一個棧初始時為空，且當前棧中的元素從棧頂到棧底依次為a,b,c,另有元素d已

經出棧，則可能的入棧依次是（D）o

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

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

文件交互的一種軟件。

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

14.（C）是目前互聯網上常用的E-mail服務協(xié)議。

A.B.FTPC.POP3D.Telnet

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

更小的子問題……直到最終的子問題可以簡潔地干脆求解。而原問題的解就是子問^解的并。

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

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

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

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

17.藍牙和Wi-Fi都是（C）設備。

A.無線廣域網B.無線城域網C.無線局域網D.無線路由器

18.在程序運行過程中，假如遞歸調用的層數過多，會因為（A）引發(fā)錯誤。

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

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

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

有（C）個不同的非空子串。

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

20.仿生學的問世開拓了獨特的科學技術發(fā)展道路。人們探討生物體的結構、功能和工作原理，

并將這些原理移植于新興的工程技術中。以下關于仿生學的敘述，錯誤的是（B）

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

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

二、問題求解（共2題，每題5分，共計10分）

I.假如平面上任取n個整點（橫縱坐標都是整數），其中肯定存在兩個點，它們連線的中點也

是整點，那么n至少是。

2.在NOI期間，主辦單位為了歡迎來自各國的選手，實行了盛大的晚宴。在第十八桌，有