《noip初赛辅导教材》由会员分享，可在线阅读，更多相关《noip初赛辅导教材（14页珍藏版）》请在金锄头文库上搜索。
1、一、全国青少年信息学奥林匹克联赛考试知识大纲1、初赛内容与要求：计算机基本常识1计算机和信息社会（信息社会的主要特征、计算机的主要特征、数字通信网络的主要特征、数字化）2信息输入输出基本原理（信息交换环境、文字图形多媒体信息的输入输出方式）3信息的表示与处理（信息编码、微处理部件MPU、内存储结构、指令，程序，和存储程序原理、程序的三种基本控制结构）4信息的存储、组织与管理（存储介质、存储器结构、文件管理、数据库管理）5信息系统组成及互连网的基本知识（计算机构成原理、槽和端口的部件间可扩展互连方式、层次式的互连结构、互联网络、TCP/IP协议、HTTP协议、WEB应用的主要方式和特点）6人机交
2、互界面的基本概念（窗口系统、人和计算机交流信息的途径（文本及交互操作）7信息技术的新发展、新特点、新应用等。基本操作1. Windows和LINUX的基本操作知识2. 互联网的基本使用常识 （网上浏览、搜索和查询等）3. 常用的工具软件使用（文字编辑、电子邮件收发等）程序 设计 的基 本知 识数据结构1程序语言中基本数据类型(字符、整数、长整、浮点) 2. 浮点运算中的精度和数值比较3一维数组（串）与线性表 4记录类型（PASCAL）/ 结构类型（C）程序设计1结构化程序设计的基本概念 2阅读理解程序的基本能力3具有将简单问题抽象成适合计算机解决的模型的基本能力4具有针对模型设计简单算法的基本
3、能力5程序流程描述（自然语言/伪码/NS图/其他） 6程序设计语言（PASCAL/C/C+）基本算法处理1初等算法（计数、统计、数学运算等）2排序算法（冒泡法、插入排序、合并排序、快速排序）3查找（顺序查找、二分法）4回溯算法2、复赛内容与要求：在初赛内容的基础上增加以下内容：数据结构1指针类型 2多维数组 3单链表及循环链表4二叉树 5文件操作（从文本文件中读入数据，并输出到文本文件中）程序设计1算法的实现能力 2程序调试基本能力3设计测试数据的基本能力 4程序的时间复杂度和空间复杂度的估计算法处理1离散数学知识的应用（如排列组合、简单图论、数理逻辑）2分治思想 3模拟法 4贪心法5简单搜索
4、算法（深度优先 广度优先）搜索中的剪枝 6动态规划的思想及基本算法二、计算机基本常识1、计算机的产生与发展计算机的产生是20世纪最重要的科学技术大事件之一。世界上的第一台计算机（ENIAC）于1946年诞生在美国宾夕法尼亚大学，到目前为止，计算机的发展大致经历了四代： 第一代电子管计算机，始于1946年，结构上以CPU为中心，使用计算机语言，速度慢，存储量小，主要用于数值计算； 第二代晶体管计算机，始于1958年，结构上以存储器为中心，使用高级语言，应用范围扩大到数据处理和工业控制； 第三代中小规模集成电路计算机，始于1964年，结构上仍以存储器为中心，增加了多种外部设备，软件得到了一定的发展
5、，文字图象处理功能加强； 第四代大规模和超大规模集成电路计算机，始于1971年，应用更广泛，很多核心部件可集成在一个或多个芯片上，从而出现了微型计算机。 我国从1956年开始电子计算机的科研和教学工作，1983年研制成功1亿/秒运算速度的“银河”巨型计算机，1992年11月研制成功10亿/秒运算速度的“银河II”巨型计算机，1997年研制了每秒130亿运算速度的“银河III”巨型计算机。 目前计算机的发展向微型化和巨型化、多媒体化和网络化方向发展。计算机的通信产业已经成为新型的高科技产业。计算机网络的出现，改变了人们的工作方式、学习方式、思维方式和生活方式。 计算机应用：科学计算（最早）、数据
6、处理（最广泛，也称信息处理）、过程控制（实时控制）、计算机辅助系统（CAD，CAM，CAI，CAT，CAE，CIMS）、智能模拟、自动控制、事物处理、信息检索、出版印刷、网络通信、多媒体技术。微机（微型计算机，个人电脑PC）性能指标：字长（内部数据总线的宽度，一次能够处理的二进制的位数）、速度（主频：CPU时钟频率，单位为Hz；存取速度：用存取周期和存取时间描述；运算速度MIPS即每秒百万条指令）、内存容量、可靠性（平均无故障时间MTBF）、可维护性（平均故障修复时间MTTR）。计算机启动：加电自检自举引导运行操作系统，自检自举程序在ROM-BIOS。2、计算机系统及工作原理2.1、计算机的系
7、统组成 计算机系统由软件和硬件两部分组成。硬件即构成计算机的电子元器件；软件即程序和有关文档资料。 (1）计算机的主要硬件 输入设备：键盘、鼠标、扫描仪等。 输出设备：显示器、打印机、绘图仪等。 中央处理器（CPU）：包括控制器和运算器运算器，可以进行算术运算和逻辑运算；控制器是计算机的指挥系统，它的操作过程是取指令分析指令执行指令。 中央处理器也称CPU,主要有控制器和运算器组成。若从功能上看，CPU包含控制器、运算器和寄存器三部分。控制器是计算机指令的执行部件，主要包括：指令指针寄存器（也称程序计数器PC，存待取指令地址，有自动加1功能）、指令寄存器（存正在执行指令）、指令译码器（分析解释
8、操作码并产生控制信号）、时序控制信号形成部件（接受译码产生控制信号并按一定时间顺序发出）。运算器是计算机中负责算术运算（加、减、乘、除）和逻辑运算（与、或、非、异或和比较）的部件，主要包括：算术逻辑单元ALU（算术、逻辑、移位、求补）、累加器（暂存操作数和运算结果的寄存器，无累加功能）、状态寄存器（又称标志寄存器，存放状态信息如进位等，每一位均可单独使用）。寄存器分成：数据寄存器、地址寄存器、控制寄存器、状态寄存器和其他寄存器。指令：计算机能够识别和执行的操作命令，由操作码和地址码组成。指令的执行分为取指阶段和执行阶段，取指过程包括取指令、分析指令及产生控制信号，指令执行过程是指令经译码器分析
9、译码后，产生相应控制信号并由时序控制信号形成部件发出，在该信号控制下完成相应操作。时序：计算机的时间控制。时序的产生：同步（统一的时钟信号）和异步（应答）。时钟周期：主频的倒数，最基本的时间周期。机器周期：完成一个基本操作所需时间，也称总线周期或CPU周期。指令周期：CPU执行一条指令所需时间。一个指令周期由若干机器周期组成，一个机器周期由若干时钟周期组成。指令从内存取出，经数据总线、数据寄存器、指令寄存器、指令译码器，发出控制信号。产生控制信号的方法：组合逻辑电路实现法、微程序控制法。一条指令的执行分成若干机器周期，一个机器周期定义为一条微指令，微指令由控制部分和下址组成，微指令的有序集合称
10、为微程序，一段微程序对应一条指令，微程序存于ROM流水线技术：将执行指令的若干子操作并行处理，首次在486使用，实现一个时钟周期完成一条指令。超流水线：流水线周期短，时钟频率高，时间换空间。超标量：重点设置大量的处理单元，一条以上流水线，每个时钟周期完成一条以上指令，空间换时间复杂指令系统CISC(兼容，指令只加不减，如Petium系列)，精简指令系统RISC的特点有：指令数目少，指令长度固定、种类少、寻址方式少，大多在一个机器周期完成，通用寄存器数量多其他CPU技术：分支预测技术，MMX,3DNOW,SSE,多CPU技术等指令格式：零地址、一地址、二地址、三地址指令寻址方式：顺序执行（PC+
11、1）、改变执行顺序（直接寻址，间接寻址，相对寻址，中断寻址）；操作数寻址方式：立即寻址，直接寻址，寄存器寻址，间接寻址，寄存器间接寻址，变址寻址，页面寻址，基址寻址，其他寻址（位寻址、块寻址、堆栈寻址）指令操作码的编码格式：固定式（操作码长度不变，用于大、中型机）和可变式（根据使用频率变化，适于微型机）指令按功能分为四类：数据传送指令（传送MOV、堆栈PUSH和POP、输入输出I/O），数据处理指令（算术、逻辑、移位），程序控制指令（转移、子程序调用和返回），处理器控制指令（空操作、停机）。其中停机是转入下一任务而非关机，特权指令用于系统资源的分配和管理，应用于多任务、多用户计算机，单任务不必
12、要。存储器：具有记忆功能的物理器件，用于存储信息。存储器分为内存和外存内存是半导体存储器(主存）：它分为只读存储器(ROM)和随机存储器(RAM)和高速缓冲存储器（Cache)；ROM:只能读，不能用普通方法写入，通常由厂家生产时写入，写入后数据不容易丢失，也可以用特殊方法（如紫外线擦除（EPROM)或电擦除(EEPROM_)存储器)；RAM:可读可写，断电后内容全部丢失；Cache:因为CPU读写RAM的时间需要等待，为了减少等待时间，在RAM和CPU间需要设置高速缓存Cache,断电后其内容丢失。 外存：磁性存储器软盘和硬盘；光电存储器光盘，它们可以作为永久存器； 存储器的两个重要技术指标
13、：存取速度和存储容量。内存的存取速度最快(与CPU速 度相匹配)，软盘存取速度最慢。存储容量是指存储的信息量，它用字节(Byte)作为基本单位，1字节用8位二进制数表示，1KB=1024B，1MB=1024KB，lGB=1024MB 按存储介质，存储器可分为半导体、磁表面、光盘。按存取方式可分为RAM(随机存取、易失)和ROM(只读、非易失)主存的指标：存储容量、存取速度（存取周期、存取时间），容量末地址-起始地址+1RAM所用元件有双极型（速度快、集成度低、价格高，用于CACHE）和MOS。MOS型有静态SRAM和动态DRAM，SRAM由双稳态触发器组成，不断电信息不丢失，DRAM根据电容的
14、电荷量存储信息，需动态刷新（集中刷新、分散刷新、异步刷新）ROM的基本存储单元是一个固定的开关电路，分为掩膜ROM、PROM、EPROM、EEPROMCACHE采取双极型存储器组成，实现CPU与主存速度上的匹配，基本操作有读、写（直写或回写），特点是：容量小、速度快，其内容是主存的副本，地址映像和替换算法由硬件实现ROM-BIOS采用EEPROM，存放CMOS参数的芯片属于RAMCACHE-主存层次结构解决速度与成本的矛盾。主存辅存层次结构解决大容量与低成本矛盾，扩大了编程空间，称为虚拟存储器。半导体存储芯片容量计算：地址线n决定了字数，数据线决定了字长，容量2n*数据线/8(字节)。存储容量
15、的扩展有位扩展（加大字长）、字扩展（增加芯片数量）、字位扩展总线是一种在多于二个模块间传送信息的公共通路，能被各模块分时共享按连接部件总线分为内部总线（同一部件内）、系统总线（部件之间）、外部总线（通信总线，与外设之间）。按信息传送格式分为并行、串行（成本低、速度慢）。按信息传送方式分为单向总线、双向总线常见总线结构有单总线（系统总线）、双总线（+存储总线）、多总线（+I/O总线）系统总线由数据总线、地址总线、控制总线组成。数据总线用于传送数据（含指令），双向，并行，同步，其位数为计算机字长。地址总线用于存储器操作和I/O操作，单向，并行，其位数决定可直接寻址的内存容量，地址线N与可直接寻址地址单元数M的关系：M2N 。控制总线用于传送各类控制/状态信号常见的微机总线标准有ISA、VESA
