《信息学奥赛培训教程c++版.doc》由会员分享，可在线阅读，更多相关《信息学奥赛培训教程c++版.doc（229页珍藏版）》请在金锄头文库上搜索。
1、目 录青少年信息学奥林匹克竞赛情况简介5第一章 计算机基础知识71.1 计算机的基本常识71.1.1 计算机的产生与发展71.1.2 计算机系统及工作原理71.1.3 计算机中有关数及编码的知识81.1.4 原码、反码与补码101.1.5 逻辑运算101.2 操作系统111.2.1 DOS(Disk Operating System)的组成111.2.2 DOS的文件和目录111.2.3 DOS命令121.2.4 Windows简介121.3 计算机网络常识131.3.1 网络基础知识131.3.2 Internet简介141.4 计算机信息安全基础知识161.4.1 计算机的网络安全161.
2、4.2 计算机病毒171.4.3 病毒的分类17第2章C+编程简介192.1 机器语言、汇编语言和高级语言192.2 C语言与C+的历史202.3 C+标准库202.4 结构化编程212.5 简单程序222.6 简单程序：两个整数相加252.7 算术运算272.8 判断：相等与关系运算符292.9 新型头文件与名字空间31第3章 C+输入/输出流333.1 简介333.2 流333.2.1 iostream类库的头文件343.2.2 输入/输出流类和对象343.3 输出流353.3.1 流插入运算符353.3.2 连续使用流插入/流读取运算符373.3.3 输出char*类型的变量373.3.
3、4 用成员函数put输出字符和put函数的连续调383. 4 输入流393.4.1 流读取运算符393.4.2 成员函数get和getline413.5 成员函数read、gcount和write的无格式输入/输出443.6 流操纵算子453.6.1 整数流的基数：流操纵算子dec、oct、hex和setbase453.6.2 设置浮点数精度(precision、setprecision)463.6.3 设置域宽(setw、width)473.6.4 用户自定义的流操纵算子483.7 流格式状态493.7.1 格式状态标志503.7.2 尾数零和十进制小数点(ios:showpoint)503
4、.7.3 对齐(ios:left、ios:right、ios:internal)513.7.4 设置填充字符(fill、setfill)533.7.5 整数流的基数：(ios:dec、ios:oct、ios:hex、ios:showbase)543.7.6 浮点数和科学记数法(ios:scientific、ios:fixed)553.7.7 大/小写控制(ios:upercase)563.7.8 设置及清除格式标志(flags、setiosflags、resetosflags)573.8 流错误状态58第4章 文件处理614.1 简介614.2 文件和流614.3 建立并写入文件614.4 读
5、取文件中的数据654.5 更新访问文件67第5章 C+的字符串流685.1 流的继承关系685.2 字串流的输入操作685.3 字串流的输出操作695.4 字串流在数据类型转换中的应用705.5 输入/输出的状态标志71第6章 控制结构746.1 简介746.2 算法746.3 控制结构746.4 if选择结构756.5 if/else选择结构766.6 while重复结构786.7 构造算法：实例研究1(计数器控制重复)786.8 构造算法与自上而下逐步完善：实例研究2(标记控制重复)806.9 构造算法与自上而下逐步完善：实例研究3(嵌套控制结构)856.10 赋值运算符886.11 自增
6、和自减运算符886.12 计数器控制循环的要点916.13 for重复结构926.14 for结构使用举例946.15 switch多项选择结构976.16 do/while重复结构1016.17 break和continue语句1026.18 逻辑运算符1046.19 混淆相等(=)与赋值(=)运算符1056.20 结构化编程小结106第7章 函数1087.1 简介1087.2 数学函数库1087.3 函数1097.4 函数定义1097.5 头文件1127.6 作用域规则1137.7 递归1167.8 使用递归举例，Fibonacci数列1187.9 递归与迭代1207.10 带空参数表的函
7、数1217.11 内联函数1227.12 函数重载123第8章 数组1258.1 简介1258.2 数组1258.3 声明数组1268.4 使用数组的举例1268.5 将数组传递给函数1378.6 排序数组1418.7 查找数组：线性查找与折半查找1428.8 多维数组147第9章 指针与字符串1539.1 简介1539.2 指针变量的声明与初始化1539.3 指针运算符1549.4 按引用调用函数1569.5 指针与常量限定符1589.6 按引用调用的冒泡排序1639.7 指针表达式与指针算法1679.8 指针与数组的关系1699.9 指针数组1729.10 函数指针1739.11 字符与字
8、符串处理简介1779.11.1 字符与字符串基础1779.11.2 字符串处理库的字符串操作函数179第10章 信息学奥赛中的常用算法18510.1 算法简介18510.2 枚举算法18710.3 回溯算法19110.4 递归算法19310.5 递推算法19610.6 分治算法20010.7 贪心算法20210.8 搜索算法一（深度优先）20510.9 搜索算法二（广度优先）20910.10 动态规划法21210.11 高精度计算215附 录228ASCII表228青少年信息学奥林匹克竞赛情况简介 信息学奥林匹克竞赛是一项旨在推动计算机普及的学科竞赛活动，重在培养学生能力，使得有潜质有才华的学
9、生在竞赛活动中锻炼和发展。近年来，信息学竞赛活动组织逐步趋于规范和完善，基本上形成了“地级市省(直辖市)全国国际”四级相互接轨的竞赛网络。现把有关赛事情况简介如下：全国青少年信息学（计算机）奥林匹克分区联赛： 在举办1995年NOI活动之前，为了扩大普及的面，并考虑到多数省、直辖市、自治区已经开展了多年省级竞赛，举办了首届全国青少年信息学（计算机）奥林匹克分区联赛。考虑到不同年级学生的知识层次，也为了鼓励更多的学生积极参与，竞赛设提高组、普及组，并分初、复赛进行，这样可以形成一个梯队，确保每年的竞赛活动有比较广泛扎实的基础。从1995年起，至2001年共举办了七届全国青少年信息学奥林匹克分区联
10、赛，每年举办一次（下半年十月左右），有选手个人奖项（省、国家级）、选手等级证书、优秀参赛学校奖项。安徽省青少年信息学（计算机）奥林匹克复决赛（简称AHOI）： 省级信息学奥赛是一个水平较高的、有较大影响力的学科竞赛。由各市组织代表队参赛，参赛名额实行动态分配制度，每年举办一次（上半年五月左右）。从1984年起安徽省奥林匹克竞赛活动得到了蓬勃发展。奖项有个人一、二、三等奖，女选手第一、二、三名，奖励学校团体总分1-8名、市团体总分1-8名。全国青少年信息学（计算机）奥林匹克竞赛（简称NOI）： 由中国算机学会主办的、并与国际信息学奥林匹克接轨的一项全国性青少年学科竞赛活动。1984年举办首届全国
11、计算机竞赛。由各省市组织参赛，每年举办一次。奖项有个人一、二、三等奖，女选手第一、二、三名，各省队团体总分名次排队。国际青少年信息学（计算机）奥林匹克竞赛（简称IOI）： 每年举办一次，由各参赛国家组队参赛。 全国青少年信息学（计算机）奥林匹克分区联赛竞赛大纲一、初赛内容与要求：（#表示普及组不涉及，以下同）计 基算 本机 常的 识* 诞生与发展 *特点*在现代社会中的应用* 计算机系统的基本组成* 计算机的工作原理#*计算机中的数的表示* 计算机信息安全基础知识 *计算机网络计 基算 本机 操的 作* MS DOS与Windows的使用基础* 常用输入/输出设备的种类、功能、使用* 汉字输入
12、/输出方法* 常用计算机屏示信息程序设计基本知识程序的表示* 自然语言的描述* PASCAL或BASIC语言数据结构的类型* 简单数据的类型* 构造类型：数组、字符串* 了解基本数据结构（线性表、队列与栈）程序设计* 结构化程序的基本概念* 阅读理解程序的基本能力* 具有完成下列过程的能力：现实世界（指知识范畴的问题）信息世界（表达解法）计算机世界（将解法用计算机能实现的数据结构和算法描述出来）基本算法处理* 简单搜索 * 字串处理* 排序 * 查找* 统计 * 分类 * 合并* 简单的回溯算法* 简单的递归算法二、复赛内容与要求：在初赛的内容上增加以下内容(2008年修改稿)：计算机软 件*
13、操作系统的使用知识*编程语言的使用数据结构*结构类型中的记录类型*指针类型*文件（提高组必须会使用文本文件输入）*链表*树*图#程序设计*程序设计能力*设计测试数据的能力*运行时间和占用空间的估算能力#算法处理*排列组合的应用*进一步加深回溯算法、递归算法*分治法*搜索算法：宽度、深度优先算法*表达式处理：计算、展开、化简等#*动态规划#三、初赛试题类型：注：试题语言两者选一（程序设计语言： FREE PASCAL、C、C+）*判断 *填空 *完善程序 *读程序写运行结果 *问答四、推荐读物：*分区联赛辅导丛书 *学生计算机世界报及少年电世界杂志第一章 计算机基础知识1.1 计算机的基本常识1.1.1 计算机的产生与发展计算机的产生是20世纪最重要的科学技术大事件之一。世界上的第一台计算机（ENIAC）于1946年诞生在美国宾夕法尼亚大学，到目前为止，计算机的发展大致经历了四代： 第一代电子管计算机，始于1946年，结构上以CPU为中心，使用计算机语言，速度慢，存储量小，主要用于数值计算； 第二代晶体管计算机，始于1958年，结构上以存储器为中心，使用高级语言，应用范围扩大到数据处理和工业控制； 第
