搜索
第八届全国青少年信息学奥林匹克联赛（NOIP2002）初赛试题（提高组PASCAL语言二小时完成）●●全部试题答案均要求写在答卷纸上，写在试卷纸上一律无效●●一．选择一个正确答案代码（A/B/C/D），填入每题的括号内（每题1.5分，多选无分，共30分）1．微型计算机的问世是由于（）的出现。A）中小规模集成电路B）晶体管电路C）（超）大规模集成电路D）电子管电路2．中央处理器（CPU）能访问的最大存储器容量取决于（）。A）地址总线B）数据总线C）控制总线D）实际内存容量3．十进制书11/128可用二进制数码序列表示为：（）。A）1011/1000000B）1011/100000000C）0.001011D）0.00010114．算式（2047）10－（3FF）16＋（2000）8的结果是（）。A）（2048）10B）（2049）10C）（3746）8D）（1AF7）165．已知x=（0.1011010）2，则[x/2]补=（）2。A）0.1011101B）11110110C）0.0101101D）0.1001106．IPv4地址是由（）位二进制数码表示的。A）16B）32C）24D）87．计算机病毒传染的必要条件是：（）。A）在内存中运行病毒程序B）对磁盘进行读写操作C）在内存中运行含有病毒的可执行的程序D）复制文件8．在磁盘上建立子目录有许多优点，下列描述中不属于建立子目录优点的是（）。A）便于文件管理B）解决根目录中目录项个数有限问题C）加快文件查找速度D）节省磁盘使用空间9．在使用E-mail前，需要对Outlook进行设置，其中ISP接收电子邮件的服务器称为（）服务器。A）POP3B）SMTPC）DNSD）FTP10．多媒体计算机是指（）计算机。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）110B）108C）100D）10915．已知A=35H，A/\05H\/A/\30H的结果是：（）。A）30HB）05HC）35HD）53H16．设有一个含有13个元素的Hash表（0~12），Hash函数是：H（key）=key%13，，其中%是求余数运算。用线性探查法解决冲突，则对于序列（2、8、31、20、19、18、53、27），18应放在第（）号格中。A）5B）9C）4D）017．按照二叉数的定义，具有3个结点的二叉树有（）种。A）3B）4C）5D）618．在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的（）倍。A）1/2B）1C）2D）419．要使1．．．8号格字的访问顺序为：8、2、6、5、7、3、1、4，则下图中的空格中应填入（）。12345678461-1732A）6B）0C）5D）320．设栈S和队列Q的初始状态为空，元素e1，e2，e3，e4，e5，e6依次通过栈S，一个元素出栈后即进入队列Q，若出队的顺序为e2，e4，e3，e6，e5，e1，则栈S的容量至少应该为（）。A）2B）3C）4D）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．programGxp1;vari,n,jr,jw,jb:integer;ch1:char;ch:array[1..20]ofchar;beginreadln(n);fori:=1tondoread(ch[i]);jr:=1;jw:=n;jb:=n;while(jr=jw)dobeginif(ch[jw]=’R’)thenbeginch1:=ch[jr];ch[jr]:=ch[jw];ch[jw]:=ch1;jr:=jr+1;endelseifch[jw]=’W’thenjw:=jw-1;elsebeginch1:=ch[jw];ch[jw]:=ch[jb];ch[jb]:=ch1;jw:=jw-1;jb:=jb-1;endend;fori:=1tondowrite(ch[1]);writeln;end.输入：10RBRBWWRBBR输出：2．programGxp2;vari,j,s,sp1:integer;p:boolean;a:array[1..10]ofinteger;beginsp1:=1;a[1]:=2;j:=2;whilesp110dobeginj:=j+1;p:=true;fori:=2toj-1doif(jmodi=0)thenp:=false;ifpthenbeginsp1:=sp1+1;a[sp1]:=j;end;end;j:=2;p:=true;whilepdobegins:=1;fori:=1tojdos:=s*a[i];s:=s+1;fori:=2tos-1doifsmodi=0thenp:=false;j:=j+1;end;writeln(s);writeln;end.输出：3．ProgramGxp2Vard1,d2,X,Min:real;beginMin:=10000;X:=3;whileX15dobegind1:=sqrt(9+(X-3)*(X-3));d2:=sqrt(36+(15-X)*(15-X));if(d1+d2)MinthenMin:=d1+d2;X:=x+0.001;end;writeln(Min:10:2);end.输出：四．完善程序：（15+15=30分）1．问题描述：工厂在每天的生产中，需要一定数量的零件，同时也可以知道每天生产一个零件的生产单价。在N天的生产中，当天生产的零件可以满足当天的需要，若当天用不完，可以放到下一天去使用，但要收取每个零件的保管费，不同的天收取的费用也不相同。问题求解：求得一个N天的生产计划（即N天中每天应生产零件个数），使总的费用最少。输入：N（天数N=29）每天的需求量（N个整数）每天生产零件的单价（N个整数）每天保管零件的单价（N个整数）输出：每天的生产零件个数（N个整数）例如：当N=3时，其需要量与费用如下：第一天第二天第三天需要量251530生产单价203032保管单价5100生产计划的安排可以有许多方案，如下面的三种：第一天第二天第三天总的费用25153025*20+15*30+30*32=19104003040*20+15*5+30*32=1835700070*20+45*5+30*10=1925程序说明：b[n]：存放每天的需求量c[n]：每天生产零件的单价d[n]：每天保管零件的单价e[n]：生产计划程序：programexp5;vari,j,n,yu,j0,j1,s:integer;b,c,d,e:array[0..30]ofinteger;beginreadln(n);fori:=1tondoreadln(b[i],c[i],d[i]);fori:=1tondoe[i]:=0;①__________:=10000;c[n+2]=0;b[n+1]:=0j0:=1;while(j0=n)dobeginyu:=c[j0];j1:=j0;s:=b[j0];while②__________dobegin③__________j1:=j1+1;s:=s+b[j1];end;④__________j0:=j1+1;end;fori:=1tondo⑤__________readln;end.二．问题描述：有n种基本物质（n≤10），分别记为P1，P2，……，Pn，用n种基本物质构造物质，这些物品使用在k个不同地区（k≤20），每个地区对物品提出自己的要求，这些要求用一个n位的数表示：a1a2……an，其中：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种物品是不需要的程序：programgxp2;vari,j,k,n:integer;p:boolean;b:array[0..20]of0..1;a:array[1..20,1..10]ofinteger;beginreadln(n,k);fori:=1tokdobeginforj:=1tondoread(a[i,j]);readln;end;fori:=0tondob[i]:=0;p:=true;while①__________dobeginj:=n;whileb[j]=1doj:=j-1;②__________fori:=j+1tondob[i]:=0;③__________fori:=1tokdoforj:=1tondoif(a[i,j]=1)and(b[j]=0)or④__________thenp:=true;end;if⑤__________thenwriteln(‘找不到！’)elsefori:=1tondoif(b[i]=1)thenwriteln(‘物质’,i,’需要’)elsewriteln(‘物质’,i,’不需要’);end.