NOIP2020提高組C++初賽試題

歡迎關(guān)注作者！作者每天都會(huì)更新精品文章！歡迎關(guān)注作者！作者每天都會(huì)更新精品文章！NOIP2020提高組C++初賽試題NOIP2020提高組C++初賽試題第二十二屆全國青少年信息學(xué)奧林匹克聯(lián)賽初賽提高組C++語言試題競賽?不得使用任何電子設(shè)備（如計(jì)算器、手機(jī)、電子詞典等）或查閱任何書籍資料。一、單項(xiàng)選擇題（共15題，每題1.5分，共計(jì)22.5分；每題有且僅有一個(gè)正確選項(xiàng)）1.以下不是微軟公司出品的軟件是（）。A.PowerpointB.WordC.ExcelD.AcrobatReader2.如果開始時(shí)計(jì)算機(jī)處于小寫輸入狀態(tài)，現(xiàn)在有一只小老鼠反復(fù)按照CapsLock、字母鍵A、字母鍵S和字母鍵D的順序來回按鍵，即CapsLock、A、S、D、S、A、CapsLock、A、S、D、S、A、CapsLock、A、S、D、S、A 屏幕上輸出的第81個(gè)字符是字母（）。A.AB.SC.DD.A3.二進(jìn)制數(shù)00101100和01010101異或的結(jié)果是（）。A.00101000B.01111001C.01000100D.001110004.與二進(jìn)制小數(shù)0.1相等的八進(jìn)進(jìn)制數(shù)是（）。A.0.8B.0.4C.0.2D.0.15.以比較作為基本運(yùn)算，在N個(gè)數(shù)中找最小數(shù)的最少運(yùn)算次數(shù)為（）。A.NB.N-1C.N2D.logN6.表達(dá)式a*（b+c）-d的后綴表達(dá)形式為（）。A.abcd*+-B.abc+*d-C.abc*+d-D.-+*abcd7.一棵二叉樹如右圖所示，若采用二叉樹鏈表存儲(chǔ)該二叉樹（各個(gè)結(jié)點(diǎn)包括結(jié)點(diǎn)的數(shù)據(jù)、左孩子指針、右孩子指針）。如果沒有左孩子或者右孩子，則對應(yīng)的為空指針。那么該鏈表中空指針的數(shù)目為（）。A.6B.7C.12D.148.G是一個(gè)非連通簡單無向圖，共有28條邊，則該圖至少有（）個(gè)頂點(diǎn)。A.10B.9C.8D.7CCFNOIP2020初賽提高組C++語言試題第1頁，共13頁9.某計(jì)算機(jī)的CPU和內(nèi)存之間的地址總線寬度是32位（bit）,這臺計(jì)算機(jī)最多可以使用（）的內(nèi)存。A.2GBB.4GBC.8GBD.16GB10.有以下程序：#includeiostreamusingnamespacestd;intmain(){intk=4,n=0;while(nk){n++;if(n%3!=0)continue;k--;}coutk“,“nendl;return0;}程序運(yùn)行后的輸出結(jié)果是()。A.2,2B.2,3C.3,2D.3,311.有7個(gè)一模一樣的蘋果，放到3個(gè)一樣的盤子中，一共有()種放法。A.7B.8C.21D.3712.Lucia和她的朋友以及朋友的朋友都在某社交網(wǎng)站上注冊了賬號。下圖是他們之間的關(guān)系圖，兩個(gè)人之間有邊相連代表這兩個(gè)人是朋友，沒有邊相連代表不是朋友。這個(gè)社交網(wǎng)站的規(guī)則是：如果某人A向他(她)的朋友B分享了某張照片，那么B就可以對該照片進(jìn)行評論；如果B評論了該照片，那么他(她)的所有朋友都可以看見這個(gè)評論以及被評論的照片，但是不能對該照CCFNOIP2020初賽提高組C++語言試題第2頁，共13頁片進(jìn)行評論(除非A也向他(她)分享了該照片)?，F(xiàn)在Lucia已經(jīng)上傳了一張照片，但是她不想讓Jacob看見這張照片，那么她可以向以下朋友()分享該照片。A.Dana,Michael,EveB.Dana,Eve,MonicaC.Michael,Eve,JacobD.Micheal,Peter,Monica13.周末小明和爸爸媽媽三個(gè)人一起想動(dòng)手做三道菜。小明負(fù)責(zé)洗菜、爸爸負(fù)責(zé)切菜、媽媽負(fù)責(zé)炒菜。假設(shè)做每道菜的順序都是：先洗菜10分鐘，然后切菜10分鐘，最后炒菜10分鐘。那么做一道菜需要30分鐘。注意：兩道不同的菜的相同步驟不可以同時(shí)進(jìn)行。例如第一道菜和第二道的菜不能同時(shí)洗， 也不能同時(shí)切。那么做完三道菜的最短A.90B.60C.50D.4014.假設(shè)某算法的計(jì)算A.O(n)B.O()C.O(logn)D.O(n2)1.給定含有n個(gè)不同的數(shù)的數(shù)組L=x1,x2,...,xn。如果L中存在xi(1in)使得x1x2...xi-1xixi+1...xn，則稱L是單峰的，并稱xi是L的“峰頂”?，F(xiàn)在已知L是單峰的，請把a(bǔ)-c三行代碼補(bǔ)全到算法中使得算法正確找到L的峰頂。a.Search(k+1,n)b.Search(1,k-1)c.returnL[k]Search(1,n)1.k-[n/2]2.ifL[k]L[k-1]andL[k]L[k+1]3.then 4.elseifL[k]L[k-1]andL[k]L[k+1]5.then 6.else 正確的填空順序是()。A.c,a,bB.c,b,aC.a,b,cD.b,a,c二、不定項(xiàng)選擇題(共5題，每題1.5分，共計(jì)7.5分；每題有一個(gè)或多個(gè)正確選項(xiàng)，多選或少選均不得分）CCFNOIP2020初賽提高組C++語言試題第3頁，共13頁1.以下屬于無線通信技術(shù)的有（）。A.藍(lán)牙B.WiFiC.GPRSD.以太網(wǎng)2.可以將單個(gè)計(jì)算機(jī)接入到計(jì)算機(jī)網(wǎng)絡(luò)中的網(wǎng)絡(luò)接入通訊設(shè)備有（）。A.網(wǎng)卡B.光驅(qū)C.鼠標(biāo)D.顯卡3.下列算法中運(yùn)用分治的有（）。A.快速排序B.歸并排序C.冒泡排序D.計(jì)數(shù)排序4.下圖表示一個(gè)果園灌溉系統(tǒng)，有A、B、C、D四個(gè)閥門，每個(gè)閥門可以打開或關(guān)上，所有管道粗細(xì)相同，以下設(shè)置閥門的方法中，可以讓果樹澆上水的有水有水果樹有（）。A.B打開，其他都關(guān)上B.AB都打開，CD都關(guān)上C.A打開，其他都關(guān)上D.D打開，其他都關(guān)上5.參加NOI比賽，以下能帶入考場的有（）。A.鋼筆B.適量的衣服C.U盤D.鉛筆三、問題求解（共2題，每題5分，共計(jì)10分；每題全部答對得5分，沒有部分分）1.一個(gè)1x8的方格圖形（不可旋轉(zhuǎn)）用黑、白兩種顏色填涂每個(gè)方格。如果每個(gè)方格只能填涂一種顏色，且不允許兩個(gè)黑格相鄰，共有 種填涂方案。2.某中學(xué)在安排期末考試時(shí)發(fā)現(xiàn)，有7個(gè)學(xué)生要參加7門課程的考試，下表列出了哪些學(xué)生參加哪些考試（用d表示要參加相應(yīng)的考試）。最少要安排 個(gè)不同的考試現(xiàn)在有n名身高兩兩不相同的同學(xué)依次走入教室，調(diào)查人員想預(yù)測每個(gè)人在走入教室的瞬間最想和已經(jīng)進(jìn)入教室的哪個(gè)人做朋友。當(dāng)有兩名同學(xué)和這名同學(xué)的身高差一樣時(shí)，這名同學(xué)會(huì)更想和高的那個(gè)人做朋友。比如一名身高為1.80米的同學(xué)進(jìn)入教室時(shí)，有一名身高為1.79米的同學(xué)和一名身高為1.81米的同學(xué)在教室里，那么這名身高為1.80米的同學(xué)會(huì)更想和身高為1.81米的同學(xué)做朋友。對于第一個(gè)走入教室的同學(xué)我們不做預(yù)測。由于我們知道所有人的身高和走進(jìn)教室的次序，所以我們可以采用離線的做法來解決這樣的問題，我們用排序加鏈表的方式幫助每一個(gè)人找到在他之前進(jìn)入教室的并且和他身高最相近的人。（第一空2分，其余3分）#includeiostreamusingnamespacestd;#defineMAXN202000#defineinfinity2147483647intanswer[MAXN],height[MAXN],previous[MAXN],next[MAXN];intrank[MAXN];intn;voidsort(intl,intr){intx=height[rank[(l+r)/2]],i=l,j=r,temp;while(i=j){while(height[rank[i]]x)i++;while(height[rank[j]]x)j--;if((1)){temp=rank[i];rank[i]=rank[j];rank[j]=temp;CCFNOIP2020初賽提高組C++語言試題第9頁，共13頁i++;j--;}}if(ir)sort(i,r);if(lj)sort(l,j);}intmain(){cinn;inti,higher,shorter;for(i=1;ii++){cinheight[i];rank[i]=i;sort(1,n);for(i=1;ii++){previous[rank[i]]=rank[i-1];(2);}for(i=n;ii--){higher=shorter=infinity;if(previous[i]!=0)shorter=height[i]-height[previous[i]];if(next[i]!=0)(3);if((4))answer[i]=previous[i];elseanswer[i]=next[i];next[previous[i]]=next[i];(5);}for(i=2;ii++)couti“:“answer[i];return0;}2.(交通中斷)有一個(gè)小國家，國家內(nèi)有n座城市和m條雙向的道路，每條道路連接著兩座不同的城市。其中1號城市為國家的首都。由于地震頻繁可能導(dǎo)致某一個(gè)城市與外界交通全部中斷。這個(gè)國家的首腦想知道，如果只有第i(i1)個(gè)城市因地震而導(dǎo)致交通中斷時(shí)，首都到多少個(gè)城市的最短路徑長度會(huì)發(fā)生改變。如果因?yàn)闊o法通過第i個(gè)城市而導(dǎo)致從首都出發(fā)無法到達(dá)某個(gè)城CCFNOIP2020初賽提高組C++語言試題第10頁，共13頁市，也認(rèn)為到達(dá)該城市的最短路徑長度改變。對于每一個(gè)城市i，假定只有第i個(gè)城市與外界交通中斷，輸出有多少個(gè)城市會(huì)因此導(dǎo)致到首都的最短路徑長度改變。我們采用鄰接表的方式存儲(chǔ)圖的信息，其中head[x]表示頂點(diǎn)x的第一條邊的編號，next[i]表示第i條邊的下一條邊的編號，point[i]表示第i條邊的終點(diǎn)，weight[i]表示第i條邊的長度。(第一空2分，其余3分)#includeiostream#includecstringusingnamespacestd;#defineMAXN6000#defineMAXM100000#defineinfinity2147483647inthead[MAXN],next[MAXM],point[MAXM],weight[MAXM];intqueue[MAXN],dist[MAXN],visit[MAXN];intn,m,x,y,z,total=0,answer;voidlink(intx,inty,intz){total++;next[total]=head[x];head[x]=total;point[total]=y;weight[total]=z;total++;next[total]=head[y];head[y]=total;point[total]=x;weight[total]=z;}intmain(){inti,j,s,t;cinnm;for(i=1;ii++){cinxyz;link(x,y,z);}for(i=1;ii++)dist[i]=infinity;(1);queue[1]=1;visit[1]=1;s=1;CCFNOIP2020初賽提高組C++語言試題第11頁，共13頁t=1;//使用SPFA求出第一個(gè)點(diǎn)到其余各點(diǎn)的最短路長度while(s=t){x=queue[s%MAXN];j=head[x];while(j!=0){if((2))