全国第四届青少年信息学奥林匹克竞赛分区联赛初赛试题 [1998年]

1. 操作系统是一类重要的系统软件，下面几个软件中不属于操作系统的是 。 {1%}

2. 在计算机内部，用来传送、存贮、加工处理的数据或指令（命令）都是以 形式进行的。{1%}

3. 已知在计算机C:\DOS下有一个正确的FORMAT.COM 文件，当执行如下命令： C:\> FORMAT A: < 回车 > 得到的回答是 BAD COMMAND OR FILE NAME 提示信息，下面解释正确的是_____________。 {2%}

4. 将A盘上50个文件用C:\>COPY A: *.* 命令复制到C盘的当前目录中，在复制到某个文件时，由于读数据出错，屏幕显示： ABORT, RETRG , IGNORE , FAIL ? 键入“I”后，继续复制没再出现过错误信息，最后复制的结果是_________。 {2%}

5. 表达式（4 MOD（-3））与（-4 MOD 3）的值为： 。 {2%}

6. 小张用十六进制、八进制和十进制写了如下的一个等式： 52 - 19 = 33 式中三个数是各不相同进位制的数，试问52、19、33，分别为_________。 {3%}

7. 某班有50名学生，每位学生发一张调查卡，上面写a，b，c三本书的书名，将读过的书打?，结果统计数字如下： 只读a者8人；只读b者4人；只读c者3人；全部读过的有2人；读过a，b两本书的有4人；读过a，c两本书的有2人；读过b，c两本书的有3人；{4%} （1）读过a的人数是 ， （2）一本书也没有读过的人数是 。

8. 下列IF语句中，ENDIF 表示相应IF的结束： {2%} y=0 if x<0 then y=5 else if x<10 then y=10 if x<100 then y=100 endif else y=200 endif endif 试指出： 当X=80 时，运行的结果是______,X=5 时，运行结果为_________。 {2%}

9. 如果用一个字节来表示整数，最高位用作符号位，其它位表示数值。 例如： {4%} 0 0 0 0 0 0 0 1 表示+1 ↑ 符号位表示正 1 0 0 0 0 0 0 1 表示-1 ↑ 符号位表示负 试问这样表示法的整数A 的范围应该是_____________________。

10. (接上题) 在这样表示法中，以下 说法是正确的。

11. 设栈S的初始状态为空，现有5个元素组成的序列{1，2，3，4，5}，对该序列在S栈上依次进行如下操作（从序列中的1开始，出栈后不再进栈）：进栈、进栈、进栈，出栈、进栈、出栈、进栈。试问出栈的元素序列是______________。 {2%}

1. 已知一个数列U1，U2，U3，…，UN，… 往往可以找到一个最小的K值和K个数a1，a2，…,an使得数列从某项开始都满足： U(N+K)=a1U(N+K-1)+a2U(N+K-2)+……+akU(N) (A) 例如对斐波拉契数列1，1，2，3，5，…可以发现：当K=2，a1 =1，a2 =1时，从第3项起（即N&gt;=1）都满足U(n+2) =U(n+1)+U(n)。试对数列1^3，2^3，3^3，…，n^3,…求K和a1,a2, …,aK使得（A）式成立。 {8%}
答案：当K=4,a1,a2,a3...为a1=4,a2=6,a3=4,a4=-1,对列(A)成立。

2. 给出一棵二叉树的中序遍历：DBGEACHFI 与后序遍历：DGEBHIFCA 画出此二叉树。 {8%}
答案：

3. 用邻接矩阵表示下面的无向图： {6%}
答案： 0 1 0 0 0 0 0 1 0 1 1 0 0 0 0 1 0 1 0 0 0 0 1 1 0 1 1 1 0 0 0 1 0 0 1 0 0 0 1 0 0 1 0 0 0 1 1 1 0

1.

program  exp1  (imput,output);                                         {6%}
    VAR  i,  s,  max: integer;
          a    ：array [1..10]  of  integer;
        begin 
          for i:=1 to 10  do   read (a[i]);
          max:=a[1] ；s:=a[1];
          for i：=2  to  10  do 
            begin 
              if  s<0  then  s：=0;                
              s：= s+a[i];                        
           if s>max  then  max：=s
        end;
     writeln(‘max=’, MAX)
 end.  
      输入：8  9  －1  24  6  5  11  15  －28  9      
输出：max=77

2.

program  exp3 (input,output);                                         {9%}
     CONST  N=10;
VAR S,I : INTEGER;
FUNCTION  CO(I1:INTEGER) : INTEGER;
   VAR J1,S1 : INTEGER;                           
 BEGIN                                          
   S1:=N;
     FOR J1:= (N-1)  DOWNTO  (N-I1+1)  DO       
     S1:= S1*J1  DIV  (N-J1+1);                
     CO:=S1
   END;
BEGIN                                      
  S:=N+1;                                    
  FOR I:= 2  TO  N  DO  S:=S + CO(I);
       WRITELN(‘S=’,S);
END.
输出：S=1024

3.

program  exp3(input,output);                                          {12%}
VAR I,J,S:INTEGER;
     B    :ARRAY[0..5]  OF  INTEGER;
     BEGIN
   S:=1;
   FOR I:=1  TO  5  DO   B[I]:=I   
   J:=1;
   WHILE  J>0  DO
       BEGIN
          J:=5;
          WHILE  (J>0) AND (B[J]=10+J-5) DO 
            J:=J-1;
       IF J>0 THEN  BEGIN
                      S:=S+1;  B[J]:=B[J]+1;
                      FOR I:=J+1 TO 5 DO  B[I]:=B[J]+I-J
                    END;
 END;
       WRITELN('S=',S);
     END.

输出：S=252

4.

Program  EXP4 (input,output);                                        {12%}
        const n=4;
type  se=array[1..n*2] of char;
var   i,j,i1,j1,k,s,t,s1,l,swap:integer;
       temp    :char;
       a       :se;
begin
  for  i:=1  to  n*2  do   read(a[i]);  readln;      
  s:=0;  t:=0;                                            
  for i:=1 to n*2 do                                    
            if a[i]='1' then s:=s+1 
                  else if a[i]='0' then t:=t+1;
          if  (s<>n)  or  (t<>n)  then  writeln('error')
             else  begin 
                    s1:=0;
                    for i:=1 to 2*n-1  do  if a[i]<>a[i+1] then s1:=s1+1;
                    writeln('jamp=',s1);  swap:=0;
             
 for i:=1 to 2*n-1 do
                     for j:=i+1 to 2*n do
                     if a[i]<>a[j] then begin
                           temp:=a[i];a[i]:=a[j] ;a[j]:=temp;
                           s:=0;
                           for l:=1 to 2*n-1 do
                               if a[l]<>a[l+1]  then  s:=s+1;
if s>swap  then  begin 
                   swap:=s;  i1:=i;  j1:=j  
                 end;
                           temp:=a[i]; a[i]:=a[j]; a[j]:=temp
                       end;
                 if  swap>0  then  writeln('maxswap=',swap-s1,' i=',i1,' j=',j1)
              end
       END.
  输入：10101100
输出：jamp=5 maxswap=2 i=6 j=7

1. FBZ串问题。已知一个由0，1字符组成的长度为2n的字符串。请按以下规则将已给出的字符串分解为FBZ串：

（1）若其中字符全为'1'，则称其为'B'串；
（2）若其中字符全为'0'，则称其为'Z'串；
（3）若不全为'0'，同时也不全为'1'，则称'F'串。若此串为F串，则应将此串分解为2个长为2n-1的子串。
对分解后的子串，仍按以上规则继续分解，直到全部为B串或为Z串为止。
例如n=3时，给出0-1串为：'10111001'
最后输出：FFFBZBFFBZFZB
问题：给出01串，分解成FBZ串。
程序如下：

Program EXP-5;
  CONST  N = 8;
  VAR
   I,J,ST11,ST12,ST2，S,T : INTEGER;
   STR1 : ARRAY[1..N*2, 1..N] OF CHAR;
   STR2 : ARRAY[1..40] OF CHAR;
   BEGIN
 FOR  I := 1 TO N*2 DO
       FOR  J := 1  TO N  DO  STR1[I,J] := '□';
       ST11 := 1;  ST12 := 1; ST2 := 0;
 FOR  I := 1 TO N DO READ(STR1[1,I]); READLN;                      4%
 WHILE  st12<=st11  DO
    BEGIN
     S := 0;  T := 0;
     FOR  I := 1 TO N DO
        BEGIN
           IF  STR1[ST12,I] = '1'  THEN S := S + 1;
           IF  STR1[ST12,I] = '0'  THEN T := T + 1
       END;                                                
     IF   t=0 THEN  BEGIN                                 2%
                         ST2 := ST2 + 1;  STR2[ST2] := 'B'
                       END                              
         ELSE IF  s=0 THEN BEGIN                            2%
                                 ST2 := ST2+1; STR2[ST2]:='Z'
                               END
              ELSE BEGIN
   ST2 := ST2+1; STR2[ST2] := 'F'; J := (S+T) DIV 2;
   FOR  S := N*2-2  DOWNTO   st12+1 DO  3%
      FOR T := 1  TO  N DO
        STR1[S+2,T] := STR1[S,T];
   ST11 := ST11 + 2;
   FOR  I := 1 TO  J  DO
      BEGIN
         STR1[ST12+1,I] := STR1[ST12,I];
         STR1[ST12+2,I] :=  st1[st12,i+j]    4%
      END;
           FOR I :=  j+1 to n  DO   BEGIN       2%
   STR1[ST12+1,I] := '□';    STR1[ST12+2,I] := '□'
  END
         END
         ST12:=ST12+1
   END;
  FOR  I := 1 TO ST2 DO WRITE(STR2[I]); WRITELN
  END.