信息学奥赛初赛辅导.ppt

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

2、不属于NOIP竞赛（复赛）推荐使用的语言环境有（ ）。 A. gcc/g+ B. Turbo Pascal C. RHIDE D. free pascal,4Linux是一种( )。 A. 绘图软件 B. 程序设计语言 C. 操作系统 D. 网络浏览器,3、5、10、11、15、18：微机原理,3. 以下断电之后仍能保存数据的有（ ）。 A. 寄存器 B. ROM C. RAM D. 高速缓存,5. CPU是( )的简称。 A. 硬盘 B. 中央处理器 C. 高级程序语言 D. 核心寄存器,10在编程时（使用任一种高级语言，不一定是Pascal），如果需要从磁盘文件中输入一个很大的二维数组（例

3、如1000*1000的double型数组），按行读（即外层循环是关于行的）与按列读（即外层循环是关于列的）相比，在输入效率上（ ）。 A. 没有区别 B. 按行读的方式要高一些 C. 按列读的方式要高一些 D. 取决于数组的存储方式。,分析,1、从读取上说没有影响 2、关键是在数组中的保存，或者说在内存中的寻址并保存。 3、如果系统是按照行优先编址的，则行优先效率高，否则消耗在寻址上的时间会很高。,位运算（二进制） Xor(异或) （与） （或） shl（左移） shr（右移）,1、Xor(异或)：对应位相同为“0”，不同为“1” 10101 00111 - 10010,2、 （与） 、 （或

4、）,运算：对应位都为1时为1，否则为0。如下： 110111 001101 - 000101,运算：对应位只要有一个1就为1。如下： 110111 001101 - 111111,3、shl（左移） 、 shr（右移）,shl（左移位） (00001)2 shl 1 =(00010)2 (00101)2 shl 2 =(10100)2 小结：二进制每左移一位相当于乘以一个2,shr（右移位） (00010)2 shr 1 =(00001)2 (00100)2 shr 2 =(00001)2 小结：二进制每左移一位相当于除以一个2,11在Pascal语言中，表达式 (21 xor 2)的值是（

5、） A. 441 B. 42 C.23 D.24,分析,1、21转化为二进制为10101，2转化为二进制是10。 2、xor表示异或操作，含义是“相同为0，不同为1”。 3、列竖式计算： 10101 00010 - 10111=23,进制数的运算： 十进制（0-9）、二进制（0、1）、 八进制（0-8）、十六进制（0-9，A-F）,1、十进制数 N进制数 方法：除N取余倒序法 2、N进制数 十进制数（要求到小数的转换） 方法：整数部分：kNi求和法 小数部分：小数部分*N取整 3、十六进制数与二进制数间的关系 一位十六进制位相当于4位二进制位 如（215）16=（001000010101）2

6、4、八进制数与二进制数间的关系 一位八进制位相当于3位二进制位 如（215）8=（010001101）2,15. 与十进制数1770 对应的八进制数是（ ）。 A. 3350 B. 3351 C. 3352 D. 3540,分析,1、关键是搞懂十进制转化为二进制的原理。 2、借鉴十进制转化为二进制的做法，采用“除8取余法”,18. (2010)16 + (32)8的结果是（ ）。 A. (8234)10 B. (202B)16 C. (20056)8 D. (100000000110)2,分析,1、4位二进制与16进制数一一对应；3位二进制数和8进制数一一对应，所以可以先转化为二进制数看看，判

7、断D是否满足 2、D判断的同时，B也可判断了 3、A和C都涉及到十进制数，所以先把表达式转化为十进制数，然后再判断答案为哪个。,6:信息安全,6. 在计算机中，防火墙的作用是（ ）。 A. 防止火灾蔓延 B.防止网络攻击 C. 防止计算机死机 D. 防止使用者误删除数据,7、8、9：算法与编程常识,7. 在下列关于计算机语言的说法中，不正确的是（ ）。 A. Pascal和C都是编译执行的高级语言 B. 高级语言程序比汇编语言程序更容易从一种计算机移植到另一种计算机上 C. C+是历史上的第一个支持面向对象的计算机语言 D. 与汇编语言相比，高级语言程序更容易阅读,分析,1、高级语言是基于编程

8、系统来编译的 汇编语言比高级语言更接近CPU，是直接和操作系统交换指令的。 2、第一个面向对象语言是smalltalk,8. 在下列关于计算机算法的说法中，不正确的是（ ）。 A. 一个正确的算法至少要有一个输入 B. 算法的改进，在很大程度上推动了计算机科学与技术的进步 C. 判断一个算法的好坏的主要标准是算法的时间复杂性与空间复杂性 D. 目前仍然存在许多涉及到国计民生的重大课题，还没有找到能够在计算机上实施的有效算法,分析,1、本题出现过好几次 2、本质就在考你一个误区：算法是否必须要有输入？其实输入不是必须的，而输出是必须的。,9. 在下列各种排序算法中，不是以“比较”作为主要操作的算

9、法是（ ）。 A. 选择排序 B. 冒泡排序 C. 插入排序 D. 基数排序,分析,1、基数排序是基于“分配”和“收集”的排序 2、即使不懂基数排序，知道了前3者排序的本质是“比较”和“移动”，通过排除法也是可以分析出正确答案的。,12在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)and (b0),分析,1、前面几个不懂没有关系，抓住D答案正确即可。 2、其实从离散数学的运算规律来分析，答案A,B,C回答的是同一个答案，都是错误

10、的。,16将5个数的序列排序，不论原先的顺序如何，最少都可以通过（ ）次比较，完成从小到大的排序。 A. 6 B. 7 C. 8 D. 9,分析,1、既然是追求最少比较次数，必定不会用n2的算法排序。 2、排序本质可说是循环查找各个位置上数 （1）用二分查找 （2）总次数3227,13、14、19、20：数据结构,13某个车站呈狭长形，宽度只能容下一台车，并且只有一个出入口。已知某时刻该车站状态为空，从这一时刻开始的出入记录为：“进，出，进，进，进，出，出，进，进，进，出,出”。假设车辆入站的顺序为1，2，3，则车辆出站的顺序为（ ）。 A. 1, 2, 3, 4, 5 B. 1, 2, 4,

11、 5, 7 C. 1, 4, 3, 7, 6 D. 1, 4, 3, 7, 2,模拟堆栈的操作即可,1、堆栈操作特征： （1）FILO,LIFO （2）每次只在一段进行操作 2、模拟操作 （1）”进、出“，出站为1 （2）”进、进、进、出、出“出站为4、3 （3） ”进、进、进、出、出“出站为7、6,14高度为n的均衡的二叉树是指：如果去掉叶结点及相应的树枝，它应该是高度为n-1的满二叉树。在这里，树高等于叶结点的最大深度，根结点的深度为0，如果某个均衡的二叉树共有2381个结点，则该树的树高为（ ）。 A. 10 B. 11 C. 12 D. 13,分析,1、满二叉树指的是：对于第i层，节点

12、数必定是2i。 2、满二叉树的节点数为2(i+1)-1 3、假定均衡树的层数为x，那么该均衡树对应的满二叉树（比均衡树小1层）节点数为2x-1,则必定有下列不等式： 2x-123812(x+1)-1 满足该不等式的x就是11。,19. 设栈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,分析,1、分析题意要正确。依次入栈指的不是”连续入栈，入栈之间没有出栈“。 2、接下来的关键是运用堆栈的操作特征。 （1）对各个

13、答案模拟入栈和出栈操作，是否有矛盾 （2）对于答案C” a, e, c, b, d “，既然e（最后入栈）在a后面出现，说明e出来时剩余字母都在堆栈中，而这些字母是顺序入栈的，那么出栈肯定是倒序，而这里没有倒序输出”c,b,d“，显然错误。,20. 已知6个结点的二叉树的先根遍历是1 2 3 4 5 6（数字为结点的编号，以下同），后根遍历是3 2 5 6 4 1，则该二叉树的可能的中根遍历是（ ） A. 3 2 1 4 6 5 B. 3 2 1 5 4 6 C. 2 1 3 5 4 6 D. 2 3 1 4 6 5,分析,1、知道后根（或者前根）遍历和中序遍历，可以唯一确定一棵二叉树。但知道

14、后根和前根是无法唯一确定一棵二叉树的。原因是对于根节点下面的节点我们无法根据前根和后根确定左右子树的根（可能只有某个子树）。 2、根据前根遍历和中根遍历，计算后根遍历是否满足试题顺序。,17：离散数学,17. 设A=B=D=true，C=false，以下逻辑运算表达式值为真(假)的有（ ）。 A. (AB)(CD) B. (ABD)C) C. A(BCD) D. (ABC)D,分析,1、离散数学的表示方法 2、其实只要知道表示and，表示or即可计算。,总结,1、进制转换是必考的 2、堆栈是必考的 3、二叉树性质、遍历必考的 4、微机原理必考的（CPU、ROM等） 5、排序算法的分析，概率较大

15、 6、新动向：和信息学奥赛的知识 7、信息安全，概率较大 8、网络有关知识，今年估计会出现,问题求解,1、数据结构 2、算法设计（构造类算法） 3、数学知识（初中不多，高中较多）,题1,1（寻找假币） 现有80枚硬币，其中有一枚是假币，其重量稍轻，所有真币的重量都相同，如果使用不带砝码的天平称重，最少需要称几次，就可以找出假币？你还要指出第1次的称重方法。请写出你的结果：_。,题1考察算法：分治法,1、该题的原型是用“二分法”编程求解。二分法至少需要log(80）次，大约是7。 2、二分法的优越在于每次判断时可以排除一半。进一步思考是否分成的部分越多，每次判断可以排除的数量越多？ 3、平均分成3份来判断，每次可以排除2/3数量。（思考分成更多份是否效果更好？）,具体算法,1、平均分成3份，如果不能被3整除，那么尽量让两份相同并且相同的两分应该比其他一份大1（每次判断可以排除更多的数量） 2、每次称相同的两份。直到最后相同的两分是1。,实例,27，27，26,9，9，9,1，1，1,3，3，3,9，9，8,1，1，1,3，3，2,1，1,题2,2（取石子游戏） 现有5堆石子,石子数依次为3