第十二屆全國(guó)青少年信息學(xué)奧林匹克聯(lián)賽普及組初賽試題

1、第十二屆全國(guó)青少年信息學(xué)奧林匹克聯(lián)賽初賽試題（  普及組  Pascal 語(yǔ)言    二小時(shí)完成  ）由OIF整理收集    全部試題答案均要求寫(xiě)在答卷紙上，寫(xiě)在試卷紙上一律無(wú)效          一、  單項(xiàng)選擇題  （共 20 題，每題 1.5 分，共計(jì) 30 分。每題有且僅有一個(gè)正確答案.）。由OIF收集  1.在下面各世界頂級(jí)的獎(jiǎng)項(xiàng)中，為計(jì)算機(jī)科學(xué)與技術(shù)領(lǐng)域做出杰出貢獻(xiàn)

2、的科學(xué)家設(shè)立的獎(jiǎng)項(xiàng)是（            ）。    A. 沃爾夫獎(jiǎng)         B.    諾貝爾獎(jiǎng)         C. 菲爾茲獎(jiǎng)        D. 圖靈獎(jiǎng)  2. 在下列各軟件中，不屬于 NOI

3、P 競(jìng)賽（復(fù)賽）推薦使用的語(yǔ)言環(huán)境有（         ）。 A. gcc/g+                     B. Turbo Pascal C. RHIDE           

4、;            D. free pascal  3. 以下斷電之后仍能保存數(shù)據(jù)的有（      ）。 A. 寄存器         B. ROM          C. RAM    

5、60;    D. 高速緩存  4Linux 是一種(     )。 A. 繪圖軟件       B. 程序設(shè)計(jì)語(yǔ)言  C. 操作系統(tǒng)           D. 網(wǎng)絡(luò)瀏覽器  5. CPU 是(   )的簡(jiǎn)稱(chēng)。 A. 硬盤(pán)        &

6、#160;  B. 中央處理器       C. 高級(jí)程序語(yǔ)言   D. 核心寄存器  6.  在計(jì)算機(jī)中，防火墻的作用是（       ）。 A. 防止火災(zāi)蔓延               B.防止網(wǎng)絡(luò)攻擊 C. 防止計(jì)算機(jī)死機(jī)  

7、60;          D. 防止使用者誤刪除數(shù)據(jù)由OIF收集  7. 在下列關(guān)于計(jì)算機(jī)語(yǔ)言的說(shuō)法中，不正確的是（       ）。 A. Pascal和C都是編譯執(zhí)行的高級(jí)語(yǔ)言 B. 高級(jí)語(yǔ)言程序比匯編語(yǔ)言程序更容易從一種計(jì)算機(jī)移植到另一種計(jì)算機(jī)上 C. C+是歷史上的第一個(gè)支持面向?qū)ο蟮挠?jì)算機(jī)語(yǔ)言 D. 與匯編語(yǔ)言相比，高級(jí)語(yǔ)言程序更容易閱讀  8. 在下列關(guān)于

8、計(jì)算機(jī)算法的說(shuō)法中，不正確的是（       ）。 A. 一個(gè)正確的算法至少要有一個(gè)輸入 B. 算法的改進(jìn)，在很大程度上推動(dòng)了計(jì)算機(jī)科學(xué)與技術(shù)的進(jìn)步 C. 判斷一個(gè)算法的好壞的主要標(biāo)準(zhǔn)是算法的時(shí)間復(fù)雜性與空間復(fù)雜性D. 目前仍然存在許多涉及到國(guó)計(jì)民生的重大課題，還沒(méi)有找到能夠在計(jì)算機(jī)上實(shí)施的有效算法  9. 在下列各種排序算法中，不是以“比較”作為主要操作的算法是（        ）。 A. 選擇排序

9、60;        B. 冒泡排序           C. 插入排序           D. 基數(shù)排序  10在編程時(shí)（使用任一種高級(jí)語(yǔ)言，不一定是  Pascal），如果需要從磁盤(pán)文件中輸入一個(gè)很大的二 維數(shù)組（例如 1000*1000 的 double 型數(shù)組），按行讀（即外層循環(huán)是關(guān)于行的）與按列讀（即外層

10、 循環(huán)是關(guān)于列的）相比，在輸入效率上（ ）。 A. 沒(méi)有區(qū)別                  B. 按行讀的方式要高一些 C. 按列讀的方式要高一些        D. 取決于數(shù)組的存儲(chǔ)方式。由OIF收集  11在 Pascal 語(yǔ)言中，表達(dá)式 (21 xor 2)的值是（     &#

11、160;    ）   A. 441        B. 42         C.23        D.24  12在 Pascal 語(yǔ)言中，判斷 a 不等于 0 且 b 不等于 0 的正確的條件表達(dá)式是（         ）A. not a=0

12、 or not b=0         B. not(a=0)and(b=0) C. not(a=0 and b=0) D. (a<>0)and (b<>0)  13某個(gè)車(chē)站呈狹長(zhǎng)形，寬度只能容下一臺(tái)車(chē)，并且只有一個(gè)出入口。已知某時(shí)刻該車(chē)站狀態(tài)為空，從 這一時(shí)刻開(kāi)始的出入記錄為：“進(jìn)，出，進(jìn)，進(jìn)，進(jìn)，出，出，進(jìn)，進(jìn)，進(jìn)，出,出”。假設(shè)車(chē)輛入站的 順序?yàn)?1，2，3，則車(chē)輛出站的順序?yàn)椋?）。 A. 1, 2, 3, 4, 5   &

13、#160;       B. 1, 2, 4, 5, 7 C. 1, 4, 3, 7, 6           D. 1, 4, 3, 7, 2  14高度為 n 的均衡的二叉樹(shù)是指：如果去掉葉結(jié)點(diǎn)及相應(yīng)的樹(shù)枝，它應(yīng)該是高度為 n-1 的滿二叉樹(shù)。 在這里，樹(shù)高等于葉結(jié)點(diǎn)的最大深度，根結(jié)點(diǎn)的深度為 0，如果某個(gè)均衡的二叉樹(shù)共有 2381 個(gè)結(jié)點(diǎn)， 則該樹(shù)的樹(shù)高為（    ）。&

14、#160;A. 10         B. 11              C. 12              D. 13  15. 與十進(jìn)制數(shù) 1770 對(duì)應(yīng)的八進(jìn)制數(shù)是（      ）。 A.

15、3350         B. 3351             C. 3352      D. 3540  16將 5 個(gè)數(shù)的序列排序，不論原先的順序如何，最少都可以通過(guò)（        ）次比較，完成從小到大的排序。 A. 6  

16、60;          B. 7              C. 8            D. 9    17. 設(shè)A=B=D=true，C=false，以下邏輯運(yùn)算表達(dá)式值為真的有（     &

17、#160;    ）。 A. (¬ AB)(CD)            B.¬ (ABD)C)由OIF收集 C.   ¬ A(BCD)            D. (ABC) ¬ D  18.  (2010)16 + (32)8的結(jié)果是（  

18、60;     ）。 A. (8234)10                     B. (202B)16   C. (20056)8                  

19、; D. (100000000110)2  19. 設(shè)棧S的初始狀態(tài)為空，元素a, b, c, d, e 依次入棧，以下出棧序列不可能出現(xiàn)的有（            ）。 A. a, b, c, e, d             B. b, c, a, e, d C. a, e, c, b, d  

20、0;        D. d, c, e, b, a  20. 已知 6 個(gè)結(jié)點(diǎn)的二叉樹(shù)的先根遍歷是 1 2 3 4 5 6（數(shù)字為結(jié)點(diǎn)的編號(hào)，以下同），后根遍歷是 3 2 5 6 4 1，則該二叉樹(shù)的可能的中根遍歷是（        ） A. 3 2 1 4 6 5            B. 3 2 1

21、5 4 6 C. 2 1 3 5 4 6            D. 2 3 1 4 6 5  二問(wèn)題求解（共 2 題，每題 5 分，共計(jì) 10 分）  1（尋找假幣） 現(xiàn)有 80 枚硬幣，其中有一枚是假幣，其重量稍輕，所有真幣的重量都相同，如果使 用不帶砝碼的天平稱(chēng)重，最少需要稱(chēng)幾次，就可以找出假幣？你還要指出第 1 次的稱(chēng)重方法。請(qǐng)寫(xiě)出你的 結(jié)果：_。  2（取石子游戲）  現(xiàn)有 5 堆石子,石子數(shù)依次

22、為 3，5，7，19，50，甲乙兩人輪流從任一堆中任?。看沃荒苋∽砸欢?，不能不?。? 取最后一顆石子的一方獲勝。甲先取，問(wèn)甲有沒(méi)有獲勝策略（即無(wú)論 乙怎樣取，甲只要不失誤，都能獲勝）？如果有，甲第一步應(yīng)該在哪一堆里取多少？請(qǐng)寫(xiě)出你的結(jié)果： _。  三閱讀程序?qū)懡Y(jié)果（共 4 題，每題 8 分，共計(jì) 32 分）由OIF收集   1. Program ex301; var u:array0.3 of integer; i,a,b,x,y:integer; begin   

23、; y:=10; for i:=0 to 3 do    read(ui);    a:=(u0+u1+u2+u3) div 7; b:=u0 div (u1-u2) div u3);    x:=(u0+a+2)-u(u3+3) mod 4;    if (x>10) then   y:=y+(b*100-u3) div (uu0 mod 3*5)    else   y:=y+20+(b

24、*100-u3) div (uu0 mod 3*5);    writeln (x,',',y); end. *注：本例中，給定的輸入數(shù)據(jù)可以避免分母為 0 或下標(biāo)越界。  輸入：9 3 9 4 輸出：_   2.Program ex302;  const   m:array0.4 of integer=(2,3,5,7,13);  var   i,j:integer;   t: longi

25、nt;  begin for i:=0 to 4 do    begin   t:=1;   for j:=1 to mi-1 do  t:=t*2;   t:=(t*2-1)*t;   write (t,' ');    end;   writeln; end. 輸出:_  3.Program ex303; Const 

26、 NN=7; Type   Arr1=array0.30 of char;由OIF收集 var   s:arr1;   k,p:integer; Function fun(s:arr1; a:char;n:integer):integer;    var    j:integer;   begin    j:=n;    while (a<sj)and(j>0) do dec

27、(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:longint; procedure di

28、git(n,m:longint);  var n2:integer;  begin    if(m>0) then   begin    n2:=n mod 10;    write(n2:2);    if(m>1) then  digit(n div 10,m div 10);    n2:=n mod 10;    write(n

29、2:2);   end;  end; begin   writeln('Input a number:');由OIF收集   readln(x);   x2:=1;   while(x2<x) do  x2:=x2*10;   x2:=x2 div 10;   digit(x,x2);   writeln;  end. 輸入：9734526 輸出

30、：_  四完善程序 (前 4 空，每空 2.5 分，后 6 空，每空 3 分，共 28 分)  1（全排列）下面程序的功能是利用遞歸方法生成從 1 到 n(n<10)的 n 個(gè)數(shù)的全部可能的排列（不一 定按升序輸出）。例如，輸入 3，則應(yīng)該輸出（每行輸出 5 個(gè)排列）： 123 132 213     231 321 312 程序：Program ex401; Var  i,n,k:integer; a:array1.10 of integer;co

31、unt:longint;  變量 count 記錄不同排列的個(gè)數(shù)，這里用于控制換行 Procedure    perm(k:integer);  var j,p,t:integer;  begin  if          then    begin   inc(count);   for p:=1 to k do  write

32、(ap:1);   write('  ');   if (         ) then writeln;   exit;    end; for j:=k to n do    begin  t:=ak; ak:=aj; aj:=t;由OIF收集         t:=ak;

33、60;         ;    end  end; begin   writeln('Entry n:');   read(n);    count:=0; for i:=1 to n do ai:=i;      end.  2.  由鍵盤(pán)輸入一個(gè)奇數(shù) P (P<100,000,000)，其個(gè)

34、位數(shù)字不是  5，求一個(gè)整數(shù) S，使 P×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 個(gè) 1。  程序：  

35、program ex402; var  p,a,b,c,t,n:longint; begin   while (true) do    begin writeln ('Input      p, the last digit is        1 or 3 or 7 or 9:');  readln(p); if (p mod 2

36、<>0)and(p mod 5<>0) then    ; 如果輸入的數(shù)符合要求，結(jié)束循環(huán)     end;    a:=0; n:=0;    while (a<p) do由OIF收集  begin    a:=a*10+1; inc(n);  end;    t:=0;    repeat  &

37、#160; b:=a div p;    write(b:1);    inc(t);    if (      ) then writeln;    c:=       ;  a:=         inc(n);    until c<=0;   

38、dec(n);     writeln; writeln('n=',             ); end. 普及組（Pascal 語(yǔ)言）參考答案與評(píng)分標(biāo)準(zhǔn)由OIF整理收集   一、單項(xiàng)選擇題：（每題 1.5 分）由OIF收集     1. D      2. B   &#

39、160;  3. B      4. C      5. B        6.B        7. C        8. A        9. D      10. D 11. C