NOIP2006提高组初赛题目答案

第十二届全国青少年信息学奥林匹克联赛初赛试题（提高组Pascal语言二小时完成）●●全部试题答案均要求写在答卷纸上，写在试卷纸上一律无效●●一、单项选择题（共10题，每题1.5分，共计15分。每题有且仅有一个正确答案.）。1.在以下各项中。（）不是CPU的组成部分。A.控制器B.运算器C.寄存器D.ALUE.RAM2.BIOS（基本输入输出系统）是一组固化在计算机内（）上一个ROM芯片上的程序。A.控制器B.CPUC.主板D.内存条E.硬盘3.在下面各世界顶级的奖项中，为计算机科学与技术领域作出杰出贡献的科学家设立的奖项是（）。A.沃尔夫奖B.诺贝尔奖C.菲尔兹奖D.图灵奖E.南丁格尔奖4．在编程时（使用任一种高级语言，不一定是Pascal），如果需要从磁盘文件中输入一个很大的二维数组（例如1000*1000的double型数组），按行读（即外层循环是关于行的）与按列读（即外层循环是关于列的）相比，在输入效率上（）。A.没有区别B.有一些区别，但机器处理速度很快，可忽略不计C.按行读的方式要高一些D.按列读的方式要高一些E.取决于数组的存储方式。5．在Pascal语言中，表达式(21xor2)的值是（）A.441B.42C.23D.24E.256．在Pascal语言中，判断a不等于0且b不等于0的正确的条件表达式是（）A.nota=0ornotb=0B.not((a=0)and(b=0))C.not(a=0andb=0)D.(a0)or(b0)E.(a0)and(b0)7．某个车站呈狭长形，宽度只能容下一台车，并且只有一个出入口。已知某时刻该车站状态为空，从这一时刻开始的出入记录为：“进，出，进，进，进，出，出，进，进，进，出,出”。假设车辆入站的顺序为1，2，3，……，则车辆出站的顺序为（）。A.1,2,3,4,5B.1,2,4,5,7C.1,4,3,7,6D.1,4,3,7,2E.1,4,3,7,58．高度为n的均衡的二叉树是指：如果去掉叶结点及相应的树枝，它应该是高度为n-1的满二叉树。在这里，树高等于叶结点的最大深度，根结点的深度为0，如果某个均衡的二叉树共有2381个结点，则该树的树高为（）。A.10B.11C.12D.13E.210–19.与十进制数1770.625对应的八进制数是（）。A.3352.5B.3350.5C.3352.1161D.3350.1151E.前4个答案都不对???10．将5个数的序列排序，不论原先的顺序如何，最少都可以通过（）次比较，完成从小到大的排序。A.6B.7C.8D.9E.10二、不定项选择题（共10题，每题1.5分，共计15分。每题正确答案的个数大于或等于1。多选或少选均不得分）。11.设A=B=D=true，C=E=false，以下逻辑运算表达式值为真的有（）。A.(A∧B)∨(C∧D)∨EB.(((A∧B)∨C)∧D∧E)C.A∧(B∨C∨D∨E)D.(A∧(B∨C))∧D∧E12.(2010)16+(32)8的结果是（）。A.(8234)10B.(202A)16C.(100000000110)2D.(2042)1613.设栈S的初始状态为空，元素a,b,c,d,e依次入栈，以下出栈序列不可能出现的有（）。A.a,b,c,e,dB.b,c,a,e,dC.a,e,c,b,dD.d,c,e,b,a14.已知6个结点的二叉树的先根遍历是123456（数字为结点的编号，以下同），后根遍历是325641，则该二叉树的可能的中根遍历是（）A.321465B.321546C.231546D.23146515.在下列各数据库系统软件中，以关系型数据库为主体结构的是（）。A.ACCESSB.SQLServerC.OracleD.Foxpro16.在下列各软件中，属于NOIP竞赛（复赛）推荐使用的语言环境有（）。A.gcc/g++B.TurboPascalC.TurboCD.freepascal17.以下断电之后将不能保存数据的有（）。A.硬盘B.ROMC.显存D.RAM18.在下列关于计算机语言的说法中，正确的有（）。A.Pascal和C都是编译执行的高级语言B.高级语言程序比汇编语言程序更容易从一种计算机移植到另一种计算机上C.C++是历史上的第一个支持面向对象的计算机语言D.高级语言比汇编语言更高级，是因为它的程序的运行效率更高19.在下列关于计算机算法的说法中，正确的有（）。A.一个正确的算法至少要有一个输入B.算法的改进，在很大程度上推动了计算机科学与技术的进步C.判断一个算法的好坏，主要依据它在某台计算机上具体实现时的运行时间D.目前仍然存在许多涉及到国计民生的重大课题，还没有找到能够在计算机上实施的有效算法20.在下列关于青少年信息学竞赛的说法中，你赞成的是（）（本题不回答为0分，答题一律满分）。A.举行信息学竞赛的目的，是为了带动广大青少年学科学、爱科学，为造就一大批优秀的计算机科学与技术人才奠定良好的基础B.如果竞赛优胜者不能直接保送上大学，我今后就不再参与这项活动了C.准备竞赛无非要靠题海战术，为了取得好成绩，就得拼时间、拼体力D.为了取得好成绩，不光要看智力因素，还要看非智力因素。优秀选手应该有坚韧不拔的意志，有严谨求实的作风，既要努力奋进，又要胜不骄败不馁三．问题求解（共2题，每题5分，共计10分）1．将2006个人分成若干不相交的子集，每个子集至少有3个人，并且：（1）在每个子集中，没有人认识该子集的所有人。（2）同一子集的任何3个人中，至少有2个人互不认识。（3）对同一子集中任何2个不相识的人，在该子集中恰好只有1个人认识这两个人。则满足上述条件的子集最多能有__________个？2．将边长为n的正三角形每边n等分，过每个分点分别做另外两边的平行线，得到若干个正三角形，我们称为小三角形。正三角形的一条通路是一条连续的折线，起点是最上面的一个小三角形，终点是最下面一行位于中间的小三角形。在通路中，只允许由一个小三角形走到另一个与其有公共边的且位于同一行或下一行的小三角形，并且每个小三角形不能经过两次或两次以上（图中是n=5时一条通路的例子）。设n=10，则该正三角形的不同的通路的总数为____________。四．阅读程序写结果（共4题，每题8分，共计32分）1.Programex401;varu,v:array[0..3]ofinteger;i,x,y:integer;beginx:=10;y:=10;fori:=0to3doread(u[i]);v[0]:=(u[0]+u[1]+u[2]+u[3])div7;v[1]:=u[0]div((u[1]-u[2])divu[3]);v[2]:=u[0]*u[1]divu[2]*u[3];v[3]:=v[0]*v[1];x:=(v[0]+v[1]+2)-u[(v[3]+3)mod4];if(x10)theny:=y+(v[2]*100-v[3])div(u[u[0]mod3]*5)elsey:=y+20+(v[2]*100-v[3])div(u[v[0]mod3]*5);writeln(x,',',y);end.{*注：本例中，给定的输入数据可以避免分母为0或下标越界。)输入：9394输出：_______________2.Programex402;constm:array[0..4]ofinteger=(2,3,5,7,13);vari,j:integer;t:longint;beginfori:=0to4dobegint:=1;forj:=1tom[i]-1dot:=t*2;t:=(t*2-1)*t;write(t,'');end;writeln;end.输出:3.Programex403;ConstNN=7;TypeArr1=array[0..30]ofchar;vars:arr1;k,p:integer;functionfun1(s:arr1;a:char;n:integer):integer;varj:integer;beginj:=n;while(as[j])and(j0)dodec(j);fun1:=j;end;Functionfun2(s:arr1;a:char;n:integer):integer;varj:integer;beginj:=1;while(as[j])and(jn)doinc(j);fun2:=j;end;beginfork:=1toNNdos[k]:=chr(ord('A')+2*k+1);k:=fun1(s,'M',NN)+fun2(s,'M',NN);writeln(k);end.输出：4.programex404;varx,x2:longint;proceduredigit(n,m:longint);varn2:integer;beginif(m0)thenbeginn2:=nmod10;write(n2:2);if(m1)thendigit(ndiv10,mdiv10);n2:=nmod10;write(n2:2);end;end;beginwriteln('Inputanumber:');readln(x);x2:=1;while(x2x)dox2:=x2*10;x2:=x2div10;digit(x,x2);writeln;end.输入：9734526输出：Inputanumber:五．完善程序(前5空，每空2分，后6空，每空3分，共28分)1．（选排列）下面程序的功能是利用递归方法生成从1到n(n10)的n个数中取k(1=k=n)个数的全部可能的排列（不一定按升序输出）。例如，当n=3，k=2时，应该输出（每行输出5个排列）：121321233231程序：Programex501;Vari,n,k:integer;a:array[1..10]ofinteger;count:longint;Procedureperm2(j:integer);vari,p,t:integer;beginif（1）thenbeginfori:=ktondobegininc(count);t:=a[k];a[k]:=a[i];a[i]:=t;for（2）dowrite(a[p]:1);write('');t:=a[k];a[k]:=a[i];a[i]:=t;if(countmod5=0)thenwriteln;end;exit;end;fori:=jtondobegint:=a[j];a[j]:=a[i];a[i]:=t;（3）t:=a[j];（4）endend;beginwriteln('Entryn,k(k=n):');read(n,k);count:=0;fori:=1tondoa[i]:=i;（5）end.2．（TSP问题的交叉算子）TSP问题(TravelingSalesmanProblem)描述如下：给定n个城市，构成一个完全图，任何两城市之间都有一个代价（例如路程、旅费等），现要构造遍历所有城市的环路，每个城市恰好经过一次，求使总代价达到最小的一条环路。遗传算法是求解该问题的一个很有效的近似算法。在该算法中，一个个体为一条环路，其编码方法之一是1到n这n个数字的一个排列，每个数字为一个城市的编号。例如当n=5时，“34215”表示该方案实施的路线为3-4-2-1-5-3。遗传算法的核心是通过两个个体的交叉操作，产生两个新的个体。下面的程序给出了最简单的一种交叉算法。具体过程如下：(1)选定中间一段作为互换段，该段的起止下标为t1，t2，随机生成t1，t2后，互换两段。(2)互换后，在每个新的排列中可能有重复数字，因而不能作为新个体的编码，一般再做两步处理：(2.1)将两个互换段中，共同的数字标记为0，表示已处理完。(2.2)将两个互换段中其余数字标记为1，按顺序将互换段外重复的数字进行替换。例如：n=12，两个个体分别是：a1:1354*2679*1012811a2:32112*671011*8549t1=5，t2=8