全國青少年信息學奧賽普及組 C++語言試題

第二十三屆全國青少年信息學奧林匹克聯(lián)賽初賽普及組C++語言試題競賽時間：2017年10月14日14:30~16:30選手注意：?試題紙共有7頁，答題紙共有2頁，滿分100分。請在答題紙上作答，寫在試題紙上的一律無效。?不得使用任何電子設(shè)備（如計算器、手機、電子詞典等）或查閱任何書籍資料。一、單項選擇題（共20題，每題1.5分，共計30分；每題有且僅有一個正確選項）在8位二進制補碼中，10101011表示的數(shù)是十進制下的（）。A.43B.-85C.-43D.-84計算機存儲數(shù)據(jù)的基本單位是（）。A.bitB.ByteC.GBD.KB下列協(xié)議中與電子郵件無關(guān)的是（）。A.POP3B.SMTPC.WTOD.IMAP分辨率為800x600、16位色的位圖，存儲圖像信息所需的空間為（）。A.937.5KBB.4218.75KBC.4320KBD.2880KB計算機應(yīng)用的最早領(lǐng)域是（）。A.數(shù)值計算B.人工智能C.機器人D.過程控制下列不屬于面向?qū)ο蟪绦蛟O(shè)計語言的是（）。A.CB.C++C.JavaD.C#NOI的中文意思是（）。A.中國信息學聯(lián)賽B.全國青少年信息學奧林匹克競賽C.中國青少年信息學奧林匹克競賽D.中國計算機協(xié)會2017年10月1日是星期日，1999年10月1日是（）。A.星期三B.星期日C.星期五D.星期二甲、乙、丙三位同學選修課程，從4門課程中，甲選修2門，乙、丙各選修3門，則不同的選修方案共有()種。A.36B.48C.96D.192.設(shè)G是有n個結(jié)點、m條邊(n<m)的連通圖，必須刪去G的()條邊，才能使得G變成一棵樹。A.m-n+1B.m-nC.m+n+1D.n-m+1.對于給定的序列{ak},我們把(i,j)稱為逆序?qū)Ξ斍覂H當i<j且ai>aj。那么序列1,7,2,3,5,4的逆序?qū)?shù)為()個。A.4B.5C.6D.7.表達式a*(b+c)*d的后綴形式是()。A.abcd*+*B.abc+*d*C.a*bc+*dD.b+c*a*d13.向一個棧頂指針為hs的鏈式棧中插入一個指針s指向的結(jié)點時，應(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;若串S="copyright”，其子串的個數(shù)是()。A.72B.45C.46D.36十進制小數(shù)13.375對應(yīng)的二進制數(shù)是()。A.1101.011B.1011.011C.1101.101D.1010.01對于入棧順序為a,b,c,d,e,f,g的序列，下列()不可能是合法的出棧序列。A.a,b,c,d,e,f,gB.a,d,c,b,e,g,fC.a,d,b,c,g,f,eD.g,f,e,d,c,b,a.設(shè)A和B是兩個長為n的有序數(shù)組，現(xiàn)在需要將A和B合并成一個排好序的數(shù)組，任何以元素比較作為基本運算的歸并算法在最壞情況下至少要做()次比較。A.n2B.nlognC.2nD.2n-1

.從（）年開始，NOIP競賽將不再支持Pascal語言。A.2020B.2021C.2022D.2023.一家四口人，至少兩個人生日屬于同一月份的概率是（）（假定每個人生日屬于每個月份的概率相同且不同人之間相互獨立）。A.1/12B.1/144C.41/96D.3/4.以下和計算機領(lǐng)域密切相關(guān)的獎項是（）。A.奧斯卡獎B.圖靈獎C.諾貝爾獎D.普利策獎二、問題求解（共2題，每題5分，共計10分）1.一個人站在坐標（0,0）處，面朝x軸正方向。第一輪，他向前走1單位距離，然后右轉(zhuǎn)；第二輪，他向前走2單位距離，然后右轉(zhuǎn)；第三輪，他向前走3單位距離，然后右轉(zhuǎn)……他一直這么走下去。請問第2017輪后，他的坐標是：（，）。（請在答題紙上用逗號隔開兩空答案）2.如下圖所示，共有13個格子。對任何一個格子進行一次操作，會使得它自己以及與它上下左右相鄰的格子中的數(shù)字改變（由1變0，或由0變1）?，F(xiàn)在要使得所有的格子中的數(shù)字都變?yōu)?，至少需要在要使得所有的格子中的數(shù)字都變?yōu)?，至少需要次操作。三、閱讀程序?qū)懡Y(jié)果（共4題，每題8分，共計32分）.#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輸出：.#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輸出：.#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分，共計28分）1.（快速冪）請完善下面的程序，該程序使用分治法求Xpmodm的值。（第一空2分，其余3分）輸入：三個不超過10000的正整數(shù)X，p，m。輸出：Xpmodm的值。提示：若P為偶數(shù)，Xp=（X2）p/2；若P為奇數(shù)，Xp=X*（X2）（p-i）/2。#includeusingnamespacestd;intX,p,m,i,result;intmain(){cin>>x>>p>>m;TOC\o"1-5"\h\zresult=(1);while((2)){if(p%2==1)result=(3);p/=2;x=(4);}cout<<(5)<<endl;return0;}2.(切割繩子)有n條繩子，每條繩子的長度已知且均為正整數(shù)。繩子可以以任意正整數(shù)長度切割，但不可以連接。現(xiàn)在要從這些繩子中切割出m條長度相同的繩段，求繩段的最大長度是多少。(第一、二空2.5分，其余3分)輸入：第一行是一個不超過100的正整數(shù)n,第二行是n個不超過106的正整數(shù)，表示每條繩子的長度，第三行是一個不超過108的正整數(shù)m。輸出：繩段的最大長度，若無法切割，輸出Failed。#includeusingnamespacestd;intn,m,i,lbound,ubound,mid,count;intlen[100];//繩子長度intmain(){cin>>n;count=0;for(i=0;i<n;i++){cin>>len[i];;}cin>>m;if((2)){cout<<"Failed"<<endl;return0;}lbound=1;ubound=1000000;TOC\o"1-5"\h\zwhile((3)){mid=(4);count=0;for(i=0;i<n;i++)(5);if(count<m)ubound=mid-1;elselbound=mid;}cout<<lbound<<endl;return0;}第二十三屆全國青少年信息學奧林匹克聯(lián)賽初賽普及組參考基集www,shaoerbianchengwan2；,con一,單項選前邀《共卻庖-每咫L5生共計？0分）12a4367卜，4106BcAAABCCA111213141517IK1920BB6CACDCC&二、間感求解（共2題?每四，分「共計帕分工每咫全部答對得百分，役育部分分）1.1009,10682.3三，間彘程#寫踣果（注目題.每盟H分.共計薨分J1.z811輸出1：13C3分1輸出2；20171C5四、完善程序門用■期先以.F卉程）字填空M研白,一^等價的寫送，由*古賽鳳姐組本省弋取審定及上機驗證，可以不:上播IITN5科學委員會復(fù)桂）Pasml用目C++語月（:班言1.口｝12⑵P>0或P<>0P>?或pl-0或p3⑶result*xmodimresult*x%m3(4)x*xmodiimk*m%m3⑸resultJ力上.(1)SMt”8MRLen[lJ或incCcDuntjlenfi])coumtscount+le-nKi]或coant+-len[l]15田eountcm或n>count2.5⑶lbDLrd<Libound虱此口undilhwnd3的(1bound-HJbounch-1)div2或(lbound+ubounckl)s