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

北京清北學(xué)堂 報名咨詢熱線： 400-699-3290 北京清北學(xué)堂 報名咨詢熱線： 400-699-3290 更多競賽真題免費下載 見北京清北學(xué)堂官方網(wǎng)站 學(xué)習(xí)資源：自主招生 學(xué)科競賽 高考等資源 第九屆全國青少年信息學(xué)奧林匹克聯(lián)賽初賽試題 (提高組 PASCAL 語言二小時完成 ) 全部試題答案均要求寫在答卷紙上，寫在試卷紙上一律無效 ) 一、單項選擇題 (共 10 題，每題 1.5 分，共計 15 分。每題有且僅有 -個正確答案 )。 1圖靈 (Alan Turing)是 ( )。 A)美國人 B)英國人 C)德國人 D)匈牙利人 E)法國人 2第一個給計算機寫程序的人是 ( )。 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，邏輯運算表達(dá)式 ABCD 的值是 ( )。 A)true B)false C)0 D)1 E)NULL 5一個高度為 h 的二叉樹最小 元素數(shù)目是 ( )。 A)2h+l B)h C)2h-1 D)2h E)2h-1 6已知隊列 (13， 2， 11， 34， 4l， 77， 5， 7， 18， 26， 15)，第一個進(jìn)入隊列的元素是 13，則第五個出隊列的元素是 ( )。 A)5 B)41 C)77 D)13 E)18 北京清北學(xué)堂 報名咨詢熱線： 400-699-3290 北京清北學(xué)堂 報名咨詢熱線： 400-699-3290 7下面一段程序是用 ( )語言書寫的。 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下列計算機設(shè)備，既是輸入設(shè)備，又是輸出設(shè)備的是 ( )。 A)鍵盤 B)觸摸屏 C)掃描儀 D)投影儀 E)數(shù)字化儀 二、不定項選擇題 (共 10 題，每題 1.5 分，共計 15 分。多選或少選均不得分 )。 11下列分辨率的顯示器所顯示出的圖像，最清晰的是 ( )。 A)800*600 B)1024*768 C)640*480 D)1280*1024 E)800*1000 12下列說法中，哪個 (些 )是錯誤的 ( )。 A)程序是指令的序列，它有三種結(jié)構(gòu)：順序、分支和循環(huán)。 B)數(shù)據(jù)總線決定了中央處理器 CPU 所能訪問的最大內(nèi)存空間的大小。 C)中央處理器 CPU 內(nèi)部有寄存器組，用來存儲數(shù)據(jù)。 D)不同廠家生產(chǎn)的 CPU 所能處理的指令集是相同的。 E)數(shù)據(jù)傳輸過程中可能會出錯，奇偶校驗法可以檢測出數(shù)據(jù)中那一位在傳輸中出了差錯。 13 CPU 訪問內(nèi)存的速度比訪問下列哪個 (些 )存儲設(shè)備要慢 ( )。 A)寄存器 B)硬盤 C)軟盤 D)高速緩存 E)光盤 14下列電子郵件地址，哪個 (些 )是正確的 ( )。 北京清北學(xué)堂 報名咨詢熱線： 400-699-3290 北京清北學(xué)堂 報名咨詢熱線： 400-699-3290 A) B).jp C)162.105.111. 22 D) E) 15數(shù)字圖像文件可以用下列哪個 (些 )軟件來編輯 ( )。 A)畫筆 (Paintbrush) B)記事簿 (Notepad) C)Photoshop D)WmRAR E)MidiSoft 16下列哪個 (些 )軟件不是操作系 統(tǒng)軟件的名字 ( )。 A)Windows XP B)DOS C)Linux D)OS 2 E)Arch Info 17下列哪個 (些 )不是個人計算機的硬件組成部分 ( )。 A)主板 B)虛擬內(nèi)存 C)電源 D)硬盤 E)總線 18運算式 (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)，問這些元素以怎 樣的順序進(jì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)，表示無向圖 G 的 5 個頂 點的度數(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) 三問題求解 (共 2 題，每題 5 分，共計 10 分 ) 1無向圖 G 有 16 條邊，有 3 個 4 度頂點、 4 個 3 度頂點，其余頂點的度均小于 3，則 G 至少 個頂點。 2某年級學(xué)生共選修 6 門課程，期末考試前，必須提前將這 6 門課程考完，每人每天只在下午至多考一門課程，設(shè) 6 門課程分別為 c1， c2， c3， c4， c5， c6，S(ci)為學(xué)習(xí) ci的學(xué)生集合。已知 S(ci)S(c 6)? ， i=l， 2， 5，北京清北學(xué)堂 報名咨詢熱線： 400-699-3290 北京清北學(xué)堂 報名咨詢熱線： 400-699-3290 S(ci)S(c i+1)? ， i=1， 2， 3， 4， S(c5)S(c 1)? ，問至少安排 天才能考完這 6 門課程。 四閱讀程序 (共 4 題，每題 8 分，共計 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é)堂 報名咨詢熱線： 400-699-3290 北京清北學(xué)堂 報名咨詢熱線： 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é)堂 報名咨詢熱線： 400-699-3290 北京清北學(xué)堂 報名咨詢熱線： 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 分。共計 28 分 ) 1翻硬幣 題目描述： 一摞硬幣共有 m 枚，每一枚都是正面朝上。取下最上面的一枚硬幣，將它翻面后放回原處。然后取下最上面的 2 枚硬幣，將他們一 起翻面后再放回原處。再取 3 枚，取 4 枚 直至 m 枚。然后再從這摞硬幣最上面的一枚開始，重復(fù)剛才的做法。這樣一直做下去，直到這摞硬幣中的每一枚又都是正面朝上為止。例如，m 為 1 時，翻兩次即可。 輸 入：僅有的一個數(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é)堂 報名咨詢熱線： 400-699-3290 北京清北學(xué)堂 報名咨詢熱線： 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：而 / 不是。 / 這個世界的地理學(xué)家們?yōu)榱朔奖阌涗?，給 OIM 所有可能的形狀用正整數(shù)編好號，而且每個正整數(shù)恰好對應(yīng)一種山形。他們規(guī)定，若兩座山的寬度不同，則較寬的編號較大；若寬度相同，則比較從左邊開始第 1 個坡度不同的地方，坡度上升的編號較大。以下三座 OIM 的編號由小到大遞增： / / / / / / / / / / 。顯然 /的編號為 1。但是地理學(xué) 家在整理記錄時發(fā)覺，查找編號與山形的對應(yīng)關(guān)系不是很方便。他們希望能快速地從編號得到山的形狀。你自告奮勇答應(yīng)給他們寫一個程序，輸入編號，能馬上輸出山形。 輸 入： 北京清北學(xué)堂 報名咨詢熱線： 400-699-3290 北京清北學(xué)堂 報名咨詢熱線： 400-699-3290 一個編號 (編號大小不超過 600， 000， 000)， 輸 出： 輸入編號所對應(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é)堂 報名咨詢熱線： 400-699-3290 北京清北學(xué)堂 報名咨詢熱線： 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. 北京清