NOIP提高组初赛C++.docx

NOIP提高组初赛C++.docx

《NOIP提高组初赛C++.docx》由会员分享，可在线阅读，更多相关《NOIP提高组初赛C++.docx（18页珍藏版）》请在冰点文库上搜索。

NOIP提高组初赛C++

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

进步组C++语言试题〔2小时〕

选手注意:

●不得使用任何电子设备〔如计算器、手机、电子词典等〕或查阅任何书籍资料。

一、单项选择题〔共15题，每题1.5分，共计22.5分；每题有且仅有一个正确选项〕

1.以下不是微软公司出品的软件是〔〕。

Ａ.PowerpointＢ.WordＣ.ExcelＤ.AcrobatReader

2.假如开场时计算机处于小写输入状态，如今有一只小老鼠反复按照CapsLock、字母键A、字母键S和字母键D的顺序来回按键，即CapsLock、A、S、D、S、A、CapsLock、A、S、D、S、A、CapsLock、A、S、D、S、A、……，屏幕上输出的第81个字符是字母〔〕。

Ａ.AＢ.SＣ.DＤ.A

3.二进制数00101100和01010101异或的结果是〔〕。

Ａ.00101000Ｂ.01111001Ｃ.01000100Ｄ.00111000

4.与二进制小数0.1相等的八进进制数是〔〕。

Ａ

5.以比拟作为根本运算，在N个数中找最小数的最少运算次数为〔〕。

Ａ.NＢ.N-1Ｃ.N2Ｄ.logN

6.表达式a*（b+c）-d的后缀表达形式为〔〕。

Ａ.abcd*+-Ｂ.abc+*d-Ｃ.abc*+d-Ｄ.-+*abcd

7.一棵二叉树如右图所示，假设采用二叉树链表存储该二叉树〔各个结点包括结点的数据、左孩子指针、右孩子指针〕。

假如没有左孩子或者右孩子，那么对应的为空指针。

那么该链表中空指针的数目为〔〕。

A.6B.7C.12Ｄ.14

8.G是一个非连通简单无向图，共有28条边，那么该图至少有〔〕个顶点。

Ａ

9.某计算机的CPU和内存之间的地址总线宽度是32位〔bit〕，这台计算机最多可以使用〔〕的内存。

A.2GBB.4GBC.8GBD.16GB

10.有以下程序：

#include

usingnamespacestd;

intmain（）{

intk=4,n=0;

while（n

n++;

if（n%3!

=0）continue;

k--;

}

cout<

return0;

}

程序运行后的输出结果是〔〕。

Ａ.2,2Ｂ.2,3Ｃ.3,2Ｄ.3,3

11.有7个一模一样的苹果，放到3个一样的盘子中，一共有〔〕种放法。

Ａ.7Ｂ.8Ｃ.21Ｄ.37

12.Lucia和她的朋友以及朋友的朋友都在某社交网站上注册了账号。

以下图是他们之间的关系图，两个人之间有边相连代表这两个人是朋友，没有边相连代表不是朋友。

这个社交网站的规那么是：

假如某人A向他〔她〕的朋友B分享了某张照片，那么B就可以对该照片进展评论；假如B评论了该照片，那么他〔她〕的所有朋友都可以看见这个评论以及被评论的照片，但是不能对该照片进展评论〔除非A也向他〔她〕分享了该照片〕。

如今Lucia已经上传了一张照片，但是她不想让Jacob看见这张照片，那么她可以向以下朋友〔〕分享该照片。

Ａ.Dana,Michael,EveＢ.Dana,Eve,Monica

Ｃ.Michael,Eve,JacobＤ.Micheal,Peter,Monica

13.周末小明和爸爸妈妈三个人一起想动手做三道菜。

小明负责洗菜、爸爸负责切菜、妈妈负责炒菜。

假设做每道菜的顺序都是：

先洗菜10分钟，然后切菜10分钟，最后炒菜10分钟。

那么做一道菜需要30分钟。

注意：

两道不同的菜的一样步骤不可以同时进展。

例如第一道菜和第二道的菜不能同时洗，也不能同时切。

那么做完三道菜的最短时间需要〔〕分钟。

A.90B.60C.50D.40

14.假设某算法的计算时间表示为递推关系式

T（n）=2T（

）+

T

（1）=1

那么算法的时间复杂度为〔〕。

A.O（n）B.O（

）C.O（

logn）D.O（n2）

1.给定含有n个不同的数的数组L=。

假如L中存在Xi〔1xi+1>...>Xn，那么称L是单峰的，并称xi是L的“峰顶〞。

如今L是单峰的，请把a-c三行代码补全到算法中使得算法正确找到L的峰顶。

a.Search（k+1,n）

b.Search（1,k-1）

c.returnL[k]

Search（1,n）

1.k←[n/2]

2.ifL[k]>L[k-1]andL[k]>L[k+1]

3.then__________

4.elseifL[k]>L[k-1]andL[k]

5.then__________

6.else__________

正确的填空顺序是〔〕。

A.c,a,bB.c,b,aC.a,b,cD.b,a,c

二、不定项选择题〔共5题，每题1.5分，共计7.5分；每题有一个或多个正确选项，多项选择或少选均不得分〕

1.以下属于无线通信技术的有〔〕。

A.蓝牙B.WiFiC.GPRSD.以太网

2.可以将单个计算机接入到计算机网络中的网络接入通讯设备有〔〕。

A.网卡B.光驱C.鼠标D.显卡

3.以下算法中运用分治思想的有〔〕。

A.快速排序B.归并排序C.冒泡排序D.计数排序

4.以下图表示一个果园灌溉系统，有A、B、C、D四个阀门，每个阀门可以翻开或关上，所有管道粗细一样，以下设置阀门的方法中，可以让果树浇上水的有〔〕。

有水有水

果树

A.B翻开，其他都关上B.AB都翻开，CD都关上

C.A翻开，其他都关上D.D翻开，其他都关上

5.参加NOI比赛，以下能带入考场的有〔〕。

A.钢笔B.适量的衣服C.U盘D.铅笔

三、问题求解〔共2题，每题5分，共计10分；每题全部答对得5分，没有局部分〕

1.一个1×8的方格图形〔不可旋转〕用黑、白两种颜色填涂每个方格。

假如每个方格只能填涂一种颜色，且不允许两个黑格相邻，共有_________种填涂方案。

2.某中学在安排期末考试时发现，有7个学生要参加7门课程的考试，下表列出了哪些学生参加哪些考试〔用√表示要参加相应的考试〕。

最少要安排_________个不同的考试时间段才能防止冲突？

考试

学生1

学生2

学生3

学生4

学生5

学生6

学生7

通用技术

√

√

√

物理

√

√

√

化学

√

√

生物

√

√

√

历史

√

√

√

地理

√

√

√

政治

√

√

四、阅读程序写结果〔共4题，每题8分，共计32分〕

1.#include

usingnamespacestd;

intmain（）{

inta[6]={1,2,3,4,5,6};

intpi=0;

intpj=5;

intt,i;

while（pi

t=a[pi];a[pi]=a[pj];a[pj]=t;

pi++;

pj--;

}

for（i=0;i<6;i++）

cout<

cout<

return0;

}

输出：

_________

2.#include

usingnamespacestd;

intmain（）{

chara[100][100],b[100][100];

stringc[100];

stringtmp;

intn,i=0,j=0,k=0,total_len[100],length[100][3];

cin>>n;

getline（cin,tmp）;

for（i=0;i

getline（cin,c[i]）;

total_len[i]=c[i].size（）;

}

for（i=0;i

j=0;

while（c[i][j]!

=':

'）{

a[i][k]=c[i][j];k=k+1;j++;

}

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

a[i][k]=0;

k=0;

for（j=j+1;j

b[i][k]=c[i][j];

k=k+1;

}

length[i][2]=k-1;

b[i][k]=0;

k=0;

}

for（i=0;i

if（length[i][1]>=length[i][2]）

cout<<"NO,";

else{

k=0;

for（j=0;j

if（a[i][k]==b[i][j]）

k=k+1;

if（k>length[i][1]）break;

}

if（j==length[i][2]）

cout<<"NO,";

else

cout<<"YES,";

}

}

cout<

return0;

}

输入：

3AB:

ACDEbFBkBD

AR:

ACDBrT

SARS:

SevereAtypicalRespiratorySyndrome输出：

_________

〔注：

输入各行前后均无空格〕

3.#include

usingnamespacestd;

intlps（stringseq,inti,intj）{

intlen1,len2;

if（i==j）return1;

if（i>j）return0;

if（seq[i]==seq[j]）

returnlps（seq,i+1,j-1）+2;

len1=lps（seq,i,j-1）;

len2=lps（seq,i+1,j）;

if（len1>len2）returnlen1;

returnlen2;

}

intmain（）{

stringseq="acmerandacm";

intn=（）;

cout<

return0;

}

输出：

_________

4.#include

#include

usingnamespacestd;

intmap[100][100];

intsum[100],weight[100];

intvisit[100];

intn;

voiddfs（intnode）{

visit[node]=1;

sum[node]=1;

intv,maxw=0;

for（v=1;v<=n;v++）{

if（!

map[node][v]||visit[v]）

continue;

dfs（v）;

sum[node]+=sum[v];

if（sum[v]>maxw）maxw=sum[v];

}

if（n-sum[node]>maxw）maxw=n-sum[node];

weight[node]=maxw;

}

intmain（）{

memset（map,0,sizeof（map））;

memset（sum,0,sizeof（sum））;

memset（weight,0,sizeof（weight））;

memset（visit,0,sizeof（visit））;

cin>>n;

inti,x,y;

for（i=1;i

cin>>x>>y;

map[x][y]=1;

map[y][x]=1;

}

dfs

（1）;

intans=n,ansN=0;

for（i=1;i<=n;i++）

if（weight[i]

ans=weight[i];

ansN=i;

}

cout<

return0;

}

输入：

11

12

13

24

25

26

37

78

711

69

910

输出：

_________

五、完善程序〔共2题，每题14分，共计28分〕

1.〔交朋友〕根据社会学研究说明，人们都喜欢找和自己身高相近的人做朋友。

如今有n名身高两两不一样的同学依次走入教室，调查人员想预测每个人在走入教室的瞬间最想和已经进入教室的哪个人做朋友。

当有两名同学和这名同学的身高差一样时，这名同学会更想和高的那个人做朋友。

比方一名身高为1.80米的同学进入教室时，有一名身高为1.79米的同学和一名身高为1.81米的同学在教室里，那么这名身高为1.80米的同学会更想和身高为1.81米的同学做朋友。

对于第一个走入教室的同学我们不做预测。

由于我们知道所有人的身高和走进教室的次序，所以我们可以采用离线的做法来解决这样的问题，我们用排序加链表的方式帮助每一个人找到在他之前进入教室的并且和他身高最相近的人。

〔第一空2分，其余3分〕

#include

usingnamespacestd;

#defineMAXN200000

#defineinfinity2147483647

intanswer[MAXN],height[MAXN],previous[MAXN],next[MAXN];

intrank[MAXN];

intn;

voidsort（intl,intr）{

intx=height[rank[（l+r）/2]],i=l,j=r,temp;

while（i<=j）{

while（height[rank[i]]

while（height[rank[j]]>x）j--;

if（

（1））{

temp=rank[i];rank[i]=rank[j];rank[j]=temp;

i++;

j--;

}

}

if（i

if（l

}

intmain（）{

cin>>n;

inti,higher,shorter;

for（i=1;i<=n;i++）{

cin>>height[i];

rank[i]=i;

sort（1,n）;

for（i=1;i<=n;i++）{

previous[rank[i]]=rank[i-1];

（2）;

}

for（i=n;i>=2;i--）{

higher=shorter=infinity;

if（previous[i]!

=0）

shorter=height[i]-height[previous[i]];

if（next[i]!

=0）

（3）;

if（（4））

answer[i]=previous[i];

else

answer[i]=next[i];

next[previous[i]]=next[i];

（5）;

}

for（i=2;i<=n;i++）

cout<

"<

return0;

}

2.（交通中断〕有一个小国家，国家内有n座城市和m条双向的道路，每条道路连接着两座不同的城市。

其中1号城市为国家的首都。

由于地震频繁可能导致某一个城市与外界交通全部中断。

这个国家的首脑想知道，假如只有第i（i>1）个城市因地震而导致交通中断时，首都到多少个城市的最短途径长度会发生改变。

假如因为无法通过第i个城市而导致从首都出发无法到达某个城市，也认为到达该城市的最短途径长度改变。

对于每一个城市i，假定只有第i个城市与外界交通中断，输出有多少个城市会因此导致到首都的最短途径长度改变。

我们采用邻接表的方式存储图的信息，其中head[x]表示顶点x的第一条边的编号，next[i]表示第i条边的下一条边的编号，point[i]表示第i条边的终点，weight[i]表示第i条边的长度。

〔第一空2分，其余3分〕

#include

#include

usingnamespacestd;

#defineMAXN6000

#defineMAXM100000

#defineinfinity2147483647

inthead[MAXN],next[MAXM],point[MAXM],weight[MAXM];

intqueue[MAXN],dist[MAXN],visit[MAXN];

intn,m,x,y,z,total=0,answer;

voidlink（intx,inty,intz）{

total++;

next[total]=head[x];head[x]=total;point[total]=y;weight[total]=z;

total++;

next[total]=head[y];head[y]=total;point[total]=x;weight[total]=z;

}

intmain（）{

inti,j,s,t;

cin>>n>>m;

for（i=1;i<=m;i++）{

cin>>x>>y>>z;

link（x,y,z）;

}

for（i=1;i<=n;i++）dist[i]=infinity;

（1）;

queue[1]=1;

visit[1]=1;

s=1;

t=1;

//使用SPFA求出第一个点到其余各点的最短路长度

while（s<=t）{

x=queue[s%MAXN];

j=head[x];

while（j!

=0）{

if（

（2））{

dist[point[j]]=dist[x]+weight[j];

if（visit[point[j]]==0）{

t++;

queue[t%MAXN]=point[j];

visit[point[j]]=1;

}

}

j=next[j];

}

（3）;

s++;

}

for（i=2;i<=n;i++）{

queue[1]=1;

memset（visit,0,sizeof（visit））;

visit[1]=1;

s=1;

t=1;

while（s<=t）{//判断最短路长度是否不变

x=queue[s];

j=head[x];

while（j!

=0）{

if（point[j]!

=i&&（4）&&visit[point[j]]==0）{

（5）;

t++;

queue[t]=point[j];

}

j=next[j];

}

s++;

}

answer=0;

for（j=1;j<=n;j++）

answer+=1-visit[j];

cout<

"<

return0;

}

答案：

一、DABBBBBBBDBACCA

二、ABCAABAABD

三、553

四、1.6,5,4,3,2,1

2.YES,NO,YES,

3.5

4.25

五、1.

（1）i<=j

（2）next[rank[i]]=rank[i+1]

（3）higher=height[next[i]]-height[i]

（4）shorter

（5）previous[next[i]]=previous[i]

2.

（1）dist[1]=0

（2）dist[x]+weight[j]

（3）visit[x]=0

（4）dist[x]+weight[j]==dist[point[j]]

（5）visit[point[j]]=1