信息学奥赛初赛辅导.ppt

《信息学奥赛初赛辅导.ppt》由会员分享，可在线阅读，更多相关《信息学奥赛初赛辅导.ppt（48页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、选择题vIT文化、微机原理、信息安全、基本应用v与奥赛活动有关的知识v算法的基础知识、数据结构v离散数学1、IT文化v1.在下面各世界顶级的奖项中，为计算机科学与技术领域做出杰出贡献的科学家设立的奖项是（）。vA.沃尔夫奖 B.诺贝尔奖 C.菲尔兹奖 D.图灵奖 图灵奖是计算机界最负盛名的奖项，有图灵奖是计算机界最负盛名的奖项，有“计算机界诺贝尔奖计算机界诺贝尔奖”之称。图灵奖之称。图灵奖对获奖者的要求极高，评奖程序也极严，一般每年只奖励一名计算机科学家，对获奖者的要求极高，评奖程序也极严，一般每年只奖励一名计算机科学家，只有极少数年度有两名以上在同一方向上做出贡献的科学家同时获奖。目前图只有

2、极少数年度有两名以上在同一方向上做出贡献的科学家同时获奖。目前图灵奖由英特尔公司赞助，奖金为灵奖由英特尔公司赞助，奖金为100,000美元。美元。2、3:与奥赛活活动相关v2.在下列各软件中，不属于NOIP竞赛（复赛）推荐使用的语言环境有（）。vA.gcc/g+B.Turbo Pascal vC.RHIDE D.free pascal v4Linux是一种()。vA.绘图软件 B.程序设计语言 C.操作系统 D.网络浏览器 3、5、10、11、15、18：微机原理v3.以下断电之后仍能保存数据的有（）。vA.寄存器 B.ROM C.RAM D.高速缓存 v5.CPU是()的简称。vA.硬盘 B

3、.中央处理器 C.高级程序语言 D.核心寄存器 v10在编程时（使用任一种高级语言，不一定是Pascal），如果需要从磁盘文件中输入一个很大的二维数组（例如1000*1000的double型数组），按行读（即外层循环是关于行的）与按列读（即外层循环是关于列的）相比，在输入效率上（）。vA.没有区别 B.按行读的方式要高一些 vC.按列读的方式要高一些 D.取决于数组的存储方式。分析v1、从读取上说没有影响v2、关键是在数组中的保存，或者说在内存中的寻址并保存。v3、如果系统是按照行优先编址的，则行优先效率高，否则消耗在寻址上的时间会很高。位运算位运算（二进制）XorXor(异或异或)（与）（与

4、）（或）（或）shlshl（左移）左移）shrshr（右移）右移）1、Xor(异或)：对应位相同为“0”，不同为“1”10101 00111 -100102、（与）（与）、（或）（或）运算：对应位都为运算：对应位都为1 1时为时为1 1，否则为，否则为0 0。如下：。如下：110111 110111 001101 001101 -000101000101运算：对应位只要有一个运算：对应位只要有一个1 1就为就为1 1。如下：。如下：110111 110111 001101 001101 -1111111111113 3、shlshl（左移）左移）、shrshr（右移）右移）shlshl（左移位

5、）左移位）(00001)2 shl 1=(00010)2(00101)2 shl 2=(10100)2 小结：小结：二二进制每左移一位相当于乘以一个制每左移一位相当于乘以一个2shrshr（右移位）右移位）(00010)2 shr 1=(00001)2(00100)2 shr 2=(00001)2 小结：小结：二二进制每左移一位相当于制每左移一位相当于除除以一个以一个2v11在Pascal语言中，表达式(21 xor 2)的值是（）vA.441 B.42 C.23 D.24 分析v1、21转化为二进制为10101，2转化为二进制是10。v2、xor表示异或操作，含义是“相同为0，不同为1”。v

6、3、列竖式计算：v10101v00010v-v10111=23进制数的运算：进制数的运算：十进制（十进制（0-90-9）、二进制（）、二进制（0 0、1 1）、）、八进制（八进制（0-80-8）、十六进制（）、十六进制（0-90-9，A-A-F F）1、十进制数 N进制数方法：除N取余倒序法2、N进制数 十进制数（要求到小数的转换）方法：整数部分：kNi求和法 小数部分：小数部分*N取整3、十六进制数与二进制数间的关系一位十六进制位相当于4位二进制位如（215）16=（001000010101）24、八进制数与二进制数间的关系一位八进制位相当于3位二进制位如（215）8=（010001101）

7、2v15.与十进制数1770 对应的八进制数是（）。vA.3350 B.3351 C.3352 D.3540分析v1、关键是搞懂十进制转化为二进制的原理。v2、借鉴十进制转化为二进制的做法，采用“除8取余法”v18.(2010)16+(32)8的结果是（）。vA.(8234)10 B.(202B)16 vC.(20056)8 D.(100000000110)2分析v1、4位二进制与16进制数一一对应；3位二进制数和8进制数一一对应，所以可以先转化为二进制数看看，判断D是否满足v2、D判断的同时，B也可判断了v3、A和C都涉及到十进制数，所以先把表达式转化为十进制数，然后再判断答案为哪个。6:信

8、息安全v6.在计算机中，防火墙的作用是（）。vA.防止火灾蔓延 B.防止网络攻击 vC.防止计算机死机 D.防止使用者误删除数据 7、8、9：算法与编程常识v7.在下列关于计算机语言的说法中，不正确的是（）。vA.Pascal和C都是编译执行的高级语言 vB.高级语言程序比汇编语言程序更容易从一种计算机移植到另一种计算机上 vC.C+是历史上的第一个支持面向对象的计算机语言 vD.与汇编语言相比，高级语言程序更容易阅读 分析v1、高级语言是基于编程系统来编译的v汇编语言比高级语言更接近CPU，是直接和操作系统交换指令的。v2、第一个面向对象语言是smalltalkv8.在下列关于计算机算法的说

9、法中，不正确的是（）。vA.一个正确的算法至少要有一个输入 vB.算法的改进，在很大程度上推动了计算机科学与技术的进步 vC.判断一个算法的好坏的主要标准是算法的时间复杂性与空间复杂性 vD.目前仍然存在许多涉及到国计民生的重大课题，还没有找到能够在计算机上实施的有效算法 分析v1、本题出现过好几次v2、本质就在考你一个误区：算法是否必须要有输入？其实输入不是必须的，而输出是必须的。v9.在下列各种排序算法中，不是以“比较”作为主要操作的算法是（）。vA.选择排序 B.冒泡排序 C.插入排序 D.基数排序 分析v1、基数排序是基于“分配”和“收集”的排序v2、即使不懂基数排序，知道了前3者排序

10、的本质是“比较”和“移动”，通过排除法也是可以分析出正确答案的。v12在Pascal语言中，判断a不等于0且b不等于0的正确的条件表达式是（）vA.not a=0 or not b=0 B.not(a=0)and(b=0)vC.not(a=0 and b=0)D.(a0)and(b0)分析v1、前面几个不懂没有关系，抓住D答案正确即可。v2、其实从离散数学的运算规律来分析，答案A,B,C回答的是同一个答案，都是错误的。v16将5个数的序列排序，不论原先的顺序如何，最少都可以通过（）次比较，完成从小到大的排序。vA.6 B.7 C.8 D.9 分析v1、既然是追求最少比较次数，必定不会用n2的算

11、法排序。v2、排序本质可说是循环查找各个位置上数v（1）用二分查找v（2）总次数322713、14、19、20：数据结构v13某个车站呈狭长形，宽度只能容下一台车，并且只有一个出入口。已知某时刻该车站状态为空，从这一时刻开始的出入记录为：“进，出，进，进，进，出，出，进，进，进，出,出”。假设车辆入站的顺序为1，2，3，则车辆出站的顺序为（）。vA.1,2,3,4,5 B.1,2,4,5,7 vC.1,4,3,7,6 D.1,4,3,7,2 模拟堆栈的操作即可v1、堆栈操作特征：v（1）FILO,LIFOv（2）每次只在一段进行操作v2、模拟操作v（1）”进、出“，出站为1v（2）”进、进、进

12、、出、出“出站为4、3v（3）”进、进、进、出、出“出站为7、6v14高度为n的均衡的二叉树是指：如果去掉叶结点及相应的树枝，它应该是高度为n-1的满二叉树。在这里，树高等于叶结点的最大深度，根结点的深度为0，如果某个均衡的二叉树共有2381个结点，则该树的树高为（）。vA.10 B.11 C.12 D.13 分析v1、满二叉树指的是：对于第i层，节点数必定是2i。v2、满二叉树的节点数为2(i+1)-1v3、假定均衡树的层数为x，那么该均衡树对应的满二叉树（比均衡树小1层）节点数为2x-1,则必定有下列不等式：v2x-123812(x+1)-1v满足该不等式的x就是11。v19.设栈S的初始

13、状态为空，元素a,b,c,d,e 依次入栈，以下出栈序列不可能出现的有（）。vA.a,b,c,e,d B.b,c,a,e,d vC.a,e,c,b,d D.d,c,e,b,a 分析v1、分析题意要正确。依次入栈指的不是”连续入栈，入栈之间没有出栈“。v2、接下来的关键是运用堆栈的操作特征。v（1）对各个答案模拟入栈和出栈操作，是否有矛盾v（2）对于答案C”a,e,c,b,d“，既然e（最后入栈）在a后面出现，说明e出来时剩余字母都在堆栈中，而这些字母是顺序入栈的，那么出栈肯定是倒序，而这里没有倒序输出”c,b,d“，显然错误。v20.已知6个结点的二叉树的先根遍历是1 2 3 4 5 6（数字

14、为结点的编号，以下同），后根遍历是3 2 5 6 4 1，则该二叉树的可能的中根遍历是（）vA.3 2 1 4 6 5 B.3 2 1 5 4 6 vC.2 1 3 5 4 6 D.2 3 1 4 6 5 分析v1、知道后根（或者前根）遍历和中序遍历，可以唯一确定一棵二叉树。但知道后根和前根是无法唯一确定一棵二叉树的。原因是对于根节点下面的节点我们无法根据前根和后根确定左右子树的根（可能只有某个子树）。v2、根据前根遍历和中根遍历，计算后根遍历是否满足试题顺序。17：离散数学v17.设A=B=D=true，C=false，以下逻辑运算表达式值为真(假)的有（）。vA.(AB)(CD)B.(AB

15、D)C)vC.A(BCD)D.(ABC)D 分析v1、离散数学的表示方法v2、其实只要知道表示and，表示or即可计算。总结v1、进制转换是必考的v2、堆栈是必考的v3、二叉树性质、遍历必考的v4、微机原理必考的（CPU、ROM等）v5、排序算法的分析，概率较大v6、新动向：和信息学奥赛的知识v7、信息安全，概率较大v8、网络有关知识，今年估计会出现问题求解v1、数据结构v2、算法设计（构造类算法）v3、数学知识（初中不多，高中较多）题1v1（寻找假币）现有80枚硬币，其中有一枚是假币，其重量稍轻，所有真币的重量都相同，如果使用不带砝码的天平称重，最少需要称几次，就可以找出假币？你还要指出第1

16、次的称重方法。请写出你的结果：_。题1考察算法：分治法v1、该题的原型是用“二分法”编程求解。二分法至少需要log(80）次，大约是7。v2、二分法的优越在于每次判断时可以排除一半。进一步思考是否分成的部分越多，每次判断可以排除的数量越多？v3、平均分成3份来判断，每次可以排除2/3数量。（思考分成更多份是否效果更好？）具体算法v1、平均分成3份，如果不能被3整除，那么尽量让两份相同并且相同的两分应该比其他一份大1（每次判断可以排除更多的数量）v2、每次称相同的两份。直到最后相同的两分是1。实例27，27，269，9，91，1，13，3，39，9，81，1，13，3，21，1题2v2（取石子游戏）现有5堆石子,石子数依次为3，5，7，19，50，甲乙两人轮流从任一堆中任取（每次只能取自一堆，不能不取）,取最后一颗石子的一方获胜。甲先取，问甲有没有获胜策略（即无论乙怎样取，甲只要不失误，都能获胜）？如果有，甲第一步应该在哪一堆里取多少？请写出你的结果：v_。题2：xor操作v1、异或结果非0，必胜，否则必输。v2、根据下面列式，只要让50对应的最高位1去掉，xor结果就是0，而这个最高位的1对应是32。v000011（3）v000101（5）v000111（7）v010011（19）v110010（50）