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

1. 下列无符号数中，最小的数是（ ）．

2. 在外部设备中，绘图仪属于（ ）．

3. GB2312-80 规定了一级汉字3755个，二级汉字3008个，其中二级汉字字库中的汉字是以（ ）为序排列的．

4. 算法是指（ ）．

5. RAM 中的信息是（ ）．

6. 计算机主机是由CPU 与（ ）构成的．

7. 计算机病毒的特点是（ ）．

8. 设循环队列中数组的下标范围是1–n，其头尾指针分别为f和r，则其元素个数为（ ）

9. 在待排序的数据表已经为有序时，下列排序算法中花费时间反而多的是（ ）．

10. Internet 的规范译名应为（ ）．

11. WINDOWS 9X 是一种（ ）操作系统．

12. 某种计算机的内存容量是640K, 这里的640K 容量是指( ) 个字节．

13. 在Windows 9X中，菜单项后带有符号“…”，表示该菜单项( ) ．

14. 某数列有1000个各不相同的单元，由低至高按序排列；现要对该数列进行二分法检索(binary search)，在最坏的情況下，需检视( )个单元．

15. 已知数组A中，每个元素A[I，J]在存贮时要占3个字节，设I从1变化到8，J从1变化到10，分配内存时是从地址SA开始连续按行存贮分配的。试问：A[5，8]的起始地址为（ ）．

16. 大家知道，不同类型的存储器组成了多层次结构的存储器体系，按存取速度从快到慢的排列是（ ）．

17. 线性表若采用链表存贮结构，要求内存中可用存贮单元地址（ ）．

18. 下列叙述中，正确的是（ ）．

19. 电线上停着两种鸟（A，B），可以看出两只相邻的鸟就将电线分为了一个线段。这些线段可分为两类：一类是两端的小鸟相同；另一类则是两端的小鸟不相同．已知：电线两个顶点上正好停着相同的小鸟，试问两端为不同小鸟的线段数目一定是（ ）．

20. 请仔细阅读下列程序段: 上列程序段的正确输出是（ ）．

1. 已知，按中序遍历二叉树的结果为：abc 问：有多少种不同形态的二叉树可以得到这一遍历结果，并画出这些二叉树。
答案：有 5 种不同形态的二叉树可以得到这一遍历结果；可画出的这些二叉树为

2. 有2×n的一个长方形方格，用一个1×2的骨牌铺满方格。例如n=3时，为2×3方格。 此时用一个1×2的骨牌铺满方格，共有3种铺法： 试对给出的任意一个n（n>0），求出铺法总数的递推公式。
答案：F(1)=1 F(2)=2 F(n)=F(n-2)+F(n-1)(n≥3)

1.

PROGRAM NOI_002;
     VAR   I, J, L, N, K, S, T :  INTEGER;
           B                   :  ARRAY[1..10] OF  0..9;  
   BEGIN
      READLN(L,N);       S:=L; K:=1; T:=L;
      WHILE  S<N  DO
       BEGIN   K:=K+1;  T:=T*L;  S:=S+T   END;
      S:=S-T;  N:=N-S-1;
      FOR  I:=1 TO 10 DO  B[I]:=0;
      J:=11;
      WHILE  N>0 DO
        BEGIN  J:=J-1; B[J]:=N MOD L;  N:=N DIV L   END;
       FOR  I:=10-K+1  TO  10  DO   WRITE(CHR(ORD('A')+B[I]));
   END.
 输入：　4     167
输出：BBAC

2.

PROGRAM NOI_004;
    VAR　  I, J, J1, J2,  P, Q :  INTEGER;
           P1           :  BOOLEAN;
           B,C           :  ARRAY[1..100]  OF  INTEGER;
    BEGIN
      READLN(Q,P);   J:=1;  P1:=TRUE;     B[J]:=Q;  J1:=0;
       WHILE  (Q>0) AND  P1 DO
         BEGIN
           J1:=J1+1;  C[J1]:=Q*10 DIV P;  Q:=Q*10-C[J1]*P;
            IF Q>0 THEN  BEGIN 
                           J2:=1;
                           WHILE  (B[J2]<>Q) AND (J2<=J)  DO   J2:=J2+1;
                             IF   B[J2]=Q   THEN 
                                BEGIN 
                                  P1:=FALSE;  WRITE('0.');
                                  FOR I:=1 TO J2-1 DO    WRITE(C[I]:1);
                                  WRITE('{');
                                  FOR I:=J2 TO J1 DO   WRITE(C[I]:1);
                                  WRITELN('}')
                                END
                    ELSE   BEGIN   J:=J+1;  B[J]:=Q   END
               END
        END;
      IF  Q=0  THEN   BEGIN
                       WRITE('0.');
                       FOR I:=1 TO J1 DO   WRITE(C[I]:1);
                       WRITELN
                     END;     READLN
 END.
输入　　①　1   8　　　　输出          
输入　  ②　2   7　　　　输出
输出：0.125|0.285714

1. 将2^n个0和2^n 个1，排成一圈。从任一个位置开始，每次按逆时针的方向以长度为n+1的单位进行数二进制数。
要求给出一种排法，用上面的方法产生出来的2^(n+1)个二进制数都不相同。
例如，当n=2时, 即2^2个0 和2……2个1 排成如下一圈：

比如，从A位置开始，逆时针方向取三个数000，然后再从B位置上开始取三个数001，接着从C开始取三个数010，．．．可以得到000，001，010，101，011，111，110，100共8个二进制数且都不相同。

程序说明
以n=4为例，即有16个0，16个1，
数组a用以记录32个0，1的排法，
数组b统计二进制数是否已出现过。

程序清单

  PROGRAM NOI00;
VAR
   A             : ARRAY[1..36] OF  0..1;
       B             :ARRAY[0..31] OF  INTEGER;
       I, J, K, S, P : INTEGER;
  BEGIN
     FOR I:=1 TO 36 DO  A[I]:=0;
      FOR I:=28 TO 32 DO  A[I]:=1;
     P:=1; A[6]:=1;
     WHILE  (P=1)  DO
       BEGIN
         J:=27;
         WHILE  A[J]=1  DO  J:=J-1;
                 a[j]:=1;           
         FOR  I:=J+1 TO 27 DO         a[i]:=0;           
         FOR  I:=0  TO 31 DO  B[I]:=0;
         FOR  I:=1 TO 32 DO
          BEGIN
                     s:=0;             
             FOR  K:=I  TO  I+4  DO  S:=S*2+A[K];
                      b[s]:=1;             
          END;
         S:=0;
         FOR  I:=0  TO 31 DO  S:=S+B[I];
         IF        s=32            THEN  P:=0
        END;
     FOR  I:=1 TO 32 DO   FOR J：=I TO I+4 DO WRITE(A[J]);
  WRITELN
  END. 

2. 多项式的乘法。
例如有如下多项式：
P(X)=2X2-X+1, Q(X)=X+1
则：
P(X)•Q(X)=(2X2-X+1)(X+1)=2X3+X2+1

程序说明：
多项式的表示：系数、指数
如上例中： P(X)： 系数 指数 Q(X) 系数 指数
2 2 1 1
-1 1 1 0
1 0 0 0
0 0
PXQ的结果存入C中。其输出格式是：依次用一对括号内的（系数，指数）分别来表示。如上例的输出结果表示为：（2，3）（1，2）（1，0）
程序清单

PROGRAM NOI_007;
  VAR 
        I, J, K, L , JP, JQ, JC, X, Y, X1, Y1  :  INTEGER;
        P, Q :  ARRAY[1..10,1..2]  OF  INTEGER;
        C :  ARRAY[1..20,1..2]  OF  INTEGER;
  BEGIN
    
    JP:=0;
    READLN(X,Y);    
　　WHILE X<>0 DO
      BEGIN   JP:=JP+1;  P[JP,1]:=X;  P[JP,2]:=Y;  READLN(X,Y)   END;   
    JQ:=0;
READLN(X,Y);

    WHILE X<>0 DO
      BEGIN   JQ:=JQ+1;  Q[JQ,1]:=X;  Q[JQ,2]:=Y;  READLN(X,Y)   END;     
     JC:=1;  C[JC,1]:=0;  C[JC,2]:=-1000;
     FOR  I:=1 TO JP DO
       BEGIN
             x:=p[i,1];               
　　　　　 Y:=P[I,2];
          FOR  J:=1 TO JQ DO
            BEGIN
                        x1:=x*q[j,1];                   
　　　　　　　Y1:=Y+Q[J,2];
              K:=1;
              WHILE  Y1<C[K,2]  DO  K:=K+1;
              IF  Y1=C[K,2]  THEN        c[k,1]:=c[k,1]+x1            
                             ELSE
                                 BEGIN
                                    FOR  L:=JC DOWNTO K DO
                                     BEGIN
                                       C[L+1,1]:=C[L,1]; 
　　　　　　　　　　　　　　　　　　　 C[L+1,2]:=C[L,2]
　　      　                         END;
    　　　　　　　　　　             C[K,1]:=X1;  C[K,2]:=Y1;
               　　　　　　　　　　          jc:=jc+1             
            　　　　　　　　　　　END
        　 END
      END;
    FOR  I:=1 TO JC DO
      IF       c[i,1]<>0              THEN  WRITE(‘（’，C[I,1],‘，’，C[I,2],'）');
    READLN
 END.