2016年NOIP提高組初賽C++

第二十二屆全國青少年信息學(xué)奧林匹克聯(lián)賽初賽提高組C++語言試題（2小時）選手注意:?不得使用任何電子設(shè)備（如計算器、手機、電子詞典等）或查閱任何書籍資料。一、單項選擇題（共15題，每題1.5分，共計22.5分；每題有且僅有一個正確選項）.以下不是微軟公司出品的軟件是（）。A.PowerpointB.Word C.Excel D.AcrobatReader2.如果開始時計算機處于小寫輸入狀態(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個字符是字母（）。A.A B.S C.DD.A二進制數(shù)00101100和01010101異或的結(jié)果是（）。A.00101000 B.01111001 C.01000100D.00111000與二進制小數(shù)0.1相等的八進進制數(shù)是（）。A.0.8B.0.4C.0.2D.0.15.以比較作為基本運算，A.0.8B.0.4C.0.2D.0.15.以比較作為基本運算，在N個數(shù)中找最小數(shù)的最少運算次數(shù)為（ ）。A.NN-1N2D.logN6.表達式A.NN-1N2D.logN6.表達式a*（b+c）-d的后綴表達形式為（）。A.abcd*+-B.abc+*d-C.abc*+d-A.abcd*+-B.abc+*d-C.abc*+d-D.-+*abcdO'一棵二叉樹如右圖所示，若采用二叉樹鏈表存Q儲該二叉樹（各個結(jié)點包括結(jié)點的數(shù)據(jù)、左孩子指針、右孩子指針）。如果沒有左孩子或者右孩子，則對應(yīng)的為空指針。那么該鏈表中空指針的數(shù)目為（）。A.6 B.7D.14C.D.-+*abcdO'一棵二叉樹如右圖所示，若采用二叉樹鏈表存Q儲該二叉樹（各個結(jié)點包括結(jié)點的數(shù)據(jù)、左孩子指針、右孩子指針）。如果沒有左孩子或者右孩子，則對應(yīng)的為空指針。那么該鏈表中空指針的數(shù)目為（）。A.6 B.7D.14C.12G是一個非連通簡單無向圖，共有28條邊，則該圖至少有（）個頂點。109C.8D.79.某計算機的CPU和內(nèi)存之間的地址總線寬度是32位（bit）,這臺計算機最多可以使用（）的內(nèi)存。A.2GBB.4GBC.8GBD.16GB10.有以下程序：#include<iostream>usingnamespacestd;intmain（）{intk=4,n=0;while（n<k）{n++;if（n%3!=0）continue;k--;}cout<<k<<","<<n<<endl;return0;}程序運行后的輸出結(jié)果是（）。A.2,2 B.2,3C.3,2 D.3,311.有7個一模一樣的蘋果，放到3個一樣的盤子中，一共有（）種放法。A.7 B.8 C.21 D.3712.Lucia和她的朋友以及朋友的朋友都在某社交網(wǎng)站上注冊了賬號。下圖是他們之間的關(guān)系圖，兩個人之間有邊相連代表這兩個人是朋友，沒有邊相連代表不是朋友。這個社交網(wǎng)站的規(guī)則是：如果某人A向他（她）的朋友B分享了某張照片，那么B就可以對該照片進行評論；如果B評論了該照片，那么他（她）的所有朋友都可以看見這個評論以及被評論的照片，但是不能對該照片進行評論（除非A也向他（她）分享了該照片）?，F(xiàn)在Lucia已經(jīng)上傳了一張照片，但是她不想讓Jacob看見這張照片，那么她可以向以下朋友()分享該照片。A.Dana,Michael,Eve B.Dana,Eve,MonicaC.Michael,Eve,Jacob D.Micheal,Peter,Monica.周末小明和爸爸媽媽三個人一起想動手做三道菜。小明負責(zé)洗菜、爸爸負責(zé)切菜、媽媽負責(zé)炒菜。假設(shè)做每道菜的順序都是：先洗菜10分鐘，然后切菜10分鐘，最后炒菜10分鐘。那么做一道菜需要30分鐘。注意：兩道不同的菜的相同步驟不可以同時進行。例如第一道菜和第二道的菜不能同時洗，也不能同時切。那么做完三道菜的最短時間需要0分鐘。A.90B.60C.50D.40.假設(shè)某算法的計算時間表示為遞推關(guān)系式T(n)=2T(n)+nn4 , 4T(1)=1則算法的時間復(fù)雜度為()。A.O(n)B.OQn)C.O(vnlogn)D.O(n2)1.給定含有n個不同的數(shù)的數(shù)組L=<X1,X2,...,Xn>。如果L中存在Xi(1<i<n)使得X1<X2<...<Xi-1<Xi>xi+1>...>Xn則稱L是單峰的，并稱xi是L的“峰頂”?，F(xiàn)在已知L是單峰的，請把a-c三行代碼補全到算法中使得算法正確找到L的峰頂。Search(k+1,n)Search(1,k-1)returnL[k]Search（1,n）k-[n/2]ifL[k]>L[k-1]andL[k]>L[k+1]then elseifL[k]>L[k-1]andL[k]<L[k+1]then else 正確的填空順序是（）。A.c,a,bB.c,b,aC.a,b,cD.b,a,c二、不定項選擇題（共5題，每題1.5分，共計7.5分；每題有一個或多個正確選項，多選或少選均不得分）.以下屬于無線通信技術(shù)的有（）。A.藍牙B.WiFiC.GPRSD.以太網(wǎng).可以將單個計算機接入到計算機網(wǎng)絡(luò)中的網(wǎng)絡(luò)接入通訊設(shè)備有（）。A.網(wǎng)卡B.光驅(qū)C.鼠標D.顯卡.下列算法中運用分治思想的有（）。A.快速排序B.歸并排序C.冒泡排序D.計數(shù)排序.下圖表示一個果園灌溉系統(tǒng)，有A、B、C、D四個閥門，每個閥門可以打開或關(guān)上，所有管道粗細相同，以下設(shè)置閥門的方法中，可以讓果樹澆上水的有（）。

有水樹A.B打開，其他都關(guān)上CD都關(guān)上有水DAB都打開，C.A打開，其他都關(guān)上 DD.D打開，其有水DAB都打開，他都關(guān)上5.參加NOI比賽，以下能帶入考場的有（）。A.鋼筆B. 適量的衣服C.U盤D.鉛筆三、問題求解（共2題，每題5分，共計10分；每題全部答對得5分，沒有部分分）.一個1X8的方格圖形（不可旋轉(zhuǎn)）用黑、白兩種顏色填涂每個方格。如果每個方格只能填涂一種顏色，且不允許兩個黑格相鄰，共有種填涂方案。.某中學(xué)在安排期末考試時發(fā)現(xiàn)，有7個學(xué)生要參加7門課程的考試，下表列出了哪些學(xué)生參加哪些考試（用，表示要參加相應(yīng)的考試）。最少要安排 個不同的考試時間段才能避免沖突？考試學(xué)生1學(xué)生2學(xué)生3學(xué)生4學(xué)生5學(xué)生6學(xué)生7通用技術(shù)VVV物理VVV化學(xué)VVusingnamespacestd;intmain(){inta[6]={1,2,3,4,5,6};intpi=0;intpj=5;intt,i;while(pi<pj){=a[pi];a[pi]=aja[pj]=t;pi++;pj--;}for(i=0;i<6;i++)cout<<a[i]<<",";cout<<endl;return0;輸出： #include<iostream>usingnamespacestd;intmain(){chara[100][100],b[100][100];stringc[100];stringtmp;intn,i=0,j=0,k=0,total_len[100],length[100][3];cin>>n;getline(cin,tmp);for(i=0;i<n;i++){getline(cin,c[i]);total_len[i]=c[i].size();}for(i=0;i<n;i++){j=0;while(c[i][j]!='：'){a[i][k]=c[i][j];k=k+1;j++;}length[i][1]=k-1;a[i][k]=0;k=0;for(j=j+1;j<total_len[i];j++){b[i][k]=c[i][j];k=k+1;}length[i][2]=k-1;b[i][k]=0;k=0;}for(i=0;i<n;i++){if(length[i][1]>=length[i][2])cout<<"NO,";else{k=0;for(j=0;j<length[i][2];j++){if(a[i][k]==b[i][j])k=k+1;if(k>length[i][1])break;}if(j==length[i][2])cout<<"NO,";elsecout<<"YES,";}}cout<<endl;return0;}輸入：3AB:ACDEbFBkBDAR:ACDBrTSARS:SevereAtypicalRespiratorySyndrome輸出： (注：輸入各行前后均無空格)#include<iostream>usingnamespacestd;intlps(stringseq,inti,intj){intlen1,len2;if(i==j)return1;if(i>j)return0;if(seq[i]==seq[j])returnlps(seq,i+1,j-1)+2;len1=lps(seq,i,j-1);len2=lps(seq,i+1,j);if(len1>len2)returnlen1;returnlen2;}intmain(){stringseq="acmerandacm";intn=seq.size();cout<<lps(seq,0,n-1)<<endl;return0;}輸出： #include<iostream>#include<cstring>usingnamespacestd;intmap[100][100];intsum[100],weight[100];intvisit[100];intn;voiddfs(intnode){visit[node]=1;sum[node]=1;intv,maxw=0;for(v=1;v<=n;v++){if(!map[node][v]||visit[v])continue;dfs(v);sum[node]+=sum[v];if(sum[v]>maxw)maxw=sum[v];}if(n-sum[node]>maxw)maxw=n-sum[node];weight[node]=maxw;}intmain(){memset(map,0,sizeof(map));memset(sum,0,sizeof(sum));memset(weight,0,sizeof(weight));memset(visit,0,sizeof(visit));cin>>n;inti,x,y；for(i=1;i<n;i++){cin>>x>>y;map[x][y]=1;map[y][x]=1;}dfs(1);intans=n,ansN=0;for(i=1;i<=n;i++)if(weight[i]<ans){ans=weight[i];ansN=i;…ansN_<<ans…return0;輸入：112345677871169910輸出： 五、完善程序(共2題，每題14分，共計28分)1.（交朋友）根據(jù)社會學(xué)研究表明，人們都喜歡找和自己身高相近的人做朋友?，F(xiàn)在有n名身高兩兩不相同的同學(xué)依次走入教室，調(diào)查人員想預(yù)測每個人在走入教室的瞬間最想和已經(jīng)進入教室的哪個人做朋友。當(dāng)有兩名同學(xué)和這名同學(xué)的身高差一樣時，這名同學(xué)會更想和高的那個人做朋友。比如一名身高為1.80米的同學(xué)進入教室時，有一名身高為1.79米的同學(xué)和一名身高為1.81米的同學(xué)在教室里，那么這名身高為1.80米的同學(xué)會更想和身高為1.81米的同學(xué)做朋友。對于第一個走入教室的同學(xué)我們不做預(yù)測。由于我們知道所有人的身高和走進教室的次序，所以我們可以采用離線的做法來解決這樣的問題，我們用排序加鏈表的方式幫助每一個人找到在他之前進入教室的并且和他身高最相近的人。（第一空2分，其余3分）#include<iostream>usingnamespacestd;#defineMAXN200000intanswer[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){i++;while(height[rank[i]]<x)i++;while(height[rank[j]]>x) j--;if(⑴){temp=rank[i];rank[i]=rank[j];rank[j]=temp;i++;j--；if(i<r)sort(i,r);if(l<j)sort(l,j)；intmain(){cin>>n;inti,higher,shorter;for(i=1;i<=n;i++){cin>>height[i];rank[i]=i;sort(1,n);for(i=1;i<=n;i++){previous[rank[i]]=rank[i-1];(2) ;for(i=n;i>=2;i--){higher=shorter=infinity;if(previous[i]!=0)shorter=height[i]-height[previous[i]];if(next[i]!=0)⑶ ；if(⑷ )answer[i]=previous[i];elseanswer[i]=next[i];next[previous[i]]=next[i];⑸ ；}for(i=2;i<=n;i++)cout<<i<<":"<<answer[i];return0;}2.(交通中斷)有一個小國家，國家內(nèi)有n座城市和m條雙向的道路，每條道路連接著兩座不同的城市。其中1號城市為國家的首都。由于地震頻繁可能導(dǎo)致某一個城市與外界交通全部中斷。這個國家的首腦想知道，如果只有第i(i>1)個城市因地震而導(dǎo)致交通中斷時，首都到多少個城市的最短路徑長度會發(fā)生改變。如果因為無法通過第i個城市而導(dǎo)致從首都出發(fā)無法到達某個城市，也認為到達該城市的最短路徑長度改變。對于每一個城市i，假定只有第i個城市與外界交通中斷，輸出有多少個城市會因此導(dǎo)致到首都的最短路徑長度改變。我們采用鄰接表的方式存儲圖的信息，其中head[x]表示頂點x的第一條邊的編號，next[i]表示第i條邊的下一條邊的編號，point[i]表示第i條邊的終點，weight[i]表示第i條邊的長度。(第一空2分，其余3分)#include<iostream>#include<cstring>usingnamespacestd;#defineMAXN6000#defineMAXM100000inthead[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;cin>>n>>m;for(i=1;i<=m;i++){cin>>x>>y>>z;link(x,y,z);}for(i=1;i<=n;i++)dist[i]=infinity;⑴ ;queue[1]=1;visit[1]=1;s=1;t=1;//使用SPFA求出第一個點到其余各點的最短路長度while(s<=t){x=queue[s%MAXN];j=h