全國青少年信息學(計算機)奧林匹克競賽初中組初賽試題及答案

1、第十二屆全國青少年信息學奧林匹克聯(lián)賽初賽試題 普及組 Pascal 語言 二小時完成 ） 由 OIF 整理收集 全部試題答案均要求寫在答卷紙上，寫在試卷紙上一律無效 單項選擇題 （共 20題，每題 1.5 分，共計 30分。每題有且僅有一個正確答案. 。） 1.在下面各世界頂級的獎項中，為計算機科學與技術(shù)領(lǐng)域做出杰出貢獻的科學家設(shè)立的獎項是 （ ）。 A. 沃爾夫獎 獎 D. 圖靈獎 B. 諾貝爾獎 C. 菲爾茲 at 2.在下列各軟件中，不屬于NOI虎賽（復(fù)賽） 推薦使用的語言環(huán)境有（ ）。 A. gcc/g+ B. Turbo Pascal C. RHIDE D. free pascal

2、3. 以下斷電之后仍能保存數(shù)據(jù)的有（ ）。 A. 寄存器 緩存 B. ROM C. RAM D. 高速 4Linux 是一種（ ）。 A. 繪圖軟件 B. 程序設(shè)計語言 C. 操作系統(tǒng) D. 網(wǎng)絡(luò)瀏覽器 A. 硬盤 B. 中央處理器 C. 高級程序語言 D. 核心寄存 器 6. 在計算機中，防火墻的作用是（ ）。 A. 防止火災(zāi)蔓延 B. 防止網(wǎng)絡(luò)攻擊 C. 防止計算機死機 D. 防止使用者誤刪除數(shù)據(jù) 7. 在下列關(guān)于計算機語言的說法中，不正確的是（ ）。 A. Pascal和C都是編譯執(zhí)行的高級語言 B. 高級語言程序比匯編語言程序更容易從一種計算機移植到另一種計算機上 C. C+是歷史上的

3、第一個支持面向?qū)ο蟮挠嬎銠C語言 D. 與匯編語言相比，高級語言程序更容易閱讀 8. 在下列關(guān)于計算機算法的說法中，不正確的是（ ）。 A. 一個正確的算法至少要有一個輸入 B. 算法的改進，在很大程度上推動了計算機科學與技術(shù)的進步 C. 判斷一個算法的好壞的主要標準是算法的時間復(fù)雜性與空間復(fù)雜性 D. 目前仍然存在許多涉及到國計民生的重大課題，還沒有找到能夠在計算機上實施的有效算法 9. 在下列各種排序算法中，不是以“比較”作為主要操作的算法是（ ）。 A. 選擇排序 B. 冒泡排序 C. 插入排 序 D. 基數(shù)排序15. 與十進制數(shù) 1770 對應(yīng)的八進制數(shù)是（ ） 10在編程時（使用任一種

4、高級語言，不一定是 Pascal ），如果需要從磁盤文件中輸入一個很大的 二 維數(shù)組（例如 1000*1000 的 double 型數(shù)組），按行讀（即外層循環(huán)是關(guān)于行的）與按列讀（即外層 循環(huán)是關(guān)于列的）相比，在輸入效率上（ ）。 A. 沒有區(qū)別 B. 按行讀的方式要高一些 C. 按列讀的方式要高一些 D. 取決于數(shù)組的存儲方式。 11在 Pascal 語言中，表達式（21 xor 2） 的值是（ 12. 在Pascal語言中，判斷a不等于0且 b不等于0的正確的條件表達式是( ) A. not a=0 or not b=0 B. not(a=0)and(b=0) C. not(a=0 and

5、 b=0) D. (a0)and (b0) 13. 某個車站呈狹長形，寬度只能容下一臺車，并且只有一個出入口。已知某時刻該車站狀態(tài)為空，從 這 一時刻開始的出入記錄為“：進，出，進，進，進，出，出，進，進，進，出, 出”。假設(shè)車輛入站的 順 序為1, 2, 3,貝悴輛出站的順序為() A. 1, 2, 3, 4, 5 B. 1, 2, 4, 5, 7 C. 1, 4, 3, 7, 6 D. 1, 4, 3, 7, 2 14. 高度為n的均衡的二叉樹是指：如果去掉葉結(jié)點及相應(yīng)的樹枝，它應(yīng)該是高度為n-1的滿二叉樹。 在這里,樹高等于葉結(jié)點的最大深度,根結(jié)點的深度為 0 ,如果某個均衡的二叉樹共有

6、 2381 個結(jié)點, 貝該樹的樹高為（ ）。 A. 10 B. 11 C. 12 D. 13 A. 441 B. 42 C.23 D.24 17. 設(shè) A=B=D=true，C=false ，以下邏輯運算表達式值為真的有（ 20. 已知 6 個結(jié)點的二叉樹的先根遍歷是 1 2 3 4 5 6 （數(shù)字為結(jié)點的編號，以下同），后根遍歷是A. 3350 B. 3351 C. 3352 D. 3540 16將 5個數(shù)的序列排序，不論原先的順序如何， 最少都可以通過 （ 小到大的排序。 ）次比較，完成從 A. 6 B. 7 8 D. 9 C. ）。 A. ( ? AA B)V(CAD) B. ? C.

7、?AA(BVCVD) D. (AABAC)V ? D 18. (2010) 16 + (32) 8 的結(jié)果是( A. (8234) 10 C. (20056) 8 19. 設(shè)棧S的初始狀態(tài)為空，元素a, b, c, d, e ( )。 A. a, b, c, e, d C. a, e, c, b, d )。 B. (202B) 16 D. (1 000000001 1 0) 2 依次入棧，以下出棧序列不可能出現(xiàn)的有 B. b, c, a, e, d D. d, c, e, b, a 3 2 5 6 4 1 ，則該二叉樹的可能的中根遍歷是（ ） begin for i:=0 to 3 do A.

8、 3 2 1 4 6 5 C. 2 1 3 5 4 6 二問題求解（共 2題，每題 5分，共計 10分） 1（尋找假幣） 現(xiàn)有 80枚硬幣，其中有一枚是假幣，其重量稍輕，所有真幣的重量都相同，如果 使 用不帶砝碼的天平稱重，最少需要稱幾次，就可以找出假幣？你還要指出第 1 次的稱重方法。請寫出 你的 結(jié)果： _ 。_ 2（取石子游戲） 現(xiàn)有 5堆石子, 石子數(shù)依次為 3，5，7，19，50，甲乙兩人輪流從任一堆中 任取 （每次只能取自一堆，不能不?。? 取最后一顆石子的一方獲勝。甲先取，問甲有沒有獲勝策略（即無 論 乙怎樣取，甲只要不失誤，都能獲勝）？如果有，甲第一步應(yīng)該在哪一堆里取多少？請寫

9、出你的結(jié) 果： 三閱讀程序?qū)懡Y(jié)果（共 4題，每題 8分，共計 32分） 1. Program ex301; var u:array0.3 of integer; i,a,b,x,y:integer; y:=10; read(ui); a:=(u0+u1+u2+u3) div 7; B. 3 2 1 5 4 6 D. 2 3 1 4 6 5 begin for i:=0 to 4 do b:=u0 div (u1-u2) div u3); x:=(u0+a+2)-u(u3+3) mod 4; if (x10) then y:=y+(b*100-u3) div (uu0 mod 3*5) else

10、 y:=y+20+(b*100-u3) div (uu0 mod 3*5); writeln (x,y); end. * 注：本例中，給定的輸入數(shù)據(jù)可以避免分母為 0或下標越界。 輸入：9 3 9 4 輸出： _ 2. Program ex302; const m:array0.4 of integer=(2,3,5,7,13); var i,j:integer; t: longint;begin begin t:=1; for j:=1 to mi-1 do t:=t*2; t:=(t*2-1)*t; write (t, ); end; writeln; end. 輸出: _ 3. Prog

11、ram ex303; Const NN=7; Type Arr1=array0.30 of char; var s:arr1; k,p:integer; Function fun(s:arr1; a:char;n:integer):integer; var j:integer; j:=n; while (a0) do dec(j); fun:=j; end; begin for k:=1 to NN do sk:=chr(ord(A)+2*k+1); k:=fun(s,M,NN); writeln(k); end. 輸出： _ 4. program ex304; var x,x2:longin

12、t; procedure digit(n,m:longint); var n2:integer; begin if(m0) then begin n2:=n mod 10; write(n2:2); if(m1) then digit(n div 10,m div 10); n2:=n mod 10; 312 write(n2:2); end; end; begin writeln(Input a number:); readln(x); x2:=1; while(x2x) do x2:=x2*10; x2:=x2 div 10; digit(x,x2); writeln; end. 輸入：9

13、734526 輸出： _ 四完善程序 （ 前 4 空，每空 2.5 分，后 6空，每空 3分，共 28分） 1.（全排列）下面程序的功能是利用遞歸方法生成從1到n（n10）的n個數(shù)的全部可能的排列（不一定 按升序輸出。）例如，輸入 3，則應(yīng)該輸出（每行輸出 5個排列）： 123 132 213231 321 程序： Program ex401; Var i,n,k:integer; a:array1.10 of integer; count:longint; 變量 count 記錄不同排列的個數(shù)，這里用于控制換行 Procedure perm(k:integer); var j,p,t:int

14、eger; begin if then begin inc(count); for p:=1 to k do write(ap:1); write( ); if ( ) then writeln; exit; end; for j:=k to n do begin t:=ak; ak:=aj; aj:=t; ; t:=ak; ; end end; begin writeln(Entry n:); read(n); count:=0; for i:=1 to n do ai:=i; ; end. 2. 由鍵盤輸入一個奇數(shù)P (P100,000,000)，其個位數(shù)字不是 5,求一個整數(shù)S,使PX

15、S = 1111.1 (在給定的條件下，解S必存在)。要求在屏幕上依次輸出以下結(jié)果： (1)S 的全部數(shù)字。除最后一行外，每行輸出50位數(shù)字。 (2) 乘積的數(shù)字位數(shù)。 例 1：輸 入p=13,由于13*8547=111111,則應(yīng)輸出(1)8547,(2)6例2：輸入p=147,則輸出結(jié)果應(yīng)為 ( 1 ) 755857898715041572184429327286470143613 (2) 42，即等式的右端有 42個 1。 程序： program ex402; var p,a,b,c,t,n：longint; begin while (true) do begin readln(p);

16、if (p mod 20)and(p mod 50) then ; 如果輸入的數(shù)符合要求，結(jié)束循環(huán) end; a:=0; n:=0; while (ap) do begin a:=a*10+1; inc(n); end; t:=0; repeat b:=a div p; write(b:1); inc(t); if ( ) then writeln; c:= ; a:= inc(n); until c=0; dec(n); writeln; writeln(n=, writeln (Input 9:); p, the last digit is 1 or 3 or 7 or ); end. 普

17、及組（ Pascal 語言）參考答案與評分標準 由 OIF 整理收集 、單項選擇題：（每題 1.5 分） 1. D 2. B 3. B 4. C 5 B 6.B 7. C 8. A 9. D 10. D 11. C 12. D 13. C 14. B 15. C 16. B 17. B 18. A 19. C 20. B 、問題求解：（每題 5 分） 1 4 次 （1 分） ， 第一步：分成 3 組： 27， 27，26，將前 2 組放到天平上（ 4 分）。 2 有獲勝策略 （1 分），第 1 次在第 5 堆中取 32 顆石子 （4 分），。 三、閱讀程序?qū)懡Y(jié)果 1. 10 ，10 （對 1 個數(shù)給 4 分，無逗號扣 1 分