第二十三屆全國青少年信息學奧林匹克聯(lián)賽初賽含標準答案(WORD重新匯總整編排版)

第二十三屆全國青少年信息學奧林匹克聯(lián)賽初賽

提t(yī)Wj組C++語言試題競賽時間：2017年10月14日14:30~16:30（WOR區(qū)新整理排版）選手注意：試題紙共有10頁，答題紙共有2頁，滿分100分。請在答題紙上作答， 寫在試題紙上的一律無效。不得使用任何電子設備（如計算器、手機、電子詞典等）或查閱任何書籍資料。一、單項選擇題（共15題，每題1.5分，共計22.5分；每題有且僅有一個正確選項）.從（ ）年開始，NOIP競賽將不再支持Pascal語言。A.2020B.2021C.2022D.2023TOC\o"1-5"\h\z.在8位二進制補碼中，10101011表示的數(shù)是十進制下的（ ）。A.43B.-85C.-43D.-84.分辨率為1600x900、16位色的位圖，存儲圖像信息所需的空間為（ ）。A.2812.5KBB.4218.75KBC.4320KBD.2880KB.2017年10月1日是星期日，1949年10月1日是（ ）。A.星期三B.星期日C.星期六D.星期二.設G是有n個結點、m條邊（n<m）的連通圖，必須刪去G的（ ）條邊，才能使得G變成一棵樹。A.m-n+1B.m-nC.m+n+1D.n -m+1.若某算法的計算時間表示為遞推關系式：T（N）=2T（N/2）+NlogNT（1）=1TOC\o"1-5"\h\z則該算法的時間復雜度為（ ）。A.O（N）B.O（NlogN）C.O（Nlog 2N） D.O（N2）.表達式a*（b+c）*d 的后綴形式是（ ）。A.abcd*+*B.abc+*d*C.a*bc+*dD.b+c*a*d.由四個不同的點構成的簡單無向連通圖的個數(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/3C.(sqrt(5) -1)/2D.1.設A和B是兩個長為n的有序數(shù)組，現(xiàn)在需要將A和B合并成一個排好序的數(shù)組，請問任何以元素比較作為基本運算的歸并算法最壞情況下至少要做( )次比較。A.n2B.nlognC.2nD.2n-1.在n(n>3)枚硬幣中有一枚質量不合格的硬幣(質量過輕或質量過重) ，如果只有一架天平可以用來稱重且稱重的硬幣數(shù)沒有限制， 下面是找出這枚不合格的硬幣的算法。 請把a-c三行代碼補全到算法中。A—XUYA—Zc.n—|A|算法Coin(A,n)k—如/3?將A中硬幣分成X,Y,Z三個集合，使得|??=|??=????=??-2??if????豐????//W(X),W(Y)分別為X或Y的重量then else ifn>2thengoto1ifn=2then任取A中1枚硬幣與拿走硬幣比較， 若不等，則它不合格；若相等，則A中剩下的硬幣不合格.ifn=1thenA中硬幣不合格正確的填空順序是( )。A.b,c,aB.c,b,aC.c,a,bD.a,b,c13.有正實數(shù)構成的數(shù)字三角形排列形式如圖所示。第一行的數(shù)為a11;第二行的數(shù)從左到右依次為a21,a22；…第n行的數(shù)為an1,an2,…，ann。從a11開始，每一行的數(shù) aj只有兩條邊可以分別通向下一行的兩個數(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]=( )。色I心絲

￡Im由工日外燈對 max{C[i-1,j-1],C[i-1,j]}+a ijC[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]}+a 1.小明要去南美洲旅游，一共乘坐三趟航班才能到達目的地，其中第1個航班準點的概率是0.9,第2個航班準點的概率為 0.8,第3個航班準點的概率為0.9。如果存在第i個（i=1,2）航班晚點，第i+1個航班準點，則小明將趕不上第 i+1個航班，旅行失敗；除了這種情況，其他情況下旅行都能成功。請問小明此次旅行成功的概率是（ ）。A.0.5B.0.648C.0.72D.0.74.歡樂噴球：兒童游樂場有個游戲叫“歡樂噴球”，正方形場地中心能不斷噴出彩色乒乓球，以場地中心為圓心還有一個圓形軌道， 軌道上有一列小火車在勻速運動， 火車有六節(jié)車廂。假設乒乓球等概率落到正方形場地的每個地點，包括火車車廂。小朋友玩這個游戲時，只能坐在同一個火車車廂里，可以在自己的車廂里撿落在該車廂內的所有乒乓球， 每個人每次游戲有三分鐘時間，則一個小朋友獨自玩一次游戲期望可以得到 （ ）個乒乓球。假TOC\o"1-5"\h\z設乒乓球噴出的速度為2個/秒，每節(jié)車廂的面積是整個場地面積的 1/20。A.60B.108C.18D.20\o"CurrentDocument"二、不定項選擇題（共5題，每題1.5分，共計7.5分；每題有一個或多個正確選項，多選或少選均不得分 ）.以下排序算法在最壞情況下時間復雜度最優(yōu)的有（ ）。A.冒泡排序 B.快速排序 C.歸并排序 D.堆排序.對于入棧順序為a,b,c,d,e,f,g 的序列，下列（ ）不可能是合法的出棧序列。A.a,b,c,d,e,f,g B.a,d,c,b,e,g,fC.a,d,b,c,g,f,e D.g,f,e,d,c,b,a.下列算法中，（ ）是穩(wěn)定的排序算法。A.快速排序 B.堆排序 C.希爾排序 D.插入排序.以下是面向對象的高級語言的有（ ）。A.匯編語言 B.C++ C.Fortran D.Java

.以下和計算機領域密切相關的獎項有（ ）。A.奧斯卡獎| |B.圖靈獎| |C.諾貝爾獎| |D.王選獎三、問題求解（共2題，每題題5分，共計10分）.如右圖所示，共有13個格子。對任何一個格子進行一次操作，會使得它自己以及與它上下左右相鄰的格子中的數(shù)字改變（由 1變0,或由0變1）?，F(xiàn)在要使得所有的格子中的數(shù)字都變?yōu)?0,至少需要次操作。.如下圖所示，A到B是連通的。假設刪除一條細的邊的代價是 1,刪除一條粗的邊的代價是2,要讓A價是2,要讓A、B不連通，最小代價是（2分），最小代價的不同方案數(shù)是（3分）。（只要有一條刪除的邊不同，就是不同的方案）四、閱讀程序寫結果（共4題，每題8分，共計32分）#include<iostream>usingnamespacestd;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輸出： #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輸出： #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+=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輸出： #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:（2分）輸入2:20171014輸出2:（3分）輸入3:987321輸出3:（3分）五、完善程序 （共共2題，每題14分，共計28分）.（大整數(shù)除法））給定兩個正整數(shù)p和q,其中p不超過10100,q不超過100000,求p除以q的商和余數(shù)。（第一空2分，其余3分）輸入：第一行是p的位數(shù)n,第二行是正整數(shù)p,第三行是正整數(shù)q。輸出：兩行，分別是p除以q的商和余數(shù)。#include<iostream>usingnamespacestd;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= ⑴ ;i=1;while((2)&&i<n){rest=rest*10+p[i];i++;}if(rest<q)cout<<0<<endl;else{cout<<_(3) ; while(i<n){rest= (4) ; i++;cout<<rest/q;}cout<<endl;}cout<< (5) <<endl;return0;}. (最長路徑)給定一個有向無環(huán)圖，每條邊長度為 1,求圖中的最長路徑長度。(第五空2分，其余3分)輸入：第一行是結點數(shù) n(不超過100)和邊數(shù)m,接下來m行，每行兩個整數(shù)a,b,表示從結點a到結點b有一條有向邊。結點標號從 0至1j(n-1)。輸出：最長路徑長度。提示：先進行拓撲排序，然后按照拓撲序計算最長路徑。#include<iostream>

usingnamespacestd;intn,m,i,j,a,b,head,tail,ans;intgraph[100][100];//intdegree[100];//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;⑴ ；}tail=0;for(i=0;i<n;i++)if( _(2)_)_{ queue[tail]=i;tail++;}head=0;while(tail<n-1){for(i=0;i<n;i++)if(graph[queue[head]][i]==1){?(3);if(degree[i]==0){queue[tail]=i;tail++;}}_(4)—; }ans=0;for(i=0;i<n;i++){a=queue[i];len[a]=1;for(j=0;j<n;j++)if(graph皿a]==1&&len[j]+1>len[a])len[a]=len[j]+1;if(⑸)ans=len[a];}cout<<ans<<endl;return0;}第二十三屆全國青少年信息學奧林匹克聯(lián)賽初賽

提高組參考答案、單項選擇題（共15題，每題1.5分，共計22.5分）12345678CBACACBC9101112131415DBDDA