P普及組初賽及答案++

第十八屆全國青少年信息學奧林匹克聯(lián)賽初賽（普及組 C++語言試題）競賽時間：2012年10月13日14:30~16:30選手注意：試題紙共有 10頁，答題紙共有 2頁，滿分 100分。請在答題紙上作答，寫在試題紙上一律無效。不得使用任何電子設備（如計算器、手機、電子詞典等）或查閱任何書籍資料一、單項選擇題（共20題，每題分，共計30分；每題且僅有一個正確選項）1．計算機如果缺少（），將無法正常啟動。A．內(nèi)存B．鼠標C．U盤D．攝像頭2．（）是一種先進先出的線性表。A．棧B．隊列C．哈希表（散列表）D．二叉樹3．目前計算機芯片（集成電路）制造的主要原料是（），它是一種可以在沙子中提煉出的物質(zhì)。A．硅B．銅C．鍺D．鋁4．十六進制數(shù)9A在（）進制下是232。A．四B．八C．十D．十二5．（）不屬于操作系統(tǒng)。A．WindowsB．DOSC．PhotoshopD．NOILinux6．如果一棵二叉樹的中序遍歷是BAC，那么它的先序遍歷不可能是（）。A．ABCB．CBAC．ACBD．BAC7．目前個人電腦的（）市場占有率最靠前的廠商包括Intel、AMD等公司。A．顯示器B．CPUC．內(nèi)存D．鼠標8．使用冒泡排序?qū)π蛄羞M行升序排列，每執(zhí)行一次交換操作系統(tǒng)將會減少1個逆序?qū)?，因此序?，4，3，2，1需要執(zhí)行（）次操作，才能完成冒泡排序。A．0B．5C．10D．159．1946年誕生于美國賓夕法尼亞大學的ENIAC屬于（）計算機。A．電子管B．晶體管C．集成電路D．超大規(guī)模集成電路10．無論是TCP/IP模型還是OSI模型，都可以視為網(wǎng)絡的分層模型，每個網(wǎng)絡協(xié)議都會被歸入某一層中。如果用現(xiàn)實生活中的例子來比喻這些“層”，以下最恰當?shù)氖牵ǎ?。A．中國公司的經(jīng)理與波蘭公司的經(jīng)理交互商業(yè)文件B．軍隊發(fā)布命令C．國際會議中，每個人都與他國地位對等的人直接進行會談D．體育比賽中，每一級比賽的優(yōu)勝者晉級上一級比賽11．矢量圖（Vector Image）圖形文件所占的貯存空間比較小，并且無論如何放大、縮小或旋轉(zhuǎn)等都不會失真，是因為它（ ）。A．記錄了大量像素塊的色彩值來表示圖像B．用點、直線或者多邊形等基于數(shù)學方程的幾何圖元來表示圖像C．每個像素點的顏色信息均用矢量表示D．把文件保存在互聯(lián)網(wǎng)，采用在線瀏覽的方式查看圖像12．如果一個棧初始時為空，且當前棧中的元素從棧頂?shù)綏５滓来螢閯t可能的入棧順序是（ ）。A．a(chǎn),d,c,b B．b,a,c,d C．a(chǎn),c,b,d

a，b，c，另有元素D．d,a,b,c

d已經(jīng)出棧，13．（

）是主要用于顯示網(wǎng)頁服務器或者文件系統(tǒng)的

HTML文件的內(nèi)容，并讓用戶與這些文件交互的一種軟件。A．資源管理器

B．瀏覽器

C．電子郵件

D．編譯器14．（A．HTTP

）是目前互聯(lián)網(wǎng)上常用的B．FTP

E-mail 服務協(xié)議。C．POP3

D．Telnet15．（

）就是把一個復雜的問題分成兩個或更多的相同類似的子問題，再把子問題分解成更小的子問題??直到最后的子問題可以簡單地直接求解。而原問題的解就是子問題解的并。A．動態(tài)規(guī)劃 B．貪心 C．分治 D．搜索16．地址總線的位數(shù)決定了 CPU可直接尋址的內(nèi)存空間大小，例如地址總線為空間為64KB。如果地址總線是 32位，則理論上最大可尋址的內(nèi)存空間為（A．128KB B．1MB C．1GB D．4GB

16位，其最大的可尋址）。17．藍牙和Wi-FiA．無線廣域網(wǎng)

都是（

）設備。B．無線城域網(wǎng)

C．無線局域網(wǎng)

D．無線路由器18．在程序運行過程中，如果遞歸調(diào)用的層數(shù)過多，會因為（ ）引發(fā)錯誤。A．系統(tǒng)分配的?？臻g溢出 B．系統(tǒng)分配的堆空間溢出C．系統(tǒng)分配的隊列空間溢出

D．系統(tǒng)分配的鏈表空間溢出19．原字符串中任意一段連續(xù)的字符所組成的新字符串稱為子串。則字符“

AAABBBCCC”共有（

）個不同的非空子串。A．3

B．12

C．36

D．4520．仿生學的問世開辟了獨特的科學技術發(fā)展道路。人們研究生物體的結構、功能和工作原理，并將這些原理移植于新興的工程技術中。以下關于仿生學的敘述，錯誤的是（）A．由研究蝙蝠，發(fā)明雷達 B．由研究蜘蛛網(wǎng)，發(fā)明因特網(wǎng)C．由研究海豚，發(fā)明聲納 D．由研究電魚，發(fā)明伏特電池二、問題求解（共

2題，每題

5分，共計

10分）1．如果平面上任取 n個整點（橫縱坐標都是整數(shù)）那么n至少是__________。

，其中一定存在兩個點，

它們連線的中點也是整點，2．在NOI期間，主辦單位為了歡迎來自各國的選手，舉行了盛大的晚宴。在第十八桌，有 5名大陸選手和5名港澳選手共同進膳。 為了增進交流， 他們決定相隔就坐， 即每個大陸選手左右旁都是港澳選手，每個港澳選手左右旁都是大陸選手。那么，這一桌一共有 _______種不同的就坐方案。注：如果在兩個方案中，每個選手左右相鄰的選手相同，則視為同一種方案。三、閱讀程序?qū)懡Y果。（共

4題，每題

8分，共計

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-142-1-2-164032-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=();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分，共計

28分）1．（坐標統(tǒng)計）輸入 n個整點在平面上的坐標。對于每個點，可以控制所有位于它左下方的點（即

x、坐標都比它?。?，它可以控制的點的數(shù)目稱為“戰(zhàn)斗力”。依次輸出每個點的戰(zhàn)斗力，最后輸出戰(zhàn)斗力最高的點的編號（如果若干個點的戰(zhàn)斗力并列最高，輸出其中最大的編號）。#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++){if(x[j]<x[i]&&

②

)③

;}if(

④

){max_f=f[i];;}}for(i=1;i<=n;i++)cout<<f[i]<<endl;cout<<ans<<endl;return0;}2．（排列數(shù)）輸入兩個正整數(shù) n，m（1<n<20,1<m<n），在1~n中任取 m個數(shù)，按字典序從小到大輸出所有這樣的排列。例如：輸入：32輸出：12313132#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;}參考答案一、單項選擇題（共 20題，每題 1．5分，共計 30分；每題且僅有一個正確選項）12345678910ABABCCBCAA111213141516171