NOIP2012初賽普及組C題目及答案

1、第十八屆全國青少年信息學奧林匹克聯(lián)賽初賽（普及組C+語言試題）競賽時間：2012年10月13日14:3016:30選手注意：l 試題紙共有10頁，答題紙共有2頁，滿分100分。請在答題紙上作答，寫在試題紙上一律無效。l 不得使用任何電子設備（如計算器、手機、電子詞典等）或查閱任何書籍資料一、單項選擇題（共20題，每題1.5分，共計30分；每題且僅有一個正確選項） 1計算機如果缺少（ ），將無法正常啟動。A內存 B鼠標C U盤 D 攝像頭 2（ ）是一種先進先出的線性表。A棧B隊列 C哈希表（散列表） D二叉樹 3目前計算機芯片（集成電路）制造的主要原料是（ ），它是一種可以在沙子中提煉出的物質

2、。A硅 B銅 C鍺 D鋁4十六進制數(shù)9A在（ ）進制下是232。A四 B八 C十 D十二 5（ ）不屬于操作系統(tǒng)。 AWindows BDOS CPhotoshop DNOI Linux 6如果一棵二叉樹的中序遍歷是BAC，那么它的先序遍歷不可能是（ ）。 AABC BCBA CACB DBAC 7 目前個人電腦的（ ）市場占有率最靠前的廠商包括Intel、AMD等公司。A顯示器 BCPU C內存 D鼠標 8 使用冒泡排序對序列進行升序排列，每執(zhí)行一次交換操作系統(tǒng)將會減少1個逆序對，因此序列 5，4，3，2，1需要執(zhí)行（ ）次操作，才能完成冒泡排序。 A0 B5 C10 D15 9 1946年

3、誕生于美國賓夕法尼亞大學的ENIAC屬于（ ）計算機。 A電子管 B晶體管 C集成電路 D超大規(guī)模集成電路 10 無論是TCP/IP模型還是OSI模型，都可以視為網(wǎng)絡的分層模型，每個網(wǎng)絡協(xié)議都會被歸入某一層中。如果用現(xiàn)實生活中的例子來比喻這些“層”，以下最恰當?shù)氖牵?）。 A 中國公司的經理與波蘭公司的經理交互商業(yè)文件B 軍隊發(fā)布命令C 國際會議中，每個人都與他國地位對等的人直接進行會談D 體育比賽中，每一級比賽的優(yōu)勝者晉級上一級比賽11矢量圖（Vector Image）圖形文件所占的貯存空間比較小，并且無論如何放大、縮小或旋轉等都不會失真，是因為它（ ）。 A記錄了大量像素塊的色彩值來表示圖

4、像 B用點、直線或者多邊形等基于數(shù)學方程的幾何圖元來表示圖像 C每個像素點的顏色信息均用矢量表示 D把文件保存在互聯(lián)網(wǎng)，采用在線瀏覽的方式查看圖像 12 如果一個棧初始時為空，且當前棧中的元素從棧頂?shù)綏５滓来螢閍，b，c，另有元素d已經出棧，則可能的入棧順序是（ ）。Aa, d, c, b Bb, a, c, d Ca, c, b, d Dd, a, b, c 13（ ）是主要用于顯示網(wǎng)頁服務器或者文件系統(tǒng)的HTML文件的內容，并讓用戶與這些文件交互的一種軟件。A資源管理器 B瀏覽器 C電子郵件 D編譯器 14（ ）是目前互聯(lián)網(wǎng)上常用的E-mail服務協(xié)議。AHTTP BFTP CPOP3 D

5、Telnet 15（ ）就是把一個復雜的問題分成兩個或更多的相同類似的子問題，再把子問題分解成更小的子問題直到最后的子問題可以簡單地直接求解。而原問題的解就是子問題解的并。A動態(tài)規(guī)劃 B貪心 C分治 D搜索 16地址總線的位數(shù)決定了CPU可直接尋址的內存空間大小，例如地址總線為16位，其最大的可尋址空間為64KB。如果地址總線是32位，則理論上最大可尋址的內存空間為（ ）。 A128KB B1MB C1GB D4GB 17藍牙和Wi-Fi都是（ ）設備。A無線廣域網(wǎng) B無線城域網(wǎng) C無線局域網(wǎng) D無線路由器 18 在程序運行過程中，如果遞歸調用的層數(shù)過多，會因為（ ）引發(fā)錯誤。A系統(tǒng)分配的?？?/p>

6、間溢出 B系統(tǒng)分配的堆空間溢出 C系統(tǒng)分配的隊列空間溢出 D系統(tǒng)分配的鏈表空間溢出 19 原字符串中任意一段連續(xù)的字符所組成的新字符串稱為子串。則字符“AAABBBCCC”共有（ ）個不同的非空子串。A3 B12 C36 D45 20 仿生學的問世開辟了獨特的科學技術發(fā)展道路。人們研究生物體的結構、功能和工作原理，并將這些原理移植于新興的工程技術中。以下關于仿生學的敘述，錯誤的是（ ）A由研究蝙蝠，發(fā)明雷達 B由研究蜘蛛網(wǎng)，發(fā)明因特網(wǎng) C由研究海豚，發(fā)明聲納 D由研究電魚，發(fā)明伏特電池二、問題求解（共2題，每題5分，共計10分） 1 如果平面上任取n個整點（橫縱坐標都是整數(shù)），其中一定存在兩個

7、點，它們連線的中點也是整點，那么n至少是_。 2 在NOI期間，主辦單位為了歡迎來自各國的選手，舉行了盛大的晚宴。在第十八桌，有5名大陸選手和5名港澳選手共同進膳。為了增進交流，他們決定相隔就坐，即每個大陸選手左右旁都是港澳選手，每個港澳選手左右旁都是大陸選手。那么，這一桌一共有_種不同的就坐方案。注：如果在兩個方案中，每個選手左右相鄰的選手相同，則視為同一種方案。三、閱讀程序寫結果。（共4題，每題8分，共計32分） 1 #include <iostream>using namespace std;int a,b,c,d,e,ans;int main()cin>>a&g

8、t;>b>>c;d=a+b;e=b+c;ans=d+e;cout<<ans<<endl;return 0;輸入：1 2 5 輸出：_ 2#include <iostream>using namespace std;int n,i,ans;int main()cin>>n;ans=0;for(i=1;i<=n;i+)if(n%i=0) ans+;cout<<ans<<endl;return 0;輸入：18輸出：_ 3 #include <iostream>using namespace s

9、td;int n,i,j,a100100;int solve(int x,int y)int u,v;if(x=n) return axy;u=solve(x+1,y);v=solve(x+1,y+1);if(u>v) return axy+u;else return axy+v;int main()cin>>n;for(i=1;i<=n;i+)for(j=1;j<=i;j+) cin>>aij;cout<<solve(1,1)<<endl;return 0;輸入： 5 2 -1 4 2 -1 -2 -1 6 4 0 3 2 -

10、1 5 8輸出：_ 4 #include <iostream>#include <string>using namespace std;int n,i,j,ans;string s;char get(int i)if(i<n) return si;else return si-n;int main()cin>>s;n=s.size();ans=0;for(i=1;i<=n-1;i+)for(j=0;j<=n-1;j+)if(get(i+j)<get(ans+j)ans=i;break;else if(get(i+j)>get(a

11、ns+j) break;for(j=0;j<=n-1;j+) cout<<get(ans+j);cout<<endl;return 0;輸入：CBBADADA輸出：_ 四、完善程序（前2空每空2分，后8空每空3分，共計28分） 1（坐標統(tǒng)計）輸入n個整點在平面上的坐標。對于每個點，可以控制所有位于它左下方的點（即x、y坐標都比它?。?，它可以控制的點的數(shù)目稱為“戰(zhàn)斗力”。依次輸出每個點的戰(zhàn)斗力，最后輸出戰(zhàn)斗力最高的點的編號（如果若干個點的戰(zhàn)斗力并列最高，輸出其中最大的編號）。#include <iostream>using namespace std;c

12、onst int SIZE =100;int xSIZE,ySIZE,fSIZE;int n,i,j,max_f,ans;int main()cin>>n;for(i=1;i<=n;i+) cin>>xi>>yi;max_f=0;for(i=1;i<=n;i+)fi= ;for(j=1;j<=n;j+)if(xj<xi && ) ;if( )max_f=fi; ;for(i=1;i<=n;i+) cout<<fi<<endl;cout<<ans<<endl;retu

13、rn 0;2 （排列數(shù)）輸入兩個正整數(shù)n，m（1<n<20,1<m<n），在1n中任取m個數(shù)，按字典序從小到大輸出所有這樣的排列。例如： 輸入：3 2 輸出：1 21 3 2 1 2 33 1 3 2#include <iostream>#include <cstring>using namespace std;const int SIZE =25;bool usedSIZE;int dataSIZE;int n,m,i,j,k;bool flag;int main()cin>>n>>m;memset(used,false

14、,sizeof(used);for(i=1;i<=m;i+)datai=i;usedi=true;flag=true;while(flag)for(i=1;i<=m-1;i+) cout<<datai<<" "cout<<datam<<endl;flag= ;for(i=m;i>=1;i-) ;for(j=datai+1;j<=n;j+)if(!usedj)usedj=true;datai= ;flag=true;break;if(flag)for(k=i+1;k<=m;k+)for(j=1;j<= ;j+)if(!usedj)datak=j;usedj=true;break; ;return 0;參考答案一、單項選擇題（共20題，每題15分，共計30分；每題且僅有一個正確選項）12345678910ABABCCBCAA111