信息學(xué)競(jìng)賽真題

1、6. vm）的連通圖，必須刪去G的（）條邊，才能使得G變成一棵樹(shù)A.m-n+1B.m-nC.m+n+1D.n-m+1若某算法的計(jì)算時(shí)間表示為遞推關(guān)系式:T(N)=2T(N/2)+NlogNT(1)=1則該算法的時(shí)間復(fù)雜度為()。7. A.O(N)B.O(NlogN)C.O(Nlog2N)D.O(N2)表達(dá)式a*(b+c)*d的后綴形式是()。8. A.abcd*+*B.abc+*d*C.a*bc+*dD.b+c*a*d由四個(gè)不同的點(diǎn)構(gòu)成的簡(jiǎn)單無(wú)向連通圖的個(gè)數(shù)是（）A.32B.35C.38D.41將7個(gè)名額分給4個(gè)不同的班級(jí)，允許有的班級(jí)沒(méi)有名額，有（）種不同的分配方案。9. A.60B.84C

2、.96D.120若f0=0,f1=1,fn+1=（fn+fn-1）/2，則隨著i的增大，fi將接近與（）。A.1/2B.2/310. D.1設(shè)A和B是兩個(gè)長(zhǎng)為n的有序數(shù)組，現(xiàn)在需要將A和B合并成一個(gè)排好序的數(shù)組，請(qǐng)問(wèn)任何以元素比較作為基本運(yùn)算的歸并算法最壞情況下至少要做（）次比較。11. A.n2B.nlognC.2nD.2n-1在n（n>=3戲硬幣中有一枚質(zhì)量不合格的硬幣（質(zhì)量過(guò)輕或質(zhì)量過(guò)重），如果只有一架天平可以用來(lái)稱重且稱重的硬幣數(shù)沒(méi)有限制，下面是找出這枚不合格的硬幣的算法。請(qǐng)把a(bǔ)-c三行代碼補(bǔ)全到算法中。AXUYAZn|A|算法Coin(A,n)kn/3將A中硬幣分成X,Y,3個(gè)

3、集合，使得|X|=|Y|=k,|Z|=n-2kifW(X片W(Y)/W(X),W(Y別為X或Y的重量thenelseifn>2thengoto1ifn=2then任取A中1枚硬幣與拿走硬幣比較，若不等，則它不合格；若相等，貝UA中剩下的硬幣不合格ifn=1thenA中硬幣不合格正確的填空順序是()。A.b,c,aB.c,b,aC.c,a,bD.a,b,c在正實(shí)數(shù)構(gòu)成的數(shù)字三角形排列形式如圖所示，第一行的數(shù)為all;第二行的數(shù)從左到右依次為a21,a22;第n行的數(shù)為an1,an2,，ann。從all開(kāi)始，每一行的數(shù)aij只有兩條邊可以分別通向下一行的兩個(gè)數(shù)a（i+1）j和a（i+1）（j

4、+1）。用動(dòng)態(tài)規(guī)劃算法找出一條從all向下通到an1,an2,“歡樂(lè)噴球”,正方形場(chǎng)地中心能不斷噴出彩色乒乓球，以場(chǎng)地中心為圓心還有一個(gè)圓軌道，軌道上有一歹0小火車在勻速運(yùn)動(dòng)，火車有六節(jié)車廂。假設(shè)乒乓球等概率落到正方形場(chǎng)地的每個(gè)地點(diǎn)，包括火車車廂。小朋友玩這個(gè)游戲時(shí)，只能坐在同一個(gè)火車車廂里，可以在自己的車廂里撿落在該車廂內(nèi)的所有乒乓球，每個(gè)人每次游戲有三分鐘時(shí)間，則一個(gè)小朋友獨(dú)自玩一次游戲期望可以得到（）個(gè)乒乓球。假設(shè)乒乓球噴出的速度為2個(gè)/秒，每節(jié)車廂的面積是整個(gè)場(chǎng)地面積的1/20。1. A.60B.108C.18D.20二、不定項(xiàng)選擇題（共5題，每題1.5分，共計(jì)7.5分；每題有一個(gè)或多

5、個(gè)正確選項(xiàng)，多選或少選均不得分）以下排序算法在最壞情況下時(shí)間復(fù)雜度最優(yōu)的有（）。2. A.冒泡排序B.快速排序C.歸并排序D.堆排序?qū)τ谌霔ｍ樞驗(yàn)閍,b,c,d,e,f,g的序列，下列（）不可能是合法的出棧序列。3. 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下列算法中，（）是穩(wěn)定的排序算法。4. A.快速排序B.堆排序C希爾排序D.插入排序以下是面向?qū)ο蟮母呒?jí)語(yǔ)言的是（）。5. A.匯編語(yǔ)言B.C+C.FortanD.Java以下和計(jì)算機(jī)領(lǐng)域密切相關(guān)的獎(jiǎng)項(xiàng)是（）。1. A.奧斯卡獎(jiǎng)B.圖靈獎(jiǎng)C.諾貝爾獎(jiǎng)D.王選獎(jiǎng)三

6、、問(wèn)題求解（共2題，每題5分，共計(jì)10分）如圖所示，共有13個(gè)格子。對(duì)任何一個(gè)格子進(jìn)行一次操作，會(huì)使得它自己以及與它上下左右相鄰的格子中的數(shù)字改變（由1變0,或由0變1）?，F(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;int

7、i;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;inta4040;for(i=0;i<40;i+)for(j=0;j<40;j+)aij=0;cin»n;y=0;x=n-1;n=2*n-1;for

8、(i=1;i<=n*n;i+)ayx=i；ny=(y-1+n)%n;nx=(x+1)%n;if(y=0&&x=n-1)|anynx!=0)y=y+1;elsey=ny;x=nx;)for(j=0;j<n;j+)cout«aOj«cout«endl;輸入：3輸出：172418153.#includeusingnamespacestd;intn,s,a100005,t100005,i;voidmergesort(intl,intr)if(l=r)return;intmid=(l+r)/2;intp=l;inti=l;intj=mid+1；m

9、ergesort(l,mid);mergesort(mid+1,r);while(i<=mid&&j<=r)(if(aj<ai)(s+=mid-i+1;tp=aj;p+；j+；else(tp=ai;p+;i+;while(i<=mid)(tp=ai;p+;i+;while(j<=r)(tp=aj;p+；j+；for(i=l;i<=r;i+)ai=ti；intmain()(cin>>n;for(i=1;i<=n;i+)cin>>ai;mergesort(1,n);cout<<s<<endl;

10、return0;輸入:6263451輸出：84.#includeusingnamespacestd;intmain()intn,m;cin>>n>>m;intx=1;inty=1;intdx=1;intdy=1;intcnt=0;while(cnt!=2)ent=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（

11、3分）輸入3:987321輸出3:1321（3分）五、完善程序（共2題，每題14分，共計(jì)28分）1.大整數(shù)除法：給定兩個(gè)正整數(shù)p和q,其中p不超過(guò)10100,q不超過(guò)100000,求p除以q的商和余數(shù)。（第一空2分，其余3分）輸入：第一行是p的位數(shù)n,第二行是正整數(shù)p,第三行是正整數(shù)q。輸出：兩行，分別是p除以q的商和余數(shù)。#includeusingnamespacestd;intp100;intn,i,q,rest;charc;cin»n;for(i=0;i<n;i+)cin»c;pi=c-'O'cin»q;rest=p0;i=1；whil

12、e(rest<q&&i<n)rest=rest*10+pi;i+；if(restvq)cout«0«endl;elsecout<<rest/q;while(i<n)(rest=rest%q*10+pi;i+；cout<<rest/q;cout<<endl;cout<<rest%q<<endl;return0;2.最長(zhǎng)路徑：給定一個(gè)有向五環(huán)圖，每條邊長(zhǎng)度為1,求圖中的最長(zhǎng)路徑長(zhǎng)度。(第五空2分，其余3分)輸入：第一行是結(jié)點(diǎn)數(shù)n(不超過(guò)100)和邊數(shù)m,接下來(lái)m行，每行兩個(gè)整數(shù)a,b,

13、表示從結(jié)點(diǎn)a到結(jié)點(diǎn)b有一條有向邊。結(jié)點(diǎn)標(biāo)號(hào)從0到(n-1)。輸出：最長(zhǎng)路徑長(zhǎng)度。提示：先進(jìn)行拓?fù)渑判?，然后按照拓?fù)渑判蛴?jì)算最長(zhǎng)路徑。#includeusingnamespacestd;intn,m,i,j,a,b,head,tail,ans;intgraph100100;/用鄰接矩陣存儲(chǔ)圖intdegree100;/記錄每個(gè)結(jié)點(diǎn)的入度intlen100;/記錄以各結(jié)點(diǎn)為終點(diǎn)的最長(zhǎng)路徑長(zhǎng)度intqueue100;/存放拓?fù)渑判蚪Y(jié)果intmain()cin>>n>>m;for(i=0;i<n;i+)for(j=0;j<n;j+)graphij=0;for(i=0;i<n;i+)degreei=0;for(i=0;i<m;i+)cin>>a>>b;graphab=1;degreeb+;tail=0;for(i=0;i<n;i+)if(degreei=0)queuetail=i;tail+;head=0;while(tail<n-1)for(i=0;i<n;i+)if(graphqueueheadi=1