NOIP2004提高組初賽試題和答案

PAGE1第十屆全國青少年信息學(xué)奧林匹克聯(lián)賽初賽試題（提高組Pascal語言二小時(shí)完成）●全部試題答案均要求寫在答卷紙上，寫在試卷紙上一律無效●●一、單項(xiàng)選擇題（共10題，每題1.5分，共計(jì)15分。每題有且僅有一個(gè)正確答案.）。設(shè)全集I={a,b,c,d,e,f,g}，集合A={a,b,c}，B={b,d,e}，C={e,f,g}，那么集合為（）。A.{a,b,c,d}B.{a,b,d,e}C.{b,d,e}D.{b,c,d,e}E.{d,f,g}由3個(gè)a，5個(gè)b和2個(gè)c構(gòu)成的所有字符串中，包含子串“abc”的共有（）個(gè)。A.40320B.39600C.840D.780E.60某個(gè)車站呈狹長形，寬度只能容下一臺(tái)車，并且只有一個(gè)出入口。已知某時(shí)刻該車站狀態(tài)為空，從這一時(shí)刻開始的出入記錄為：“進(jìn)，出，進(jìn)，進(jìn)，出，進(jìn)，進(jìn)，進(jìn)，出，出，進(jìn)，出”。假設(shè)車輛入站的順序?yàn)?，2，3，……，則車輛出站的順序?yàn)椋ǎ?。A.1,2,3,4,5B.1,2,4,5,7C.1,3,5,4,6D.1,3,5,6,7E.1,3,6,5,7滿二叉樹的葉結(jié)點(diǎn)個(gè)數(shù)為N，則它的結(jié)點(diǎn)總數(shù)為（）。A.NB.2*NC.2*N–1D.2*N+1E.2N–1二叉樹T，已知其前序遍歷序列為1243576，中序遍歷序列為4215736，則其后序遍歷序列為（）。A.4257631B.4275631C.4275361D.4723561E.4526371十進(jìn)制數(shù)100.625等值于二進(jìn)制數(shù)（）。A.1001100.101B.1100100.101C.1100100.011D.1001100.11E.1001100.01下面哪個(gè)部件對于個(gè)人桌面電腦的正常運(yùn)行不是必需的（）。CPUB.圖形卡（顯卡）C.光驅(qū)D.主板E.內(nèi)存下列哪個(gè)網(wǎng)絡(luò)上常用的名字縮寫是錯(cuò)誤的（）。WWW（WorldWideWeb）URL（UniformResourceLocator）HTTP（HypertextTransferProtocol）FTP（FastTransferProtocol）TCP（TransferControlProtocol）。用靜電吸附墨粉后轉(zhuǎn)移到紙張上，是哪種輸出設(shè)備的工作方式（）。A.針式打印機(jī)B.噴墨打印機(jī)C.激光打印機(jī)D.筆式繪圖儀E.噴墨繪圖儀一臺(tái)計(jì)算機(jī)如果要利用電話線上網(wǎng)，就必須配置能夠?qū)?shù)字信號和模擬信號進(jìn)行相互轉(zhuǎn)換的設(shè)備，這種設(shè)備是（）。A.調(diào)制解調(diào)器B.路由器C.網(wǎng)卡D.網(wǎng)關(guān)E.網(wǎng)橋二、不定項(xiàng)選擇題（共10題，每題1.5分，共計(jì)15分。多選或少選均不得分）。美籍匈牙利數(shù)學(xué)家馮·諾依曼對計(jì)算機(jī)科學(xué)發(fā)展所做出的貢獻(xiàn)包括（）。提出理想計(jì)算機(jī)的數(shù)學(xué)模型，成為計(jì)算機(jī)科學(xué)的理論基礎(chǔ)。提出存儲(chǔ)程序工作原理，對現(xiàn)代電子計(jì)算機(jī)的發(fā)展產(chǎn)生深遠(yuǎn)影響。設(shè)計(jì)出第一臺(tái)具有存儲(chǔ)程序功能的計(jì)算機(jī)EDVAC。采用集成電路作為計(jì)算機(jī)的主要功能部件。指出計(jì)算機(jī)性能將以每兩年翻一番的速度向前發(fā)展。下列哪個(gè)（些）是64位處理器（）。A.IntelItaniumB.IntelPentiumIIIC.AMDAthlon64D.AMDOpteronE.IBMPower5(2004)10+(32)16的結(jié)果是（）。A.(2036)16B.(2054)10C.(4006)8D.(100000000110)2E.(2036)10下列哪個(gè)（些）不是數(shù)據(jù)庫軟件的名稱（）。A.MySQLB.SQLServerC.OracleD.OutlookE.Foxpro下列哪個(gè)（些）不是計(jì)算機(jī)的存儲(chǔ)設(shè)備（）。A.文件管理器B.內(nèi)存C.顯卡D.硬盤E.U盤下列哪個(gè)（些）軟件屬于操作系統(tǒng)軟件（）。A.MicrosoftWordB.WindowsXPC.FoxmailD.金山影霸E.RedHatLinux下列說法中正確的有（）。CPU的基本功能就是執(zhí)行指令。CPU的主頻是指CPU在1秒內(nèi)完成的指令周期數(shù)，主頻越快的CPU速度一定越快。內(nèi)部構(gòu)造不同的CPU運(yùn)行相同的機(jī)器語言程序，一定會(huì)產(chǎn)生不同的結(jié)果。在一臺(tái)計(jì)算機(jī)內(nèi)部，一個(gè)內(nèi)存地址編碼對應(yīng)唯一的一個(gè)內(nèi)存單元。數(shù)據(jù)總線的寬度決定了一次傳遞數(shù)據(jù)量的大小，是影響計(jì)算機(jī)性能的因素之一。彩色顯示器所顯示的五彩斑斕的色彩，是由哪三色混合而成的（）。A.紅B.白C.藍(lán)D.綠E.橙下列哪個(gè)（些）程序設(shè)計(jì)語言支持面向?qū)ο蟪绦蛟O(shè)計(jì)方法（）。A.C++B.ObjectPascalC.CD.SmalltalkE.Java某大學(xué)計(jì)算機(jī)專業(yè)的必修課及其先修課程如下表所示：請你判斷下列課程安排方案哪個(gè)（些）是合理的（）。A.C0,C1,C2,C3,C4,C5,C6,C7B.C0,C1,C2,C3,C4,C6,C7,C5C.C0,C1,C6,C7,C2,C3,C4,C5D.C0,C1,C6,C7,C5,C2,C3,C4E.C0,C1,C2,C3,C6,C7,C5,C4三．問題求解（共2題，每題5分，共計(jì)10分）75名兒童到游樂場去玩。他們可以騎旋轉(zhuǎn)木馬，坐滑行鐵道，乘宇宙飛船。已知其中20人這三種東西都玩過，55人至少玩過其中的兩種。若每樣乘坐一次的費(fèi)用是5元，游樂場總共收入700，可知有名兒童沒有玩過其中任何一種。已知a,b,c,d,e,f,g七個(gè)人中，a會(huì)講英語；b會(huì)講英語和漢語；c會(huì)講英語、意大利語和俄語；d會(huì)講漢語和日語；e會(huì)講意大利語和德語；f會(huì)講俄語、日語和法語；g會(huì)講德語和法語。能否將他們的座位安排在圓桌旁，使得每個(gè)人都能與他身邊的人交談？如果可以，請以“ab”開頭寫出你的安排方案：。四．閱讀程序（共4題，每題8分，共計(jì)32分）1．programprogam1;var u:array[0..3]ofinteger; a,b,c,x,y,z:integer;begin read(u[0],u[1],u[2],u[3]); a:=u[0]+u[1]+u[2]+u[3]-5; b:=u[0]*(u[1]-u[2]divu[3]+8); c:=u[0]*u[1]divu[2]*u[3]; x:=(a+b+2)*3-u[(c+3)mod4]; y:=(c*100-13)divadiv(u[bmod3]*5); if((x+y)mod2=0)thenz:=(a+b+c+x+y)div2; z:=(a+b+c–x-y)*2; writeln(x+y-z);end.輸入：2574輸出：。2．programprogram2;var i,number,ndata,sum:integer; data:array[1..100]ofinteger;proceduresolve(s,sign,n:integer);vari:integer;beginfori:=stondatadobegininc(sum,sign*(numberdiv(n*data[i])));solve(i+1,-sign,n*data[i]);end;end;begin read(number,ndata); sum:=0; fori:=1tondatadoread(data[i]); solve(1,1,1); writeln(sum);end.輸入：1000351311輸出：。3．programprogram3;varc:array[1..3]ofstring[200];s:array[1..10]ofinteger;m,n,i:integer;procedurenumara;varcod:boolean;i,j,nr:integer;begin forj:=1tondobegin nr:=0;cod:=true; fori:=1tomdo ifc[i,j]='1'thenbegin ifnotcodthenbegin cod:=true;inc(s[nr]);nr:=0; end end elsebegin ifcodthenbegin nr:=1;cod:=false; end elseinc(nr); end; ifnotcodtheninc(s[nr]); end;end;begin readln(m,n); fori:=1tomdoreadln(c[i]); numara; fori:=1tomdo ifs[i]<>0thenwrite(i,'',s[i],'');end.輸入：310111000011111000011111000000011輸出：。4．programprogram4;const u:array[0..2]ofinteger=(1,-3,2); v:array[0..1]ofinteger=(-2,3);var i,n,sum:integer;functiong(n:integer):integer;vari,sum:integer;begin sum:=0; fori:=1tondoinc(sum,u[imod3]*i); g:=sum;end;begin sum:=0; read(n); fori:=1tondoinc(sum,v[imod2]*g(i)); writeln(sum);end.輸入：103輸出：。五．完善程序(前5空，每空2分，后6空，每空3分，共28分)1．Joseph題目描述:原始的Joseph問題的描述如下：有n個(gè)人圍坐在一個(gè)圓桌周圍，把這n個(gè)人依次編號為1，…，n。從編號是1的人開始報(bào)數(shù)，數(shù)到第m個(gè)人出列，然后從出列的下一個(gè)人重新開始報(bào)數(shù)，數(shù)到第m個(gè)人又出列，…，如此反復(fù)直到所有的人全部出列為止。比如當(dāng)n=6，m=5的時(shí)候，出列的順序依次是5，4，6，2，3，1?，F(xiàn)在的問題是：假設(shè)有k個(gè)好人和k個(gè)壞人。好人的編號的1到k，壞人的編號是k+1到2k。我們希望求出m的最小值，使得最先出列的k個(gè)人都是壞人。輸入:僅有的一個(gè)數(shù)字是k（0<k<14）。輸出: 使得最先出列的k個(gè)人都是壞人的m的最小值。輸入樣例:4輸出樣例:30程序：programprogram1;var i,k,m,start:longint; find:boolean;functioncheck(remain:integer):boolean;varresult:integer;begin result:=(①)modremain; if(②)thenbegin start:=result;check:=true; end elsecheck:=false;end;begin find:=false; read(k); m:=k; while(③)dobegin find:=true;start:=0; fori:=0tok-1do if(notcheck(④))thenbegin find:=false;break; end; inc(m); end; writeln(⑤);end.2．邏輯游戲題目描述:一個(gè)同學(xué)給了我一個(gè)邏輯游戲。他給了我圖1，在這個(gè)圖上，每一段邊界都已經(jīng)進(jìn)行了編號。我的任務(wù)是在圖中畫一條連續(xù)的曲線，使得這條曲線穿過每一個(gè)邊界一次且僅穿過一次，而且曲線的起點(diǎn)和終點(diǎn)都在這整個(gè)區(qū)域的外面。這條曲線是容許自交的。對于圖1，我的同學(xué)告訴我畫出這樣的一條曲線（圖2）是不可能的，但是對于有的圖形（比如圖3），畫出這樣一條曲線是可行的。對于給定的一個(gè)圖，我想知道是否可以畫出滿足要求的曲線。圖1圖2圖3圖4輸入:輸入的圖形用一個(gè)n×n的矩陣表示的。矩陣的每一個(gè)單元里有一個(gè)0到255之間（包括0和255）的整數(shù)。處于同一個(gè)區(qū)域的單元里的數(shù)相同，相鄰區(qū)域的數(shù)不同（但是不相鄰的區(qū)域里的數(shù)可能相同）。輸入的第一行是n（0<n<100）。以下的n行每行包括n個(gè)整數(shù)，分別給出對應(yīng)的單元里的整數(shù)（這n個(gè)整數(shù)之間用空格分開）。圖4給出了輸入樣例對應(yīng)的圖形。輸出: 當(dāng)可以畫出滿足題意的曲線的時(shí)候，輸出“YES”；否則，輸出“NO”。輸入樣例:3112122112輸出樣例: YES程序：programprogram2;const d:array[0..7]ofinteger=(1,0,-1,0,0,1,①);var orig,n,i,j,ns:integer;a:array[0..101,0..101]ofinteger;bun:boolean;procedureplimba(x,y:integer);vari,x1,y1:integer;begin a[x,y]:=-a[x,y]; if(abs(a[x-1,y])<>orig)and((②<>a[x-1,y])or(abs(a[x,y-1])<>orig))theninc(ns); if(abs(a[x+1,y])<>orig)and((a[x+1,y-1]<>a[x+1,y])or(abs(a[x,y-1])<>orig))theninc(ns); if(abs(a[x,y-1])<>orig)and((③<>a[x,y-1])or(abs(a[x-1,y])<>orig))theninc(ns); if(abs(a[x,y+1])<>orig)and((a[x-1,y+1]<>a[x,y+1])or(abs(a[x-1,y])<>orig))theninc(ns); fori:=0to3dobegin x1:=x+d[2*i];y1:=y+④; if(x1>=1)and(x1<=n)and(y1>=1)and(y1<=n)and(⑤)thenplimba(x1,y1); end;end;begin bun:=true; read(n); fori:=0ton+1doforj:=0ton+1doa[i,j]:=0; a[0,0]:=-1;a[n+1,0]:=-1; a[0,n+1]:=-1;a[n+1,n+1]:=-1; fori:=1tondoforj:=1tondoread(a[i,j]); fori:=1tondoforj:=1tondoifa[i,j]>-1thenbegin ns:=0;⑥; plimba(i,j); ifnsmod2=1thenbun:=false; end; ifbunthenwriteln('YES'); ifnotbunthenwriteln('NO');end.

賽區(qū)市學(xué)校姓名==========================密封線=======================第十屆全國青少年信息學(xué)奧林匹克聯(lián)賽初賽試題提高組答卷紙閱卷記錄總閱卷人總得分第一大題得分第三大題得分題號12345678910第四大題得分得分1)2)3)4)第二大題得分第五大題得分題號11121314151617181920(1)(2)得分============================以下由考生填寫============================答卷部分單項(xiàng)選擇題（共10題，每題1.5分，共計(jì)15分。每題有且僅有一個(gè)正確答案.）。題號12３45678910選擇二．不定項(xiàng)選擇題（共10題，每題1.5分，共計(jì)15分。多選或少選均不得分）。題號11121314151617181920選擇三．問題求解（共2題，每題5分，共計(jì)10分）1.答：2.答:四.閱讀程序（共4題，每題8分，共計(jì)32分）程序的運(yùn)行結(jié)果是:程序的運(yùn)行結(jié)果是:賽區(qū)市學(xué)校姓名==========================密封線=======================四.閱讀程序（共4題，每題8分，共計(jì)32分）程序的運(yùn)行結(jié)果是:（4）程序的運(yùn)行結(jié)果是:五.完善程序(前5空，每空2分，后6空，每空3分，共28分)Pascal語言＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝1.（1）________________________________（2）________________________________（3）________________________________（4）________________________________（5）________________________________2.（1）________________________________（2）________________________________（3）________________________________（4）________________________________（5）_______________________________