NOIP-2017全國青少年信息學(xué)奧林匹克聯(lián)賽提高組初賽試題答案

./NOIP2017全國青少年信息學(xué)奧林匹克聯(lián)賽提高組初賽試題答案一、單項(xiàng)選擇題〔共15題,每題1.5分,共計(jì)22.5分；每題有且僅有一個(gè)正確選項(xiàng)1.從<>年開始,NOIP競賽將不再支持Pascal語言.A.2020B.2021C.2022D.20232.在8位二進(jìn)制補(bǔ)碼中,10101011表示的數(shù)是十進(jìn)制下的<>.A.43B.-85C.-43D.-843.分辨率為1600x900、16位色的位圖,存儲圖像信息所需的空間為<>.A.2812.5KBB.4218.75KBC.4320KBD.2880KB4.2017年10月1日是星期日,1949年10月1日是<>.A.星期三B.星期日C.星期六D.星期二5.設(shè)G是有n個(gè)結(jié)點(diǎn)、m條邊<n≤m>的連通圖,必須刪去G的<>條邊,才能使得G變成一棵樹.A.m–n+1B.m-nC.m+n+1D.n–m+16.若某算法的計(jì)算時(shí)間表示為遞推關(guān)系式：T<N>=2T<N/2>+NlogNT<1>=1則該算法的時(shí)間復(fù)雜度為<>.A.O<N>B.O<NlogN>C.O<Nlog2N>D.O<N2>7.表達(dá)式a*<b+c>*d的后綴形式是<>.A.abcd*+*B.abc+*d*C.a*bc+*dD.b+c*a*d8.由四個(gè)不同的點(diǎn)構(gòu)成的簡單無向連通圖的個(gè)數(shù)是<>.A.32B.35C.38D.419.將7個(gè)名額分給4個(gè)不同的班級,允許有的班級沒有名額,有<>種不同的分配方案.A.60B.84C.96D.12010.若f[0]=0,f[1]=1,f[n+1]=<f[n]+f[n-1]>/2,則隨著i的增大,f[i]將接近與<>.A.1/2B.2/3D.111.設(shè)A和B是兩個(gè)長為n的有序數(shù)組,現(xiàn)在需要將A和B合并成一個(gè)排好序的數(shù)組,請問任何以元素比較作為基本運(yùn)算的歸并算法最壞情況下至少要做<>次比較.A.n2B.nlognC.2nD.2n-112.在n<n>=3>枚硬幣中有一枚質(zhì)量不合格的硬幣〔質(zhì)量過輕或質(zhì)量過重,如果只有一架天平可以用來稱重且稱重的硬幣數(shù)沒有限制,下面是找出這枚不合格的硬幣的算法.請把a(bǔ)-c三行代碼補(bǔ)全到算法中.a.AXUYb.AZc.n|A|算法Coin<A,n>1.kn/32.將A中硬幣分成X,Y,Z三個(gè)集合,使得|X|=|Y|=k,|Z|=n-2k3.ifW<X>≠W<Y>//W<X>,W<Y>分別為X或Y的重量4.then_______5.else_______6.__________7.ifn>2thengoto18.ifn=2then任取A中1枚硬幣與拿走硬幣比較,若不等,則它不合格；若相等,則A中剩下的硬幣不合格9.ifn=1thenA中硬幣不合格正確的填空順序是<>.A.b,c,aB.c,b,aC.c,a,bD.a,b,c13.在正實(shí)數(shù)構(gòu)成的數(shù)字三角形排列形式如圖所示,第一行的數(shù)為a11；第二行的數(shù)從左到右依次為a21,a22;…第n行的數(shù)為an1,an2,…,ann.從a11開始,每一行的數(shù)aij只有兩條邊可以分別通向下一行的兩個(gè)數(shù)a<i+1>j和a<i+1><j+1>.用動態(tài)規(guī)劃算法找出一條從a11向下通到an1,an2,…,ann中某個(gè)數(shù)的路徑,使得該路徑上的數(shù)之和達(dá)到最大.令C[i,j]是從a11到aij的路徑上的數(shù)的最大和,并且C[i,0]=C[0,j]=0,則C[i,j]=<>.A.max{C[i-1,j-1],C[i-1,j]}+aijB.C[i-1,j-1]+c[i-1,j]C.max{C[i-1,j-1],C[i-1,j]}+1D.max{C[i,j-1],C[i-1,j]}+aij14.小明要去南美洲旅游,一共乘坐三趟航班才能到達(dá)目的地,其中第1個(gè)航班準(zhǔn)點(diǎn)的概率是0.9,第2個(gè)航班準(zhǔn)點(diǎn)的概率為0.8,第3個(gè)航班準(zhǔn)點(diǎn)的概率為0.9.如果存在第i個(gè)〔i=1,2航班晚點(diǎn),第i+1個(gè)航班準(zhǔn)點(diǎn),則小明將趕不上第i+1個(gè)航班,旅行失??；除了這種情況,其他情況下旅行都能成功.請問小明此次旅行成功的概率是<>.A.0.5B.0.648C.0.7215.歡樂噴球：兒童游樂場有個(gè)游戲叫"歡樂噴球",正方形場地中心能不斷噴出彩色乒乓球,以場地中心為圓心還有一個(gè)圓軌道,軌道上有一列小火車在勻速運(yùn)動,火車有六節(jié)車廂.假設(shè)乒乓球等概率落到正方形場地的每個(gè)地點(diǎn),包括火車車廂.小朋友玩這個(gè)游戲時(shí),只能坐在同一個(gè)火車車廂里,可以在自己的車廂里撿落在該車廂內(nèi)的所有乒乓球,每個(gè)人每次游戲有三分鐘時(shí)間,則一個(gè)小朋友獨(dú)自玩一次游戲期望可以得到<>個(gè)乒乓球.假設(shè)乒乓球噴出的速度為2個(gè)/秒,每節(jié)車廂的面積是整個(gè)場地面積的1/20.A.60B.108C.18D.20二、不定項(xiàng)選擇題〔共5題,每題1.5分,共計(jì)7.5分；每題有一個(gè)或多個(gè)正確選項(xiàng),多選或少選均不得分1.以下排序算法在最壞情況下時(shí)間復(fù)雜度最優(yōu)的有<>.A.冒泡排序B.快速排序C.歸并排序D.堆排序2.對于入棧順序?yàn)閍,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,a3.下列算法中,<>是穩(wěn)定的排序算法.A.快速排序B.堆排序C.希爾排序D.插入排序4.以下是面向?qū)ο蟮母呒壵Z言的是<>.A.匯編語言B.C++C.FortanD.Java5.以下和計(jì)算機(jī)領(lǐng)域密切相關(guān)的獎項(xiàng)是<>.A.奧斯卡獎B.圖靈獎C.諾貝爾獎D.王選獎三、問題求解〔共2題,每題5分,共計(jì)10分1.如圖所示,共有13個(gè)格子.對任何一個(gè)格子進(jìn)行一次操作,會使得它自己以及與它上下左右相鄰的格子中的數(shù)字改變<由1變0,或由0變1>.現(xiàn)在要使得所有的格子中的數(shù)字都變?yōu)?,至少需要3次操作.2.如圖所示,A到B是連通的.假設(shè)刪除一條細(xì)的邊的代價(jià)是1,刪除一條粗的邊的代價(jià)是2,要讓A、B不連通,最小代價(jià)是4<2分>,最小代價(jià)的不同方案數(shù)是9<3分>.〔只要有一條刪除的邊不同,就是不同的方案四、閱讀程序?qū)懡Y(jié)果〔共4題,每題8分,共計(jì)32分1.#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;}輸入:84輸出:152.#includeusingnamespacestd;intmain<>{intn,i,j,x,y,nx,ny;inta[40][40];for<i=0;i<40;i++>for<j=0;j<40;j++>a[i][j]=0;cin>>n;y=0;x=n-1;n=2*n-1;for<i=1;i<=n*n;i++>{a[y][x]=i;ny=<y-1+n>%n;nx=<x+1>%n;if<<y==0&&x==n-1>||a[ny][nx]!=0>y=y+1;else{y=ny;x=nx;}}for<j=0;j<n;j++>cout<<a[0][j]<<"";cout<<endl;return0;}輸入:3輸出:172418153.#includeusingnamespacestd;intn,s,a[100005],t[100005],i;voidmergesort<intl,intr>{if<l==r>return;intmid=<l+r>/2;intp=l;inti=l;intj=mid+1；mergesort<l,mid>;mergesort<mid+1,r>;while<i<=mid&&j<=r>{if<a[j]<a[i]>{s+=mid–i+1;t[p]=a[j];p++;j++;}else{t[p]=a[i];p++;i++;}}while<i<=mid>{t[p]=a[i];p++;i++;}while<j<=r>{t[p]=a[j];p++;j++;}for<i=l;i<=r;i++>a[i]=t[i];}intmain<>{cin>>n;for<i=1;i<=n;i++>cin>>a[i];mergesort<1,n>;cout<<s<<endl;return0;}輸入:6263451輸出:84.#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:13<2分>輸入2:20171014輸出2:20171<3分>輸入3:987321輸出3:1321<3分>五、完善程序〔共2題,每題14分,共計(jì)28分1.大整數(shù)除法：給定兩個(gè)正整數(shù)p和q,其中p不超過10100,q不超過100000,求p除以q的商和余數(shù).〔第一空2分,其余3分輸入：第一行是p的位數(shù)n,第二行是正整數(shù)p,第三行是正整數(shù)q.輸出：兩行,分別是p除以q的商和余數(shù).#includeusingnamespacestd;intp[100];intn,i,q,rest;charc;intmain<>{cin>>n;for<i=0;i<n;i++>{cin>>c;p[i]=c–‘0’；}cin>>q;rest=p[0];i=1;while<rest<q&&i<n>{rest=rest*10+p[i];i++;}if<rest<q>cout<<0<<endl;else{cout<<rest/q;while<i<n>{rest=rest%q*10+p[i];i++;cout<<rest/q;}cout<<endl;}cout<<rest%q<<endl;return0;}2.最長路徑：給定一個(gè)有向五環(huán)圖,每條邊長度為1,求圖中的最長路徑長度.〔第五空2分,其余3分輸入：第一行是結(jié)點(diǎn)數(shù)n〔不超過100和邊數(shù)m,接下來m行,每行兩個(gè)整數(shù)a,b,表示從結(jié)點(diǎn)a到結(jié)點(diǎn)b有一條有向邊.結(jié)點(diǎn)標(biāo)號從0到<n-1>.輸出：最長路徑長度.提示：先進(jìn)行拓?fù)渑判?然后按照拓?fù)渑判蛴?jì)算最長路徑.#includeusingnamespacestd;intn,m,i,j,a,b,head,tail,ans;intgraph[100][100];//用鄰接矩陣存儲圖intdegree[100];//記錄每個(gè)結(jié)點(diǎn)的入度intlen[100];//記錄以各結(jié)點(diǎn)為終點(diǎn)的最長路徑長度intqueue[100];//存放拓?fù)渑判蚪Y(jié)果intmain<>{cin>>n>>m;for<i=0;i<n;i++>for<j=0;j<n;j++>graph[i][j]=0;for<i=0;i<n;i++>degree[i]=0;for<i=0;i<m;i++>{cin>>a>>b;graph[a][b]=1;degree[b]++;}tail=0;for<i=0;i<n;i++>if<degree[i]==0>{queue[tail]=i;tail++;}head=0;while<tail<n-1>{for<i=0;i<n;i++>if<graph[q