NOIP2022提升組初賽試題及答案一、單項選擇題〔共15題,每題1.5分,共計22.5分；每題有且僅有一個正確選項〕1.從〔〕年開始,NOIP競賽將不再支持Pascal語言.CA.2022B.2021C.2022D.2023.在8位二進制補碼中,10101011表示的數是十進制下的〔〕.B.分辨率為1600x900、16位色的位圖,存儲圖像信息所需的空間為A.43B.-85C.-43D.-84().AA.2812.5KBB.4218.75KBC.4320KBD.2880KB4.2022年10月1日是星期日,1949年10月1日是〔〕.CA.星期三B.星期日C.星期六D.星期二GG變成一棵樹.A5.設G是有n個結點、m條邊〔n<m的連通圖,必須刪去G的〔〕條邊,才能使得A.mf+1B.m-nC.m+n+1D.n5+16.假設某算法的計算時間表示為遞推關系式:那么該算法的時間復雜度為〔〕.CA.O(N)T(N)=2T(N/2)+NlogNB.O(NlogN)T(1)=1C.O(Nlog2N)D.O(N2).表達式a*〔b+c〕*d的后綴形式是〔〕.B.由四個不同的點構成的簡單無向連通圖的個數是A.abcd*+*().C9.將7個名額分給4個不同的班級,允許有的班級沒有名額,有10.假設f[0]=0,f[1]=1,f[n+1]=(f[n]+f[n-1])/2,那么隨著i的增大,A.1/2B.2/3B.abc+*d*C.a*bc+*dA.32B.35C.38D.41〔〕種不同的分配方案.Df[i]將接近與〔〕oBD.b+c*a*dA.60B.84C.96D.12011.設A和B是兩個長為n的有序數組,最壞情況下至少要做〔〕次比擬.DD.1現在需要將A和B合并成一個排好序的數組,請問任何以元素比擬作為根本運算的歸并算法A.n2B.NlognC.2nD.2n-112.在n〔n>=3〕枚硬幣中有一枚質量不合格的硬幣下面是找出這枚不合格的硬幣的算法.請把a-c〔質量12.在n〔n>=3〕枚硬幣中有一枚質量不合格的硬幣下面是找出這枚不合格的硬幣的算法.請把a-c將A中硬幣分成X,Y,Z三個集合,使得|X|=|Y|=k,|Z|=n-2kifW〔X〕,W〔Y〕//W〔X〕,W〔Y〕分別為X或丫的重量thenelseifn>2thengoto1ifn=2then任取A中1枚硬幣與拿走硬幣比擬,假設不等,那么它不合格；假設相等,那么A中剩下的硬幣不合格ifn=1thenA中硬幣不合格正確的填空順序是〔〕.DA.b,c,aB.c,b,aC.c,a,bD.a,b,c.在正實數構成的數字三角形排列形式如下圖,第一行的數為a11;第二行的數從左到右依次為a21,a22;…第n行的數為an1,an2,…,ann.從a11開始,每一行的數aij只有兩條邊可以分別通向下一行的兩個數a〔i+1〕j和a〔i+1〕〔j+1〕.用動態規劃算法找出一條從a11向下通到an1,an2,…,ann中某個數的路徑,使得該路徑上的數之和到達最大.令C[i,j]是從a11到aij的路徑上的數的最大和,并且C[i,0]=C[0,j]=0,那么C[i,j]=〔〕.AA.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]}+aij.小明要去南美洲旅游,一共乘坐三趟航班才能到達目的地,其中第1個航班準點的概率是0.9,第2個航班準點的概率為0.8,第3個航班準點的概率為0.9.如果存在第i個〔i=1,2〕航班晚點,第i+1個航班準點,那么小明將趕不上第i+1個航班,旅行失??；除了這種情況,其他情況下旅行都能成功.請問小明此次旅行成功的概率是〔〕.D

A.0.5B,0.648C.0.72D.0.74.歡樂噴球：兒童游樂場有個游戲叫歡樂噴球〞,正方形場地中央能不斷噴出彩色乒乓球,以場地中心為圓心還有一個圓軌道,軌道上有一列小火車在勻速運動,火車有六節車廂.假設乒乓球等概率落到正方形場地的每個地點,包括火車車廂.小朋友玩這個游戲時,只能坐在同一個火車車廂里,可以在自己的車廂里撿落在該車廂內的所有乒乓球,每個人每次游戲有三分鐘時間,那么一個小朋友單獨玩一次游戲期望可以得到〔〕個乒乓球.假設乒乓球噴出的速度為2個/秒,每節車廂的面積是整個場地面積的1/20.CA.60B,108C.18D.20二、不定項選擇題〔共5題,每題1.5分,共計7.5分；每題有一個或多個正確選項,多項選擇或少選均不得分〕.以下排序算法在最壞情況下時間復雜度最優的有〔〕.CDA,冒泡排序B,快速排序C,歸并排序D,堆排序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,以下算法中,〔〕是穩定的排序算法..以下是面向對象的高級語言的是〔〕..以下和計算機領域密切相關的獎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,以下算法中,〔〕是穩定的排序算法..以下是面向對象的高級語言的是〔〕..以下和計算機領域密切相關的獎項是BDA.快速排序B,堆排序C,希爾排序D,插入排序()oBDA.匯編語言B.C++C.FortanD.JavaA,奧斯卡獎B.圖靈獎C.諾貝爾獎D,王選獎三、問題求解〔共2題,每題5分,共計10分〕.如下圖,共有13個格子.對任何一個格子進行一次操作,會使得它自己以及與它上下左右相鄰的格子中的數字改變〔由1變0,或由0變1〕.現在要使得所有的格子中的數字都變為0,至少需要3次操作.答案3.如下圖,A到B是連通的.假設刪除一條細的邊的代價是1,刪除一條粗的邊的代價是2,要讓A、B不連通,最小代價是4〔2分〕,最小代價的不同方案數是9〔3分〕.〔只要有一條刪除的邊不同,就是不同的方案〕答案4,9四、閱讀程序寫結果〔共4題,每題8分,共計32分〕1.#include<iostream>usingnamespacestd;intg(intm,intn,intx){intans=0;inti;if(n==1)return1;for(i=x;i<=m/n;i++)ans+=g(mH,n-1,i);returnans;}intmain(){intt,m,n;cin>>m>>n;cout<<g(m,n,0)<<endl;return0;}輸入：84輸出:152.#include<iostream>usingnamespacestd;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.#include<iostream>usingnamespacestd;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+=midi+1;t[p]=a[j];p++;TOC\o"1-5"\h\zj++;}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);五、完善程序(共2題,每題14分,共計28分)cout<<s<<endl;return0;}輸入：6263451輸出：84.#include<iostrecout<<s<<endl;return0;}輸入：6263451輸出：84.#include<iostream>usingnamespacestd;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:20221014輸出2:20221(3分)輸入3:987321輸出3:1321(3分)輸入：第一行是p的位數n,第二行是正整數p,第三行是正整數q.輸出：兩行,分別是p除以q的商和余數.#include<iostream>cin>>n;usingnamespacestd;for(i=0;i<n;i++){intp[100];cin>>c;intn,i,q,rest;p[i]=c'0'}charc;cin>>q;其余3分)intmain(){rest=p[其余3分)=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++;couwhile(i<n){rest=rest%q*10+p[i];i++;cout<<rest/q;}cout<<endl;}cout<<rest%q<<endl;return0;}輸入：第一行是結點數n〔不超過100〕和邊數m,接下來m行,每行兩個整數a,b,表示從結點a到結點b有一條有向邊.結點標號從0到〔n-1〕.輸出：最長路徑長度.提示：先進行拓撲排序,然后根據拓撲排序計算最長路徑.#include<iostream>usingnamespacestd;intn,m,i,j,a,b,head,tail,ans;intgraph[100][100];//用鄰接矩陣存儲圖intdegree[100];//記錄每個結點的入度intlen[100];//記錄以各結點為終點的最長路徑長度intqueue[100];//存放拓撲排序結果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[queue[tail++;}head=0;while(tail<n-1){for(i=0;i<n;i++)if(graph[queue[head]][i]==1){degree[i]--;if(degree[i]==0){queue[tail]=i;tail++;}}head++