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

-.z.一、單項(xiàng)選擇題〔共15題，每題1.5分，共計(jì)22.5分；每題有且僅有一個(gè)正確選項(xiàng)〕1.從()年開(kāi)場(chǎng)，NOIP競(jìng)賽將不再支持Pascal語(yǔ)言。A.2020B.2021C.2022D.20232.在8位二進(jìn)制補(bǔ)碼中，10101011表示的數(shù)是十進(jìn)制下的()。A.43B.-85C.-43D.-843.分辨率為1600*900、16位色的位圖，存儲(chǔ)圖像信息所需的空間為()。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變成一棵樹(shù)。A.m–n+1B.m-nC.m+n+1D.n–m+16.假設(shè)*算法的計(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)成的簡(jiǎn)單無(wú)向連通圖的個(gè)數(shù)是()。A.32B.35C.38D.419.將7個(gè)名額分給4個(gè)不同的班級(jí)，允許有的班級(jí)沒(méi)有名額，有()種不同的分配方案。A.60B.84C.96D.12010.假設(shè)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è)長(zhǎng)為n的有序數(shù)組，現(xiàn)在需要將A和B合并成一個(gè)排好序的數(shù)組，請(qǐng)問(wèn)任何以元素比擬作為根本運(yùn)算的歸并算法最壞情況下至少要做()次比擬。A.n2B.nlognC.2nD.2n-112.在n(n>=3)枚硬幣中有一枚質(zhì)量不合格的硬幣〔質(zhì)量過(guò)輕或質(zhì)量過(guò)重〕，如果只有一架天平可以用來(lái)稱重且稱重的硬幣數(shù)沒(méi)有限制，下面是找出這枚不合格的硬幣的算法。請(qǐng)把a(bǔ)-c三行代碼補(bǔ)全到算法中。a.A*UYb.AZc.n|A|算法Coin(A,n)1.kn/32.將A中硬幣分成*,Y,Z三個(gè)集合，使得|*|=|Y|=k,|Z|=n-2k3.ifW(*)≠W(Y)//W(*),W(Y)分別為*或Y的重量4.then_______5.else_______6.__________7.ifn>2thengoto18.ifn=2then任取A中1枚硬幣與拿走硬幣比擬，假設(shè)不等，則它不合格；假設(shè)相等，則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開(kāi)場(chǎng)，每一行的數(shù)aij只有兩條邊可以分別通向下一行的兩個(gè)數(shù)a(i+1)j和a(i+1)(j+1)。用動(dòng)態(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.ma*{C[i-1,j-1],C[i-1,j]}+aijB.C[i-1,j-1]+c[i-1,j]C.ma*{C[i-1,j-1],C[i-1,j]}+1D.ma*{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è)航班，旅行失?。怀诉@種情況，其他情況下旅行都能成功。請(qǐng)問(wèn)小明此次旅行成功的概率是()。A.0.5B.0.648C.0.72D.0.7415.歡樂(lè)噴球：兒童游樂(lè)場(chǎng)有個(gè)游戲叫"歡樂(lè)噴球〞，正方形場(chǎng)地中心能不斷噴出彩色乒乓球，以場(chǎng)地中心為圓心還有一個(gè)圓軌道，軌道上有一列小火車在勻速運(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。A.60B.108C.18D.20二、不定項(xiàng)選擇題〔共5題，每題1.5分，共計(jì)7.5分；每題有一個(gè)或多個(gè)正確選項(xiàng)，多項(xiàng)選擇或少選均不得分〕1.以下排序算法在最壞情況下時(shí)間復(fù)雜度最優(yōu)的有()。A.冒泡排序B.快速排序C.歸并排序D.堆排序2.對(duì)于入棧順序?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ū)ο蟮母呒?jí)語(yǔ)言的是()。A.匯編語(yǔ)言B.C++C.FortanD.Java5.以下和計(jì)算機(jī)領(lǐng)域密切相關(guān)的獎(jiǎng)項(xiàng)是()。A.奧斯卡獎(jiǎng)B.圖靈獎(jiǎng)C.諾貝爾獎(jiǎng)D.王選獎(jiǎng)三、問(wèn)題求解〔共2題，每題5分，共計(jì)10分〕1.如下圖，共有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分)?！仓灰幸粭l刪除的邊不同，就是不同的方案〕四、閱讀程序?qū)懡Y(jié)果〔共4題，每題8分，共計(jì)32分〕1.#includeusingnamespacestd;intg(intm,intn,int*){intans=0;inti;if(n==1)return1;for(i=*;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,*,y,n*,ny;inta[40][40];for(i=0;i<40;i++)for(j=0;j<40;j++)a[i][j]=0;cin>>n;y=0;*=n-1;n=2*n-1;for(i=1;i<=n*n;i++){a[y][*]=i;ny=(y-1+n)%n;n*=(*+1)%n;if((y==0&&*==n-1)||a[ny][n*]!=0)y=y+1;else{y=ny;*=n*;}}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;int*=1;inty=1;intd*=1;intdy=1;intt=0;while(cnt!=2){cnt=0;*=*+d*;y=y+dy;if(*==1||*==n){++cnt;d*=-d*;}if(y==1||y==m){++cnt;dy=-dy;}}cout<<*<<""<<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不超過(guò)10100，q不超過(guò)100000，求p除以q的商和余數(shù)?！驳谝豢?分，其余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.最長(zhǎng)路徑：給定一個(gè)有向五環(huán)圖，每條邊長(zhǎng)度為1，求圖中的最長(zhǎng)路徑長(zhǎng)度?！驳谖蹇?分，其余3分〕輸入：第一行是結(jié)點(diǎn)數(shù)n〔不超過(guò)100〕和邊數(shù)m，接下來(lái)m行，每行兩個(gè)整數(shù)a,b，表示從結(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;intgraph[100][100];//用鄰接矩陣存儲(chǔ)圖intdegree[100];//記錄每個(gè)結(jié)點(diǎn)的入度intlen[100];//記錄以各結(jié)點(diǎn)為終點(diǎn)的最長(zhǎng)路徑長(zhǎng)度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]+