信息學(xué)競賽真題

、單項選擇題(共15題，每題1.5分，共計22.5分；每題有且僅有一個正確選項)1?從()年開始，NOIP競賽將不再支持Pascal語言。2020B.2021C.2022D.20232?在8位二進制補碼中，10101011表示的數(shù)是十進制下的()。A.433?分辨率為1600x900、16位色的位圖，存儲圖像信息所需的空間為()。2017年10月1日是星期日，1949年10月1日是()。A.星期三B.星期日C.星期六D.星期二設(shè)G是有n個結(jié)點、m條邊(n<m)的連通圖，必須刪去G的()條邊，才能使得G變成一棵樹。A.m-n+1B.m-nC.m+n+1D.n—m+1若某算法的計算時間表示為遞推關(guān)系式:T(N)=2T(N/2)+NlogNT(1)=1則該算法的時間復(fù)雜度為()。A.O(N)B.O(NlogN)C.O(Nlog2N)D.O(N2)表達式a*(b+c)*d的后綴形式是()。A.abcd*+*B.abc+*d*C.a*bc+*dD.b+c*a*d由四個不同的點構(gòu)成的簡單無向連通圖的個數(shù)是()。A.32B.35C.38D.41將7個名額分給4個不同的班級，允許有的班級沒有名額，有()種不同的分配方案。A.60B.84C.96D.120若f[0]=0,f[1]=1,f[n+1]=(f[n]+f[n-1])/2，則隨著i的增大，f[i]將接近和()。A.1/2B.2/3D.1設(shè)A和B是兩個長為n的有序數(shù)組，現(xiàn)在需要將A和B合并成一個排好序的數(shù)組，請問任何以元素比較作為基本運算的歸并算法最壞情況下至少要做()次比較。

在n(n>=3)枚硬幣中有一枚質(zhì)量不合格的硬幣(質(zhì)量過輕或質(zhì)量過重)，如果只有一架天平可以用來稱重且稱重的硬幣數(shù)沒有限制，下面是找出這枚不合格的硬幣的算法。請把a-c三行代碼補全到算法中。AXUYAZn|A|算法Coin(A,n)kn/3將A中硬幣分成X,YZ三個集合，使得|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ù)構(gòu)成的數(shù)字三角形排列形式如圖所示，第一行的數(shù)為a11;第二行的數(shù)從左到右依次為a21,a22;…第n行的數(shù)為an1,an2,…，ann。從a11開始，每一行的數(shù)aij只有兩條邊可以分別通向下一行的兩個數(shù)a(i+1)j和a(i+1)(j+1)。用動態(tài)規(guī)劃算法找出一條從a11向下通到an1,an2,…,ann中某個數(shù)的路徑，使得該路徑上的數(shù)之和達到最大。令C[i,j]是從a11到aij的路徑上的數(shù)的最大和，并且C[i,0]=C[0,j]=0，則C[i,j]=()。max{C[i-1,j-1],C[i-1,j]}+aijC[i-1,j-1]+c[i-1,j]max{C[i-1,j-1],C[i-1,j]}+1max{C[i,j-1],C[i-1,j]}+aij小明要去南美洲旅游，一共乘坐三趟航班才能到達目的地，其中第1個航班準點的概率是0.9,第2個航班準點的概率為0.8,第3個航班準點的概率為0.9。如果存在第i個(i=1,2)航班晚點，第i+1個航班準點，則小明將趕不上第i+1個航班，旅行失??；除了這種情況，其他情況下旅行都能成功。請問小明此次旅行成功的概率是()。歡樂噴球：兒童游樂場有個游戲叫“歡樂噴球”，正方形場地中心能不斷噴出彩色乒乓球，以場地中心為圓心還有一個圓軌道，軌道上有一列小火車在勻速運動，火車有六節(jié)車廂。假設(shè)乒乓球等概率落到正方形場地的每個地點，包括火車車廂。小朋友玩這個游戲時，只能坐在同一個火車車廂里，可以在自己的車廂里撿落在該車廂內(nèi)的所有乒乓球，每個人每次游戲有三分鐘時間，則一個小朋友獨自玩一次游戲期望可以得到()個乒乓球。假設(shè)乒乓球噴出的速度為2個/秒，每節(jié)車廂的面積是整個場地面積的1/20。

二、不定項選擇題（共5題，每題1.5分，共計7.5分；每題有一個或多個正確選項，多選或少選均不得分）以下排序算法在最壞情況下時間復(fù)雜度最優(yōu)的有（）。A.冒泡排序B.快速排序C.歸并排序D.堆排序?qū)τ谌霔ｍ樞驗閍,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下列算法中，（）是穩(wěn)定的排序算法。A.快速排序B.堆排序C希爾排序D.插入排序以下是面向?qū)ο蟮膯J級語言的是（）。A.匯編語言以下和計算機領(lǐng)域密切相關(guān)的獎項是（）。A.奧斯卡獎B.圖靈獎C.諾貝爾獎D.王選獎三、問題求解（共2題，每題5分，共計10分）如圖所示，共有13個格子。對任何一個格子進行一次操作，會使得它自己以及和它上下左右相鄰的格子中的數(shù)字改變（由1變0，或由0變1）?，F(xiàn)在要使得所有的格子中的數(shù)字都變?yōu)?,至少需要3次操作。如圖所示，A到B是連通的。假設(shè)刪除一條細的邊的代價是1，刪除一條粗的邊的代價是2，要讓A、B不連通，最小代價是4（2分），最小代價的不同方案數(shù)是9（3分）。（只要有一條刪除的邊不同，就是不同的方案）四、閱讀程序?qū)懡Y(jié)果（共4題，每題8分，共計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=(I+r)/2;intp=I;inti=I;intj=mid+1;mergesort(I,mid);mergesort(mid+1,r);while(i<=mid&&j<=r){if(a[j]<a[i]){i+1;s+=mid-t[p]=a[j];i+1;P++；P++；j++；i++;i++;}else{t[p]=a[i];p++;}}while(i<=mid){i++;}else{t[p]=a[i];p++;}}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;intent=0;while（ent!=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（3分）輸入3:987321輸出3:1321（3分）五、完善程序（共2題，每題14分，共計28分）1.大整數(shù)除法：給定兩個正整數(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-‘O'}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.最長路徑：給定一個有向五環(huán)圖，每條邊長度為1，求圖中的最長路徑長度。（第五空2分，其余3分）輸入：第一行是結(jié)點數(shù)n（不超過100）和邊數(shù)m，接下來m行，每行兩個整數(shù)a,b,表示從結(jié)點a到結(jié)點b有一條有向邊。結(jié)點標號從0到（n-1）。輸出：最長路徑長度。提示：先進行拓撲排序，然后按照拓撲排序計算最長路徑。#includeusingnamespacestd;intn,m,i,j,a,b,head,tail,ans;intgraph[100][100];II用鄰接矩陣存儲圖intdegree[100];II記錄每個結(jié)點的入度intlen[100];II記錄以各結(jié)點為終點的最長路徑長度

intqueue[100];//存放拓撲排序結(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[qu