NOIP2012普及組初賽及答案

第十八屆全國(guó)青少年信息學(xué)奧林匹克聯(lián)賽初賽（普及組C++語(yǔ)言試題）競(jìng)賽時(shí)間：2012年10月13日14:30?16:30選手汪意：試題紙共有10頁(yè)，答題紙共有2頁(yè)，滿分100分。請(qǐng)?jiān)诖痤}紙上作答，寫(xiě)在試題紙上一律無(wú)效。不得使用任何電子設(shè)備（如計(jì)算器、手機(jī)、電子詞典等）或查閱任何書(shū)籍資料一、單項(xiàng)選擇題（共20題，每題1.5分，共計(jì)30分；每題且僅有一個(gè)正確選項(xiàng)）計(jì)算機(jī)如果缺少（），將無(wú)法正常啟動(dòng)。內(nèi)存 B.鼠標(biāo) C.U盤(pán) D.攝像頭（ ）是一種先進(jìn)先出的線性表。棧 B.隊(duì)列 C.哈希表（散列表） D.二叉樹(shù)目前計(jì)算機(jī)芯片（集成電路）制造的主要原料是（），它是一種可以在沙子中提煉出的物質(zhì)。A.硅 B.銅 C.鍺 D.鋁十六進(jìn)制數(shù)9A在（ ）進(jìn)制下是232。A.四 B.A C.十 D.十二（ ）不屬于操作系統(tǒng)。A.Windows B.DOS C.Photoshop D.NOILinux如果一棵二叉樹(shù)的中序遍歷是BAC，那么它的先序遍歷不可能是（）。A.ABC B.CBA C.ACB D.BAC目前個(gè)人電腦的（ ）市場(chǎng)占有率最靠前的廠商包括Intel、AMD等公司。A.顯示器 B.CPU C.內(nèi)存 D.鼠標(biāo)使用冒泡排序?qū)π蛄羞M(jìn)行升序排列，每執(zhí)行一次交換操作系統(tǒng)將會(huì)減少1個(gè)逆序?qū)?，因此序?,4,3,2,1需要執(zhí)行（）次操作，才能完成冒泡排序。A.0 B.5 C.10 D.15）計(jì)算機(jī)。D.超大規(guī)模集成電路9.1946年誕生于美國(guó)賓夕法尼亞大學(xué)的）計(jì)算機(jī)。D.超大規(guī)模集成電路A.電子管B.晶體管 C.集成電路無(wú)論是TCP/IP模型還是OSI模型，都可以視為網(wǎng)絡(luò)的分層模型，每個(gè)網(wǎng)絡(luò)協(xié)議都會(huì)被歸入某一層中。如果用現(xiàn)實(shí)生活中的例子來(lái)比喻這些“層”，以下最恰當(dāng)?shù)氖牵?）。A.中國(guó)公司的經(jīng)理與波蘭公司的經(jīng)理交互商業(yè)文件第4層中國(guó)公司經(jīng)理波蘭公司經(jīng)理t411第3層j卜國(guó)恣可婪理秘書(shū)耳蘭恐可豎理秘三t111第2層波蘭公司翻譯t119第1層中國(guó)郵遞員波蘭郵遞員軍隊(duì)發(fā)布命令

第4層司令'1第3層軍長(zhǎng)1軍長(zhǎng)W4第￡層師長(zhǎng)1師長(zhǎng)2師長(zhǎng)3師長(zhǎng)41441第1層團(tuán)長(zhǎng)1團(tuán)長(zhǎng)Z團(tuán)長(zhǎng)3團(tuán)長(zhǎng)4團(tuán)長(zhǎng)5團(tuán)長(zhǎng)&團(tuán)長(zhǎng)7團(tuán)長(zhǎng)8國(guó)際會(huì)議中，每個(gè)人都與他國(guó)地位對(duì)等的人直接進(jìn)行會(huì)談第4層英國(guó)女王———*瑞典國(guó)王第3層英國(guó)首相?——*瑞典首相第2層英國(guó)外交大臣?——*瑞典外交海第1層——*是我琶英國(guó)大便D.體育比賽中，每一級(jí)比賽的優(yōu)勝者晉級(jí)上一級(jí)比賽第4層奧運(yùn)套第3層全運(yùn)登t第￡層省運(yùn)合第1層市運(yùn)會(huì)矢量圖（VectorImage）圖形文件所占的貯存空間比較小，并且無(wú)論如何放大、縮小或旋轉(zhuǎn)等都不會(huì)失真，是因?yàn)樗?）。記錄了大量像素塊的色彩值來(lái)表示圖像用點(diǎn)、直線或者多邊形等基于數(shù)學(xué)方程的幾何圖元來(lái)表示圖像每個(gè)像素點(diǎn)的顏色信息均用矢量表示把文件保存在互聯(lián)網(wǎng)，采用在線瀏覽的方式查看圖像如果一個(gè)棧初始時(shí)為空，且當(dāng)前棧中的元素從棧頂?shù)綏５滓来螢閍，b，c，另有元素d已經(jīng)出棧，則可能的入棧順序是（ ）。A.a,d,c,bB.b,a,c,d C.a,c,b,dD.d,a,b,c（ ）是主要用于顯示網(wǎng)頁(yè)服務(wù)器或者文件系統(tǒng)的HTML文件的內(nèi)容，并讓用戶與這些文件交互的一種軟件。A.資源管理器 B.瀏覽器C.電子郵件 D.編譯器14.14.(）是目前互聯(lián)網(wǎng)上常用的E-mail服務(wù)協(xié)議。A.HTTP B.FTP C.POP3 D.Telnet（ ）就是把一個(gè)復(fù)雜的問(wèn)題分成兩個(gè)或更多的相同類(lèi)似的子問(wèn)題，再把子問(wèn)題分解成更小的子問(wèn)題……直到最后的子問(wèn)題可以簡(jiǎn)單地直接求解。而原問(wèn)題的解就是子問(wèn)題解的并。A.動(dòng)態(tài)規(guī)劃 B-貪心 C.分治 D.搜索地址總線的位數(shù)決定了CPU可直接尋址的內(nèi)存空間大小，例如地址總線為16位，其最大的可尋址空間為64KB。如果地址總線是32位，則理論上最大可尋址的內(nèi)存空間為（ ）。A.128KB B.1MB C.1GB D.4GB藍(lán)牙和Wi-Fi都是（ ）設(shè)備。A.無(wú)線廣域網(wǎng) B.無(wú)線城域網(wǎng) C.無(wú)線局域網(wǎng)D.無(wú)線路由器在程序運(yùn)行過(guò)程中，如果遞歸調(diào)用的層數(shù)過(guò)多，會(huì)因?yàn)椋ǎ┮l(fā)錯(cuò)誤。A.系統(tǒng)分配的?？臻g溢出 B.系統(tǒng)分配的堆空間溢出C.系統(tǒng)分配的隊(duì)列空間溢出 D.系統(tǒng)分配的鏈表空間溢出原字符串中任意一段連續(xù)的字符所組成的新字符串稱(chēng)為子串。則字符“AAABBBCCC”共有（）個(gè)不同的非空子串。TOC\o"1-5"\h\zA.3 B.12 C.36 D.45仿生學(xué)的問(wèn)世開(kāi)辟了獨(dú)特的科學(xué)技術(shù)發(fā)展道路。人們研究生物體的結(jié)構(gòu)、功能和工作原理，并將這些原理移植于新興的工程技術(shù)中。以下關(guān)于仿生學(xué)的敘述，錯(cuò)誤的是（ ）A.由研究蝙蝠，發(fā)明雷達(dá) B.由研究蜘蛛網(wǎng)，發(fā)明因特網(wǎng)C.由研究海豚，發(fā)明聲納 D.由研究電魚(yú)，發(fā)明伏特電池二、問(wèn)題求解（共2題，每題5分，共計(jì)10分）如果平面上任取n個(gè)整點(diǎn)（橫縱坐標(biāo)都是整數(shù)），其中一定存在兩個(gè)點(diǎn)，它們連線的中點(diǎn)也是整點(diǎn)，那么n至少是 。在NOI期間，主辦單位為了歡迎來(lái)自各國(guó)的選手，舉行了盛大的晚宴。在第十八桌，有5名大陸選手和5名港澳選手共同進(jìn)膳。為了增進(jìn)交流，他們決定相隔就坐，即每個(gè)大陸選手左右旁都是港澳選手，每個(gè)港澳選手左右旁都是大陸選手。那么，這一桌一共有 種不同的就坐方案。注：如果在兩個(gè)方案中，每個(gè)選手左右相鄰的選手相同，則視為同一種方案。三、閱讀程序?qū)懡Y(jié)果。（共4題，每題8分，共計(jì)32分）1.#include<iostream>usingnamespacestd;inta,b,c,d,e,ans;intmain（）{cin>>a>>b>>c;d=a+b;e=b+c;ans=d+e;cout<<ans<<endl;return0;}輸入：125輸出： 2.#include<iostream>usingnamespacestd;intn,i,ans;intmain(){cin>>n;ans=0;for(i=1;i<=n;i++)if(n%i==0)ans++;cout<<ans<<endl;return0;}輸入：18輸出： 3.#include<iostream>usingnamespacestd;intn,i,j,a[100][100];intsolve(intx,inty){intu,v;if(x==n)returna[x][y];u=solve(x+1,y);v=solve(x+1,y+1);if(u>v)returna[x][y]+u;elsereturna[x][y]+v;}intmain(){cin>>n;for(i=1;i<=n;i++)for(j=1;j<=i;j++)cin>>a[i][j];cout<<solve(1,1)<<endl;return0;}輸入：52-14-1-2-16402-158輸出： 4.#include<iostream>#include<string>usingnamespacestd;intn,i,j,ans;strings;charget(inti){if(i<n)returns[i];elsereturns[i-n];}intmain(){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;}elseif(get(i+j)>get(ans+j))break;}for(j=0;j<=n-1;j++)cout<<get(ans+j);cout<<endl;return0;}輸入：CBBADADA輸出： 四、完善程序(前2空每空2分，后8空每空3分，共計(jì)28分)(坐標(biāo)統(tǒng)計(jì))輸入n個(gè)整點(diǎn)在平面上的坐標(biāo)。對(duì)于每個(gè)點(diǎn)，可以控制所有位于它左下方的點(diǎn)(即x、y坐標(biāo)都比它小)，它可以控制的點(diǎn)的數(shù)目稱(chēng)為“戰(zhàn)斗力”。依次輸出每個(gè)點(diǎn)的戰(zhàn)斗力，最后輸出戰(zhàn)斗力最高的點(diǎn)的編號(hào)(如果若干個(gè)點(diǎn)的戰(zhàn)斗力并列最高，輸出其中最大的編號(hào))。#include<iostream>usingnamespacestd;constintSIZE=100;intx[SIZE],y[SIZE],f[SIZE];intn,i,j,max_f,ans;intmain(){cin>>n;for(i=1;i<=n;i++)cin>>x[i]>>y[i];max_f=0;for(i=1;i<=n;i++){f「i]=①;for(j=1;j<=n;j++){TOC\o"1-5"\h\zif(x「j]<x「i]&& ② );}if(④ ){max_f=f「i];⑤ ;}}for(i=1;i<=n;i++)cout<<f「i]<<endl;cout<<ans<<endl;return0;}(排列數(shù))輸入兩個(gè)正整數(shù)n，m(1<n<20,1<m<n)，在1~n中任取m個(gè)數(shù)，按字典序從小到大輸出所有這樣的排列。例如：輸入：32輸出：12TOC\o"1-5"\h\z313132#include<iostream>#include<cstring>usingnamespacestd;constintSIZE=25;boolused[SIZE];intdata[SIZE];intn,m,i,j,k;boolflag;intmain(){cin>>n>>m;memset(used,false,sizeof(used));for(i=1;i<=m;i++){data[i]=i;used[i]=true;}flag=true;while(flag){for(i=1;i<=m-1;i++)cout<<data[i]<<""cout<<data[m]<<endl;flag=① ;for(i=m;i>=1;i--){② ;for(j=data[i]+1;j<=n;j++)if(!used[j]){used[j]=true;data「i]=③ ;flag=true;break;}if(flag){for(k=i+1;k<=m;k++)for(j=1;j<= ④ ;j++)if(!used[j]){data[k]=j;used[j]=true;break;} ⑤ ;}}}return0;}參考答案、單項(xiàng)選擇題（共20題，每題1.5分，共計(jì)30分；每題且僅有一個(gè)正確選項(xiàng)）1212345AB