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

.#:第9頁第二十三屆全國青少年信息學(xué)奧林匹克聯(lián)賽初賽進(jìn)步組C++語言試題競賽時(shí)間：2019年10月14日14:30~16:30選手注意：試題紙共有10頁，答題紙共有2頁，總分值100分。請(qǐng)?jiān)诖痤}紙上作答，寫在試題紙上的一律無效。不得使用任何電子設(shè)備〔如計(jì)算器、手機(jī)、電子詞典等〕或查閱任何書籍資料。一、單項(xiàng)選擇題〔共15題，每題1.5分，共計(jì)22.5分；每題有且僅有一個(gè)正確選項(xiàng)〕1.從〔〕年開場，NOIP競賽將不再支持Pascal語言。A.2020B.2021C.2022D.20232.在8位二進(jìn)制補(bǔ)碼中，10101011表示的數(shù)是十進(jìn)制下的〔〕。A.43B.-85C.-43D.-843.分辨率為1600x900、16位色的位圖，存儲(chǔ)圖像信息所需的空間為〔〕。A.2812.5KBB.4218.75KBC.4320KBD.2880KB4.2019年10月1日是星期日，1949年10月1日是〔〕。A.星期三B.星期日C.星期六D.星期二5.設(shè)G是有n個(gè)結(jié)點(diǎn)、m條邊〔n≤m〕的連通圖，必須刪去G的〔〕條邊，才能使得G變成一棵樹。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ù)雜度為〔〕。O〔N〕B.O〔NlogN〕C.O〔Nlog2N〕D.O〔N2〕解：當(dāng)a=b=2、f〔n〕=nlgn時(shí)候〔lgn:log2n的簡記〕，計(jì)算遞歸方程的解。T〔n〕=2T〔n/2〕+nlgn

。

T〔n/2〕=2T〔n/22〕+〔n/2〕lg〔n/2〕。

T〔〔n/22〕=2T〔n/23〕+〔n/22〕lg〔n/22〕。

于是得到：T〔n〕=nlgn+〔nlgn-lg2〕+〔nlgn-2lg2〕+〔nlgn-22lg2〕+···+〔nlgn-2hlg2〕，h=lgn。

根據(jù)等差、等比數(shù)列求和公式化簡有：

T〔n〕=n〔lgn〕2

–〔n-1〕lg2，所以T〔n〕=

O〔n〔lgn〕2〕，而不是O〔nlgn〕。7.表達(dá)式a*〔b+c〕*d的后綴形式是〔〕。A.abcd*+*B.abc+*d*C.a*bc+*dD.b+c*a*d8.由四個(gè)不同的點(diǎn)構(gòu)成的簡單無向連通圖的個(gè)數(shù)是〔〕。A.32B.35C.38D.41解：9.將7個(gè)名額分給4個(gè)不同的班級(jí)，允許有的班級(jí)沒有名額，有〔〕種不同的分配方案。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/3C.〔sqrt〔5〕?1〕/2D.111.設(shè)A和B是兩個(gè)長為n的有序數(shù)組，如今需要將A和B合并成一個(gè)排好序的數(shù)組，請(qǐng)問任何以元素比較作為根本運(yùn)算的歸并算法最壞情況下至少要做〔〕次比較。A.n2B.nlognC.2nD.2n-112.在n〔n≥3〕枚硬幣中有一枚質(zhì)量不合格的硬幣〔質(zhì)量過輕或質(zhì)量過重〕，假如只有一架天平可以用來稱重且稱重的硬幣數(shù)沒有限制，下面是找出這枚不合格的硬幣的算法。請(qǐng)把a(bǔ)-c三行代碼補(bǔ)全到算法中。a.A←X∪Yb.A←Zc.n←|A|算法Coin〔A,n〕1.k←?n/3?2.將A中硬幣分成X，Y，Z三個(gè)集合，使得|??X|=|Y??|=??,|Z??|=N???2K??3.if??〔??X〕≠??〔Y??〕//W〔X〕,W〔Y〕分別為X或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開場，每一行的數(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.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]}+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)問小明此次旅行成功的概率是〔〕。A.0.5B.0.648C.0.72D.0.7415.歡樂噴球：兒童游樂場有個(gè)游戲叫“歡樂噴球〞，正方形場地中心能不斷噴出彩色乒乓球，以場地中心為圓心還有一個(gè)圓形軌道，軌道上有一列小火車在勻速運(yùn)動(dòng)，火車有六節(jié)車廂。假設(shè)乒乓球等概率落到正方形場地的每個(gè)地點(diǎn)，包括火車車廂。小朋友玩這個(gè)游戲時(shí)，只能坐在同一個(gè)火車車廂里，可以在自己的車廂里撿落在該車廂內(nèi)的所有乒乓球，每個(gè)人每次游戲有三分鐘時(shí)間，那么一個(gè)小朋友單獨(dú)玩一次游戲期望可以得到〔〕個(gè)乒乓球。假設(shè)乒乓球噴出的速度為2個(gè)/秒，每節(jié)車廂的面積是整個(gè)場地面積的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í)語言的有〔〕。A.匯編語言B.C++C.FortranD.Java5.以下和計(jì)算機(jī)領(lǐng)域親密相關(guān)的獎(jiǎng)項(xiàng)有〔〕。A.奧斯卡獎(jiǎng)B.圖靈獎(jiǎng)C.諾貝爾獎(jiǎng)D.王選獎(jiǎng)三、問題求解〔共2題，每題題5分，共計(jì)10分〕1.如右圖所示，共有13個(gè)格子。對(duì)任何一個(gè)格子進(jìn)展一次操作，會(huì)使得它自己以及與它上下左右相鄰的格子中的數(shù)字改變〔由1變0，或由0變1〕。如今要使得所有的格子中的數(shù)字都變?yōu)?，至少需要________次操作。2.如以下圖所示，A到B是連通的。假設(shè)刪除一條細(xì)的邊的代價(jià)是1，刪除一條粗的邊的代價(jià)是2，要讓A、B不連通，最小代價(jià)是_________〔2分〕，最小代價(jià)的不同方案數(shù)是_________〔3分〕?！仓灰幸粭l刪除的邊不同，就是不同的方案〕四、閱讀程序?qū)懡Y(jié)果〔共4題，每題8分，共計(jì)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〔m-i,n-1,i〕; returnans;intmain〔〕{ intt,m,n; cin>>m>>n; cout<<g〔m,n,0〕<<endl; return0;輸入：84輸出：__________2.#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輸出：___________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輸出：________________4.#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：20191014輸出2：__________〔3分〕輸入3：987321輸出3：__________〔3分〕五、完善程序〔共共2題，每題14分，共計(jì)28分〕1.〔大整數(shù)除法〕〕給定兩個(gè)正整數(shù)p和q，其中p不超過10100，q不超過100000，求p除以q的商和余數(shù)?！驳谝豢?分，其余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=〔1〕; 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;2.〔最長途徑〕給定一個(gè)有向無環(huán)圖，每條邊長度為1，求圖中的最長途徑長度?！驳谖蹇?分，其余3分〕輸入：第一行是結(jié)點(diǎn)數(shù)n〔不超過100〕和邊數(shù)m，接下來m行，每行兩個(gè)整數(shù)a，b，表示從結(jié)點(diǎn)a到結(jié)點(diǎn)b有一條有向邊。結(jié)點(diǎn)標(biāo)號(hào)從0到〔n-1〕。輸出：最長途徑長度。提示：先進(jìn)展拓?fù)渑判?，然后按照拓?fù)湫蛴?jì)算最長途徑。#include<iostream>usingnamespacestd;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)的最長途徑長度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; 〔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[j][a]==1&&len[j]+1>len[a]〕 len[a]=len[j]+1; if〔〔5〕〕 ans=len[a]; cout<<ans<<en