2018年第二十四屆全國青少年信息學(xué)奧林匹克聯(lián)賽初賽提高組含問題詳解重新整理排版

1、第二十四屆全國青少年信息學(xué)奧林匹克聯(lián)賽初賽提t(yī)Wj組C+語言試題競(jìng)賽時(shí)間:2018年10月13日14:3016:30(WOR區(qū)新整理排版)選手注意：試題紙共有9頁，答題紙共有2頁，滿分100分。請(qǐng)?jiān)诖痤}紙上作答，寫在試題紙上的一律無效。不得使用任何電子設(shè)備(如計(jì)算器、手機(jī)、電子詞典等)或查閱任何書籍資料。一、單項(xiàng)選擇題(共10題，每題2分，共計(jì)20分；每題有且僅有一個(gè)正確選項(xiàng))1,下列四個(gè)不同進(jìn)制的數(shù)中，與其它三項(xiàng)數(shù)值上不相等的是()。A. (269)16B. (617)10C. (1151)8D. (1001101011)22,下列屬于解釋執(zhí)行的程序設(shè)計(jì)語言是()。A. CB. C+C. P

2、ascalD. Python3.中國計(jì)算機(jī)學(xué)會(huì)于()年創(chuàng)辦全國青少年計(jì)算機(jī)程序設(shè)計(jì)競(jìng)賽。A.1983B.1984C.1985D.19864,設(shè)根節(jié)點(diǎn)深度為0,一棵深度為h的滿k(k>1)叉樹，即除最后一層無任何子節(jié)點(diǎn)外,每一層上的所有結(jié)點(diǎn)都有k個(gè)子結(jié)點(diǎn)的樹，共有()個(gè)結(jié)點(diǎn)。A. (kh+1-1)/(k-1)B. kh-1C. khD. (kh-1)/(k-1)5,設(shè)某算法的時(shí)間復(fù)雜度函數(shù)的遞推方程是T(n)=T(n-1)+n(n為正整數(shù))及T(0)=1,則該算法的時(shí)間復(fù)雜度為()。A.O(logn)B.O(nlogn)C.O(n)D.O(n2)6 .表達(dá)式a*d-b*c的前綴形式是()。

3、A. ad*bc*-B. -*ad*bcC. a*d-b*cD. -*adbc7 .在一條長度為1的線段上隨機(jī)取兩個(gè)點(diǎn)，則以這兩個(gè)點(diǎn)為端點(diǎn)的線段的期望長度是（）。A. 1/2B. 1/3C. 2/3D. 3/58 .關(guān)于Catalan數(shù)Cn=（2n）!/（n+1）!/n!,下列說法中錯(cuò)誤的是（）。A. Cn表示有n+1個(gè)結(jié)點(diǎn)的不同形態(tài)的二叉樹的個(gè)數(shù)。B. Cn表示含n對(duì)括號(hào)的合法括號(hào)序列的個(gè)數(shù)。C. Cn表示長度為n的入棧序列對(duì)應(yīng)的合法出棧序列個(gè)數(shù)。D. Cn表示通過連接頂點(diǎn)而將n+2邊的凸多邊形分成三角形的方法個(gè)數(shù)。9 .假設(shè)一臺(tái)抽獎(jiǎng)機(jī)中有紅、藍(lán)兩色的球，任意時(shí)刻按下抽獎(jiǎng)按鈕，都會(huì)等概率獲得

4、紅球或藍(lán)球之一有足夠多的人每人都用這臺(tái)抽獎(jiǎng)機(jī)抽獎(jiǎng)假如他們的策略均為=抽中藍(lán)球則繼續(xù)抽球，抽中紅球則停止。最后每個(gè)人都把自己獲得的所有球放到一個(gè)大箱子里，最終大箱子里的紅球與藍(lán)球的比例接近于（）。10 .為了統(tǒng)計(jì)一個(gè)非負(fù)整數(shù)的二進(jìn)制形式中1的個(gè)數(shù)，代碼如下:intCountBit(intx)|intret=0;while(x)ret+;returnret;則空格內(nèi)要填入的語句是()。A. x>>=1B. x&=x-1C. x|=x>>1D. x<<=1二、不定項(xiàng)選擇題（共5題，每題2分，共計(jì)10分；每題有一個(gè)或多個(gè)正確選項(xiàng),多選或少選均不得分）1. N

5、OIP初賽中，選手可以帶入考場(chǎng)的有（）。A.筆B.橡皮C.手機(jī)（關(guān)機(jī)）D.草稿紙2. 2-3樹是一種特殊的樹，它滿足兩個(gè)條件：（1）每個(gè)內(nèi)部結(jié)點(diǎn)有兩個(gè)或三個(gè)子結(jié)點(diǎn)；（2）所有的葉結(jié)點(diǎn)到根的路徑長度相同。如果一棵2-3樹有10個(gè)葉結(jié)點(diǎn)，那么它可能有（）個(gè)非葉結(jié)點(diǎn)。A. 5B. 6C. 7D. 83.下列關(guān)于最短路算法的說法正確的有（）。A.當(dāng)圖中不存在負(fù)權(quán)回路但是存在負(fù)權(quán)邊時(shí)，Dijkstra算法不一定能求出源點(diǎn)到所有點(diǎn)的最短路。B.當(dāng)圖中不存在負(fù)權(quán)邊時(shí)，調(diào)用多次Dijkstra算法能求出每對(duì)頂點(diǎn)間最短路徑。C.圖中存在負(fù)權(quán)回路時(shí)，調(diào)用一次Dijkstra算法也一定能求出源點(diǎn)到所有點(diǎn)的最短路。D

6、.當(dāng)圖中不存在負(fù)權(quán)邊時(shí)，調(diào)用一次Dijkstra算法不能用于每對(duì)頂點(diǎn)間最短路計(jì)算。4 .下列說法中，是樹的性質(zhì)的有（）。A.無環(huán)B.任意兩個(gè)結(jié)點(diǎn)之間有且只有一條簡單路徑C.有且只有一個(gè)簡單環(huán)D.邊的數(shù)目恰是頂點(diǎn)數(shù)目減15 .下列關(guān)于圖靈獎(jiǎng)的說法中，正確的有（）。A.圖靈獎(jiǎng)是由電氣和電子工程師協(xié)會(huì)（IEEE）設(shè)立的。B.目前獲得該獎(jiǎng)項(xiàng)的華人學(xué)者只有姚期智教授一人。C.其名稱取自計(jì)算機(jī)科學(xué)的先驅(qū)、英國科學(xué)家艾倫麥席森圖靈。D.它是計(jì)算機(jī)界最負(fù)盛名、最崇高的一個(gè)獎(jiǎng)項(xiàng)，有“計(jì)算機(jī)界的諾貝爾獎(jiǎng)”之稱。三、問題求解（共2題，每題5分，共計(jì)10分）1 .甲乙丙丁四人在考慮周末要不要外出郊游。已知如果周末下雨

7、，并且乙不去，則甲一定不去；如果乙去，則丁一定去；如果丙去，則丁一定不去；如果丁不去，而且甲不去，則丙一定不去。如果周末丙去了，則甲（去了/沒去）（1分），乙（去了/沒去）（1分），丁（去了/沒去）（1分），周末（下雨/沒下雨）（2分）。2 .方程a*b=（aorb）*（aandb）,在a,b都取0,31中的整數(shù)時(shí)，共有組解。（*表示乘法；or表示按位或運(yùn)算；and表示按位與運(yùn)算）四、閱讀程序?qū)懡Y(jié)果(共4題，每題8分，共計(jì)32分)1.#include<cstdio>intmain()intx;scanf("%d",&x);intres=0;for(int

8、i=0;i<x;+i)if(i*i%x=1)+res;)printf("%d",res);return0;)輸入：15輸出：2.#include<cstdio>intn,d100;boolv100;intmain()scanf("%d",&n);for(inti=0;i<n;+i)scanf("%d",d+i);vi=false;)intcnt=0;for(inti=0;i<n;+i)if(!vi)for(intj=i;!vj;j=dj)vj=true;)+cnt;)printf("%d

9、n",cnt);return0;)輸入：107143259806輸出：3.#include<iostream>usingnamespacestd;strings;longlongmagic(intl,intr)longlongans=0;for(inti=l;i<=r;+i)ans=ans*4+si-'a'+1;)returnans;)intmain()cin>>s;intlen=s.length();intans=0;for(intl1=0;l1<len;+l1)for(intri=l1;r1<len;+r1)boolbo=

10、true;for(intl2=0;l2<len;+l2)for(intr2=l2;r2<len;+r2)if(magic(l1,r1)=magic(l2,r2)&&(l1!=l2|r1!=r2)bo=false;)if(bo)ans+=1;)cout<<ans<<endl;return0;)輸入：abacaba輸出：4.#include<cstdio>usingnamespacestd;constintN=110;boolisUseN;intn,t;intaN,bN;boolisSmall()for(inti=1;i<=n;

11、+i)if(ai!=bi)returnai<bi;returnfalse;)boolgetPermutation(intpos)if(pos>n)returnisSmall();)for(inti=1;i<=n;+i)if(!isUsei)bpos=i;isUsei=true;if(getPermutation(pos+1)returntrue;)isUsei=false;)returnfalse;)voidgetNext()for(inti=1;i<=n;+i)isUsei=false;)getPermutation(1);for(inti=1;i<=n;+i)

12、ai=bi;)intmain()scanf("%d%d",&n,&t);for(inti=1;i<=n;+i)scanf("%d”,&ai);)for(inti=1;i<=t;+i)getNext();)for(inti=1;i<=n;+i)printf("%d",ai);if(i=n)putchar('n');elseputchar('');)return0;)輸入1:610164532輸出1:(3分)輸入2:6200153426輸出2:（5分）五、完善程序（共共2題，

13、每題14分，共計(jì)28分）1.對(duì)于一個(gè)1至ijn的排列P（即1至ijn中每一個(gè)數(shù)在P中出現(xiàn)了恰好一次），令qi為第個(gè)位置之后第一個(gè)比P值更大的位置，如果不存在這樣的位置，則qi=n+1。舉例來說，如果n=5且P為15423，則P為26656。下列程序讀入了排列巳使用雙向鏈表求解了答案。試補(bǔ)全程序。（第二空2分，其余3分）數(shù)據(jù)范圍1<n<105。#include<iostream>usingnamespacestd;constintN=100010;intn;intLN,RN,aN;intmain()cin>>n;for(inti=1;i<=n;+i)in

14、tx;cin>>x;for(inti=1;i<=n;+i)Ri=JLi=i-1;(2)for(inti=1;i<=n;+i)L(3)=Lai;RLai=R(4);for(inti=1;i<=n;+i)cout<<(5)<<""cout<<endl;return0;2.一只小豬要買N件物品（N不超過1000）。它要買的所有物品在兩家商店里都有賣。第i件物品在第一家商店的價(jià)格是ai,在第二家商店的價(jià)格是bi,兩個(gè)價(jià)格都不小于0且不超過10000。如果在第一家商店買的物品的總額于不少于50000,那么在第一家店買的

15、物品都可以打95折（價(jià)格變?yōu)樵瓉淼?.95倍）。第一行一個(gè)數(shù)No接下來N行，每行兩個(gè)數(shù)。求小豬買齊所有物品所需最少的總額。輸入：第i行的兩個(gè)數(shù)分別代表ai,bi。輸出：輸出一行一個(gè)數(shù)，表示最少需要的總額，保留兩位小數(shù)。試補(bǔ)全程序。（第一空2分，其余3分）#include<cstdio>#include<algorithm>usingnamespacestd;constintInf=1000000000;constintthreshold=50000;constintmaxn=1000;intn,amaxn,bmaxn;boolput_amaxn;inttotal_a,t

16、otal_b;doubleans;intfthreshold;intmain()scanf("%d",&n);total_a=total_b=0;for(inti=0;i<n;+i)scanf("%d%d",a+i,b+i);if(ai<=bi)total_a+=ai;elsetotal_b+=bi;ans=total_a+total_b;total_a=total_b=0;for(inti=0;i<n;+i)if(_(1)_)_put_ai=true;total_a+=ai;elseput_ai=false;total_b+=

17、bi;if()printf("%.2f",total_a*0.95+total_b);return0;f0=0;for(inti=1;i<threshold;+i)fi=Inf;inttotal_b_prefix=0;for(inti=0;i<n;+i)if(!put_ai)total_b_prefix+=bi;for(intj=threshold-1;j>=0;-j)if(3)>=threshold&&fj!=Inf)ans=min(ans,(total_a+j+ai)*0.95+(4);fj=min(fj+bi,j>=ai?

18、(5):Inf);|)printf("%.2f",ans);return0;)第二十四屆全國青少年信息學(xué)奧林匹克聯(lián)賽初賽提高組參考答案、單項(xiàng)選擇題（共10題，每題2分，共計(jì)20分）12345678910DDBADBBADB二、不定項(xiàng)選擇題（共5題，每題2分，共計(jì)10分；每題有一個(gè)或多個(gè)正確選項(xiàng)，沒有部分分）12345ABCDABDABDBCD三、問題求解（共2題，每題5分，共計(jì)10分）1 .去了沒去沒去沒下雨（第4空2分，其余1分）2 .454四、閱讀程序?qū)懡Y(jié)果（共4題，每題8分，共計(jì)32分）1. 42. 63. 164. 輸出1:213564（3分）輸出2:325614（5分）五、完善程序（共計(jì)28分，以下