第二十三屆全國(guó)青少年信息學(xué)奧林匹克聯(lián)賽初賽普及組C++語(yǔ)言試題

競(jìng)賽時(shí)間：2017年10月14日14:30~16:30選手注意：

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

●不得使用任何電子設(shè)備（如計(jì)算器、手機(jī)、電子詞典等）或查閱任何書(shū)籍資料。一、單項(xiàng)選擇題（共20題，每題1.5分，共計(jì)30分；每題有且僅有一個(gè)正確選項(xiàng)）1.在8位二進(jìn)制補(bǔ)碼中，10101011表示的數(shù)是十進(jìn)制下的（）。

A.43

B.-85

C.-43

D.-842.計(jì)算機(jī)存儲(chǔ)數(shù)據(jù)的基本單位是（）。

A.bit

B.Byte

C.GB

D.KB3.下列協(xié)議中與電子郵件無(wú)關(guān)的是（）。

A.POP3

B.SMTP

C.WTO

D.IMAP4.分辨率為800x600、16位色的位圖，存儲(chǔ)圖像信息所需的空間為（）。

A.937.5KB

B.4218.75KB

C.4320KB

D.2880KB5.計(jì)算機(jī)應(yīng)用的最早領(lǐng)域是（）。

A.數(shù)值計(jì)算

B.人工智能

C.機(jī)器人

D.過(guò)程控制6.下列不屬于面向?qū)ο蟪绦蛟O(shè)計(jì)語(yǔ)言的是（）。

A.C

B.C++

C.Java

D.C#7.NOI的中文意思是（）。

A.中國(guó)信息學(xué)聯(lián)賽

B.全國(guó)青少年信息學(xué)奧林匹克競(jìng)賽

C.中國(guó)青少年信息學(xué)奧林匹克競(jìng)賽

D.中國(guó)計(jì)算機(jī)協(xié)會(huì)8.2017年10月1日是星期日，1999年10月1日是（）。

A.星期三

B.星期日

C.星期五

D.星期二9.甲、乙、丙三位同學(xué)選修課程，從4門(mén)課程中，甲選修2門(mén)，乙、丙各選修3門(mén)，則不同的選修方案共有（）種。

A.36

B.48

C.96

D.19210.設(shè)G是有n個(gè)結(jié)點(diǎn)、m條邊（n≤m）的連通圖，必須刪去G的（）條邊，才能使得G變成一棵樹(shù)。

A.m–n+1

B.m-n

C.m+n+1

D.n–m+111.對(duì)于給定的序列{ak}，我們把(i,j)稱(chēng)為逆序?qū)Ξ?dāng)且僅當(dāng)i<j且ai>aj。那么

序列1,7,2,3,5,4的逆序?qū)?shù)為（）個(gè)。

A.4

B.5

C.6

D.712.表達(dá)式a*(b+c)*d的后綴形式是（）。

A.abcd*+*

B.abc+*d*

C.a*bc+*d

D.b+c*a*d13.向一個(gè)棧頂指針為hs的鏈?zhǔn)綏Ｖ胁迦胍粋€(gè)指針s指向的結(jié)點(diǎn)時(shí)，應(yīng)執(zhí)行（）。

A.hs->next=s;

B.s->next=hs;hs=s;

C.s->next=hs->next;hs->next=s;

D.s->next=hs;hs=hs->next;14.若串S=“copyright”，其子串的個(gè)數(shù)是（）。

A.72

B.45

C.46

D.3615.十進(jìn)制小數(shù)13.375對(duì)應(yīng)的二進(jìn)制數(shù)是（）。

A.1101.011

B.1011.011

C.1101.101

D.1010.0116.對(duì)于入棧順序?yàn)閍,b,c,d,e,f,g的序列，下列（）不可能是合法的出棧序

列。

A.a,b,c,d,e,f,g

B.a,d,c,b,e,g,f

C.a,d,b,c,g,f,e

D.g,f,e,d,c,b,a17.設(shè)A和B是兩個(gè)長(zhǎng)為n的有序數(shù)組，現(xiàn)在需要將A和B合并成一個(gè)排好序的數(shù)組，任何以元素比較作為基本運(yùn)算的歸并算法在最壞情況下至少要做（）次比較。

A.n2

B.nlogn

C.2n

D.2n-1三、閱讀程序?qū)懡Y(jié)果（共4題，每題8分，共計(jì)32分）1.#includeusingnamespacestd;

intmain(){intt[256];strings;inti;

cin>>s;

for(i=0;i<256;i++)t[i]=0;

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

for(i=0;i<s.length();i++)if(t[s[i]]==1){

cout<<s[i]<<endl;return0;

}

cout<<"no"<<endl;return0;

}輸入：xyzxyw

輸出：_________2.#includeusingnamespacestd;

intg(intm,intn,intx){intans=0;

inti;

if(n==1)return1;

for(i=x;i<=m/n;i++)ans+=g(m-i,n-1,i);returnans;}intmain(){intt,m,n;cin>>m>>n;

cout<<g(m,n,0)<<endl;return0;

}輸入：73

輸出：_________3.#includeusingnamespacestd;

intmain(){stringch;inta[200];intb[200];

intn,i,t,res;cin>>ch;

n=ch.length();

for(i=0;i<200;i++)b[i]=0;

for(i=1;i<=n;i++){a[i]=ch[i-1]-'0';b[i]=b[i-1]+a[i];

}

res=b[n];

t=0;

for(i=n;i>0;i--){if(a[i]==0)

t++;

if(b[i-1]+t<res)res=b[i-1]+t;

}

cout<<res<<endl;return0;

}輸入：1001101011001101101011110001

輸出：_________4.#includeusingnamespacestd;

intmain(){intn,m;

cin>>n>>m;intx=1;

inty=1;intdx=1;intdy=1;intcnt=0;

while(cnt!=2){cnt=0;

x=x+dx;

y=y+dy;

if(x==1||x==n){++cnt;

dx=-dx;

}

if(y==1||y==m){++cnt;

dy=-dy;

}

}

cout<<x<<""<<y<<endl;return0;

}輸入1：43

輸出1：_________（3分）

輸入2：20171014

輸出2：_________（5分）四、完善程序（共2題，每題14分，共計(jì)28分）1.（快速冪）請(qǐng)完善下面的程序，該程序使用分治法求xp

modm的值。（第一空2分，其余3分）輸入：三個(gè)不超過(guò)10000的正整數(shù)x，p，m。

輸出：xp

modm的值。

提示：若p為偶數(shù)，xp=(x2)p/2；若p為奇數(shù)，xp=x*(x2)(p-1)/2。#includeusingnamespacestd;intx,p,m,i,result;intmain(){

cin>>x>>p>>m;

result=

(1)

;

while(

(2)

){

if(p%2==1)

result=

(3)

;

p/=2;

x=

(4)

;

}

cout<<

(5)

<<endl;

return0;

}2.（切割繩子）有n條繩子，每條繩子的長(zhǎng)度已知且均為正整數(shù)。繩子可以以任意正整數(shù)長(zhǎng)度切割，但不可以連接。現(xiàn)在要從這些繩子中切割出m條長(zhǎng)度相同的繩段，求繩段的最大長(zhǎng)度是多少。（第一、二空2.5分，其余3分）輸入：第一行是一個(gè)不超過(guò)100的正整數(shù)n，第二行是n個(gè)不超過(guò)106的正整數(shù)，表示每條繩子的長(zhǎng)度，第三行是一個(gè)不超過(guò)108的正整數(shù)m。

輸出：繩段的最大長(zhǎng)度，若無(wú)法切割，輸出Failed。#includeusingnamespacestd;intn,m,i,lbound,ubound,mid,count;

intlen[100];//繩子長(zhǎng)度intmain(){cin>>n;count=0;

for(i=0;i<n;i++){cin>>len[i];

(1)

;

}

cin>>m;

if(

(2)

){

cout<<"Failed"<<endl;

return0;

}

lbound=1;

ubound=1000000;

while(

(3)