不是VIP会员,不能显示答案,请在后台“我的信息” 在线升级 VIP

一、选择一个正确答案代码(A/B/C/D),填入每题的括号内 (每题1.5分,多选无分,共30分)

1. 下列无符号数中,最小的数是( ).

  • A.(11011001)2
  • B.(75)10
  • C.(37)8
  • D.(2A)16

2. 在外部设备中,绘图仪属于( ).

  • A.输入设备
  • B.输出设备
  • C.辅(外)存储器
  • D.主(内)存储器

3. GB2312-80 规定了一级汉字3755个,二级汉字3008个,其中二级汉字字库中的汉字是以( )为序排列的.

  • A.以笔划多少
  • B.以部首
  • C.以ASCII码
  • D.以机内码

4. 算法是指( ).

  • A.为解决问题而编制的计算机程序
  • B.为解决问题而采取的方法与步骤
  • C.为解决问题而需要采用的计算机语言
  • D.为解决问题而采用的计算方法

5. RAM 中的信息是( ).

  • A.生产厂家预先写入的
  • B.计算机工作时随机写入的
  • C.防止计算机病毒侵入所使用的
  • D.专门用于计算机开机时自检用的

6. 计算机主机是由CPU 与( )构成的.

  • A.控制器
  • B.运算器
  • C.输入、输出设备
  • D.内存储器

7. 计算机病毒的特点是( ).

  • A.传播性、潜伏性、易读性与隐蔽性
  • B.破坏性、传播性、潜伏性与安全性
  • C.传播性、潜伏性、破坏性与隐蔽性
  • D.传播性、潜伏性、破坏性与易读性

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

  • A.r- f
  • B.r- f +1
  • C.(r- f ) MOD n+1
  • D.(r- f + n) MOD n

9. 在待排序的数据表已经为有序时,下列排序算法中花费时间反而多的是( ).

  • A.堆排序
  • B.希尔排序
  • C.冒泡排序
  • D.快速排序

10. Internet 的规范译名应为( ).

  • A.英特尔网
  • B.因特网
  • C.万维网
  • D.以太网

11. WINDOWS 9X 是一种( )操作系统.

  • A.单任务字符方式
  • B.单任务图形方式
  • C.多任务字符方式
  • D.多任务图形方式

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

  • A.640
  • B. 640*1000
  • C. 640 * 1024
  • D.640*1024*1024

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

  • A.可以进行开关选择
  • B.执行时有对话框
  • C.有若干子命令
  • D.不能执行

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

  • A.1000
  • B.10
  • C.100
  • D.500

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

  • A.SA+141
  • B.SA+180
  • C.SA+222
  • D.SA+225

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

  • A.快存 / 辅存 / 主存
  • B.外存 / 主存 / 辅存
  • C.快存 / 主存 / 辅存
  • D.主存 / 辅存 / 外存

17. 线性表若采用链表存贮结构,要求内存中可用存贮单元地址( ).

  • A.必须连续
  • B.部分地址必须连续
  • C.一定不连续
  • D.连续不连续均可

18. 下列叙述中,正确的是( ).

  • A.线性表的线性存贮结构优于链表存贮结构
  • B.队列的操作方式是先进后出
  • C. 栈的操作方式是先进先出
  • D.二维数组是指它的每个数据元素为一个线性表的线性表

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

  • A.奇数
  • B.偶数
  • C.可奇可偶
  • D.数目固定

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

  • A.-1
  • B.-2
  • C.-3
  • D.-4

二、问题解答(第1题的第1问2分,第2问5分,第2题7分,两题共14分)

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)

三、阅读程序,并写出程序的正确运行结果(10+16分,共26分)

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

四、根据题意,将程序补充完整(每个点3分,共30分)

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.