《全国信息学奥赛NOI培训教程(Pascal2016)重点》由会员分享，可在线阅读，更多相关《全国信息学奥赛NOI培训教程(Pascal2016)重点（55页珍藏版）》请在金锄头文库上搜索。
1、全国信息学奥赛NOI培训教程(Pascal 2016)目录计算机基础知识6第1章计算机基础常识第二章操作系统简介第三章计算机网络 第四章计算机信息安全基础知识Pascal语言19Pascal语言概述与预备知识第一章开始编写pascal语言程序第二章Pascal语言基础知识第三章顺序结构程序设计第四章选择结构程序设计第五章循环结构程序设计第六章数组与字符串第七章函数和过程第八章子界与枚举类型第九章集合类型第十章记录与文件类型第十一章指针第十二章程序调试56常用算法与策略第一章算法的概念第二章递归第三章回溯第四章排序第五章查找第六章穷举策略第七章贪心算法第八章分治策略数据结构101第一章什么是数据
2、结构第二章线性表第三章栈第四章队第五章树第六章图动态规戈U 144第一章 什么叫动态规划第二章用动态规划解题第三章典型例题与习题第四章动态规划的递归函数法第五章动态规划分类1数学知识及相关算法第一章有关数论的算法第二章高精度计算 第三章排列与组合第四章计算几何第五章其它数学知识及算法图论算法192第一章最小生成树第二章最短路径第三章拓扑排序（AOV网）第四章关键路径（AOE网）第五章网络流第六章图匹配搜索算法与优化218第一章双向广度优先搜索第二章分支定界法第三章A*算法青少年信息学奥林匹克竞赛情况简介信息学奥林匹克竞赛是一项旨在推动计算机普及的学科竞赛活动，重在培养学生能力，使得有潜质 有才
3、华的学生在竞赛活动中锻炼和发展。近年来，信息学竞赛活动组织逐步趋于规范和完善，基本 上形成了 地级市一一省（直辖市一一全国一一国际”四级相互接轨的竞赛网络。现把有关赛事情况 简介如下： 全国青少年信息学（计算机）奥林匹克分区联赛:在举办1995年NOI活动之前，为了扩大普及的面，并考虑到多数省、直辖市、自治区已经开展了 多年省级竞赛，举办了首届全国青少年信息学（计算机）奥林匹克分区联赛。考虑到不同年级学生 的知识层次，也为了鼓励更多的学生积极参与，竞赛设提高组、普及组，并分初、复赛进行，这样 可以形成一个梯队，确保每年的竞赛活动有比较广泛扎实的基础。从1995年起，至2001年共举办了七届全国
4、青少年信息学奥林匹克分区联赛，每年举办一次, 有选手个人奖项（省、国家级）、选手等级证书、优秀参赛学校奖项。全国青少年信息学（计算机）奥林匹克竞赛（简称NOI）：1984由中国算机学会主办的、并与国际信息学奥林匹克接轨的一项全国性青少年学科竞赛活动。年举办首届全国计算机竞赛。由各省市组织参赛，每年举办一次。奖项有个人一、二、三等奖，女 选手第一、二、三名，各省队团体总分名次排队。国际青少年信息学（计算机）奥林匹克竞赛（简称IOI）：每年举办一次，由各参赛国家组队参赛。全国青少年信息学（计算机）奥林匹克分区联赛竞赛大纲、初赛内容与要求：（#表示普及 组不涉及，以下同）*诞生与发展*特点计基*在现
5、代社会中的应用算本*计算机系统的基本组成*计算机的工作原理#*计算机中的数的表示 *计算机信息安全基础知识*计算机网络计基* MS DOS 与 Windows 的使用 基础算本*常用输入/输岀设备的种类、机操功能、使用的作*汉字输入/输出方法*常用计算机屏示信息程序 设 计 基 本 知 识程序的表示*自然语言的描述* PASCAL 或 BASIC 语数据结构的类型*简单数据的类型*构造类型：数组、字符串* 了解基本数据结构（线性 表、队列与栈）程序设计*结构化程序的基本概念*阅读理解程序的基本能力*具有完成下列过程的能力：现实世界（指知识范畴的问 题） 信息世界（表达解法） 计算机世界（将解法
6、用计算 机能实现的数据结构和算法描 述出来）基本算法处理*简单搜索*字串处理*排序*查找*统计*分类*合并*简单的回溯算法*简单的递归算法二、复赛内容与要求：在初赛的内容上增加以下内容（2002年修改稿：计算机*操作系统的使用知识软*编程语言的使用件*结构类型中的记录类型数*指针类型据*文件（提咼组必须会使用文 本文件输入）结*链表构*树*图#程*程序设计能力序*设计测试数据的能力设*运行时间和占用空间的估算计能力#*排列组合的应用算*进一步加深回溯算法、递归算法*分治法 处*搜索算法：宽度、深度优先 理 算法*表达式处理：计算、展开、化简等#*动态规划#三、初赛试题类型：注：试题语言 两者选
7、一一(程序设计语言：基本 BASIC 或 TURBO PASCAL*判断*填空*完善程序*读程 序写运行结果*问答四、推荐读物：*分区联赛辅导丛书 *学生计算 机世界报及少年电世界杂志计算机基础知识计算机基础知识1.1计算机的产生与发展计算机的产生是20世纪最重要的科学技术大事件之一。世界上的第一台计算机(ENIAC )于1946年诞生在美国宾夕法尼亚大学，到目前为止，计算机的发展大 致经历了四代： 第一代电子管计算机，始于1946年，结构上以CPU为中心，使用计算机语 言，速度慢，存储量小，主要用于数值计算； 第二代晶体管计算机，始于1958年，结构上以存储器为中心，使用高级语言， 应用范围
8、扩大到数据处理和工业控制； 第三代中小规模集成电路计算机，始于1964年，结构上仍以存储器为中心，增加了多种外部设备，软件得到了一定的发展，文字图象处理功能加强； 第四代大规模和超大规模集成电路计算机，始于1971年，应用更广泛，很多核心部件可集成在一个或多个芯片上，从而出现了微型计算机。我国从1956年开始电子计算机的科研和教学工作，1983年研制成功1亿/秒运算速 度的 银河”巨型计算机，1992年11月研制成功10亿/秒运算速度的 银河II 巨型 计算机，1997年研制了每秒130亿运算速度的 银河III ”型计算机。目前计算机的发展向微型化和巨型化、多媒体化和网络化方向发展。计算机的通
9、信 产业已经成为新型的高科技产业。计算机网络的出现，改变了人们的工作方式、学 习方式、思维方式和生活方式。1.2计算机系统及工作原理1. 计算机的系统组成计算机系统由软件和硬件两部分组成。硬件即构成计算机的电子元器件；软件即程 序和有关文档资料。（1）计算机的主要硬件输入设备：键盘、鼠标、扫描仪等。输出设备：显示器、打印机、绘图仪等。中央处理器（CPU）:包括控制器和运算器运算器，可以进行算术运算和逻辑运算；控制器是计算机的指挥系统，它的操作过程是取指令 一一分析指令一一执行指 令。存储器：具有记忆功能的物理器件，用于存储信息。存储器分为内存和外存 内存是半导体存储器（主存）：它分为只读存储器
10、（ROM和随机存储器（RAM和高速缓冲存储器（Cache；ROM:只能读，不能用普通方法写入，通常由厂家生产时写入，写入后数据不容易 丢失，也可以用特殊方法（如紫外线擦除（EPROM或电擦除（EEPROM_存储器；RAM:可读可写，断电后内容全部丢失;Cache因为CPU读写RAM的时间需要等待，为了减少等待时间，在 RAM和CPU 间需要设置高速缓存Cache断电后其内容丢失。 外存：磁性存储器一一软盘和硬盘；光电存储器 一一光盘，它们可以作为永久存 器； 存储器的两个重要技术指标：存取速度和存储容量。内存的存取速度最快（与CPU速度相匹配，软盘存取速度最慢。存储容量是指存储的信息量，它用字
11、节（Byte作为基本单位，1 字节用 8位二进制数表示，1KB=1024B，1MB=1024KB , IGB=1024MB（2计算机的软件计算机的软件主要分为系统软件和应用软件两类： 系统软件：为了使用和管理计算机的软件，主要有操作系统软件如，WINDOWS95/98/ 2000/NT4. 0、DOS 6. 0、UNIX 等；WINDOWS 95 /98/2000/ NT4. 0是多任务可视化图形 界面，而DOS是字符命令形式的单任务的操作系 统。 应用软件：为了某个应用目的而编写的软件，主要有辅助教学软件（CAI、辅助设计软件（CAD、文字处理软件、工具软件以及其他的应用软件。2. 计算机的
12、工作原理到目前为止，电子计算机的工作原理均采用冯若依曼的存储程序方式，即把程序存储 在计算机内，由计算机自动存取指令（计算机可执行的命令 =操作码+操作数）并执 行它。工作原理图如下：1.3计算机中有关数及编码的知识1. 计算机是智能化的电器设备计算机就其本身来说是一个电器设备，为了能够快速存储、处理、传递信息，其内 部采用了大量的电子元件，在这些电子元件中，电路的通和断、电压高低，这两种状态最容 易实现，也最稳定、也最容易实现对电路本身的控制。我们将计算机所能表示这样的状态， 用0，1来表示、即用二进制数表示计算机内部的所有运算和操作。2. 二进制数的运算法则二进制数运算非常简单，计算机很容
13、易实现，其主要法则是：0+0=0 0+1=1 1+0=1 1+1=0 0*0=0 0*1=0 1*0=0 1*1=1由于运算简单，电器元件容易实现，所以计算机内部都用二进制编码进行数据的传 送和计算。3. 十进制与二进制、八进制、十六进制数之间的相互转换(1数的进制与基数计数的进制不同，贝U它们的基数也不相同，如表1-1所示。进制基数特点二进制0,1逢二进一八进制0,1,2,3,4,5,6,7逢八进一十六进制0,1,2，9A,B,C,D,E,F逢十六进一(2) 数的权不同进制的数，基数不同，每位上代表的值的大小(权)也不相同。如:( 21910=2*102+1*101+9*100(110102
14、=1*24+1*23+0*22+1*21+1*20(2738=2*82+7*81+3*80(27AF16=2*163+7*162+10*161+15*160(3十进制数转换任意进制1将十进制整数除以所定的进制数，取余逆序。(3910=(1001112 (24510=(36582将十进制小数的小数部分乘以进制数取整，作为转换后的小数部分，直到为零或精 确到小数点后几位。如：（0.3510=（0.010112 （0.12510=（0.0012（4任意进制的数转换十进制按权值展开：如:（21910=2*102+1*101+9*100（110102=1*24+1*23+0*22+1*21+1*20=26（2738=2*82+7*81+3*80=187（7AF16=7*162+10*161+15*160=18674. 定点数与浮点数定点数是指数据中的小数点位置固定不变。由于它受到字长范围的限制，所能表示 的数的范围有限，计算结果容易溢出。浮点数的形式可写成：N=M*2E（其中M代表尾数,E代表阶码）其形
