第八届全国青少年信息学奥林匹克联赛(NOIP2002)初赛试题

(提高组PASCAL语言二小时完成)

全部试题答案均要求写在答卷纸上,写在试卷纸上一律无效

一、.选择一个正确答案代码(A/B/C/时,填入每题的括号内(每题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)₁₀－(3FF)₁₆＋(2000)₈的结果是(    ) 。

A)(2048)₁₀     B)(2049)₁₀    C) (3746)₈    D) (1AF7)₁₆

5.已知x=(0.1011010)₂,则[x/2]补=(    ) ₂ 。

A) 0.1011101.    B) 11110110    C) 0.0101101    D) 0.100110

6.Ip v4地址是由(    ) 位二进制数码表示的。

A)16    B)32    C) 24f    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的

B)连接在网络上的高级    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∧3OH的结果是:(    ) 。

A)3OH     B)05H     C) 35H     D) 53H

16.设有一个含有13个元素的Hash表(0~12),Hash函数是:H(key)=key % 13,其中% 是求余数运算。用线性探查法解决冲突,则对于序列(2、８、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,则下图中的空格中应填入(    ) 。

A) 6    B) O    C) 5    D) 3

20.设找S和队列Q的初始状态为空,元素e1,e2,e3,e4,e5,e6依次通过钱S,一个元素出栈后即进入队列Q,若出队的顺序为e2,e4,e3,e6,e5,e1,则钱S的容量至少应该为(    ) 。

A) 2    B) 3    C) 4    D) 5

二.问题求解:(6+8=14分}

1.在书架上放有编号为1,2,....n的n本书。现将n本书全部取下然后再放回去,当放回去时要求每本书都不能放在原来的位置上。例如:n=3时:

原来位置为:123

放回去时只能为:312或231这两种

问题:求当n=5时满足以上条件的放法共有多少种?(不用列出每种放法)

2.设有一棵k叉树,其中只有度为0和k两种结点,设n0,nk分别表示度为0和度为k的结点个数,试求出n0,nk之间的关系(n0=数学表达式,数学表达式仅含nk,k和数字)

三.阅读程序,写出正确的程序运行结果:{8+9+9=26分)

1.pmgram Gxp1;

var n,jr,jw,jb:integer;

ch1:char;

ch:array[1..20]d char;

begin

readln(n);

for i:=1 to n do read(ch[i]):

jr:=1;jwz=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+13

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[i]);

writeln;

end.

输入:10

RBRBWWRBBR

输出:

2.pmgram 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 u

begin

j :=j+1;p:=true;

for i:=2 to j-1 do

if(j mod i=O)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ωj do s:=s*a[I];

s:=s +1;

for i:=2 to s-1 do

if S mod i=O then p:=false;

j :=j+1;

end;

writeln(s);writeln;

end.

输出:

3.pmgram Gxp3

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:1O:2);

end.

输出:

四.完善程序:(15+15=30分)

1.问题描述:工厂在每天的生产中,需要一定数量的零件,同时也可以知道每天生产一个零件的生产单价。在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]];

fori:=1 to n do e[i]:=0;

   ①   :=10000;c[n+2]:=0;b[n+1]:=0;jO:=1;

while (jO<=n)do

begin

yu:=c[j0]; j1:=jO; s:=b[j0];

while    ②    do

begin

     ③    j1:=j1+1;s:=s+b[j1];

end;

   ④      jO:=j1+1;

end;

for i:=1 to n do      ⑤      

readln;

end.

2.问题描述:有n种基本物质(n≤10),分别记为P1,P2,……,Pn,用n种基本物质构造物品,这些物品使用在k个不同地区(k≤20),每个地区对物品提出自己的要求,这些要求用一个n

位的数表示:α₁α₂……αn,其中:

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

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

=0无所谓

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

程序说明:数组b[1],b[2],...,b[nJ表示某种物品

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]d 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:=O 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 :=1to 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.