2002年NOIP提高组初赛真题

一．选择一个正确答案代码（A/B/C/D），填入每题的括号内（每题1.5分，多选无分，共30分）
1. 微型计算机的问世是由于（ ）的出现。
  • A. 中小规模集成电路
  • B. 晶体管电路
  • C. （超）大规模集成电路
  • D. 电子管电路
2. 中央处理器（CPU）能访问的最大存储器容量取决于（ ）。
  • A. 地址总线
  • B. 数据总线
  • C. 控制总线
  • D. 实际内存容量
3. 十进制 11/128可用二进制数码序列表示为：（ ）。
  • A. 1011/1000000
  • B. 1011/100000000
  • C. 0.001011
  • D. 0.0001011
4. 算式（2047）10 －（3FF）16 ＋（2000）8的结果是（ ）。
  • A. （2048）10
  • B. （2049）10
  • C. （3746）8
  • D. （1AF7）16
5. 已知x =（0.1011010）2 ，则[ x / 2 ]补 =（ ）2 。
  • A. 0.1011101
  • B. 11110110
  • C. 0.0101101
  • D. 0.100110
6. IPv4地址是由（ ）位二进制数码表示的。
  • A. 16
  • B. 32
  • C. 24
  • D. 8
7. 计算机病毒传染的必要条件是：（ ）。
  • A. 在内存中运行病毒程序
  • B. 对磁盘进行读写操作
  • C. 在内存中运行含有病毒的可执行的程序
  • D. 复制文件
8. 在磁盘上建立子目录有许多优点，下列描述中不属于建立子目录优点的是（ ）。
  • A. 便于文件管理
  • B. 解决根目录中目录项个数有限问题
  • C. 加快文件查找速度
  • D. 节省磁盘使用空间
9. 在使用E-mail前，需要对Outlook进行设置，其中ISP接收电子邮件的服务器称为（ ）服务器。
  • A. POP3
  • B. SMTP
  • C. DNS
  • D. FTP
10. 多媒体计算机是指（ ）计算机。
  • A. 专供家庭使用的
  • B. 装有CD-ROM的
  • C. 连接在网络上的高级
  • D. 具有处理文字、图形、声音、影像等信息的
11. 微型计算机中，（ ）的存取速度最快。
  • A. 高速缓存
  • B. 外存储器
  • C. 寄存器
  • D. 内存储器
12. 资源管理器的目录前图标中增加“+”号，这个符号的意思是（ ）。
  • A. 该目录下的子目录已经展开
  • B. 该目录下还有子目录未展开
  • C. 该目录下没有子目录
  • D. 该目录为空目录
13. 在WORD文档编辑中实现图文混合排版时，关于文本框的下列叙述正确的是（ ）。
  • A. 文本框中的图形没有办法和文档中输入文字叠加在一起，只能在文档的不同位置
  • B. 文本框中的图形不可以衬于文档中输入的文字的下方
  • C. 通过文本框，可以实现图形和文档中输入的文字的叠加，也可以实现文字环绕
  • D. 将图形放入文本框后，文档中输入的文字不能环绕图形
14. 一个向量第一个元素的存储地址是100，每个元素的长度是2，则地5个元素的地址是（ ）。
  • A. 110
  • B. 108
  • C. 100
  • D. 109
15. 已知A = 35H，A /\ 05H \/ A /\ 30H 的结果是：（ ）。
  • A. 30H
  • B. 05H
  • C. 35H
  • D. 53H
16. 设有一个含有13个元素的Hash表（0 ~ 12），Hash函数是：H（key）= key % 13，其中%是求余数运算。用线性探查法解决冲突，则对于序列（2、8、31、20、19、18、53、27），18应放在第（ ）号格中。
  • A. 5
  • B. 9
  • C. 4
  • D. 0
17. 按照二叉数的定义，具有3个结点的二叉树有（ ）种。
  • A. 3
  • B. 4
  • C. 5
  • D. 6
18. 在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的（ ）倍。
  • A. 1/2
  • B. 1
  • C. 2
  • D. 4
19. 要使1 ．．．8号格字的访问顺序为：8、2、6、5、7、3、1、4，则下图中的空格中应填入（ ）。
1 2 3 4 5 6 7 8
4 6 1 -1 7 ? 3 2
  • A. 6
  • B. 0
  • C. 5
  • D. 3
20. 设栈S和队列Q的初始状态为空，元素e 1 ，e 2 ，e 3 ，e 4 ，e 5 ，e 6依次通过栈S，一个元素出栈后即进入队列Q，若出队的顺序为e 2 ，e 4 ，e 3 ，e 6 ，e 5 ，e 1 ，则栈S的容量至少应该为（ ）。
  • A. 2
  • B. 3
  • C. 4
  • D. 5
二．问题求解：（6 + 8 = 14分）
21. 在书架上放有编号为1 ，2 ，．．．，n的n本书。现将n本书全部取下然后再放回去，当放回去时要求每本书都不能放在原来的位置上。例如：n = 3时：
原来位置为：1 2 3
放回去时只能为：3 1 2 或 2 3 1 这两种
问题：求当n = 5时满足以上条件的放法共有_________种？（不用列出每种放法）
22. 设有一棵k叉树，其中只有度为0和k两种结点，设n0 ，nk ，分别表示度为0和度为k的结点个数，试求出n0 和nk之间的关系（n0 = 数学表达式，数学表达式仅含nk 、k和数字）。
_________
三．阅读程序，写出正确的程序运行结果：（8 + 9 + 9 = 26分）
23. 
program Gxp1;
var  i , n , jr , jw , jb : integer ;
     ch1: char ;
     ch: array[1..20] of char ;
begin
 readln(n);
   for i:=1 to n do read(ch[i]);
   jr:=1; jw:=n; jb:=n;
   while (jr<=jw) do
     begin
       if (ch[jw]=’R’)
         then begin
               ch1:=ch[jr]; ch[jr]:=ch[jw]; ch[jw]:=ch1; jr:=jr+1;
             end
         else if ch[jw]=’W’
              then jw:=jw-1;
              else begin
                    ch1:=ch[jw]; ch[jw]:=ch[jb]; ch[jb]:=ch1; jw:=jw-1; jb:=jb-1;
                  end
     end;
    for i:=1 to n do write(ch[1]);
    writeln;
end.
输入：10
      RBRBWWRBBR
输出：____①_____
24. 
program Gxp2;
var  i , j , s ,sp1 : integer ;
     p: boolean ;
     a: array[1..10] of integer ;
begin
  sp1:=1; a[1]:=2; j:=2;
  while sp1<10 do
    begin
      j:=j+1; p:=true;
      for i:=2 to j-1 do
        if (j mod i=0) then p:=false;
        if p then begin
 sp1:=sp1+1; a[sp1]:=j;
end;
    end;
  j:=2; p:=true;
  while p do
    begin
      s:=1;
      for i:=1 to j do s:=s*a[i];
      s:=s+1;
      for i:=2 to s-1 do
        if s mod i=0 then p:=false;
      j:=j+1;
    end;
  writeln(s); writeln;
end.
输出：____①_____
25. 
Program Gxp2
Var   d1 , d2 , X , Min : real ;
begin
  Min:=10000; X:=3;
  while X<15 do
    begin
      d1:=sqrt(9+(X-3)*(X-3)); d2:=sqrt(36+(15-X)*(15-X));
      if(d1+d2)<Min then Min:=d1+d2;
      X:=x+0.001;
    end;
  writeln(Min:10:2);
end.
输出：____①_____
四．完善程序：（15 + 15 = 30分）
26. 问题描述：工厂在每天的生产中，需要一定数量的零件，同时也可以知道每天生产一个零件的生产单价。在N天的生产中，当天生产的零件可以满足当天的需要，若当天用不完，可以放到下一天去使用，但要收取每个零件的保管费，不同的天收取的费用也不相同。

问题求解：求得一个N天的生产计划（即N天中每天应生产零件个数），使总的费用最少。

输入：N（天数 N<=29）

每天的需求量（N个整数）

每天生产零件的单价（N个整数）

每天保管零件的单价（N个整数）

输出：每天的生产零件个数（N个整数）

例如：当N=3时，其需要量与费用如下：

生产计划的安排可以有许多方案，如下面的三种：



程序说明：

b[n]：存放每天的需求量

c[n]：每天生产零件的单价

d[n]：每天保管零件的单价

e[n]：生产计划

程序：

program exp5;
var
    i,j,n,yu,j0,j1,s : integer ;
  b,c,d,e: array[0..30] of integer ;
begin
    readln(n);
    for i:=1 to n do readln(b[i],c[i],d[i]);
  for i:=1 to n do e[i]:=0;
    ____①_____ :=10000;  c[n+2]=0;  b[n+1]:=0 ;j0:=1;
  while (j0<=n) do
begin
    yu:=c[j0];  j1:=j0;  s:=b[j0];
    while ____②_____ do
      begin
        ____③_____ ; j1:=j1+1;  s:=s+b[j1];
      end;
  ____④_____ ; j0:=j1+1;
end;
        for i:=1 to n do ____⑤_____ ;
        readln;
end.
27. 问题描述：有n种基本物质（n≤10），分别记为P1，P2，……，Pn，用n种基本物质构造物质，这些物品使用在k个不同地区（k≤20），每个地区对物品提出自己的要求，这些要求用一个n位的数表示：a1a2……a n，其中：

ai = 1表示所需物质中必须有第i种基本物质

= -1表示所需物质中必须不能有第i种基本物质

= 0无所谓

问题求解：当k个不同要求给出之后，给出一种方案，指出哪些物质被使用，哪些物质不被使用。

程序说明：数组 b[1],b[2]……b[n] 表示某种物质

a[1..k,1..n] 记录k个地区对物品的要求，其中：

a[i,j]=1 表示第i个地区对第j种物品是需要的

a[i,j]=0 表示第i个地区对第j种物品是无所谓的

a[i,j]= -1 表示第i个地区对第j种物品是不需要的

程序：

program gxp2;
var
  i,j,k,n : integer ;
  p: boolean ;
  b: array[0..20] of 0..1 ;
  a: array[1..20,1..10] of integer ;
begin
  readln(n,k);
  for i:=1 to k do
    begin
      for j:=1 to n do read(a[i,j]);
      readln;
    end;
  for i:=0 to n do b[i]:=0;
  p:=true;
  while  ____①_____  do
    begin
      j:=n;
      while b[j]=1 do j:=j-1;
       ____②_____ ;
      for i:=j+1 to n do b[i]:=0;
       ____③_____ ;
      for i:=1 to k do
        for j:=1 to n do
          if (a[i,j]=1) and (b[j]=0) or ____④_____ ;
            then p:=true;
    end;
  if  ____⑤_____ 
    then writeln(‘找不到！’)
    else for i:=1 to n do
          if (b[i]=1) then writeln(‘物质’,i,’需要’)
                   else writeln(‘物质’,i,’不需要’);
end.
查看参考答案