全国青少年信息学奥赛全国青少年信息学奥赛 第十届初赛东风一中刘丽梅试题解析试题解析第十届第十届NOI初赛试题及答案（提高组）初赛试题及答案（提高组）n一、项选择题（共10题，每题1.5分，共计15分）n1.设全集a,b,c,d,e,f,g,集合A=a,b,c，B=b,d,e，C=e,f,g，那么集合(A-B)（CB）为（）。nA.a,b,c,dB.a,b,d,eC.b,d,eD.b,c,d,eE.d,f,g答案1.AT2T3n2.由3个a，5个b和2个c构成的所有字符串中，包含子串“abc”的共有（）个。A.40320B.39600C.840D.780E.60n3.某车站呈狭长形，宽度只能容下一台车，并且只有一个出口。某时刻车站状态为空，从这一时刻开始的出入记录为：“进，出，进，进，出，进，进，进，出，出，进，出”。假设车辆入站的顺序为1，2，3则车辆的顺序为。答案2.D3.EA.1，2，3，4，5B.1，2，4，5，7，C.1，3，5，4，6D.1，3，5，6，7E.1，3，6，5，74.满二叉树的叶节点个数为N,n则它的节点总数为（）。A.NB.2*NC.2*N-1nD.2*N+1E.2N-1n5.二叉树T已知其前序遍历序列为1243576，中序遍历序列为4215736，则其后序遍历为（）。nA.4257631B.4275631nC.4275361D.4723561E.45263715.BinaryTree图示答案4.C5.B13657426-7n6.十进制数100.625等值于二进制数（）。A.1001100.101B.1100100.101C.1100100.011D.1001100.11E.1001100.01n7.下面哪个部件对于个人桌面电脑的正常运行不是必须的（）。A.CPUB.图形卡（显卡）C.光驱D.主板E.内存答案6.B7.C8.下列哪个网络常用名字缩写是错的下列哪个网络常用名字缩写是错的?A.WWW(WorldWideWeb)B.URL(UniformResourceLocator)C.HTTP(HypertextTransterProtocol)D.FTP(FastTransgerProtocol)(File)E.TCP(TransgerControlProtocol)n9.用静电吸附墨粉后转移到纸张上，n是哪种输出设备的工作方式（）。A.针式打印机B.喷墨打印机nC.激光打印机D.笔式绘图仪E.喷墨绘图仪答案8.D9.C10.一台计算机要利用电话线上网就必须配置能够对数字信号和模拟信号进行相互转换的设备，这种设备是（）。A.调制解调器B.路由器C.网卡D.网关E.网桥答案10.A二、不定项选择题（共10题，每题1.5分，共计15分）11.美籍匈牙利数学家冯诺依曼对计算机科学发展所做出的贡献包括（）。A.提出理想计算机的数学模型，成为计算机科学的理论基础。B.提出存储程序工作原理，对现代电子计算机的发展产生深远影响。C.设计出第一台具有存储程序功能的计算机EDVAC。D.采用集成电路作为计算机的主要功能部件。E.指出计算机性能将以每两年翻一番的速度想前发展。答案11.BCEDVAC资料:一般认为ENIAC机是世界第一台电子计算机.其实英国“科洛萨斯”计算机比ENIAC机问世早两年n冯诺依曼由ENIAC机研制组的戈尔德斯廷中尉介绍参加ENIAC机研制后，带领这批富有创新精神的年轻科技人员，向着更高的目标进军1945年发表了一个全新的“存储程序通用电子计算机方案”EDVAC（ElectronicDiscreteVariableAutomaticComputer的缩写）EDVAC方案明确奠定了新机器由五个部分组成，包括：运算器、逻辑控制装置、存储器、输入和输出设备，并描述了这五部分的职能和相互关系EDVAC机两个非常重大的改进:n（1）采用了二进制，不但数据采用二进制，指令也采用二进制；n（2建立了存储程序，指令和数据便可一起放在存储器里.12.下列哪些是64位处理器12.下列哪些是64位处理器（）。A.IntelItaniumB.InterPentiumIIIC.AMDAthlon64D.AMDOpteronE.IBMPower5答案12.ACDE13.（2004）10+（32）16的结果A.(2036)10B.(2054)10C.(4006)8D.(100000000110)2E.(2036)10答案13.BCD分析:3216=3*16+2=50103216=(00110010)2200410=(11111010100)214.下列哪个（些）n不是数据库软件的名称（）。A.MySQLB.SQLServernC.OracleD.OutlooknE.Foxpro答案14.D15.下列哪个（些）不是计算机的存储设备nA.文件管理器B.内存C.显卡nD.硬盘E.U盘答案15.AC16.下列哪个（些）软件属于操作系统（）。nA.MicrosoftWordnB.WindowsXPnC.FoxmailnD.金山影霸nE.RedHatLinux答案16.BE17.下列说法中正确的是（）nA.CPU的基本功能就是执行指令B.CPU的主频是指CPU在1秒内完成的指令周期数，主频越快的CPU速度一定越快。nC.内部构造不同的CPU运行相同的机器语言程序，一定会产生不同的结果。D.在一台计算机内部，一个内存地址编码对应唯一的一个内存单元。E.数据总线的宽度决定了一次传递数据量的大小，是影响计算机性能的因素之一。答案17.ADECPU主频就是CPU的时钟频率n主频是主频是CPU乃至整个计算机系统的基准频率，乃至整个计算机系统的基准频率，单位是单位是MHz（兆赫兹）。（兆赫兹）。CPU主频是主频是CPU内内部的时钟频率，是部的时钟频率，是CPU进行运算时的工作频进行运算时的工作频率。主频越高，一个时钟周期里完成的指令数率。主频越高，一个时钟周期里完成的指令数也越多，也越多，CPU的运算速度也就越快。的运算速度也就越快。n外频即系统总线，外频即系统总线，CPU与周边设备传输数据与周边设备传输数据的频率，具体是指的频率，具体是指CPU到芯片组之间的总线到芯片组之间的总线速度。速度。n倍频是指倍频是指CPU和系统总线之间相差的倍数，和系统总线之间相差的倍数，当外频不变时，提高倍频，当外频不变时，提高倍频，CPU主频也就越主频也就越高。倍频可使系统总线工作在相对较低的频率高。倍频可使系统总线工作在相对较低的频率上，而上，而CPU速度可以通过倍频来无限提升。速度可以通过倍频来无限提升。n主频主频=外频外频x倍频。倍频。CPU主频就是CPU的时钟频率nCACHE: CPUCACHE: CPU缓存分为一级和二级缓存缓存分为一级和二级缓存n一级缓存，即一级缓存，即L1 CacheL1 Cache。集成在。集成在CPUCPU内部内部中，用于中，用于CPUCPU在处理数据过程中数据的暂在处理数据过程中数据的暂时保存。可减少时保存。可减少CPUCPU与内存的数据交换次与内存的数据交换次数，提高数，提高CPUCPU的运算效率。的运算效率。L1L1容量在容量在3232256KB256KB。n二级缓存，即二级缓存，即L2 CacheL2 Cache。L1L1级高速缓存容级高速缓存容量的限制，为再次提高量的限制，为再次提高CPUCPU的运算速度，的运算速度，在在CPUCPU外部放置一高速存储器，即二级缓外部放置一高速存储器，即二级缓存。工作主频比较灵活，可与存。工作主频比较灵活，可与CPUCPU同频同频, ,也也可不同。可不同。CPUCPU先在先在L1L1中寻找，再从中寻找，再从L2L2寻找，寻找，然后是内存，在后是外存储器。然后是内存，在后是外存储器。n现在普通台式机现在普通台式机CPU的的L2缓存一缓存一般为般为128KB到到2MB或者更高，或者更高，笔记本、服务器笔记本、服务器和工作站上用和工作站上用CPU的的L2高速缓高速缓存最高可达存最高可达1MB-3MB.答案18.ACD19.ABDEn18.彩色显示器所显示的五彩斑斓的色彩，是由哪三色混合而成的（）。A.红B.白C.蓝D.绿E.橙n19.下列哪个（些）程序设计语言支持面向对象程序设计方法。A.C+B.ObjectPascalnC.CD.SmalltalkE.Java20.某大学计算机专业的必修课及其先修课如下表,请你判断下列课程安排方案哪些合理nA.C0,C1,C2,C3,C4,C5,C6,C7nB.C0,C1,C2,C3,C4,C6,C7,C5nC.C0,C1,C6,C7,C2,C3,C4,C5D.C0,C1,C6,C7,C5,C2,C3,C4nE.C0,C1,C2,C3,C6,C7,C5,C4答案20.BCE课程代号C0C1C2C3C4C5C6C7课程名称高等数学程序设计语言离散数学数据结构编译技术操作系统普通物理计算机原理先修课程C0,C1C1,C2C3C3,C7C0C6三、问题求解（共2题，每题5分）n1.75名儿童到游乐场去玩。他们可以骑旋转木马，坐滑行铁道，乘宇宙飞船，已知其中20人这三种东西都玩过，55人至少玩过其中的两种。若每样乘坐一次的费用是5元，游乐场总共收入700元，可知有_名儿童没玩过其中任何一种。答案座次n2.已知a,b,c,d,e,f,g七个人中，a会讲英语；b会讲英语和汉语；c会讲英语、意大利语和俄语；d会讲汉语和日语；e会讲意大利语和德语；f会讲俄语、日语和法语；g会讲法语和德语。能否将他们的座位安排在圆桌旁，使得每个人都能与他身边的人交谈？如果可以，请以“ab”开头写出你的安排方案：_。答案四、阅读程序（共4题，每题8分，共计32分）n1.programprogaml;varu：array0.3ofinteger;a,b,c,x,y,z：integer;beginread(u0,u1,u2,u3);a：=u0+u1+u2+u3-5;b：=u0*(u1-u2divu3+8);c：=u0*u1divu2*u3;x：=(a+b+2)*3u(c+3)mod4;y：=(c*10013)divadiv(ubmod3*5);if(x+y)mod2=0)thenz：=(a+b+c+x+y)div2;z：=(a+b+c-x-y)*2;writeln(x+y+-z);end.n输入：2574输出：_.n2.programprogram2;vari,number,ndata,sum：integer;data：array1.100ofinteger;proceduresolve(s,sign,n:integer);varI:integer;beginfori：=stondatadobegininc(sum,sign*(numberdiv(n*data);solve(i+1,-sign,n*data);end;end;beginread(number,ndata);sum：=0;fori：=1tondatadoread(data);solve(1,1,1);writeln(sum);end.输入：1000351311输出：_。n3.programprogarm3;varc：array1.3ofstring200;s：array1.10ofinteger;m,n,i:integer;procedurenumara;varcod：boolean;i,j,nr：integer;begnforj：=1tondobeginnr：=0；cod：=true;fori:：=1tomdoifci,j=1thenbeignifnotcodthenbegincod：=true;inc(snr);nr：=0；end;endelsebeginifcodthennbeginnr：=1;cod：=false;endelseinc(nr);end;ifnotcodtheninc(snr);end;end;nbeginreadln(m,n);fori：=1tomdoreadln(c);numara;fori：=1tomdoifs0thenwrite(i,s,);end.输入：310111000011111000011111000000011输出：_.n4.programprogram4;constu：array0.2ofinteger=(1,-3,2);v：array0.1ofinteger=(-2,3);vari,n,sum：integer;functiong(n：integer)：integer;vari,sum：integer;beginsum：=0；fori：=1tondoinc(sum,uimod3*i);g：=sum;end;beginsum：=0;read(n);fori：=1tondoinc(sum,uimod2*g(i);writeln;end.输入：103输出：_.五、完善程序（前5空，每空2分；后6空，每空3分，共28分）n1.Joseph题目描述：原始的Joseph问题的描述如下：有n个人围坐在一个圆桌周围，把这n个人依次编号为1，n。从编号是1的人开始报数，数到m个人出列，然后从出列的下一个人重新开始报数，数到第m个人又出列，如此反复直到所有的人全部出列为止。比如当n=6,m=5的时候，出列的顺序依次是5，4，6，2，3，1。现在的问题是：假设有k个好人和k个坏人。好人的编号是1到k，坏人的编号是k+1到2k。我们希望求出m的最小值，使得最先出列的k个人都是坏人。输入：仅有的一个数字是k(0K14)。输出：使得最先出列的k个人都是坏人的m的最小值。输入样例：4输出样例：30programprogaram1;vari,k,m,start：longint;find：boolean;functioncheck（remain:integer）：）：boolean;varresult：integer;beginresult：=_(1)_modremain;if_(2)_thenbeginstart：=result;check：=true;endelsecheck：=false;end;beginfind：=false;read(k);m：=k;while_(3)_dobeginfind：=true;start；=0；fori：=0tok-1doif(notcheck(_(4)_)thenbeginfind：=false;break;end;inc(m);end;writeln(_(5)_);end.祝大家取得祝大家取得优异成绩！优异成绩！