第八届全国青少年信息学奥林匹克联赛(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)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.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,则下图中的空格中应填入( ) 。
12345678
461-1 732
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.program Gxp1;
var n,jr,jw,jb,i: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[i]);
writeln;
READLN;
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时,其需要量与费用如下:
第一天第二天第三天
需要量251530
生产单价203032
保管单价5l00
生产计划的安排可以有许多方案,如下面的三种:
第一天第二天第三天总的费用
25153025*2O+15*30+30*32=1910
4003040*20+15*5+30*32=1835
700070*20+45*5+30*10=1925
程序说明:
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
位的数表示:α1α2……α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.
NOI2002初赛试题参考答案
提高组
一、选择题
题号1 2 3 4 5 6 7 8 9 10
答案CA D A C B B D A D
题号11121314151617181920
答案 C B C B C B C B C B
二、问题解答
1、 44
2、 N0 = (K－1) Nk +1
三、读程序写结果
1、RRRRWWBBBB
2、30031
3、15.00(PASCAL) 15(BASIC)
四、补充程序
题一：
1、 c[n+1]
2、 (yu+d[j1]<c[j1+1])
3、 yu:=yu+d[j1];
4、 e[j0]:=s;
5、 write(e[I]:4);
题二：
1、P AND (B[0]=0)
2、B[J]：=1；
3、P：=FALSE；
4、（A[I，J]=－1） AND （B[J]=1）
5、P |
