《十二届信息NOI初赛提高组试题解析.ppt》由会员分享，可在线阅读，更多相关《十二届信息NOI初赛提高组试题解析.ppt（22页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、十二届信息NOI初赛提高组试题解析 Still waters run deep.流静水深流静水深,人静心深人静心深 Where there is life,there is hope。有生命必有希望。有生命必有希望一、单项选择题（10 题每题 1.5 分共 15 分）1.在以下各项中。（）不是 CPU 的组成部分。A.控制器 B.运算器 C.寄存器 D.ALU E.RAM 2.BIOS（基本输入输出系统）是一组固化在计算机内（）上一个 ROM 芯片上的程序。A.控制器 B.CPU C.主板 D.内存条 E.硬盘 ALU:Arighmatic Logincal Unit RAM:Random a
2、ccess memory ROM:Read Only MemoryBIOS:ROM 芯片程序 Basic Inout/Output system计算机最高奖3.在下面各世界顶级的奖项中，为计算机科学与技术在下面各世界顶级的奖项中，为计算机科学与技术领域作出杰出贡献的科学家设立的奖项是（领域作出杰出贡献的科学家设立的奖项是（）。）。A.沃尔夫奖沃尔夫奖 B.诺贝尔奖诺贝尔奖 C.菲尔兹奖菲尔兹奖 D.图灵奖图灵奖 E.南丁格尔奖南丁格尔奖 4在编程时（使用任一种高级语言，不一定是在编程时（使用任一种高级语言，不一定是 Pascal），如果需要从磁盘文件中输入一个很大的），如果需要从磁盘文件中输入
3、一个很大的二维二维 数组（例如数组（例如 1000*1000 的的 double 型数组），型数组），按行读（即外层循环是关于行的）与按列读（即外按行读（即外层循环是关于行的）与按列读（即外层循层循 环是关于列的）相比，在输入效率上（）。环是关于列的）相比，在输入效率上（）。A.没有区别没有区别 B.有一些区别，但机器处理速度很快，有一些区别，但机器处理速度很快，可忽略不计可忽略不计 C.按行读的方式要高一些按行读的方式要高一些 D.按列读按列读的方式要高一些的方式要高一些 E.取决于数组的存储方式。取决于数组的存储方式。5在 Pascal 语言中表达式(21 xor 2)的值是（）A.441
4、 B.42 C.23 D.24 E.25 6在 Pascal 语言中，判断 a 不等于 0 且 b 不等于 0 的正确的条件表达式是（）A.not a=0 or not b=0 B.not(a=0)and(b=0)C.not(a=0 and b=0)D.(a0)or(b0)E.(a0)and(b0)逻辑运算:异或逻辑运算真值表逻辑运算真值表AND与:有O出O;OR或:有1出1NOT非:取反;XOR异或:相同得O相异为1ANDANDA=0A=0A=1A=1B=0B=00 00 0B=1B=10 01 1XORXORA=0A=0A=1A=1B=0B=00 01 1B=1B=11 10 0ORORA
5、=0A=0A=1A=1B=0B=00 01 1B=1B=11 11 1NOTNOTA=0A=0A=1A=1A=1A=1 A=0A=07.栈v7某个车站呈狭长形，宽度只能容下一台车，并且只有一个出入口。已知某时刻该车站状态为空，从这一时刻开始的出入记录为：“进，出，进，进，进，出，出，进，进，进，出,出”。假设车辆入站的 顺序为 1，2，3，则车辆出站的顺序为（）。A.1,2,3,4,5 vB.1,2,4,5,7 vC.1,4,3,7,6 D.1,4,3,7,2 vE.1,4,3,7,5 二叉树 8高度为 n 的均衡的二叉树是指：如果去掉叶结点及相应的树枝，它应该是高度为 n-1 的满二叉树。在
6、这里，树高等于叶结点的最大深度，根结点的深度为 0，如果某个均衡的二叉树共有 2381 个结点，则该树的树高为 A.10 B.11 C.12 D.13 E.210 1。9.与十进制数 1770.625 对应的八进制数是（）。由OIF收集 A.3352.5 B.3350.5 C.3352.1161 D.3350.1151 E.前 4 个答案都不对 10将 5 个数的序列排序，不论原先的顺序如何，最少都可以通过（）次比较，完成从小到大的排序。A.6 B.7 C.8 D.9 E.10 二、不定项选择题（共 10 题，每题 1.5 分，共计 15 分。多选或少选均不得分）v11.设A=B=D=true
7、，C=E=false，以下逻辑运算表达式值为真的有（）。AB)(CD)A.(E B.(AB)C)DE)C.A(BCDE)D.(A(BC)DE 12.(2010)16+(32)8的结果是（）。A.(8234)10 B.(202A)16 C.(100000000110)2 D.(2042)16 栈、树v13.设栈S的初始状态为空，元素a,b,c,d,e 依次入栈，以下出栈序列不可能出现的有（）。A.a,b,c,e,d B.b,c,a,e,d C.a,e,c,b,d D.d,c,e,b,a 14.已知 6 个结点的二叉树的先根遍历是 1 2 3 4 5 6（数字为结点的编号，以下同），后根遍历是 3
8、 2 5 6 4 1，则该二叉树的可能的中根遍历是（）由OIF收集 A.3 2 1 4 6 5 B.3 2 1 5 4 6 C.2 3 1 5 4 6 D.2 3 1 4 6 5 15.在下列各数据库系统软件中 以关系型数据库为主体结构的是（）。A.ACCESS B.SQL Server C.Oracle D.Foxpro 16.在下列各软件中，属于 NOIP 竞赛（复赛）推荐使用的语言环境有（）。A.gcc/g+B.Turbo Pascal C.Turbo C D.free pascal 17.以下断电之后将不能保存数据的有（）A.硬盘 B.ROM C.显存 D.RAM 18.在下列关于计算
9、机语言的说法中，正确的有（）。A.Pascal和C都是编译执行的高级语言 B.高级语言程序比汇编语言程序更容易从一种计算机移植到另一种计算机上 C.C+是历史上的第一个支持面向对象的计算机语言 D.高级语言比汇编语言更高级，是因为它的程序的运行效率更高 算法衡量v19.在下列关于计算机算法的说法中，正确的有（）。A.一个正确的算法至少要有一个输入 B.算法的改进，在很大程度上推动了计算机科学与技术的进步由OIF收集 C.判断一个算法的好坏，主要依据它在某台计算机上具体实现时的运行时间 D.目前仍然存在许多涉及到国计民生的重大课题，还没有找到能够在计算机上实施的有效算法 20.在下列关于青少年信
10、息学竞赛的说法中，你赞成的是（）v（本题不回答为0分，答题一律满分）。A.举行信息学竞赛的目的，是为了带动广大青少年学科学、爱科学，为造就一大批优秀的计算机科学与技术人才奠定良好的基础 B.如果竞赛优胜者不能直接保送上大学，我今后就不再参与这项活动了 C.准备竞赛无非要靠题海战术，为了取得好成绩，就得拼时间、拼体力 D.为了取得好成绩，不光要看智力因素，还要看非智力因素。优秀选手应该有坚韧不拔的意志，有严谨求实的作风，既要努力奋进，又要胜不骄败不馁 三问题求解（共 2 题，每题 5 分，共计 10 分）1将 2006 个人分成若干不相交的子集，每个子集至少有 3 个人，并且：（1）在每个子集中
11、，没有人认识该子集的所有人。（2）同一子集的任何 3 个人中，至少有 2 个人互不认识。（3）对同一子集中任何 2 个不相识的人，在该子集中恰好只有 1 个人认识这两个人。则满足上述条件的子集最多能有_个？三、2 正三角形2将边长为 n 的正三角形每边 n 等分，过每个分点分别做另外两边的平行线，得到若干个正三角形，我们称为小三角形。正三角形的一条通路是一条连续的折线，起点是最上面的一个小三角形，终点是最 下面一行位于中间的小三角形。在通路中，只允许由一个小三角形走到另一个与其有公共边的且位于同一行或下一行的小三角形，并且每个小三角形不能经过两次或两次以上（图中是 n=5 时一条通路的例 子）
12、。设 n=10，则该正三角形的不同的通路的总数为_。四阅读程序写结果（4 题每题 8 分共计 32 分）1.Program ex401;var u,v:array0.3 of integer;i,x,y:integer;begin x:=10;y:=10;for i:=0 to 3 do read(ui);v0:=(u0+u1+u2+u3)div 7;v1:=u0 div(u1-u2)div u3);v2:=u0*u1 div u2*u3;v3:=v0*v1;x:=(v0+v1+2)-u(v3+3)mod 4;if(x10)then y:=y+(v2*100-v3)div(uu0 mod 3*
13、5)由OIF收集 else y:=y+20+(v2*100-v3)div(uv0 mod 3*5);writeln(x,y);end.*注：本例中，给定的输入数据可以避免分母为 0 或下标越界。输入：9 3 9 4 输出：2.Program ex402;vconst m:array0.4 of integer=(2,3,5,7,13);var i,j:integer;t:longint;begin for i:=0 to 4 do begin t:=1;for j:=1 to mi-1 do t:=t*2;t:=(t*2-1)*t;write(t,);end;writeln;end.输出:_
14、五完善程序(前 5 空每空 2 分，后 6 空每空 3 分，共 28 分)1（选排列）下面程序的功能是利用递归方法生成从 1 到 n(n10)的 n 个数中取 k(1=k4-2-1-5-3。遗传算法的核心是通过两个个体的交叉操作，产生两 个新的个体。下面的程序给出了最简单的一种交叉算法。具体过程如下：v(1)选定中间一段作为互换段，该段的起止下标为 t1，t2，随机生成 t1，t2 后，互换两段。(2)互换后，在每个新的排列中可能有重复数字，因而不能作为新个体的编码，一般再做两步处理：(2.1)将两个互换段中，共同的数字标记为 0，表示已处理完。(2.2)将两个互换段中其余数字标记为 1，按顺
15、序将互换段外重复的数字进行替换。例如：n=12，两个个体分别是：a1:1 3 5 4*2 6 7 9*10 12 8 11 a2:3 2 1 12*6 7 10 11*8 5 4 9 t1=5，t2=8。上述每一行中，两个星号间的部分为互换段。假定数组的下标从 1 开始，互换后有：a1:1 3 5 4*6 7 10 11*10 12 8 11 va2:3 2 1 12*2 6 7 9*8 5 4 9 然后，将数字 6,7 对应的项标记为 0，星号内数字 2,9,10,11 对应的项标记为 1，并且按顺序对 应关系为:102，119。于是，将 a19=10 替换为 a19=2，将 a22=2 替
16、换为 a22=10，类似再做第 2 组替换。这样处理后，就得到了两个新个体：a1:1 3 5 4 6 7 10 11 2 12 8 9 va2:3 10 1 12 2 6 7 9 8 5 4 11（3）输出两个新个体的编码。具体过程如下：NOI第十二届提高组答案v一、单项选择题：（每题1.5分）1.E 2.C 3.D 4.E 5.C 6.（满分）7.C 8.B 9.A 10.B 二、不定项选择题：（每题1.5分）11.ABC 12.AB 13.C 14.BC 15.ABCD 16.AD 17.CD 18.AB 19.BD 20.（满分，空白0分）三、问题求解：（每题 5分）1.401 2.9!
17、（或362880）四、阅读程序写结果 1.-13，57（对1个数给4分，无逗号扣1分）2.6 28 496 8128 33550336（前2个对1个数给1分，后3个对1个数给2分）3.11 4.6 2 5 4 3 7 9 9 7 3 4 5 2 6（数字之间无空格扣2分）五、完善程序(前5空，每空2分，后6空，每空3分)1 j=k（或k=j）p:=1 to k perm2(j+1)aj:=ai;ai:=t perm2(1)2 a1i:=a2i;a2i:=t kz1i:=1;kz2i:=1;kz1i:=0;kz2j:=0;(a1j=a1i)and(kz1j=-1)(a2j=a2kj)and(kz2j=-1)cross(a1,a2,t1,t2,n)