02高初试题.doc

2002 全国分区联赛 高中组（初赛）第八届全国青少年信息学奥林匹克联赛（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/1000000 B)1011/100000000 C) 0.001011 D) 0.00010114. 算式(2047)10(3FF)16(2000)8的结果是( ) 。A)(2048)10 B)(2049)10 C) (3746)8 D) (1AF7)165. 已知x=(0.1011010)2，则x/2补=( ) 2 。A) 0.1011101. B) 11110110 C) 0.0101101 D) 0.1001106. Ip v4地址是由( ) 位二进制数码表示的。A)16 B)32 C) 24f D) 87. 计算机病毒传染的必要条件是:( ) 。A) 在内存中运行病毒程序 B) 对磁盘进行读写操作C) 在内存中运行含有病毒的可执行程序 D) 复制文件8. 在磁盘上建立子目录有许多优点,下列描述中不属于建立子目录优点的是( ) 。A) 便于文件管理 B) 解决根目录中目录项个数有限问题C) 加快文件查找速度 D) 节省磁盘使用空间9. 在使用E-mail前，需要对Outlook进行设置,其中ISP接收电子邮件的服务器称为( )服务器。A)POP3 B)SMTP C) DNS D) FTP10. 多媒体计算机是指( ) 计算机。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) 10915.已知A=35H，则A05HA3OH的结果是:( ) 。A)30H B)05H C) 35H D) 53H16.设有一个含有13个元素的Hash表(012)，Hash函数是:H(key)=key % 13，其中%是求余数运算。用线性探查法解决冲突，则对于序列(2、8、31、20、19、18、53、27)，18应放在第几号格中( ) 。A) 5 B) 9 C) 4 D) 017.按照二叉树的定义，具有3个结点的二叉树有( ) 种。A) 3 B) 4 C) 5 D) 618.在一个有向图中,所有顶点的入度之和等于所有顶点的出度之和的( ) 倍。A) 1/2 B)1 C) 2 D) 419.要使1.8号格子的访问顺序为:8、2、6、5、7、3、1、4,则下图中的空格中应填入( ) 。12345678461-1732A) 6 B) 0 C) 5 D) 320.设找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时:原来位置为: 1 2 3放回去时只能为: 3 1 2 或 2 3 1 这两种问题: 求当n=5时满足以上条件的放法共有多少种?(不用列出每种放法)2. 设有一棵k叉树，其中只有度为0和k两种结点，设n0，nk 分别表示度为0和度为k的结点个数，试求出n0，nk之间的关系 ( n0 = 数学表达式，数学表达式仅含nk 、k和数字)。三阅读程序，并写出正确的运行结果（8 + 9 + 9 = 26分）1.program Gxp1;var i,n,jr,jw,jb : integer; ch1 : char; ch : array1.20d char; beginreadln(n);for i:=1 to n do read(chi):jr:=1; jwz=n; jb:=n;:while (jr<=jw) dobeginif (chjw='R')then beginch1:=Chjr; chjr:=chjw; chjw:=ch1: jr:=jr+1;endelse if chjw='W'then jw:=jw-1else beginch1:=chjw;chjw:=chjb;chjb:=ch1;jw:=jw-1;jb:=jb-1;end;end;for i:=1 to n do write(chi);writeln;end.输入: 10RBRBWWRBBR输出:2. program Gxp2; var i,j,s,sp1 : integer; p : boolean;a : array1.10 of integer; beginsp1:=1; a1:=2; j:=2:while sp1<10 dobeginj:=j+1; p:=true;for i:=2 to j-1 doif (j mod i=O) then p:=false;if p then beginsp1:=sp1+1; asp1:=j;end;end; j:=2; p:=true;while p dobegin s:=1;for i:=1 to j do s:=s*ai;s:=s+1;for i:=2 to s-1 doif s mod i=O then p:=false;j:=j+1; end;writeln(s); writeln;end.输出: 3. program Gxp3var d1,d2,X,Min : real;beginmin:=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 = 19104003040 * 20 + 15 * 5 + 30 * 32 = 1835700070 * 20 + 45 * 5 + 30 * 10 = 1925程序说明：bn：存放每天的需求量cn：每天生产零件的单价dn：每天保管零件的单价en：生产计划程序：Program exp5;Vari,j,n,yu,j0,j1,s:integer;b,c,d,e: array0.30of integer;beginreadln(n);for i:=1 to n do readln(bi,cI,di;fori:=1 to n do ei:=0; :=10000;cn+2:=0;bn+1:=0;jO:=1;while (jO<=n)dobeginyu:=cj0; j1:=jO; s:=bj0;while dobegin j1:=j1+1;s:=s+bj1; end; jO:=j1+1;end;for i:=1 to n do readln; end.2.问题描述: 有n种基本物质(n10)，分别记为P1,P2,Pn，用n种基本物质构造物品，这些物品使用在k个不同地区(k20)，每个地区对物品提出自己的要求，这些要求用一个n位的数表示：12n ，其中：i = 1 表示所需物质中必须有第i种基本物质=-1 表示所需物质中必须不能有第i种基本物质= 0 无所谓问题求解: 当k个不同地区要求给出之后，给出一种方案，指出哪些物质被使用，哪些物质不被使用。程序说明: 数组b1,b2,.,bn 表示某种物品a1.k,1.n 记录k个地区对物品的要求，其中:ai,j= 1 表示第i个地区对第j种物品是需要的ai,j= 0 表示第i个地区对第j种物品是无所谓的ai,j=-1 表示第i个地区对第j种物品是不需要的程序:program gxp2;var i, j ,k, n : integer;p : boolean;b : array 0.20 of 0.1; a : array1.20,1.10 of integer; beginreadln(n,k);for i:=1 to k dobeginfor j:=1 to n do read(ai,j);readln;end;for i:=O to n do bi:=0;p:=true; while do begin j:=n;while bj=1 do j:=j-1; for i:=j+1 to n do bi:=0; for i:=1 to k do for j :=1to n do if( ai,j=1 ) and (bj=0) or then p:=true;end;if then writeln('找不到! ')else for i:=1 to n doif (bi=1) then writeln('物质',i, '需要')else writeln('物质',i,'不需要');end.·7·