全国青少年信息学奥赛十届初赛.ppt
全国青少年信息学奥赛 第十届初赛,东风一中刘丽梅,试题解析,第十届NOI初赛试题及答案（提高组）,一、项选择题（共10题，每题1.5分，共计15分）1.设全集a,b,c,d,e,f,g,集合A=a,b,c，B=b,d,e，C=e,f,g，那么集合(A-B)（CB）为（）。A.a,b,c,d B.a,b,d,e C.b,d,e D.b,c,d,e E.d,f,g,答案1.A,T2 T3,2.由3个a，5个b和2个c构成的所有字符串中，包含子串“abc”的共有（）个。A.40320 B.39600 C.840 D.780 E.603.某车站呈狭长形，宽度只能容下一台车，并且只有一个出口。某时刻车站状态为空，从这一时刻开始的出入记录为：“进，出，进，进，出，进，进，进，出，出，进，出”。假设车辆入站的顺序为1，2，3则车辆的顺序为。,答案2.D 3.E,A.1，2，3，4，5 B.1，2，4，5，7，C.1，3，5，4，6D.1，3，5，6，7E.1，3，6，5，7,4.满二叉树的叶节点个数为N,则它的节点总数为（）。A.N B.2*N C.2*N-1D.2*N+1 E.2N-1 5.二叉树T已知其前序遍历序列为1243576，中序遍历序列为4215736，则其后序遍历为（）。A.4257631 B.4275631 C.4275361 D.4723561E.4526371,5.Binary Tree图示,答案4.C 5.B,1,3,6,5,7,4,2,6-7,6.十进制数100.625等值于二进制数（）。A.1001100.101 B.1100100.101 C.1100100.011 D.1001100.11 E.1001100.01 7.下面哪个部件对于个人桌面电脑的正常运行不是必须的（）。A.CPU B.图形卡（显卡）C.光驱 D.主板 E.内存,答案6.B 7.C,8.下列哪个网络常用名字缩写是错的?,A.WWW(World Wide Web)B.URL(Uniform Resource Locator)C.HTTP(Hypertext Transter Protocol)D.FTP(Fast Transger Protocol)(File)E.TCP(Transger Control Protocol)9.用静电吸附墨粉后转移到纸张上，是哪种输出设备的工作方式（）。A.针式打印机 B.喷墨打印机C.激光打印机 D.笔式绘图仪 E.喷墨绘图仪,答案8.D 9.C,10.一台计算机要利用电话线上网,就必须配置能够对数字信号和模拟信号进行相互转换的设备，这种设备是（）。A.调制解调器 B.路由器 C.网卡 D.网关 E.网桥,答案10.A,二、不定项选择题（共10题，每题1.5分，共计15分）,11.美籍匈牙利数学家冯诺依曼对计算机科学发展所做出的贡献包括（）。A.提出理想计算机的数学模型，成为计算机科学的理论基础。B.提出存储程序工作原理，对现代电子计算机的发展产生深远影响。C.设计出第一台具有存储程序功能的计算机EDVAC。D.采用集成电路作为计算机的主要功能部件。E.指出计算机性能将以每两年翻一番的速度想前发展。,答案11.BC,EDVAC资料:一般认为ENIAC机是世界第一台电子计算机.其实英国“科洛萨斯”计算机比ENIAC机问世早两年,冯诺依曼由ENIAC机研制组的戈尔德斯廷中尉介绍参加ENIAC机研制后，带领这批富有创新精神的年轻科技人员，向着更高的目标进军1945年发表了一个全新的“存储程序通用电子计算机方案”EDVAC（Electronic Discrete Variable Automatic Computer的缩写）EDVAC方案明确奠定了新机器由五个部分组成，包括：运算器、逻辑控制装置、存储器、输入和输出设备，并描述了这五部分的职能和相互关系EDVAC机两个非常重大的改进:（1）采用了二进制，不但数据采用二进制，指令也采用二进制；（2建立了存储程序，指令和数据便可一起放在存储器里.,12.下列哪些是64位处理器,12.下列哪些是64位处理器（）。A.Intel Itanium B.Inter PentiumIII C.AMD Athlon64 D.AMD Opteron E.IBM Power5,答案12.ACDE,13.（2004）10+（32）16的结果,A.(2036)10 B.(2054)10 C.(4006)8,答案13.BCD,分析:3216=3*16+2=5010 3216=(00110010)22004102,14.下列哪个（些）,不是数据库软件的名称（）。A.MySQL B.SQL ServerC.Oracle D.OutlookE.Foxpro,答案14.D,15.下列哪个（些）不是计算机的存储设备,A.文件管理器 B.内存 C.显卡 D.硬盘 E.U盘,答案15.AC,16.下列哪个（些）软件属于操作系统（）。,A.Microsoft Word B.WindowsXP C.Foxmail D.金山影霸 E.Red Hat Linux,答案16.BE,17.下列说法中正确的是（）,A.CPU的基本功能就是执行指令 B.CPU的主频是指CPU在1秒内完成的指令周期数，主频越快的CPU速度一定越快。C.内部构造不同的CPU运行相同的机器语言程序，一定会产生不同的结果。D.在一台计算机内部，一个内存地址编码对应唯一的一个内存单元。E.数据总线的宽度决定了一次传递数据量的大小，是影响计算机性能的因素之一。,答案17.ADE,CPU主频就是CPU的时钟频率,主频是CPU乃至整个计算机系统的基准频率，单位是MHz（兆赫兹）。CPU主频是CPU内部的时钟频率，是CPU进行运算时的工作频率。主频越高，一个时钟周期里完成的指令数也越多，CPU的运算速度也就越快。外频即系统总线，CPU与周边设备传输数据的频率，具体是指CPU到芯片组之间的总线速度。倍频是指CPU和系统总线之间相差的倍数，当外频不变时，提高倍频，CPU主频也就越高。倍频可使系统总线工作在相对较低的频率上，而CPU速度可以通过倍频来无限提升。主频=外频 x 倍频。,CPU主频就是CPU的时钟频率,CACHE:CPU缓存分为一级和二级缓存一级缓存，即L1 Cache。集成在CPU内部中，用于CPU在处理数据过程中数据的暂时保存。可减少CPU与内存的数据交换次数，提高CPU的运算效率。L1容量在32256KB。二级缓存，即L2 Cache。L1级高速缓存容量的限制，为再次提高CPU的运算速度，在CPU外部放置一高速存储器，即二级缓存。工作主频比较灵活，可与CPU同频,也可不同。CPU先在L1中寻找，再从L2寻找，然后是内存，在后是外存储器。,现在普通台式机CPU的L2缓存一般为128KB到2MB或者更高，笔记本、服务器和工作站上用CPU的L2高速缓存最高可达1MB-3MB.,答案18.ACD 19.ABDE,18.彩色显示器所显示的五彩斑斓的色彩，是由哪三色混合而成的（）。A.红 B.白 C.蓝 D.绿 E.橙 19.下列哪个（些）程序设计语言支持面向对象程序设计方法。A.C+B.Object PascalC.C D.Smalltalk E.Java,20.某大学计算机专业的必修课及其先修课如下表,请你判断下列课程安排方案哪些合理,A.C0,C1,C2,C3,C4,C5,C6,C7 B.C0,C1,C2,C3,C4,C6,C7,C5 C.C0,C1,C6,C7,C2,C3,C4,C5D.C0,C1,C6,C7,C5,C2,C3,C4 E.C0,C1,C2,C3,C6,C7,C5,C4,答案20.BCE,三、问题求解（共2题，每题5分）,1.75名儿童到游乐场去玩。他们可以骑旋转木马，坐滑行铁道，乘宇宙飞船，已知其中20人这三种东西都玩过，55人至少玩过其中的两种。若每样乘坐一次的费用是5元，游乐场总共收入700元，可知有_名儿童没玩过其中任何一种。,答案,座次,2.已知a,b,c,d,e,f,g七个人中，a会讲英语；b会讲英语和汉语；c会讲英语、意大利语和俄语；d会讲汉语和日语；e会讲意大利语和德语；f会讲俄语、日语和法语；g会讲法语和德语。能否将他们的座位安排在圆桌旁，使得每个人都能与他身边的人交谈？如果可以，请以“ab”开头写出你的安排方案：_。,答案,四、阅读程序（共4题，每题8分，共计32分）,1.program progaml;varu：array0.3 of integer;a,b,c,x,y,z：integer;begin read(u0,u1,u2,u3);a：=u0+u1+u2+u3-5;b：=u0*(u1-u2 div u3+8);c：=u0*u1 div u2*u3;x：=(a+b+2)*3 u(c+3)mod 4;y：=(c*100 13)div a div(ub mod 3*5);if(x+y)mod 2=0)then z：=(a+b+c+x+y)div 2;z：=(a+b+c-x-y)*2;writeln(x+y+-z);end.输入：2574 输出：_.,2.program program2;var i,number,ndata,sum：integer;data：array1.100 of integer;procedure solve(s,sign,n:integer);var I:integer;beginfor i：=s to ndata do begin inc(sum,sign*(number div(n*data);solve(i+1,-sign,n*data);end;end;beginread(number,ndata);sum：=0;for i：=1 to ndata do read(data);solve(1,1,1);writeln(sum);end.输入：1000351311输出：_。,3.program progarm3;var c：array1.3 of string200;s：array1.10 of integer;m,n,i:integer;procedure numara;var cod：boolean;i,j,nr：integer;begnfor j：=1 to n do beginnr：=0；cod：=true;for i:：=1 to m do if ci,j=1 then beignif not cod then begin cod：=true;inc(snr);nr：=0；end;endelse beginif cod then begin nr：=1;cod：=false;end else inc(nr);end;if not cod then inc(snr);end;end;,beginreadln(m,n);for i：=1 to m do readln(c);numara;for i：=1 to m do if s0 then write(i,s,);end.输入：310111000011111000011111000000011输出：_.,4.program program4;constu：array0.2 of integer=(1,-3,2);v：array0.1 of integer=(-2,3);var i,n,sum：integer;function g(n：integer)：integer;var i,sum：integer;beginsum：=0；for i：=1 to n do inc(sum,ui mod 3*i);g：=sum;end;beginsum：=0;read(n);for i：=1 to n do inc(sum,ui mod 2*g(i);writeln;end.输入：103输出：_.,五、完善程序（前5空，每空2分；后6空，每空3分，共28分）,1.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输出样例：30,program progaram1;var i,k,m,start：longint;find：boolean;function check（remain:integer）：boolean;var result：integer;beginresult：=_(1)_ mod remain;if _(2)_ then beginstart：=result;check：=true;endelse check：=false;end;beginfind：=false;read(k);m：=k;while _(3)_ do beginfind：=true;start；=0；for i：=0 to k-1 do if(not check(_(4)_)then begin find：=false;break;end;inc(m);end;writeln(_(5)_);end.,祝大家取得优异成绩！,
