工程问题(一)
例1：甲、乙两队开挖一条水渠。甲队单独挖要8天完成，乙队单独挖要12天完成。现在两队同时挖了几天后，乙队调走，余下的甲队在3天内完成。乙队挖了多少天？
解：可以理解为甲队先做3天后两队合挖的。??
? ??+÷??? ???-121813811=3（天） 例2：加工一批零件，甲单独做20天可以完工，乙单独做30天可以完工。现两队合作来完成这个任务，合作中甲休息了2 .5天，乙休息了若干天，这样共14天完工。乙休息了几天？
解：分析：共14天完工，说明甲做（14－2.5）天，其余是乙做的，用14
天减去乙做的天数就是乙休息的天数。14－301205.2141÷??? ?
?--=141（天） 例3：一池水，甲、乙两管同时开，5小时灌满，乙、丙两管同时开，4小时灌满。现在先开乙管6小时，还需甲、丙两管同时开2小时才能灌满。乙单独开几小时可以灌满？
解：分析：把乙先开做6小时看作与甲做2小时，与丙做2小时，还有2小时，现在可理解为甲乙同开2小时，乙丙同开2小时，剩下的是乙2小时放
的。1÷?
?????÷?????????? ??+-2241511=20（小时） 例4：某工程，甲、乙合作1天可以完成全工程的24
5。如果这项工程由甲队单独做2天，再由乙队单独做3天，能完成全工程的24
13。甲、乙两队单独完成这项工程各需要几天？
解：分析：可以理解为两队合作2天，余下的是乙1天做的，乙的工效8122452413=?-， 甲：??
? ??-÷812451=12（天） 例5：一项工程，甲先单独做2天，然后与乙合做7天，这样才能完成全工程的一半。已知甲、乙工效的比是2:3。如果这项工程由乙单独做，需要多少天才能完成？
解：分析：乙的工效是甲工效的3÷2=1.5倍，设甲的工效为x ，乙的工效为1.5x ，
（2+7）x+1.5x ×7=21，解之得：x=39
1，乙工效1÷1.5x =26（天）
练习：
1、修一条公路，甲队独修15天完工，乙队独修12天完工。两队合修4天后，乙队调走，剩下的路由甲队继续修完。甲队一共修了多少天？
15
11241÷??? ??-=10（天） 2、一项工程，甲单独做20天完成，乙单独做30天完成。甲、乙合做几天后，乙因事请假，甲继续做，从开工到完成任务共用了16天。乙请假多少天？
16－30
1162011÷??? ???-=10（天） 3、一条公路由甲、乙两个筑路队合修要12天完成。现在由甲队修3天后，
再由乙队修1天，共修了这条公路的20
3。如果这条公路由甲队单独修，要多少天才能修完？
1÷()??
????-÷??? ??-13121203=120（天） 4、两列火车同时从甲、乙两地同时相对开出。快车行完全程需要20小时，慢车行完全程需要30小时。开出后15小时两车相遇。已知快车中途停留4小时，慢车停留了几小时？
15－()30
14152011÷??????-?-=221（小时） 5、师徒两人共同加工一批零件，2天加工了总数的3
1。这批零件如果全部由师傅单独加工，需10天完成。如果全部由徒弟加工，需要多少天才能完成？
1÷??? ??-÷10123
1=15（天） 6、一项工程，甲、乙两队合作30天完成。如果甲队单独做24天后，乙队再加入合作，两队合作12天后，甲队因事离去，由乙队继续做了15天才完成。这项工程如果由甲队单独完成，需要多少天？
分析：甲先做24天，乙最后做15天，可以理解为又合做15天加先合做12
天，共合做27天。 ()??
????-÷??? ???-÷152********=90（天） 7、一项工程，甲、乙两队合做每天能完成全工程的
409。甲队独做3天，乙
信息技术学科信息学奥赛社团培训计划 制定人：玄王伟 2018年10月
信息学奥赛培训计划方案推进信息技术教育是全面实施素质教育的需要，是培养具有创新精神和实践能力的新型人才的需要。信息学奥赛的宗旨为：“丰富学生课余生活，提高学生学习兴趣，激发学生创新精神。”为此，我们应以竞赛作为契机进而培养学生综合分析问题、解决问题的意识和技能。 为响应学校号召，积极参与信息技术奥林匹克竞赛，校本课程特别开设C++语言程序设计部分，利用社团活动时间对部分学生进行辅导。教学材料以信息学奥赛一本通训练指导教程为主，力图让学生们对编写程序有较深入了解的同时，能够独立编写解决实际问题的算法，逐步形成解题的思维模式。因学习内容相对中小学学生具有一定的难度，本课程采用讲练结合的形式，紧紧围绕“程序=算法+数据结构”这一核思想，以数学问题激发学生学习兴趣，进而达到学习目标。为更好地保证信息学奥赛的培训效果，特制订本培训计划。 一、培训目标 1.使学生具备参加全国信息学奥林匹克竞赛分区联赛NOIP（初赛、复赛）的能力。 2.使学生养成较好的抽象逻辑推理能力、严谨的思维方式和严密的组织能力，并使学生的综合素质的提高。 3.使学生初步具备分析问题和设计算法的能力。 二、培训对象 我校小学及初中对信息学感兴趣且初赛成绩较好的学生，人数共
计14人，其中小学组12人，普及组2人。 三、培训要求 严格培训纪律，加强学生管理；信息学社团的组建由学生自愿报名、教师考察确定；培训过程中做与培训无关的事如打游戏、上网聊天等，一经发现作未参加培训处理；规定的作业、练习必须按时保质保量完成，否则按未参加培训处理。 四、培训内容 1.深入学习计算机基础知识，包括计算机软硬件系统、网络操作、信息安全等相关知识内容，结合生活实际让学生真正体会到参加信息学奥赛的乐趣。 2.全面学习C++语言的基础知识、学会程序的常用调试手段和技巧，在用C++解决问题的过程中引入基础算法的运用。 3.深入学习各类基础算法，让学生真正理解算法的精髓，遵循“算法+数据结构=程序”的程序设计思想，在算法设计的教学实例中引入数据结构的学习，从而形成一定的分析和解决问题的能力。 4.以实例为基础，展开强化训练，使学生开始具备运用计算机独立解决实际问题的能力。用计算机解决现实问题的最重要的一个前提就是数据模型的建立和数据结构的设计。数据模型的建立、数学公式的应用，是计算机解决问题的关键。因此，加强与数学学科的横向联系非常必要。 五、培训时间 自2018年10月份第三周开始至2018年11月中旬结束，包括每
全国青少年信息竞赛 培训教材 第一章 计算机和计算机语言 101 【问题描述】 求S = 1-2+3-4+……-100 102 【问题描述】 求圆面积程序，写出程序的运行结果。 #include
{ printf(“%s\n”, s); printf(“radium is: %d\n”, r); printf(“Arrea of circle is: %lf\n”, pi * r * r); printf(“Arrea of circle is: %10lf\n”, pi * r * r); printf(“Arrea of circle is: %10.3lf\n”, pi * r * r); // system(“pause”); return 0; } 103 【问题描述】 判定2000-2005年中的每一年是否闰年，输出其中所有闰年的年份。请写出程序的运行结果。 【源程序】 #include
关于成立信息学奥赛兴趣小组的方案 一、信息学奥赛简介 1、信息学奥赛概述 奥林匹克竞赛活动的宗旨，主要是激发青少年对科学的兴趣。通过竞赛达到使大多数青少年在智力上有所发展，在能力上有所提高的目标。 并在普及活动的基础上，为少数优秀的青少年脱颖而出、成为优秀人才 创造机遇和条件。全国五项学科竞赛包括数学、物理、化学、信息学（计 算机）、生物学五个学科。 全国青少年信息学奥林匹克竞赛（简称NOI）是经教育部批准、中国科协主管、中国计算机学会主办，这一活动在普及计算机知识的基础上， 激发广大青少年对信息技术及其应用的兴趣，对青少年学生开阔眼界、 扩大知识面，培养逻辑思维、创造思维及应用计算机解决实际问题的能 力都有很大促进作用。 全国青少年信息学奥林匹克联赛（National Olympiad Informatics in Pronvinces，简称NOIP）在同一时间、不同地点以各省市为单位由特派员 组织。全国统一大纲、统一试卷。初高中或其他中等专业学校的学生可 报名参加联赛。联赛分初赛和复赛两个阶段。初赛考察通用和实用的计 算机科学知识，以笔试为主。复赛为程序设计，须在计算机上调试完成。 参加初赛者须达到一定分数线后才有资格参加复赛。联赛分普及组和提 高组两个组别，难度不同，分别面向初中和高中阶段的学生。 2、针对我校实际情况成立信息学奥赛的意义： 我校有初中部和高中部，初中部面临有三中和四中的有力竞争，我校在小升初的招生中不占优势，高中部招生又面临强大的竞争对手和县 一中，高中优质生源流失。这几年编程教育逐渐被国家重视，信息学奥 赛又成为热门项目，在大城市开展的热热烈烈。而纵观全县，几乎为空 白。本人从事信息技术一线教学超过十年，编程一线教学也有三年，积 累了很多经验，愿意为我们和县的学子普及计算机并挑选人才作出努力。 也同时使得和县二中在招生中更具竞争力。 二、兴趣小组的学生选拔 面向七年级新生，有较强的逻辑思维能力，在数学、英语等学科成绩优异的，具有良好的数学基础和英文水平，能掌握程序设计语言和算法中的一些常用的英文关键词，对编程感兴趣的学生均可以报名。由各班班主任积极在班级中宣传，学生自愿报名。 三、寻求学校支持 1、辅导课按学校相关标准给予课时补贴
信息学奥赛（NOIP）必看经典书目汇总！ 小编整理汇总了一下大神们极力推荐的复习资料！（欢迎大家查漏补缺） 基础篇 1、《全国青少年信息学奥林匹克分区联赛初赛培训教材》（推荐指数：4颗星） 曹文，吴涛编著，知识点大杂烩，部分内容由学生撰写，但是对初赛知识点的覆盖还是做得相当不错的。语言是pascal的。 2、谭浩强老先生写的《C语言程序设计（第三版）》（推荐指数：5颗星） 针对零基础学C语言的筒子，这本书是必推的。 3、《骗分导论》（推荐指数：5颗星） 参加NOIP必看之经典 4、《全国信息学奥林匹克联赛培训教程（一）》（推荐指数：5颗星） 传说中的黄书。吴文虎，王建德著，系统地介绍了计算机的基础知识和利用Pascal语言进行程序设计的方法 5、《全国青少年信息学奥林匹克联赛模拟训练试卷精选》 王建德著，传说中的红书。 6、《算法竞赛入门经典》（推荐指数：5颗星） 刘汝佳著，算法必看经典。 7、《算法竞赛入门经典:训练指南》（推荐指数：5颗星） 刘汝佳著，《算法竞赛入门经典》的重要补充 提高篇 1、《算法导论》（推荐指数：5颗星） 这是OI学习的必备教材。
2、《算法艺术与信息学竞赛》（推荐指数：5颗星） 刘汝佳著，传说中的黑书。 3、《学习指导》（推荐指数：5颗星） 刘汝佳著，《算法艺术与信息学竞赛》的辅导书。（PS：仅可在网上搜到，格式为PDF）。 4、《奥赛经典》（推荐指数：5颗星） 有难度，但是很厚重。 5、《2016版高中信息学竞赛历年真题解析红宝书》（推荐指数：5颗星） 历年真题，这是绝对不能遗失的存在。必须要做！ 三、各种在线题库 1、题库方面首推USACO（美国的赛题），usaco写完了一等基本上就没有问题，如果悟性好的话甚至能在NOI取得不错的成绩. 2、除此之外Vijos也是一个不错的题库，有很多中文题. 3、国内广受NOIP级别选手喜欢的国内OJ（Tyvj、CodeVs、洛谷、RQNOJ） 4、BJOZ拥有上千道省选级别及以上的题目资源，但有一部分题目需要购买权限才能访问。 5、UOZ 举办NOIP难度的UER和省选难度的UR。赛题质量极高，命题人大多为现役集训队选手。
§3栈和队列 §3.1 栈 栈（stack）是一种仅限于在称为栈顶（top）的一端进行插入和删除操作的线性表，另一端则被为栈底（bottom）。不含元素的空表称为空栈。 栈的特点：后进先出（Last In First Out），简称：LIFO。 栈的表示和实现 和线性表类似，栈也有两种存储结构。 （1）．顺序栈 顺序栈即采用的顺序存储结构来表示栈，通常采用数组来实现。 采用顺序栈受数组空间的约束，有“溢出”的可能，编程前应作空间估算，若有溢出可能，应作溢出判断及相应的处理。 在一个程序中，常常会出现同时使用多个栈的情形。为了不因栈上溢而产生错误中断，必须给每个栈预分一个较大的空间，但这并不容易做到，因为栈实际所用的最大空间很难估计；而且各个栈的实际使用量在使用期间是变化的，往往会有这样的情况，即其中一个栈发生上溢，而另一个栈还是空的。设想，若令多个栈共享空间，则将提高空间的使用效率，并减少发生栈上溢的可能。 所以，可以采用两个栈共享空间的方法：假设在程序中需设两个栈，并共享一维数组空间。则利用“栈底位置不变”的特性，可将两个栈的栈底分别设在数组空间的两端，然后各自向中间伸展（如图），仅当两个栈的栈顶相遇时才可能发生上溢。 （2）．链栈 采用链式存储结构的栈简称链栈。 对于链栈，不含产生单个栈溢出的情况，但要记得回收结点空间（dispose（p）），否则会出现整个空间被占满，new（p）过程无法实现（即无法申请新的结点空间）的情况。
【练习】 回文串识别 输入一字符串，判断它是否为一回文串。所谓回文串是指去掉其中的空格与标点符号等非字母符号后，从前后两个方向读到的串相同，例如： ten animals I slam in a net. （我将十只动物装在网里） 输入：一字符串 输出：Yes 或No §3.2 队列 队列（queue ）是所有的插入都在一端进行，而所有的删除都在另一端进行的线性表。允许插入的一端称为队尾（rear ），允许删除的一端称为队头（front ）。 队列的特点：先进先出（|First In First Out ），简称：FIFO 。 队列的表示和实现 和栈一样，队列也有顺序存储和链式存储两种表示和实现方法。 在顺序存储结构中，同样有溢出可能，即元素因队满而无法入队。对于队列来说，可以采用循环队列的技巧，仅当队头与队尾相遇时为队满。 【例3.2.1】逐行打印二项展开式 (a + b )i 的系数： 杨辉三角形 (Pascal’s triangle) 要求：采用队列实现！ 输入： n ——层数（n<50）25 a 1 a 2 a 3 …… a n 出队列 出队列 队头 队尾 队头 队尾 1 1 i = 1 1 2 1 2 1 5 5 1 3 1 4 6 4 1 4 1 5 10 10 5 1 5 1 6 15 20 15 6 1 6
初中信息学奥赛校本教材开发的实践与研究 目前，有关信息学方面的教材比较多，如，南京大学出版社出版的《全国青少年信息学奥林匹克联赛》《信息学（计算机）奥林匹克》，电子工业出版社出版的《PASCAL语言程序设计》，科学技术文献出版社出版的《Free Pascal语言与基础算法》等，每本教材都有各自的局限性，有些并不符合我校学生的实际情况。 我校从2003年开始开展信息学奥赛校本课程，培训资料大部分来源于大学计算机专业教材，随着网络资料的不断丰富和信息学方面的教材出版增多，培训资料搜集的来源越来越丰富。 在这十几年信息学竞赛的教学过程中，笔者深知初中学生的特点和教学规律，这使得最终开发的校本教材能够适合初中信息学奥赛校本课程。现将自己在校本教材开发实践中得到的感受和思考，简述如下，希望得到同行和专家的指正。 一、适合初中生 由于初一学生在小学的时候一般都没有接触过计算机程序，程序对他们来说既神秘又陌生。这个阶段的学生好奇心强、动手解决问题的欲望强烈，但是还不能比较理智地处理问题，排除各种对学习的干扰。因此，他们往往不能保持学习精力的高度集中和自觉。 程序入门例题：
1.已知一辆自行车的售价是300元，请编程计算a辆自行车的总价是多少？ 2.“鸡兔同笼”问题，已知笼中的头共30个，脚共90只，问鸡和兔各有多少只？ 3.“兔子繁殖”问题，已知一对兔子，每个月可以生一对小兔，而小兔过一个月也可生一对小兔。即兔子的对数是：第一个月1对，第二个月2对，第三个月3对，第四个月5对……假设兔子的生育期是12个月，并且不死，问一年后，这对兔子有多少对活着的后代？ 二、培养学生自学能力为目的 参加信息学奥赛的学生都是经过选拔出来学校中最优秀的 学生，这批学生各方面能力都很强，他们需要有自由发挥的空间，在教学过程中提倡学生的自主探究，而教师对学生的学习中起到引导作用。因此，开发的校本教材本身要适合教学。 1.教材中问题的设计首先与现实生活、新兴的科技成果等问题密切联系，让学生知道学习的实际用途，如果一个学生连自己为什么要学习都弄不清楚，那么他的学习行为肯定是被动的。 2.问题的解决，必须要有思考的过程，所以每个题目都加入了对问题不同程度的解析，再通过分析得出程序，给学生参考，让学生知道为什么这么写程序。 3.学生懂得了具体的解题思路，但是对于具体程序可能还是有难度的，所以对于一个程序中关键的代码要给予注释，加深学
PASCAL程序设计 第1章计算机的发展与应用 1.1 计算机发展简史 1.1.1 第一台电子计算机的诞生 1946年，世界上第一台数字式电子计算机由美国宾夕法尼亚大学的物理学家约翰·莫克利（John Mauchly）和工程师普雷斯伯·埃克特（PresperEckert）领导研制成功，取名为ENIAC（Electronic Numerical Integrator And Calculator）。它可以在1秒进行5000次加减运算，3毫秒便可以进行一次乘法运算，能存储20个字长为10位的十进制数。 1.1.2 计算机发展的几个阶段 第四代计算机以大规模集成电路VLSI为计算机的主要功能部件，用16K、64K或集成度更高的半导体存储器作为主存储器。 新机器要继承原有机器指令系统中的全部指令，使得同一系列计算机的指令系统越来越复杂，这些计算机被称为“复杂指令系统计算机”，简称CISC。 日趋庞大的指令系统降低了系统性能，而机器中最常常的是一些简单指令，这些指令仅占指令系统中指令总数的20%，1975年提出了精简指令系统，简称RISC。 冯·诺依曼型计算机是采用存储程序方式进行工作。 研制中的第五代计算机，是一种智能计算机，具有自动识别自然语言、图形、图像有能力，具有理解和推理能力，具有知识获取、知识更新能力。研制朝两个方向努力：①创建非冯·诺依曼式语言，LISP、PROLOG、F.P.；②创建以人脑神经系统处理信息的原理为基础的非冯·诺依曼式的计算机模型，生物计算机、光子计算机、量子计算机。 1.2 计算机对现代社会的影响 1.2.1 计算机应用概述 1、科学计算：利用计算机解决科学研究和工程技术中所提出的复杂的数学问题。 2、数据处理：利用计算机对所获取的信息进行记录、整理、加工、存储和传输等。 3、人工智能：利用计算机来模仿人类的智力活动。 4、自动控制：利用计算机对动态的过程进行控制、指挥和协调。
中学信息学奥林匹克竞赛培训教程 Pascal语言和程序设计基础 （第一部分）
第一部分 Pascal语言和程序设计基础 预备知识 基本程序结构和几个概念:： 标识符保留字常量变量运算符表达式标准数据类型 Pacal语言程序结构 Program prog_name; var变量申明; begin 程序体; end. 例如： program pname; const n=4; type arr=array [1..4] of integer; var i:integer; a:arr; begin for i:=1 to n do read(a[i]); readln; for i:=n downto 1 do write(a[i]:4); writeln; end. 以上是一个PASCAL程序。从键盘读入4个数据，逆序输出。 一般来说，一个PASCAL程序包括以下几个部分： 程序头：program pname; 其中，program是保留字，表示程序从这个地方开始，pname是标识符，是程序的名字，可由程序员自定。保留字是PASCAL选定的，具有固定意义和用法的专用单词或缩写，这些单词不允许作其它使用。如上，“program”就有“程序从这里开始”这样一种特别的意义，而“const”就有“常量说明从这里开始”的意义。我们不能再用“program”、“const”来作为其它变量、常量等的名字。标识符是以字母开头的字母数字串，其长度最大为8个字符。用来表示常量、变量、类型、文件、过程、函数和程序的名字。如“pname”、“i”、“j”、“a1”就是合法的标识符；但“1a”、“#a”是非法的标识符。有一点要注意的是，在PASCAL中，字母除了作为字符值或字符串值之外，其大小写是无关的。如标识符“A1”和“a1”在PASCLA看来是同一标识符。在PASCAL中除了保留字和自定义的标识符外，还有一类有特殊含义的标识符，这类标识符称为标准标识符。它们是用来标记程序中经常引用的处理对象，如常量、函数。（PASCAL定义的保留字和标准标识符附后） 标识符在命名的时候要注意： 1、名字要易记易读，有意义。如8皇后问题程序名可以是“queen”也可以是“huanghou”等； 2、不能用保留字、标准标识符作为自定义的标识符。 说明部分： const n=4; type ar=array [1..4] of integer; var i:integer; a:ar; 其中，const部分是常量说明，说明一些在以下部分用到的，在整个程序执行过程不改变值的量。这些量PASCAL称为常量。在程序中用到这个值的地方均用常量名来代替。如上题中定义“n=4”指本程序处理4个数值，在下面的程序体中就用“n”来代替具体的值（如for i:=1 to n）。如果要改变处理数据个数，则只在常量说明部分修改“n=4”这一句就行了，而不用在程序中每一个用到的地方都加以修改。这样不但在编写程序的时候很方便，也增加了程序的可读性，修改时更方便。
树 §7.1 树的概念 【定义】 树（Tree ）是n （n>0）个结点的有限集合T ，它满足如下两个条件： (1) 有且仅有一个特定的称为根（Root ）的结点； (2) 其余的结点可分为m （m ≥0）个互不相交的有限集合，其中每一个集合又都是一颗树，并称为根的子树（Sub Tree ）。 【基本术语】k 树的结点包含一个数据元素及若干指向其子树的分支。 结点拥有的子树数称为结点的度（degree ）。 如图7.1，A 的度为3，C 的度为1，F 的度为0。 度为0的结点称为叶子（leaf ）或终端结点。例如K 、L 、F 、G 、M 、I 、J 。 度不为0的结点称为分支结点或非终端结点。 除根结点外，分支结点也称为内部结点。 树的度是树内各结点的度的最大值，如图7.1中树的度为3。 结点的子树的根称为该结点的孩子（Child ），该结点称为孩子的双亲（parent ）。 如图7.1.1，B 为A 的子树的根，则B 是A 的孩子，而A 则是B 的双亲。 同一个双亲的孩子之间互称为兄弟（sibling ），例如B 、C 、D 互为兄弟。 将这些关系进一步推广，可认为D 是M 的祖父。结点的祖先是从根到该结点所经分支上的所有结点。例如，M 的祖先为A 、D 、H 。 反之，结点的子树中的任一结点都称为该结点的子孙，如B 的为E 、F 、K 、L 。 5. 结点的层次（level ）是从根开始定义起，根为第一层，根的孩子为第二层。 若某结点在第x 层，则其子树的根就在x+1层。 树中结点的最大层次称为树的高度或深度（depth ）。如图7.1的树的深度为4。 6. 如果将树中的结点的各子树看成从左到右是有次序的（即不能互换），则称该树为有序树,否则称为无序树。如图 7.1.2。 7. 森林（forest ）是m （m ≥0）棵互不相交的树的集合。 §7.2 二叉树 §7.2.1 二叉树的定义 二叉树（binary tree ）是一种树型结构，它的每个结点至多只有二棵子树（即二叉树中不存在度大于2结点），并且，二叉树的子树有左右之分，其次序不能任意颠倒。 （如图7.2.1） 满二叉树和完全二叉树是两种特殊形态的二叉树。 满二叉树是指深度为k ，且有2k -1个结点的二叉树。 完全二叉树是指深度为k ，有n 个结点，当且仅当每一个结点都与深度为k 的满二叉树中编号从1到n 的结点一一对应时。 §7.2.2 二叉树的性质 性质1：在二叉树的第i 层上至多有 ① 个结点（i ≥1）。 性质2：深度为k 的二叉树至多有 ② 个结点（k ≥1）。 性质3：对任意一棵二叉树，如果度为2的结点数为n 2，则其叶子结点数为 ③。 性质4：具有n 个结点的完全二叉树的深度为 ○A ○B ○C ○D ○E ○F ○G ○H ○I ○J ○K ○L ○ M 图7.1.1 ○A ○A ○B ○C ○C ○B 图7.1.2 两棵不同的有序树 ○A ○B ○C ○D ○E ○F ○G ○H ○I ○J 图7.2.1 ○1 ○2 ○3 ○4 ○5 ○6 ○7 ○ 8 ○9 ○10 ○11 ○12 ○13 ○14 ○15 图7.2.2 满二叉树 ○1 ○2 ○3 ○4 ○5 ○6 ○7 ○8 ○9 ○10 ○11 ○12 图7.2.3 完全二叉树 ○1 ○2 ○3 ○4 ○5 ○6 ○7 ○8 ○9 ○10 ○11 ○12 图7.2.4 非完全二叉树
信息学（计算机）奥林匹克竞赛辅导教程浙江金华第一中学《信息技术》教研组
金华一中信息学（计算机）奥林匹克竞赛辅导教程 目录 第一部分试题的知识范围1 一、初赛的要求1 二、复赛内容与要求2第二部分计算机基础知识3 一、计算机的诞生、发展、特点及应用3 1.计算机的诞生和发展3 2.计算机的分类3 3.计算机的特点3 4.PC机及其系统配置3 5计算机在现代社会中的应用4 二、计算机系统组成及工作原理4 1.计算机的系统组成4 2.计算机语言的发展5 3.计算机的工作原理6 三、计算机信息安全6 1.计算机系统的危害来源6 2.计算机系统的安全策略6 3.计算机病毒的概念6 4.计算机病毒的种类7 5.计算机病毒的特征7 6.计算机病毒的传染途径7 四、计算机网络基础7 1.计算机网络的相关定义7
2.计算机网络的功能7 3.计算机网络发展的几个阶段7 4.计算机网络的组成8 5.计算机网络的分类8 6.计算机网络的体系结构和网络协议9 7.网际协议IP与IP地址12 8Internet的域名13 9.常见计算机网络的应用13 五、计算机中数的表示及运算15 1.十进制数16 2.二进制数16 3.八进制数与十六进制数17 4.其他进制数与十进制数之间的转换19 5.计算机中数的表示19 6.字符与汉字的编码22六图形化视窗操作系统23 1.图形用户操作系统23 2.Windows家族23 3.Windows98的主要功能与特性23 七、数据库系统简述24 1.数据库的基本概念24 2.数据表的结构24 3.表结构24
第一部分试题的知识范围 一、初赛的要求 1.1计算机的基本常识 ①计算机和信息社会（信息社会的主要特征、计算机的主要特征、数字通信网络的主要特征、数字化） ②信息输入输出基本原理（信息交换环境、文字图形多媒体信息的输入输出方式） ③信息的表示与处理（信息编码、微处理部件MPU、内存储结构、指令、程序，和存储程序原理、程序的三种基本控制结构） ④信息的存储、组织与管理（存储介质、存储器结构、文件管理、数据库管理） ⑤信息系统组成及互连网的基本知识（计算机构成原理、槽和端口的部件间可扩展互连方式、层次式的互连结构、互连网络、TCP/IP协议、HTTP协议、WEB应用的主要方式和特点） ⑥人机交互界面的基本概念（窗口系统、人和计算机交流信息的途径（文本及交互操作）） ⑦信息技术的新发展、新特点、新应用等。 1.2计算机的基本操作 ①Windows和Linux的基本操作知识 ②互联网的基本使用常识（网上浏览、搜索和查询等） ③常用的工具软件使用（文字编辑、电子邮件收发等） 1.3程序设计的基本知识 1.3.1数据结构 ①程序语言中基本数据类型（字符、整数、长整数、浮点） ②浮点运算中的精度和数值比较 ③一维数组（串）与线性表 ④记录类型（Pascal）/结构类型（C） 1.3.2程序设计 ①结构化程序设计的基本概念 ②阅读理解程序的基本能力 ③具有将简单问题抽象成适合计算机解决的模型的基本能力 ④具有针对模型设计简单算法的基本能力 ⑤程序流程描述（自然语言/伪码/NS图/其他） ⑥程序设计语言（Pascal/C/C++,2003年仍允许BASIC） 1.3.3基本算法 ①初等算法（计数、统计、数学运算等） ②排序算法（冒泡法、插入排序、合并排序、快速排序）
《信息学奥林匹克教程(数据结构篇) 奥赛经典高级教程系列(奥赛经典高级教程系列)》 内容简介 为了进一步推广、普及计算机技术，提高竞赛水平，在原来编写的一套《信息学奥林匹克教程》（基础篇·提高篇·语言篇）的基础了，我们又编写了这本《数据结构篇》。 《数据结构篇》主要帮助学生全面地掌握数据结构知识与应用技巧，相对于其他数据结构书不同之处就在于增加了一些针对性的例题和习题，着眼点是提高数据结构的应用方法与技巧，是一本具有实战意义的教材。 从逻辑角度看，数据可归结为三种基本结构：线性结构、树结构和图结构；从存储角度看，数据可归结为四种基本结构：顺序结构、链接结构、索引结构和散列结构。每一种逻辑结构可根据不同需要采用不同的存储结构，或者不同的存储结构的组合。数据的逻辑结构和存储结构确定后，再结合指定运算的算法，就容易利用一种程序设计语言编写出程序。通过数据结构的学习，能够大大提高程序设计能力和水平。 《数据结构篇》是为广大信息学爱好者学习数据结构而精心编著的一本教材。本书内容比较全面，着重于实用与实战，在算法分析上简明扼要，细致清晰，便于自学。全书共分十章：第一章为概论，它为学习以后的各章做准备；第二章至第五章为线性结构；第六章和第七章分别为树结构和图结构，分别讨论了每一种逻辑结构所对应的存储结构和相应的算法；第八章和第九章分别为查找与排序，它包含了数据处理中主要使用的几种查找和内排序方法；最后一章为读者提供了检测知识的模拟试题及解答。 作者简介 向期中，长郡中学特级教师，湖南省计算机学会理事，国际金牌教练，国家教育部计算机课程咨询委员会委员。对中小学计算机教育事业有一种执着的追求，参加工作20年来，一直以“当一流教师，办一流教育，出一流人才”为自己的工作目标，对中小学计算机教学和青少年信息学奥林匹克竞赛的辅导倾注了全部热情和心血。在信息学奥林匹克竞赛培训中把“先做人，后成才”的育人理念贯穿到整个奥赛培训的始终，学生在愉快的学习中取得了一个个辉煌的成绩：在近几年的信息学奥林匹克竞赛中，辅导的学生有100多人获湖南省一等奖，11人次进入国家集训队，3人进入国家代表队，3人获国际金牌。撰写了《信息学（计算机）国际奥林匹克Turbo Pas—cal 6.0》等十多部信息学专著。多次荣获园丁奖和全国优秀辅导员称号，还先后获得全国中小学计算机教育先进工作者、湖南省优秀教师和全国信息学奥林匹克竞赛高级指导教师等荣誉称号。
全国信息学奥林匹克竞赛中级指导教师培训班 教学大纲 一、宗旨 中国计算机学会将定期举办全国信息学奥林匹克中级指导教师培训班，旨在提高各地中学从事信息学奥林匹克培训指导教师的整体水平，从而更好地在中学里开展计算机应用和程序设计的普及教育，为培养高水平的计算机专业人才奠定良好的基础。 培训班将依据《全国青少年信息学奥林匹克联赛（NOIP）大纲》确定教学内容。鉴于培训时间较短（一般在一周左右），教学以传授相关知识为主，学员业务能力的提高主要依靠个人自身的努力。通过培训，应使学员了解参与信息学竞赛必备的知识要点；掌握基本的程序设计、算法和数据结构的有关内容；经过继续努力，可以独立承担NOIP 提高组的培训工作。 培训班还将为从事信息学奥林匹克培训的一线教师提供一个直接交流的平台，交流和探讨各校的培训内容、方法、培训模式和成功的经验，以便推动全国各省市信息学奥林匹克竞赛水平的均衡发展。 二、教学内容 （1）程序设计语言概要 由于学员水平不一，使用的程序设计语言不同，有必要用一定的时间介绍培训中将要使用的程序设计语言的核心内容（条件语句、循环语句、指针、结构、函数（或过程）的定义和引用等）。建议任课教师使用C/C++语言，也可以使用Pascal语言。程序运行环境由任课教师参照NOIP竞赛环境选定。 建议适当介绍如何检验程序的正确性和如何设计测试数据。 （2）算法设计与数据结构基础 （2.1）递归回溯与基本搜索方法（递归的基本思想与实现过程，深度优先搜索，n 后问题、0-1背包问题、图的m着色、连续邮资问题、最大团问题等；近几年NOIP相关试题）。 （2.2）贪心算法（单源最短路径、最小生成树、哈夫曼编码等）。 （2.3）线性结构、图与树的相关问题（链表、堆栈、队列、串、哈希表、树的存贮结构、几类典型的二叉树、树的遍历、图的存贮结构、图的遍历、图的连通性、拓扑排序与关键路径等；近几年NOIP相关试题） （2.4）分治算法（二分搜索、棋盘覆盖问题、快速排序、跳马问题） （2.5）动态规划（基本思想、0-1背包问题、矩阵连乘问题、最长公共子列、最优二叉搜索树等；近几年NOIP相关试题）
信息学奥赛教学的几点心得 莫兵华 江西省新余市第四中学(338000) 【内容提要】看了许多别人有关信息学奥赛教学的论文，觉得受益匪浅，从事信息学奥赛教学有几年了，取得了一些成绩，同时也积累了一些经验，特地拿出来与各位同行共享，本文从培养学生的自信心，培养学生的自学能力，不拘泥于常规的教学方式以及形成初高中信息学奥赛的衔接、形成梯队这四个方面来进行论述。 【关键词】NOIP、自信、自学、教学方式、梯队 全国青少年信息学奥林匹克分区联赛(简称NOIP)是经中国科协、国家教育部批准，由中国计算机学会主办的一项全国性的青少年学科竞赛活动。随着信息学奥林匹克竞赛的深入开展，越来越多的教师都已投入此项教学的研究之中。我从事这项工作已有一段时间。现就我在中学信息学奥林匹克竞赛教学中的做法与各位同行进行交流，希望能得到同行的批评指正。 一、培养学生的自信心 什么是自信呢？自信是一种正确、积极的自我观念和自我评价。积极意味着一种对自己的认同、肯定和支持的态度。而在现今的学生当中，普遍存在着自我评价过低的现象，很多学生在能够完成的事情面前，认为自己干不了，于是畏缩犹豫裹足不前，压抑了内在能力的发挥。在NOIP联赛中，自信心对学生至关重要，缺乏自信，要想在NOIP联赛中取得好成绩，根本就是不可能的。结合这些年的教学经验，我觉得应从下面几个方面来培养学生的自信心： 1、教师要用自己的自信心鼓舞和感染激励学生 “教师的世界观，他的品行，他的生活，他对每一现象的态度，都这样那样地影响全体学生。”这句话道出了一个道理：教师不仅是学生知识的传授者，更应该做学生的楷模。因此，教师要用自己的自信心鼓舞和感染激励学生。学生在潜移默化中受到了鼓舞和感染，也信心百倍。我经常对我的学生说，我一定可以把你们送上NOIP联赛的领奖台，比赛时，我都会对学生说，你们一定能拿到奖，因为你们有足够的实力，我让学生在心目中形成一个这样的认识：“就是我行，
目录 青少年信息学奥林匹克竞赛情况简介 (5) 第一章计算机基础知识 (7) 1.1 计算机的基本常识 (7) 1.1.1 计算机的产生与发展 (7) 1.1.2 计算机系统及工作原理 (7) 1.1.3 计算机中有关数及编码的知识 (8) 1.1.4 原码、反码与补码 (10) 1.1.5 逻辑运算 (10) 1.2 操作系统 (11) 1.2.1 DOS(Disk Operating System)的组成 (11) 1.2.2 DOS的文件和目录 (11) 1.2.3 DOS命令 (12) 1.2.4 Windows简介 (12) 1.3 计算机网络常识 (13) 1.3.1 网络基础知识 (13) 1.3.2 Internet简介 (14) 1.4 计算机信息安全基础知识 (16) 1.4.1 计算机的网络安全 (16) 1.4.2 计算机病毒 (17) 1.4.3 病毒的分类 (17) 第2章C++编程简介 (19) 2.1 机器语言、汇编语言和高级语言 (19) 2.2 C语言与C++的历史 (20) 2.3 C++标准库 (20) 2.4 结构化编程 (21) 2.5 简单程序 (22) 2.6 简单程序：两个整数相加 (25) 2.7 算术运算 (27) 2.8 判断：相等与关系运算符 (29) 2.9 新型头文件与名字空间 (31) 第3章 C++输入/输出流 (33) 3.1 简介 (33) 3.2 流 (33) 3.2.1 iostream类库的头文件 (34) 3.2.2 输入/输出流类和对象 (34) 3.3 输出流 (35)
3.3.1 流插入运算符 (35) 3.3.2 连续使用流插入/流读取运算符 (37) 3.3.3 输出char*类型的变量 (37) 3.3.4 用成员函数put输出字符和put函数的连续调 (38) 3. 4 输入流 (39) 3.4.1 流读取运算符 (39) 3.4.2 成员函数get和getline (41) 3.5 成员函数read、gcount和write的无格式输入/输出 (44) 3.6 流操纵算子 (45) 3.6.1 整数流的基数：流操纵算子dec、oct、hex和setbase (45) 3.6.2 设置浮点数精度(precision、setprecision) (46) 3.6.3 设置域宽(setw、width) (47) 3.6.4 用户自定义的流操纵算子 (48) 3.7 流格式状态 (49) 3.7.1 格式状态标志 (50) 3.7.2 尾数零和十进制小数点(ios::showpoint) (50) 3.7.3 对齐(ios::left、ios::right、ios::internal) (51) 3.7.4 设置填充字符(fill、setfill) (53) 3.7.5 整数流的基数：(ios::dec、ios::oct、ios::hex、ios::showbase) (54) 3.7.6 浮点数和科学记数法(ios::scientific、ios::fixed) (55) 3.7.7 大/小写控制(ios::upercase) (56) 3.7.8 设置及清除格式标志(flags、setiosflags、resetosflags) (57) 3.8 流错误状态 (58) 第4章文件处理 (61) 4.1 简介 (61) 4.2 文件和流 (61) 4.3 建立并写入文件 (61) 4.4 读取文件中的数据 (65) 4.5 更新访问文件 (67) 第5章 C++的字符串流 (68) 5.1 流的继承关系 (68) 5.2 字串流的输入操作 (68) 5.3 字串流的输出操作 (69) 5.4 字串流在数据类型转换中的应用 (70) 5.5 输入/输出的状态标志 (71) 第6章控制结构 (74) 6.1 简介 (74) 6.2 算法 (74) 6.3 控制结构 (74) 6.4 if选择结构 (75) 6.5 if/else选择结构 (76)
江西省南昌市2015-2016学年度第一学期期末试卷 （江西师大附中使用）高三理科数学分析 一、整体解读 试卷紧扣教材和考试说明，从考生熟悉的基础知识入手，多角度、多层次地考查了学生的数学理性思维能力及对数学本质的理解能力，立足基础，先易后难，难易适中，强调应用，不偏不怪，达到了“考基础、考能力、考素质”的目标。试卷所涉及的知识内容都在考试大纲的范围内，几乎覆盖了高中所学知识的全部重要内容，体现了“重点知识重点考查”的原则。 1．回归教材，注重基础 试卷遵循了考查基础知识为主体的原则，尤其是考试说明中的大部分知识点均有涉及，其中应用题与抗战胜利70周年为背景，把爱国主义教育渗透到试题当中，使学生感受到了数学的育才价值，所有这些题目的设计都回归教材和中学教学实际，操作性强。 2．适当设置题目难度与区分度 选择题第12题和填空题第16题以及解答题的第21题，都是综合性问题，难度较大，学生不仅要有较强的分析问题和解决问题的能力，以及扎实深厚的数学基本功，而且还要掌握必须的数学思想与方法，否则在有限的时间内，很难完成。 3．布局合理，考查全面，着重数学方法和数学思想的考察 在选择题，填空题，解答题和三选一问题中，试卷均对高中数学中的重点内容进行了反复考查。包括函数，三角函数，数列、立体几何、概率统计、解析几何、导数等几大版块问题。这些问题都是以知识为载体，立意于能力，让数学思想方法和数学思维方式贯穿于整个试题的解答过程之中。 二、亮点试题分析 1．【试卷原题】11.已知,,A B C 是单位圆上互不相同的三点，且满足AB AC → → =，则A BA C →→ ?的最小值为（ ） A ．1 4- B ．12- C ．34- D ．1-
基础篇 1、《全国青少年信息学奥林匹克分区联赛初赛培训教材》 （推荐指数：4颗星） 曹文，吴涛编著，知识点大杂烩，部分内容由学生撰写，但是对初赛知识点的覆盖还是做得相当不错的。 语言是pascal的。 2、谭浩强老先生写的《C语言程序设计（第三版）》 （推荐指数：5颗星） 针对零基础学C语言的筒子，这本书是必推的。 3、《骗分导论》（推荐指数：5颗星） 参加NOIP必看之经典 4、《全国信息学奥林匹克联赛培训教程（一）》 （推荐指数：5颗星） 传说中的黄书。吴文虎，王建德著， 系统地介绍了计算机的基础知识和利用 Pascal语言进行程序设计的方法 5、《全国青少年信息学奥林匹克联赛模拟训练试卷精选》 王建德著，传说中的红书。 6、《算法竞赛入门经典》（推荐指数：5颗星） 刘汝佳著，算法必看经典。 7、《算法竞赛入门经典：训练指南》（推荐指数：5颗星） 刘汝佳著，《算法竞赛入门经典》的重要补充 提高篇 1、《算法导论》（推荐指数：5颗星） 这是OI学习的必备教材。 2、《算法艺术与信息学竞赛》（推荐指数：5颗星） 刘汝佳著，传说中的黑书。 3、《学习指导》（推荐指数：5颗星） 刘汝佳著，《算法艺术与信息学竞赛》的辅导书。
（PS：仅可在网上搜到，格式为PDF）。 4、《奥赛经典》（推荐指数：5颗星） 有难度，但是很厚重。 5、《2016版高中信息学竞赛历年真题解析红宝书》（推荐指数：5颗星） 历年真题，这是绝对不能遗失的存在。必须要做！ 三、各种在线题库 1、题库方面首推USACO（美国的赛题），usaco写完了一等基本上就没有问题，如果悟性好的话甚至能在NOI取得不错的成绩． 2、除此之外Vijos也是一个不错的题库，有很多中文题． 3、国内广受NOIP级别选手喜欢的国内OJ（Tyvj、CodeVs、洛谷、RQNOJ） 4、BJOZ拥有上千道省选级别及以上的题目资源，但有一部分题目需要购买权限才能访问。 5、UOZ 举办NOIP难度的UER和省选难度的UR。赛题质量极高，命题人大多为现役集训队选手。