第十五届全国青少年信息学奥林匹克联赛初赛试题

第十五届全国青少年信息学奥林匹克联赛初赛试题

(普及组C++语言二小时完成)

••全部试题答案均要求写在答卷纸上，写在试卷纸上一律无效••

一.单项选择题(共20题，每题1.5分，共计30分。每题有且仅有一个正确答案。)

I、关于图灵机下面的说法哪个是正确的：

A)图灵机是世界上最早的电子计算机。

B)由于大量运用磁带操作，图灵机运行速度很慢。

C)图灵机是英国人图灵独创的，在二战中为破译德军的密码发挥J'重要作用。

D)图灵机只是一个理论上的计算模型。

2、关于计算机内存下面的说法哪个是正确的：

A)随机存储器(RAM)的意思是当程序运行时，每次详细安排给程序的内存位置是随

机而不确定的。

B)1MB内存通常是指1024*1024字节大小的内存。

C)计算机内存严格说来包括主存(memory)、高速缓存(cache)和寄存器(register)

三个部分。

D)一般内存中的数据即使在断电的状况下也能保留2个小时以上。

3、关于BIOS下面说法哪个是正确的：

A)BIOS是计算机基本输入输出系统软件的简称。

B)BIOS里包含了键盘、鼠标、声卡、显卡、打印机等常用输入输出设备的驱动程序。

C)BIOS一般由操作系统厂商来开发完成。

D)BIOS能供应各种文件拷贝、复制、删除以及书目维护等文件管理功能。

4、关于CPU下面哪个说法是正确的：

A)CPU全称为中心处理器(或中心处理单元)。

B)CPU可以干脆运行汇编语言。

C)同样主频下，32位的CPU比16位的CPU运行速度快一倍。

D)CPU最早是由Intel公司独创的。

5、关于ASCH,下面哪个说法是正确的：

A)ASCII码就是键盘上全部键的唯一编码。

B)一个ASCH码运用一个字节的内存空间就能够存放。

C)最新扩展的ASCII编码方案包含了汉字和其他欧洲语言的编码。

D)ASCII码是英国人主持制定并推广运用的。

6、下列软件中不是计算机操作系统的是：

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

7、关于互联网，下面的说法哪一个是正确的：

A)新一代互联网运用的IPv6标准是IPv5标准的升级与补充。

B)互联网的入网8主机假如有了域名就不再须要IP地址。

C)互联网的基础协议为TCP/IP协议。

D)互联网上全部可下载的软件及数据资源都是可以合法免费运用的。

8、关于HTML下面哪种说法是正确的：

A)HTML实现了文本、图形、声音乃至视频信息的统一编码。

B)HTML全称为超文本标记语言。

C)网上广泛运用的Flash动画都是由HTML编写的。

D)HTML也是一种高级程序设计语言。

9、关于程序设计语言，下面哪个说法是正确的：

A)加了注释的程序一般会比同样的没有加注释的程序运行速度慢。

D)高级语言开发的程序不能运用在低层次的硬件系统如：自控机床或低端手机上。

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、排序算法是稳定的意思是关键码相同的记录排序前后相对位置不发生变更，下列哪种排

序算法是不稳定的：

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）在提交的程序中启动多个进程以提高程序的执行效率。

二.问题求解（共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上做并行执行。每台PC执

行其中的某几个语句，并可随时通过电缆与其他PC通正，交换一些中间结果。假设每台PC

每单位时间可以执行一个语句，且通讯花费的时间不计。则这段程序最快可以在单

位时间内执行完毕。留意：随意中间结果只有在某台PC上已经得到，才可以被其他PC引

用。例如若语句4和6被分别安排到两台PC上执行，则因为语句6须要引用语句4的计算

结果，语句6必需在语句4之后执行。

三.阅读程序写结果(共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.(最大连续子段和)给出一个数列(元素个数不多于100),数列元素均为负整数、

正整数、0o请找出数列中的一个连续子数列，使得这个了•数列中包含的全部元素之和最大,

在和最大的前提下还要求该子数列包含的元素个数最多，并输出这个最大和以及该连续子数

列中元素的个数。例如数列为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)格，国王的攻击的区域是：(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.一个字节（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下可执行文件的默认扩展名为（）。

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所访问的存储单元通常都趋于聚集在一个较小的连续区域

中。于是，为了提高系统整体的执行效率，在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指向

链表中的一个结点，它的左右结点均非空。现要求删除结点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.(过河问题)在一个月黑风高的夜晚，有一群人在河的右岸，想通过唯一的一根独木桥

走到河的左岸。在这伸手不见五指的黑夜里，过桥时必需借助灯光来照明，很不幸的是，他

们只有一盏灯。另外，独木桥上最多承受两个人同时经过，否则将会坍塌。每个人单独过桥

都须要肯定的时间，不同的人须要的时间可能不同。两个人一起过桥时，由于只有一盏灯，

所以须要的时间是较慢的那个人单独过桥时所花的时间。现输入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）不属于操作系统。

A.WindowsB.DOSC.PhotoshopD.NOILinux

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

A.ABCB.CBAC.ACBD.BAC

7.目前个人电脑的（B）市场占有率最靠前的厂商包括Intel、AMD等公司。

A.显示器B.CPUC.内存D.鼠标

8.运用冒泡排序对序列进行升序排列，每执行一次交换操作系统将会削减1个逆序对，因此序

列5,4,3,2,1须要执行（C）次操作，才能完成冒泡排序。

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

9.1946年诞生于美国宾夕法尼亚高校的ENIAC属于（A）计算机。

A.电子管B.晶体管C.集成电路D.超大规模集成电路

10.无论是TCP/IP模型还是0SI模型，都可以视为网络的分层模型，每个网络协议都会被归

入某一层中。假如用现实生活中的例子来比方这些“层”，以下最恰当的是（A）。

A.中国公司的经理与波兰公司的经理交女商业文件

中国公司经理波兰公司经理

第4层

t111

卜国公亘圣理斑书

第3层:反兰公芝姿瑾受书

t111

第2层中国公巨打设波兰公司翻译

t111

第1层十五虻递员—f波兰邮递员

B.军队发布吩咐

第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.体育竞赛中，每一级竞赛的优胜者晋级上一级竞赛

第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）是主要用于显示网页服务器或者文件系统的HTML文件的内容，并让用户与这些

文件交互的一种软件。

A.资源管理器B.阅读器C.电子部件D.编译器

14.（C）是目前互联网上常用的E-mail服务协议。

A.B.FTPC.POP3D.Telnet

15.（C）就是把一个困难的问题分成两个或更多的相同类似的子问题，再把子问题分解成

更小的子问题……直到最终的子问题可以简洁地干脆求解。而原问题的解就是子问^解的并。

A.动态规划B.贪心C.分治D.搜寻

16.地址总线的位数确定了CPU可干脆寻址的内存空间大小，例如地址总线为16位，其最大的

可寻址空间为64KB。假如地址总线是32位，则理论上最大可寻址的内存空间为（D）,

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

17.蓝牙和Wi-Fi都是（C）设备。

A.无线广域网B.无线城域网C.无线局域网D.无线路由器

18.在程序运行过程中，假如递归调用的层数过多，会因为（A）引发错误。

A.系统安排的栈空间溢出B.系统安排的堆空间溢出

C.系统安排的队列空闰溢出D.系统安排的链表空间溢出

19.原字符串中随意一段连续的字符所组成的新字符串称为子串。则字符“AAABBBCCC”共

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

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

20.仿生学的问世开拓了独特的科学技术发展道路。人们探讨生物体的结构、功能和工作原理，

并将这些原理移植于新兴的工程技术中。以下关于仿生学的叙述，错误的是（B）

A.由探讨蝙蝠，独创雷达B.由探讨蜘蛛网，独创因特网

C.由探讨海豚，独创声纳D.由探讨电鱼，独创伏特电池

二、问题求解（共2题，每题5分，共计10分）

I.假如平面上任取n个整点（横纵坐标都是整数），其中肯定存在两个点，它们连线的中点也

是整点，那么n至少是。

2.在NOI期间，主办单位为了欢迎来自各国的选手，实行了盛大的晚宴。在第十八桌，有