(NOI)2003第九屆全國(guó)青少年信息學(xué)奧林匹克聯(lián)賽初賽試題

北京清北學(xué)堂 報(bào)名咨詢(xún)熱線： 400-699-3290 北京清北學(xué)堂 報(bào)名咨詢(xún)熱線： 400-699-3290 更多競(jìng)賽真題免費(fèi)下載 見(jiàn)北京清北學(xué)堂官方網(wǎng)站 學(xué)習(xí)資源：自主招生 學(xué)科競(jìng)賽 高考等資源 第九屆全國(guó)青少年信息學(xué)奧林匹克聯(lián)賽初賽試題 (提高組 PASCAL 語(yǔ)言二小時(shí)完成 ) 全部試題答案均要求寫(xiě)在答卷紙上，寫(xiě)在試卷紙上一律無(wú)效 ) 一、單項(xiàng)選擇題 (共 10 題，每題 1.5 分，共計(jì) 15 分。每題有且僅有 -個(gè)正確答案 )。 1圖靈 (Alan Turing)是 ( )。 A)美國(guó)人 B)英國(guó)人 C)德國(guó)人 D)匈牙利人 E)法國(guó)人 2第一個(gè)給計(jì)算機(jī)寫(xiě)程序的人是 ( )。 A)Alan MathisonTuring B)Ada Lovelace C)John von Neumann D)John Mc-Carthy E)Edsger Wybe Dijkstra 3十進(jìn)制數(shù) 2003 等值于二進(jìn)制數(shù) ( )。 A)0100000111 B)10000011 C)110000111 D)11111010011 E)1111010011 4假設(shè) A=true,B=false,C=true,D=true，邏輯運(yùn)算表達(dá)式 ABCD 的值是 ( )。 A)true B)false C)0 D)1 E)NULL 5一個(gè)高度為 h 的二叉樹(shù)最小 元素?cái)?shù)目是 ( )。 A)2h+l B)h C)2h-1 D)2h E)2h-1 6已知隊(duì)列 (13， 2， 11， 34， 4l， 77， 5， 7， 18， 26， 15)，第一個(gè)進(jìn)入隊(duì)列的元素是 13，則第五個(gè)出隊(duì)列的元素是 ( )。 A)5 B)41 C)77 D)13 E)18 北京清北學(xué)堂 報(bào)名咨詢(xún)熱線： 400-699-3290 北京清北學(xué)堂 報(bào)名咨詢(xún)熱線： 400-699-3290 7下面一段程序是用 ( )語(yǔ)言書(shū)寫(xiě)的。 int funcl (int n) int i， sum=0； for (i = 1； i =n； i+ sum + = i*i； return sum； A)FORTRAN B)PASCAL C)C D)PROLOG E)BASIC 8設(shè)全集 E=1， 2， 3， 4， 5，集合 A=1,4， B=l， 2, 5， C=2， 4)，則集合 (AB) C 為 ( )。 A) 空集 B) 1 C) 3， 5 D) 1， 5 E) 1， 3， 5 9表達(dá)式 (1+34)*5-56 7 的后綴表達(dá)式為 ( ) A)1+34*5-56 7 B)-*+1 345 567 C)1 34+5*56 7 - D)1 345*+56 7 - E)1 34+5 567-* 10下列計(jì)算機(jī)設(shè)備，既是輸入設(shè)備，又是輸出設(shè)備的是 ( )。 A)鍵盤(pán) B)觸摸屏 C)掃描儀 D)投影儀 E)數(shù)字化儀 二、不定項(xiàng)選擇題 (共 10 題，每題 1.5 分，共計(jì) 15 分。多選或少選均不得分 )。 11下列分辨率的顯示器所顯示出的圖像，最清晰的是 ( )。 A)800*600 B)1024*768 C)640*480 D)1280*1024 E)800*1000 12下列說(shuō)法中，哪個(gè) (些 )是錯(cuò)誤的 ( )。 A)程序是指令的序列，它有三種結(jié)構(gòu)：順序、分支和循環(huán)。 B)數(shù)據(jù)總線決定了中央處理器 CPU 所能訪問(wèn)的最大內(nèi)存空間的大小。 C)中央處理器 CPU 內(nèi)部有寄存器組，用來(lái)存儲(chǔ)數(shù)據(jù)。 D)不同廠家生產(chǎn)的 CPU 所能處理的指令集是相同的。 E)數(shù)據(jù)傳輸過(guò)程中可能會(huì)出錯(cuò)，奇偶校驗(yàn)法可以檢測(cè)出數(shù)據(jù)中那一位在傳輸中出了差錯(cuò)。 13 CPU 訪問(wèn)內(nèi)存的速度比訪問(wèn)下列哪個(gè) (些 )存儲(chǔ)設(shè)備要慢 ( )。 A)寄存器 B)硬盤(pán) C)軟盤(pán) D)高速緩存 E)光盤(pán) 14下列電子郵件地址，哪個(gè) (些 )是正確的 ( )。 北京清北學(xué)堂 報(bào)名咨詢(xún)熱線： 400-699-3290 北京清北學(xué)堂 報(bào)名咨詢(xún)熱線： 400-699-3290 A) B).jp C)162.105.111. 22 D) E) 15數(shù)字圖像文件可以用下列哪個(gè) (些 )軟件來(lái)編輯 ( )。 A)畫(huà)筆 (Paintbrush) B)記事簿 (Notepad) C)Photoshop D)WmRAR E)MidiSoft 16下列哪個(gè) (些 )軟件不是操作系 統(tǒng)軟件的名字 ( )。 A)Windows XP B)DOS C)Linux D)OS 2 E)Arch Info 17下列哪個(gè) (些 )不是個(gè)人計(jì)算機(jī)的硬件組成部分 ( )。 A)主板 B)虛擬內(nèi)存 C)電源 D)硬盤(pán) E)總線 18運(yùn)算式 (2008)10-(3723)8的結(jié)果是 ( )。 A)(-1715)10 B)(5)10 C)(5)16 D)(101)2 E)(3263)8 19已知元素 (8， 25， 14， 87， 5l， 90， 6， 19， 20)，問(wèn)這些元素以怎 樣的順序進(jìn)入棧，才能使出棧的順序滿(mǎn)足： 8 在 5l 前面； 90 在 87 后面； 20 在 14 后面； 25 在 6 前面； 19 在 90 后面。 ( ) A)20， 6， 8， 51， 90， 25， 14， 19， 87 B)51， 6， 19， 20， 14， 8， 87， 90， 25 C)19， 20， 90， 7， 6， 25， 5l， 14， 87 D)6， 25， 51， 8， 20， 19， 90， 87， 14 E)25， 6， 8， 51， 87， 90， 19， 14， 20 20假設(shè)我們用 d=(a1， a2， a5)，表示無(wú)向圖 G 的 5 個(gè)頂 點(diǎn)的度數(shù)，下面給出的哪 (些 )組 d 值合理的 ( )。 A)5， 4， 4， 3， 1 B)4， 2， 2， 1， 1 C)3， 3， 3， 2， 2 D)5， 4， 3， 2， l E)2， 2， 2， 2， 2) 三問(wèn)題求解 (共 2 題，每題 5 分，共計(jì) 10 分 ) 1無(wú)向圖 G 有 16 條邊，有 3 個(gè) 4 度頂點(diǎn)、 4 個(gè) 3 度頂點(diǎn)，其余頂點(diǎn)的度均小于 3，則 G 至少 個(gè)頂點(diǎn)。 2某年級(jí)學(xué)生共選修 6 門(mén)課程，期末考試前，必須提前將這 6 門(mén)課程考完，每人每天只在下午至多考一門(mén)課程，設(shè) 6 門(mén)課程分別為 c1， c2， c3， c4， c5， c6，S(ci)為學(xué)習(xí) ci的學(xué)生集合。已知 S(ci)S(c 6)? ， i=l， 2， 5，北京清北學(xué)堂 報(bào)名咨詢(xún)熱線： 400-699-3290 北京清北學(xué)堂 報(bào)名咨詢(xún)熱線： 400-699-3290 S(ci)S(c i+1)? ， i=1， 2， 3， 4， S(c5)S(c 1)? ，問(wèn)至少安排 天才能考完這 6 門(mén)課程。 四閱讀程序 (共 4 題，每題 8 分，共計(jì) 32 分 ) 1 program Programl； var a， b， c， d， sum： 1ongint； begin read (a， b， c， d)； a ： = a mod 23； b ： = b mod 28； c ： = c mod 33 ； sum ： = a* 5544 + b * 14421 + c*1288 - d； sum ： = sum + 21252； sum ： = sum mod 21252； if (sum = 0) then sum ： = 21252； writeln(sum)； end 輸入： 283 102 23 320 輸出： 2 program Program2； const u： array1 4 of integer = (0， 5， 3， 1)； v： array1 4 0f integer = (0， 7， 6， 5)； var a， b， c， d， e， f， x， y， z： integer； begin read (a， b， c， d， e， f)； z ： = f + e + d + (c+3) div 4； y ： = 5 * d + u c mod 4 ； if (by) then begin z ： = z+ (b-y+8) div 9； x ： = (b-y+8) div 9 * 9- (b-y) * 4+11*e+Vc mod 4； end else x ： = (y-b) *4+11*e+vc mod 4； if (ax) then z ： = z + (a-x+35) div 36； writeln(z)； end 輸入； 4 7 9 20 56 47 輸出： 3 program Programg3； var m， n： integer； Mark ： boo1ean； function test (m， N ： integer)： integer； 北京清北學(xué)堂 報(bào)名咨詢(xún)熱線： 400-699-3290 北京清北學(xué)堂 報(bào)名咨詢(xún)熱線： 400-699-3290 var i， p ： integer； flag ： boolean； begin m ： = m - 1； i ： = 0； flag ： = False； for p： = 2*N downto (N+1) do begin i： = (i+m) mod p； if ( i0) then am： = pi-pi-1 else am： = pi； m： = m+1： while (m1) and (arn-1=0) do begin m ； = m-1； bm ： = l； end； if (m0) then wi： =bm-1 else wi： =b0； 北京清北學(xué)堂 報(bào)名咨詢(xún)熱線： 400-699-3290 北京清北學(xué)堂 報(bào)名咨詢(xún)熱線： 400-699-3290 am-1 ： = am-1-1； for j ： = 0 to m-1 do bj ； = bj+1； while (m1) and (am-1=0) do begin m ： = m-1； bm ： =1； end； end； for i ： = 0 to n-1 do begin write(wi)； write( )； end； writeln( )； end 輸入： 9 4 6 6 6 6 8 9 9 9 輸出： 五完善程序 (共 2 題，第 1 題每空 3 分；第 2 題每空 2 分。共計(jì) 28 分 ) 1翻硬幣 題目描述： 一摞硬幣共有 m 枚，每一枚都是正面朝上。取下最上面的一枚硬幣，將它翻面后放回原處。然后取下最上面的 2 枚硬幣，將他們一 起翻面后再放回原處。再取 3 枚，取 4 枚 直至 m 枚。然后再?gòu)倪@摞硬幣最上面的一枚開(kāi)始，重復(fù)剛才的做法。這樣一直做下去，直到這摞硬幣中的每一枚又都是正面朝上為止。例如，m 為 1 時(shí)，翻兩次即可。 輸 入：僅有的一個(gè)數(shù)字是這摞硬幣的枚數(shù) m， 0 m 1000。 輸 出：為了使這摞硬幣中的每一枚又都是正面朝上所必需翻的次數(shù)。 輸入樣例： 30 輸出樣例： 899 程 序： program Programl； var m： integer； function solve (m： integer) ： integer； var i， t， d： integer； flag ： boolean； 北京清北學(xué)堂 報(bào)名咨詢(xún)熱線： 400-699-3290 北京清北學(xué)堂 報(bào)名咨詢(xún)熱線： 400-699-3290 begin if (m = 1) then solve ： = (1) else begin d ： = 2*m+1； t ： =2； I ： =1； flag ： =False； repeat if (t=1) then begin solve： = (2) ； flag： =True； end else if ( (3) ) then begin so1ve： = I * m-1； flag ： =True end else t ： = (4) I ： = i+1； until flag； end end； begin read (m)； if ( (5) ) and (m 1000) then writeln ( (6) )； end. 2 OIM 地形 題目描述： 二維離散世界有一種地形叫 OIM（ OI Mountain）。這種山的坡度只能上升（ /）或下降（ ），而且兩邊的山腳都與地平線等高，山上所有地方都 不低于地平線。例如： / / / / 是一座 OIM：而 / 不是。 / 這個(gè)世界的地理學(xué)家們?yōu)榱朔奖阌涗洠o OIM 所有可能的形狀用正整數(shù)編好號(hào)，而且每個(gè)正整數(shù)恰好對(duì)應(yīng)一種山形。他們規(guī)定，若兩座山的寬度不同，則較寬的編號(hào)較大；若寬度相同，則比較從左邊開(kāi)始第 1 個(gè)坡度不同的地方，坡度上升的編號(hào)較大。以下三座 OIM 的編號(hào)由小到大遞增： / / / / / / / / / / 。顯然 /的編號(hào)為 1。但是地理學(xué) 家在整理記錄時(shí)發(fā)覺(jué)，查找編號(hào)與山形的對(duì)應(yīng)關(guān)系不是很方便。他們希望能快速地從編號(hào)得到山的形狀。你自告奮勇答應(yīng)給他們寫(xiě)一個(gè)程序，輸入編號(hào)，能馬上輸出山形。 輸 入： 北京清北學(xué)堂 報(bào)名咨詢(xún)熱線： 400-699-3290 北京清北學(xué)堂 報(bào)名咨詢(xún)熱線： 400-699-3290 一個(gè)編號(hào) (編號(hào)大小不超過(guò) 600， 000， 000)， 輸 出： 輸入編號(hào)所對(duì)應(yīng)的山形， l 座山所占行數(shù)恰為它的高度，即山頂上不能有多余空行。 輸入樣例： 15 輸出樣例： / / / / 程 序： program Programg2； const L ： integer=19； SZ ： integer=50； Up ： char= ； DN ： char； Var i， nth， x， y， h， e， f： integer； m ： array0 1， 0 38， 0 190f integer； pic： array0 49， 0 49of char； procedure init； var k， s， a， b， c： integer； begin for a ： = 0 to 1 do for b ： =0 to 2*L do for c： =0 to L do ma， b， c： =0； m0， 0， 0： =1； for k： =0 to 2*L-1 do begin for s： =1 to L do begin m0， k+1， s： =m0， k， s+1+m1， k， s+1； m1， k+1， s： = (1) ； end； m0， k+1， 0： =m0， k， 1+m1， k， 1； end； end： procedure draw(k， s， nth： integer)； begin 北京清北學(xué)堂 報(bào)名咨詢(xún)熱線： 400-699-3290 北京清北學(xué)堂 報(bào)名咨詢(xún)熱線： 400-699-3290 if(k=0) then exit； if (nth-m1， k， s)=0)then begin nth： = nth-m1， k， s； if (y h) then (2) ； picy， x： = UP； y： =y+1； x： =x+l； draw( (3) )； end else begin y： =y-1； picy， x： =DN； x： =x+1； draw(k-1， s-l，nth)； end； end： begin init； read(nth)； for e： = 0 to SZ-1 do for f： =0 to SZ-l do pice， f： = ； x： =0； y： =0； h： =0； i： =0； while(nth-m0， 2*i， 0)=0)do begin nth： =nth-m0， 2*i， 0； (4) ； end； draw( (5) )； for i ： = h downto 0 do begin for e ： =0 to x-1 do write(pici， e)； writeln( )； end； end. 北京清