信息学奥赛培训教程C版.doc

目 录青少年信息学奥林匹克竞赛情况简介 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.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.4 用成员函数put输出字符和put函数的连续调 383. 4 输入流 393.4.1 流读取运算符 393.4.2 成员函数get和getline 413.5 成员函数read、gcount和write的无格式输入/输出 443.6 流操纵算子 453.6.1 整数流的基数：流操纵算子dec、oct、hex和setbase 453.6.2 设置浮点数精度(precision、setprecision) 463.6.3 设置域宽(setw、width) 473.6.4 用户自定义的流操纵算子 483.7 流格式状态 493.7.1 格式状态标志 503.7.2 尾数零和十进制小数点(ios::showpoint) 503.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 读取文件中的数据 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 自增和自减运算符 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 带空参数表的函数 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 字符与字符串处理简介 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青少年信息学奥林匹克竞赛情况简介　   信息学奥林匹克竞赛是一项旨在推动计算机普及的学科竞赛活动，重在培养学生能力，使得有潜质有才华的学生在竞赛活动中锻炼和发展。

近年来，信息学竞赛活动组织逐步趋于规范和完善，基本上形成了“地级市——省(直辖市)——全国——国际”四级相互接轨的竞赛网络现把有关赛事情况简介如下：全国青少年信息学（计算机）奥林匹克分区联赛：   在举办1995年NOI活动之前，为了扩大普及的面，并考虑到多数省、直辖市、自治区已经开展了多年省级竞赛，举办了首届全国青少年信息学（计算机）奥林匹克分区联赛考虑到不同年级学生的知识层次，也为了鼓励更多的学生积极参与，竞赛设提高组、普及组，并分初、复赛进行，这样可以形成一个梯队，确保每年的竞赛活动有比较广泛扎实的基础　　从1995年起，至2001年共举办了七届全国青少年信息学奥林匹克分区联赛，每年举办一次（下半年十月左右），有选手个人奖项（省、国家级）、选手等级证书、优秀参赛学校奖项安徽省青少年信息学（计算机）奥林匹克复决赛（简称AHOI）：   省级信息学奥赛是一个水平较高的、有较大影响力的学科竞赛由各市组织代表队参赛，参赛名额实行动态分配制度，每年举办一次（上半年五月左右）从1984年起安徽省奥林匹克竞赛活动得到了蓬勃发展奖项有个人一、二、三等奖，女选手第一、二、三名，奖励学校团体总分1-8名、市团体总分1-8名。

全国青少年信息学（计算机）奥林匹克竞赛（简称NOI）：   由中国算机学会主办的、并与国际信息学奥林匹克接轨的一项全国性青少年学科竞赛活动1984年举办首届全国计算机竞赛由各省市组织参赛，每年举办一次奖项有个人一、二、三等奖，女选手第一、二、三名，各省队团体总分名次排队国际青少年信息学（计算机）奥林匹克竞赛（简称IOI）：   每年举办一次，由各参赛国家组队参赛 全国青少年信息学（计算机）奥林匹克分区联赛竞赛大纲一、初赛内容与要求：（#表示普及组不涉及，以下同）计 基算 本机 常的 识* 诞生与发展　　　 　 *特点　　　　*在现代社会中的应用* 计算机系统的基本组成* 计算机的工作原理#　　　　　　　*计算机中的数的表示* 计算机信息安全基础知识　　　　 *计算机网络计 基算 本机 操的 作* MS DOS与Windows的使用基础* 常用输入/输出设备的种类、功能、使用* 汉字输入/输出方法* 常用计算机屏示信息程序设计基本知识程序的表示* 自然语言的描述* PASCAL或BASIC语言数据结构的类型* 简单数据的类型* 构造类型：数组、字符串* 了解基本数据结构（线性表、队列与栈）程序设计* 结构化程序的基本概念* 阅读理解程序的基本能力* 具有完成下列过程的能力：现实世界（指知识范畴的问题）—>信息世界（表达解法）—>计算机世界（将解法用计算机能实现的数据结构和算法描述出来）基本算法处理* 简单搜索   * 字串处理* 排序       * 查找* 统计       * 分类     * 合并* 简单的回溯算法* 简单的递归算法二、复赛内容与要求：在初赛的内容上增加以下内容(2008年修改稿)：计算机软 件*操作系统的使用知识*编程语言的使用数据结构*结构类型中的记录类型*指针类型*文件（提高组必须会使用文本文件输入）*链表*树*图#程序设计*程序设计能力*设计测试数据的能力*运行时间和占用空间的估算能力#算法处理*排列组合的应用*进一步加深回溯算法、递归算法*分治法*搜索算法：宽度、深度优先算法*表达式处理：计算、展开、化简等#*动态规划#三、初赛试题类型：注：试题语言两者选一　　（程序设计语言： FREE PASCAL、C、C++）　　*判断 *填空 *完善程序 *读程序写运行结果 *问答四、推荐读物：*分区联赛丛书 *学生计算机世界报及少年电世界杂志第一章 计算机基础知识1.1 计算机的基本常识1.1.1 计算机的产生与发展计算机的产生是20世纪最重要的科学技术大事件之一。

世界上的第一台计算机（ENIAC）于1946年诞生在美国宾夕法尼亚大学，到目前为止，计算机的发展大致经历了四代： ①       第一代电子管计算机，始于1946年，结构上以CPU为中心，使用计算机语言，速度慢，存储量小，主要用于数值计算； ②       第二代晶体管计算机，始于1958年，结构上以存储器为中心，使用高级语言，应用范围扩大到数据处理和工业控制； ③       第三代中。