全国青少年信息学奥林匹克联赛初赛练习卷(二)答案

1、全国青少年信息学奥林匹克联赛初赛练习卷（二）(普及组PASCAL语言 二小时完成) 全部试题答案均要求写在答卷纸上，写在试卷纸上一律无效 一、单项选择题（20题，每题1.5分，共30分）1. 完全二叉树的结点个数为11，则它的叶结点个数为（   ）。   A. 4    B. 3    C. 5    D. 2    E. 6 （最后一个分支结点：n2=112=5，故叶子有6个）2. 平面上有五个点A(5,3)、B(3,5)、C(2,1

2、)、D(3,3)、E(5,1)，以这五点作为完全图G的顶点，每两点之间的直线距离是图G中对应边的权值。以下哪条边不是图G的最小生成树中的边（   ）。   A. AD    B. BD    C. CD    D. DE    E. EA3. Intel的首颗16位处理器是（   ）。A.8088    B.80386    C.80486 

3、60;  D.8086    E.Pentium（The first chip used in PCs was Intel's 8088. This was not, at the time it was chosen, the best available CPU, . The 8088 was chosen for reasons of economics: its 8-bit data bus required less costly motherboards than the 16-bit 8086.）4. 下列活动中不属于信息学奥赛的系

4、列活动的是（   ）。   A. NOIP    B. NOI    C. IOI    D. 冬令营    E. 程序员等级考试5. 以下哪个软件不是即时通信软件（   ）。   A.网易泡泡    B.MSN Messenger    C.Google Talk    D.3DS Max 

5、60;  E.QQ6. 下列关于高级语言的说法错误的是（   ）。A. Fortran是历史上的第一个面向科学计算的高级语言B. Pascal和C都是编译执行的高级语言C. C+是历史上的第一个支持面向对象的语言D. 编译器将高级语言程序转变为目标代码E. 高级语言程序比汇编语言程序更容易从一种计算机移植到另一种计算机上7. 常见的邮件传输服务器使用（   ）协议接收邮件。   A.HTTP    B.SMTP    C.TCP   

6、D.FTP    E.POP38. 一位艺术史学家有20000幅真彩色图像，每幅图像约占3M空间。如果将这些图像以位图形式保存在CD光盘上（一张CD光盘的容量按600M计算），大约需要（   ）张CD光盘。   A. 1    B. 10    C. 100    D. 1000    E. 100009. 设A=true，B=false，C=false，D=true，以下逻辑运算表达式值为真的是（

7、0;  ）。   A. (AB)(CD)    B. (AB)C)D    C. A(BC)D)   D. (A(BC)D    E. (AB)(CD)10. (3725)8 + (B)16的运算结果是（   ）。   A. (3736)8    B. (2016)10    C. (1111110000)2    D. (30

8、06)10    E. (7B0)1611. 二叉树T的宽度优先遍历序列为A B C D E F G H I（也是二叉树中结点编号的顺序），已知A是C的父结点，D是G的父结点，F是I的父结点，树中所有结点的最大深度为3（根结点深度设为0），可知F的父结点是（   ）。ABCDEFGIH    A. 无法确定    B. B     C. C     D. D     E. E12. 美籍匈牙利数学家 冯&#

9、183;诺依曼 对计算机科学发展所做出的贡献是：（ ） A、提出理想计算机数学模型，成为计算机科学理论基础 B、是世界上第一个编写计算机程序的人 C、提出存储程序工作原理，并设计出第一台具有存储程序功能的计算机EDVAC D、采用集成电路作为计算机的主要功能部件 E、指出计算机性能将以每两年翻一番的速度向前发展13. 下列哪个不是CPU（中央处理单元）（ ） A、Intel Itanium （安腾，64位处理器） B、DDR SDRAM C、AMD Athlon64（速龙，64位的处理器；Sempron：闪龙；Turion：炫龙，双核64位） D、AMD Opteron （皓龙，64位） E、

10、IBM Power 5 （64位微处理器芯片）14. 下列网络中常用的名字缩写对应的中文解释错误的是（ ） A、WWW(World Wide Web)：万维网 B、URL（Uinform Resource Locator）：统一资源定位器 C、HTTP（Hypertext Transfer Protocol）：超文本传输协议 D、FTP (File Transfer Protocol)：快速传输协议 E、TCP （Transfer Control Protocol）：传输控制协议15. 下列哪个软件属于操作系统软件（ ） A、Microsoft Word B、金山词霸 C、Foxmail D、

11、WinRAR E、Red Hat Linux16. 下列说法中错误的是（ ） A、CPU的基本功能就是执行指令 B、CPU访问内存的速度快于访问高速缓存的速度 C、CPU的主频是指CPU在1秒内完成的指令周期数 D、在一台计算机内部，一个内存地址编码对应唯一的一个内存单元 E、数据总线的宽度决定了一次传递数据量的大小17. 彩色显示器所显示的五彩斑斓的色彩，是由红色，蓝色和（ ）色混合而成的 A、紫色 B、白色 C、黑色 D、绿色 E、橙色18. 用静电吸附磨粉后转移到纸张上，是那种输出设备的工作方式（ ） A、针式打印机 B、喷墨打印机 C、激光打印机 D、笔式绘图仪 E、喷墨绘图仪19.

12、一台计算机如果要利用电话线上网，就必须配置能够对数字信号和模拟信号进行互相转换的设备，这种设备是（ ） A、调制解调器 B、路由器 C、网卡 D、网关 E、网桥20. 下列哪个不是数据库软件的名称（ ） A、MYSQL B、SQL Sever C、Oracle D、金山影霸E、Foxpro二、问题求解（请在空格处填上答案，每空5分，共10分）1. 一个家具公司生产桌子和椅子。现有113个单位的木材。每张桌子要使用20个单位的木材，售价是30元；每张椅子要用16个单位的木材，售价是20元。使用已有的木材生产桌椅（不一定要用光木材）做多可以卖_160_元钱。2. 75名儿童去游乐场玩。他们可以骑旋

13、转木马，坐滑行轨道，乘宇宙飞船。已知其中20人这三种东西都玩过，55人至少玩过其中两种。若每玩一样的费用为5元，游乐场总共收入700，可知有_10_名儿童没有玩过其中任何一种。3. 设t(n, i)表示数列：1，2，3，n，2，3，4，n+1，3，4，5，n+2，的第i项，而s(n, i)表示该数列的前i项之和。 例如：t(4, 6)是数列：1，2，3，4，2，3，4，5，3，的第6项，所以t(4,6)=3，而s(4,6)=1+2+3+4+2+3=15。 请算出： t(8,35) s(8,35) t(13,350) s(13,350)答：t(n,i)=(i div n) + 1) + (i m

14、od n - 1)s(n,i)=1+2+3+n+ +2+3+n+n+1+ 每一段的和都比上一段的和多n (i div n)+1)+(i div n)+2)+(i div n)+ 1)+(i mod n-1) =(1+n)n/2+末项项数 (2+n+1)n/2+ (i div n)+1)+(i div n)+ 1)+(i mod n-1) (i mod n)/2 =(1+n)n/2)(i div n)+( i div n-1)n+(2(i div n)+ 1)+(i mod n-1) (i mod n)/2因此：t(8,35)= (i div n) + 1) + (i mod n - 1) =(

15、35 div 8 + 1) + (35 mod 8 - 1)=5+2=7s(8,35)=(1+8)8/2)(35 div 8)+(35 div 8 1)8+( 35 div 8+1+7)(35 mod 8)/2 =36*4+24+12*3/2=186 （应是210？）t(13,350)=(350 div 13 + 1) + (350 mod 13 - 1)=27+11=38s(13,350)=(1+13)13/2(350 div 13)+ (350 div 13 1)13+( 2(350 div 13+1)+(350 mod 13 -1)(350 mod 13)/2 =91*26+26*13+

16、(54+11)*12/2=3094 （应是6981？）三、阅读程序（共4题，每题8分，共计32分）1. vara,b : integer;beginread(a);b := (a *(a*a) + 1;if b mod 3 = 0 then b := b div 3;if b mod 5 = 0 then b := b div 5;if b mod 7 = 0 then b := b div 7;if b mod 9 = 0 then b := b div 9;if b mod 11 = 0 then b := b div 11;if b mod 13 = 0 then b := b div

17、13;if b mod 15 = 0 then b := b div 15;writeln(100*a-b) div 2);end.输入：10输出：_499 _2. var   str: string;   i: integer;   beginstr := 'Today-is-terrible!'  for i := 7 to 11 do    if stri = '-' then stri-1 := 'x'   

18、for i := 13 downto 1 do      if stri = 't' then stri+1 := 'e'writeln(str);end.输出：_ Today-ix-terrible!_3. vara, b, c, p, q: integer;r: array0.2 of integer;beginread(a,b,c);p := a div b div c; p=100 div 7 div 3 = 4q := b - c + a + p; q=7 3 + 100 + 4 = 108r0 :=

19、a * p div q *q; r0=100 * 4 div 108 * 108 = 324r1 := r0 * (r0 - 300); r1=324 * (324 - 300) = 7776if (3 * q - p mod 3 <= r0) and (r2 =r2) then 3*108-4 mod 3=323<=324r1 := rr0 div p mod 2 r1=r324 div 4 mod 2=r81 mod 2=r1=7776else r1 := rr0 div p mod 2;writeln(r0 - r1); 324 7776 = -7452end.输入：100

20、7 3输出：_-7452_正确的程序：vara, b, c, p, q: integer;r: array0.2 of integer;beginread(a,b,c);p := a div b div c;q := b - c + a + p;r0 := a * p div q *q;r1 := r0 * (r0 - 300);if (3 * q - p mod 3 <= r0) and (r2 =r2) thenr1 := rr0 div p mod 2else r1 := q mod p;writeln(r0 - r1);end.输入：100 7 3输出：-74524. varst

21、r : string;  len,i,j : integer;  nchr : array0.25 of integer;  mmin : char;begin  mmin := 'z'  readln(str); len := length(str);  i := len;  while i>= 2 do begin    if stri - 1 < stri then break; dec(i)

22、; i=4  end;  if i = 1 then begin     writeln('No result!'); exit;  end;  for j := 1 to i - 2 do write (strj); zz  fillchar(nchr,sizeof(nchr),0);  for j := i to len do begin    if (strj > stri -

23、1) and (strj < mmin) then   mmin := strj;   inc(nchrord(strj) - ord('a');  end;  dec(nchrord(mmin) - ord('a');  inc(nchrord(stri - 1) - ord('a');  write(mmin);  for i := 0 to 25 do    for

24、j := 1 to nchri do      write(chr(i + ord('a');  writeln;end.输入：zzyzcccbbbaaa输出：_ zzzaaabbbcccy _四、完善程序 ( 前8个空每空3分，最后一个空4分，共28分）1. 三角形内切圆的面积题目描述：给出三角形三边的边长，求此三角形内切圆的面积。输入：三个正实数a、b、c（满足三角形三边关系），表示三角形三边边长。输出：三角形内切圆的面积，结果四舍五入到小数点后2位输入样例： 3 4 5输出样例： 3.14程序：program p

25、rogram1;var a,b,c,r,s,t:real;begin read(a,b,c); s :=( a + b + c )/2; t:= sqrt (s*(s-a)*(s-b)*(s-c); r:=t/s; writeln(3.1415927 * r * r :0: 2 );end.2. 木材加工题目描述：木材厂有一些原木，现在想把这些木头切割成一些长度相同的小段木头（木头有可能有剩余），需要得到的小段的数目是给定的。当然，我们希望得到的小段越长越好，你的任务是计算能够得到的小段木头的最大长度。木头长度的单位是cm。原木的长度都是正整数，我们要求切割得到的小段木头的长度也是正整数。输入

26、：第一行是两个正整数N和K（1 N 10000，1 K 10000），N是原木的数目，K是需要得到的小段的数目。接下来的N行，每行有一个1到10000之间的正整数，表示一根原木的长度。输出：输出能够切割得到的小段的最大长度。如果连1cm长的小段都切不出来，输出"0"。输入样例：3 7     232 114 * 2 = 228，切割成两段     124 114 * 1 = 124，切割成一段     456 114 * 4 = 456，切割成4段，总共7

27、段输出样例：     114程序：varn, k :integer;len : array1.10000 of integer;i,left,right,mid : integer;function isok(t : integer) : boolean;varnum,i : integer;beginnum := 0;for i := 1 to n do begin 在当前最大小段长度t下，对n根木材进行计算if num >= k then break; 达到给定的小段数目了，OK  num :=  

28、60; num + leni div t  ; 计算每根木材可以切割出的小段数end;if    num >= k  （或num<k） then isok := true 线索；思考：怎样才叫做“行”？else isok :=false;end;beginreadln(n,k);right := 0;for i := 1 to n do beginreadln(leni);if right < leni then right := leni; 找最大木材长度end;inc(right);  

29、60; left := 0   ; right比最大木材长度多1。注意，不能是left=1while   left + 1   < right do  begin 注意不能是leftmid := (left + right) div 2;取左右的中点；这是线索，说明应在前面对left赋值if    not isok(mid) （或 isok(mid) = false）（或isok(mid)，与上面的num<k呼应） then right := mid 这儿该调用函数了else left := mid;end;of while loopwriteln(left);end.或者：Right不加1；Left的初值为1；While left <= right do或while left < right do；（后一种写法更好）循环体改为right := mid -1; left := mid + 1; 此外，循环体中应加一个判断，即判断mid如果为0了，直接跳出，否则会出现被0除的情况。打印改为left 1;3. Joseph问题题目描述：原始的Joseph问题的描述如下：有n个人围坐在一个圆桌周围，把这n个人依次编号为1，n。从编号是1 的人开始