第九届全国青少年信息学奥林匹克联赛初赛试题

一.单项选择题  （共10题，每题1.5分，共计15分。每题有且仅有一个正确答案.）。
1.  图灵 (alan turing) 是 （      ）。
    a） 美国人    b） 英国人     c） 德国人      d） 匈牙利人      e） 法国人

2.  第一个给计算机写程序的人是（      ）。
    a） alan mathison turing    b） ada lovelace         c） john von neumann
    d） john mc-carthy          e） edsger wybe dijkstra

3.  十进制数2003等值于二进制数（      ）。
    a） 0100000111   b） 10000011    c） 110000111  d） 11111010011  e） 1111010011

4.  假设a=true,b=false,c=ture,d=ture,逻辑运算表达式a∧b∨c∧d的值是（   ）。
    a） ture       b） false      c） 0        d） 1       e） null

5.  一个高度为h 的二叉树最小元素数目是（          ）。
    a） 2h+1       b） h          c） 2h-1     d） 2h      e） 2h-1

6.  已知队列（13，2，11，34，41，77，5，7，18，26，15），第一个进入队列的元素是13，则第五个出队列的元素是（         ）。
    a） 5          b） 41         c） 77        d） 13       e） 18

7.  下面一段程序是用（       ）语言书写的。
          int func1(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.  设全集e={1，2，3，4，5}，集合a={1，4}，b={1，2，5}，c={2，4}，则集合（a ∩b）∪～c 为（      ）。
    a） 空集        b） {1}       c） {3，5}    d）{1，5}     e） {1，3，5}

9.  表达式(1+34)*5-56/7 的后缀表达式为（        ）。
    a） 1+34*5-56/7        b） -*+1 34 5/56 7     c） 1 34 +5*56 7/-
    d） 1 34 5* +56 7/-    e） 1 34+5 56 7-*/
10.  下列计算机设备，即是输入设备，又是输出设备的是（       ）。
     a） 键盘     b） 触摸屏     c） 扫描仪     d）投影仪     e） 数字化仪  
二.不定项选择题（共10题，每题1.5分，共计15分。多选少选均不得分）。
11.  下列分辨率的显示器显示出的图像，最清晰的是（     ）。
     a） 800*600   b） 1024*768    c） 640*480    d） 1280*1024   e） 800*1000

12.  下列说法中，哪个（些）是错误的（        ）。
     a）程序是指令的序列，它有三种结构：顺序、分支和循环。
     b）数据总线决定了中央处理器cpu所能访问的最大内存空间的大小。
     c）中央处理器cpu内部有寄存器组，用来储存数据。
     d）不同厂家生产的cpu所能处理的指令集是相同的。
     e）数据传输过程中可能会出错，奇偶校验法可以检测出数据中那一为在传输中出了差错。

13.  cpu访问内存的速度比访问下列哪个（些）存储设备要慢（     ）。
     a）寄存器      b）硬盘        c）软盘         d）高速缓存    e）光盘

14.  下列电子邮件地址，哪个（些）是正确的（     ）。
     a）wang@hotmail.com   b) cai@jcc.pc.tool.rf.edu.jp   c) 162.105.111.22
     d) ccf.edu.cn         e) http://www.sina.com

15.  数字图像文件可以用下列哪个（些）软件来编辑（     ）。
     a）画笔（paintbrush） b）记事薄（notepad） c) photoshop  d) winrar  e)midisoft

16.  下列哪个（些）软件不是操作系统软件的名字（       ）。
     a）windowsxp     b) dos     c) linux     d) os/2     e) arch/info

17.  下列哪个（些）不是个人计算机的硬件组成部分（       ）。
     a）主板        b）虚拟内存     c）电源     d）硬盘     e）总线

18.  运算试(2008)10-(3723)8 的结果是（       ）。
     a）(-1715)10      b) (5)10      c) (5)16       d) (101)2       e) (3263)8

19.  已知元素（8，25，14，87，51，90，6，19，20），问这些元素以怎样的顺序进入栈，才能使出栈的顺序满足：8在51前面；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，51，14，87
     d）6，25，51，8，20，19，90，87，14
     e）25，6，8，51，87，90，19，14，20

20.  假设我们用d=(a1,a2,…,a5),表示无向图g的5个顶点的度数，下面给出的哪（些）组d 值合理（       ）。
     a）{5，4，4，3，1}     b）{4，2，2，1，1}     c）{3，3，3，2，2}
     d）{5，4，3，2，1}     e）{2，2，2，2，2}
　

三、问题求解（共2题，每题5分，共计10分）

1. 无向图g有16条边，有3个4度顶点、4个3度顶点，其余顶点的度均小于3，则g至少_______个顶点。

2. 某年级学生共选修6门课程，期末考试前，必须提前将这6门课程考完，每人每天只在下午至多考一门课程，设6门课程为c1，c2，c3，c4，c5，c6，s(ci)为学习ci 的学生集合。已知s(ci)∩s(c6)≠ф，i=1，2，…，5，s(ci)∩s(ci+1)≠ф，i=1，2，3，4，s(c5)∩s(c1)≠ф，问至少安排_____天才能考完这6门课程。

四.阅读程序（共4题，每题8分，共计32分）
1.  program program1;
    var   a,b,c,d,sum : longint;
    
    begin
      read(a,b,c,d);
      a := a mod 23;  b := b mod 28;    c := c mod 33;
sum := a * 5544 + b * 14421 + c * 1228 ╟ 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 : array[1..4] of integer = (0,5,3,1);
     v : array[1..4] of 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 (b > y) then 
       begin
         z := z + (b ╟ y + 8) div 9;
         x := ((b ╟ y + 8) div 9 * 9 ╟(b ╟ y)) * 4 + 11 * e + v[c mod 4];
         end
       else
         x := (y ╟ b) * 4 + 11 * e + v[c mod 4];
       if (a > x) then
         z := z + (a ╟ x + 35) div 36;
       writeln(z)
     end.

输入： 4 7 9 20 56 47                               输出____________________

3. program program3;
var  m,n: integer;   mark: boolean;

function test(m,n:integer):integer;
  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 (i<n) then 
        begin 
          test := 0;   flag := ture;      break;
          end
    end;
    if not(flag) then     test:=1;
  end;

begin 
  read(n);   m:=1;   mark := false;
  repeat
    if (test(m,n)=1) then 
      begin   writeln(m); break;   end;
    m:= m+1;
  until mrak;
end.

输入：7                                             输出_________

4. program program4;

var m,n,i,j: integer;
    p,w,a,b: array[0..19] of integer;
begin 
  read(n); m:= 0;
  for i:= 0 to n-1 do
  begin    read(p[i]);   b[i]:=1;  end;
  for i:=0 to  n-1 do
    begin 
      if (i>0) then
      a[m]:=p[i]-p[i-1]
      else
      a[m]:=p[i];
      m:=m+1;
while ((m>1) and (a[m-1]=0)) do 
      begin   m:=m-1;   b[m]:=1;  end;
      if (m>0) then 
        w[i]:=b[m-1];
      else
        w[i]:=b[0];
        a[m-1]:=a[m-1]-1;
        for j:=0 to m-1 do    b[j]:=b[j]+1;
while ((m>1) and (a[m-1]=0)) do 
      begin   
m:=m-1;   b[m]:=1;  
end;
      end;
    for i:= 0 to n-1 do
      begin 
        write(w[i]);      write(' ');
      end;
    writeln(' ');
  end.

输入：9
      4 6 6 6 6 8 9 9 9 9 
输出：____________________

五. 完善程序（共2题，第1题每空3分；第2题每空2分。共计28分）。
1. 翻硬币

题目描述：
        一摞硬币共有m枚，每一枚都是正面朝上。取下最上面的一枚硬币，将它翻面后放回原处。然后取下最上面的2枚硬币，将他们一起翻面后放回原处。在取3枚，取4枚……直至m枚。然后在从这摞硬币最上面的一枚开始，重复刚才的做法。这样一直做下去，直到这摞硬币中每一枚又是正面朝上为止。例如，m为1时，翻两次即可。
输    入：仅有的一个数字是这摞硬币的枚数m ，0< m <1000。
输    出：为了使这摞硬币中的每一枚都是朝正面朝上所必须翻的次数。
输入样例：30
输出样例：899

程    序：
    program program1;
    var   m:integer;
    function solve(m: integer):integer;
       var i,t,d: integer;
           flag: boolean;
       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
                           solve := 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；而 /   \    不是。
                            \/
这个世界的地理学家们为了方便纪录，给oim所有可能的形状用正整数编好号，而且每个正整数恰好对应一种山形。他们规定，若两座山的宽度不同，则较宽的编号较大；若宽度相同，则比较从左边开始第1个坡度不同的地方，坡度上升的编号较大。以下三座oim的编号有小到大递增：

 /\      /\        /\  /\
/  \/\  /  \/\/\  /  \/  \。显然/\的编号为1。但是地理学家在整理纪录是发觉，查找编号与山形的对应关系不是很方便。他们希望能快速地从编号得到山的形状。你自告奋勇答应他们写一个程序，输入编号，能马上输出山形。

输    入：一个编号（编号大小不超过600,000,000），
输    出：输入编号所对应的山形，1座山所占行数恰为它的高度，即山顶上不能有多余空行。

输入样例：15

输出样例：   /\  /\
            /  \/  \

程    序：
     program program2;
     const 
       l:integer =19;    sz: integer =50;
       up: char = '/';   dn: char = '\';
     var
       i,nth,x,y,h,e,f:integer;
       m: array[0..1,0..38,0..19] of integer;
       pic: array[0..49,0..49] of 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
m[a,b,c]:=0;   m[0,0,0]:=1;
         for k:=0 to 2*l-1 do
         begin
           for s:=1 to l do
           begin
             m[0,k+1,s] := m[0,k,s+1] + m[1,k,s+1];
m[1,k+1,s]:=      (1)      ;
           end;
             m[0,k+1,0] :=m[0,k,1]+m[1,k,1];
             end;
       end;
       
       procedure draw(k,s,nth:integer);
       begin
         if (k=0) then exit;
         if ((nth-m[1,k,s])>=0) then
           begin
             nth:=nth-m[1,k,s];
             if (y>h) then       (2)       ;
             pic[y,x]:=up;  y:=y+1;  x:=x+1;  draw(      (3)      );
           end
           else begin
                y:=y ╟ 1;   pic[y,x]:=dn;     x:=x+1;   draw(k-1,s-1,nth);
                end;
       end;  
             
     begin
       init;
       read(nth);
       for e:=0 to sz-1 do
         for f:=0 to sz-1 do
           pic[e,f]:= ' ';
           x:=0;
           y:=0
h:=0;
i:=0;
     
      while ((nth-m[0,2*i,0])>=0) do
      begin 
        nth:= nth-m[0,2*i,0];
               (4)        ;
      end;

      draw(          (5)           );
      for i:=h downto x-1 do
      begin
        for e:=0 to x-1 do 
        write(pic[i,e]);
        writeln(' ');
      end;
     end.