NOIP信息學奧賽普及組初賽C試題

2015年第二十一屆全國青少年信息學奧林匹克聯(lián)賽初賽普及組C++語言試題競賽日寸間：2015年10月l1日14:30?16:30選手注意：?試題紙共有7頁，答題紙共有2頁，滿分100分。請在答題紙上作答，寫在試題紙上的一律無效。?不得使用任何電子設備(如計算器、手機、電子詞典等)或查閱任何書籍資料。一、單項選擇題(共20題，每題1.5分，共計30分；每題有且僅有一個正確選項)MB等于()。A.1000字節(jié)B.1024字節(jié)C．1000X1000字節(jié)D．1024X1024字節(jié)2.在PC機中，PENTIUM(奔騰)、酷睿、賽揚等是指()。A.生產(chǎn)廠家名稱B.硬盤的型號C.CPU的型號D.顯示器的型號3．操作系統(tǒng)的作用是()。A.把源程序譯成目標程序B.便于進行數(shù)據(jù)管理C.控制和管理系統(tǒng)資源D.實現(xiàn)硬件之間的連接4．在計算機內(nèi)部用來傳送、存貯、加工處理的數(shù)據(jù)或指令都是以()形式進行的。A.二進制碼B.八進制碼C.十進制碼D.智能拼音碼5．下列說法正確的是()。A.CPU的主要任務是執(zhí)行數(shù)據(jù)運算和程序控制B.存儲器具有記憶能力，其中信息任何時候都不會丟失C.兩個顯示器屏幕尺寸相同，則它們的分辨率必定相同D.個人用戶只能使用Wifi的方式連接到Internet6.二進制數(shù)00100100和00010100的和是()。A.00101000B.01001001C.01000100D.00111000.與二進制小數(shù)0.1相等的十六進制數(shù)是()。A.0.8B.0.4C.0.2D.0.1.所謂的“中斷”是指()。A.操作系統(tǒng)隨意停止一個程序的運行B.當出現(xiàn)需要時，CPU暫時停止當前程序的執(zhí)行轉而執(zhí)行處理新情況的過程C.因停機而停止一個程序的運行D.電腦死機.計算機病毒是()。A.通過計算機傳播的危害人體健康的一種病毒B.人為制造的能夠侵入計算機系統(tǒng)并給計算機帶來故障的程序或指令集合C.一種由于計算機元器件老化而產(chǎn)生的對生態(tài)環(huán)境有害的物質D.利用計算機的海量高速運算能力而研制出來的用于疾病預防的新型病毒.FTP可以用于()。A.遠程傳輸文件B.發(fā)送電子郵件C.瀏覽網(wǎng)頁D.網(wǎng)上聊天.下面哪種軟件不屬于即時通信軟件()。A.QQB.MSNC.微信D.P2P12.6個頂點的連通圖的最小生成樹，其邊數(shù)為()。A.6B.5C.7D.413.鏈表不具備的特點是()。A.可隨機訪問任何一個元素B.插入、刪除操作不需要移動元素C無需事先估計存儲空間大小D.所需存儲空間與存儲元素個數(shù)成正比14.線性表若采用鏈表存儲結構，要求內(nèi)存中可用存儲單元地址()。A.必須連續(xù)B.部分地址必須連續(xù)c一定不連續(xù)D.連續(xù)不連續(xù)均可15.今有一空棧S,對下列待進棧的數(shù)據(jù)元素序列a,b,c,d,e,f依次進行進棧，進棧，出棧，進棧，進棧，出棧的操作，則此操作完成后，棧S的棧頂元素為()。A．fB．cC．a(chǎn)D．b16．前序遍歷序列與中序遍序序列相同的二叉樹為()。A.根結點無左子塒的二義樹B.根結點無右子村的二叉附C.只有根結點的二叉樹或非葉子結點只有左子樹的二叉樹D.只有根結點的二叉樹或非葉子結點只有右子樹的二叉樹17．如果根的高度為1,只有61個結點的完全二叉樹的高度為()。A．5B．6C．7D．818．下列選項中不屬于視頻文件格式的是()。A.TXTB.AVIC.MOVD.RMVB19.設某算法的計算時間表示為遞推關系式T(n)=T(n-1)+n(n為正整數(shù))及T(0)=1,則該算法的時間復雜度為()。A.O(logn)B.O(nlogn)C.O(n)D.O(n2)20.在NOI系列賽事中參賽選手必須使用由承辦單位統(tǒng)一提供的設備。下列物品中不允許選手自帶的是()。A.鼠標B.筆C.身份證D.準考證二、問題求解(共2題,每題5分,共計10分；每題全部答對得5分,沒有部分分)1．重新排列1234使得每一個數(shù)字都不在原來的位置上,一共有種排法。2．一棵結點數(shù)為2015的二叉樹最多有個葉子結點。三、閱讀程序寫結果(共4題,每題8分,共計32分)#include<iostream>usingnamespacestd;intmain(){inta,b,c;a=1;b=2;c=3;if(a>b){if(a>c)cout<<a<<'';elsecout<<b<<'';}cout<<c<<endl;return0;}輸出：#include<iostream>usingnamespacestd;structpoint{intx;inty;};intmain(){structEX{inta;intb;pointc;}e;e.a=1;e.b=2;e.c.x=e.a+e.b;e.c.y=e.a*e.b;cout<<e.c.x<<','<<e.c.y<<endl;return0;}輸出：#include<iostream>#include<string>usingnamespacestd;intmain(){stringstr;inti;intcount;count=0;getline(cin,str);for(i=0;i<str.length();i++){if(str[i]>='a'&&str[i]<='z')count++;}cout<<"Ithas"<<count<<"lowercases"<<endl;return0;}輸入:NOI2016willbeheldinMianYang.輸出：#include<iostream>usingnamespacestd;voidfun(char*a,char*b){a=b;(*a)++;}intmain(){charc1,c2,*p1,*p2;c1='A';c2='a';p1=&c1;p2=&c2;fun(p1,p2);cout<<c1<<c2<<endl;return0;}輸出:四、完善程序(共2題，每題14分，共計28分).(打印月歷)輸入月份m(1<=m<=12),按一定格式打印2015年第m月的月歷。(第三、四空2.5分，其余3分)例如，2015年1月的月歷打印效果如下(第一列為周日)：SMTWTFSTOC\o"1-5"\h\z12345678910111213141516171819202122232425262728293031【參考程序】#include<iostream>usingnamespacestd;constintdayNum[]={-1,31,28,31,30,31,30,31,31,30,31,30,31};intm,offset,i;intmain(){cin>>m;cout<<"S\tM\tT\tW\tT\tF\tS”<<endl;//'\t'為TAB制表符TOC\o"1-5"\h\z⑴；for(i=1;i<m;i++)offset=(2);for(i=0;i<offset;i++)cout<<'\t';for(i=1;i<=⑶；i++){cout<<⑷；if(i==dayNum[m]||(5)==0)cout<<endl;elsecout<<'\t';}return0;.(中位數(shù))給定n(n為奇數(shù)且小于1000)個整數(shù)，整數(shù)的范圍在O~m(O<m<2"31)之間，請使用二分法求這n個整數(shù)的中位數(shù)。所謂中位數(shù)，是指將這n個數(shù)排序之后，排在正中間的數(shù)。(第五空2分，其余3分)#include<iostream>usingnamespacestd;constintMAXN=1000;intn,i,lbound,rbound,mid,m,count;intx[MAXN];intmain(){cin>>n>>m;for(i=0;i<n;i++)cin>>x[i];TOC\o"1-5"\h\zlbound=0;rbound=m;while(⑴){mid=(lbound+rbound)/2;⑵；for(i=0;i<n;i++)if(⑶)⑷；if(count>n/2)lbound=mid+1;else(5);}cout<<rbound<<endl;return0;}、選擇題答案12345678910DCCAADABBA11121314151617181920DBADBDBADA二、問題求解9解答：全部排列24種，一個在原位的有C41=4,兩個在原位的有C42=6,m個在原位的有C43=4,四個在原位的有C44=1,所在全部不在原位的24-4-6-4-1=9種。2.1008三、閱讀程序33,2Ithas18lowerca