noip复习资料

关于联赛及初赛的有关知识内容：联赛分两个年龄组：初中组和高中组。每组竞赛分两轮：初试和复试。．初试形式为笔试，侧重考察学生的计算机基础知识和编程的基本能力，并对知识面的广度进行测试。程序设计的描述语言采用Pascal。各省市初试成绩在本赛区前百分之十五的学生进入复赛，其分数不计入复赛的成绩。初赛时间为10月的的第3个星期六举行。（具体日期可到查阅）．复试形式为上机，侧重考察学生对问题的分析理解能力，数学抽象能力，驾驭编程语言的能力和编程技巧、想象力和创造性等。程序设计语言可采用Pascal、C/C++或Java。各省市竞赛的等第奖在复试的优胜者中产生。时间为3小时。只进行一试，在11月的第3个星期六进行。试题形式每次联赛的试题分四组：初中组初试赛题；初中组复试赛题；高中组初试赛题；高中组复试赛题。其中，初中组初试赛题和高中组初试赛题类型相同，初中组复试赛题和高中组复试赛题类型相同，但初中组和高中组的题目不完全相同，高中组难度略高；以体现年龄特点和层次要求。．初试：初试全部为笔试，满分100分。试题由四部分组成：1、选择题：共20题，每题1．5分，共30分。每题有5个备选方案；前10个题为单选题，每题有且只有一个正确答案），后10题为复选题（即每题有1至5个正确答案，只有全部选对才得分）。试题内容包括计算机基本组成与原理、计算机基本操作、信息科技与人类社会发展的关系等等。2、问题求解题：共2题，每题5分，共10分。试题给出一个叙述较为简单的问题，要求学生对问题进行分析，找到一个合适的算法，并推算出问题的解。答案以字符串方式给出，考生给出的答案与标准答案的字符串相同，则得分；否则不得分。3、程序阅读理解题：共4题，每题8分，共32分。题目给出一段程序（没有关于程序功能的说明），有时也会给出程序的输入，要求考生通过阅读理解该段程序给出程序的输出。输出以字符串的形式给出，如果与标准答案一致，则得分；否则不得分。4、程序完善题：共2题，每题14分，共28分。题目给出一段关于程序功能的文字说明，然后给出一段程序代码，在代码中略去了若干个语句并在这些位置给出空格，要求考生根据程序的功能说明和代码的上下文，填出被略去的语句。填对的，则得分；否则不得分。．复试：复试的题型和形式向全国信息学奥赛（NOI）靠拢，全部为上机编程题，但难度略低。复试为决出竞赛成绩的最后一个环节。题目包括4道题，每题100分，共计400分。难度有易有难，既考虑普及面，又考虑选拔的梯度要求。每一道试题包括：题目、问题描述、样例说明（输入、输出及必要的说明）。测试时，测试程序为每道题提供了十组测试数据，考生程序每答对一组得10分；累计分即为该道题的得分。1988年4月《科学美国人》刊登了一篇文章，声称：考古学家发现了使用绳索和滑轮构造的第一代数字计算机。这篇文章详细介绍了Aprahulians的古人如何使用滑轮和绳索来建造复杂的设备。这些设备装在一个巨大的黑色的木箱中，它们可以用来处理复杂的计算。有一些设备非常巨大，以至于要使用大象来牵引以获得必须的动力。使用绳索和滑轮能够构造计算机吗？或许你已经猜到了，这只不过是愚人节的笑话。^-^如果一台这样的设备，可以称为数字计算机的话，你也可以使用其他的方法来构造计算机了。现在将向你介绍现代计算机系统的概貌，你将会认识计算机的基本概念。计算机基础包括：•电子计算机硬件与软件。•网络基础。•数据结构基础。第一部分一、计算机硬件与软件•电子计算机是一种数字化的信息处理设备。•世界上第一台电子计算机（ENIAC）于1946年诞生于美国。•电子计算机从诞生至今发展经历的四代：电子管、晶体管（20世纪50年代）、集成电路（20世纪60年代）、大规模和超大规模集成电路（20世纪70年代至今）。其发展遵循“摩尔定律”。(操作系统和微型计算机均于第三代问世)•集成电路是一个充满了微小的电路器件如电线、晶体管、电容和电阻的晶片。•电子计算机从原来的数值计算发展到对多种媒体（文字、声音、图形图像等）的处理。•电子计算机包括：巨型机、大型机、中型机、小型机和微型机等。•目前电子计算机的发展趋势：巨型化、微型化和网络化。1、电子计算机的构成：•完整的电子计算机系统由硬件和软件两大部分构成。•计算机硬件包括：输入设备、输出设备、存储器、运算器、控制器五大部分。运算器内存储器控制器输入设备输出设备数据指令辅助存储器输入输出数据输入信息输出信息数据与指令流向控制信息流向计算机的基本结构计算机的功能如此强大，似乎无所不能，是因为计算机是人发明的，到目前为止它还只能听从设计者的指挥，按照设计者事先安排好的程序进行工作。•计算机的软件就是使计算机运行的各种程序及其文档资料，包括系统软件和应用软件两大类。2、计算机硬件1）输入设备：从外部获取信息的计算机设备。（如扫描仪）2）输出设备：把计算机对信息的处理结果以人们能够识别的形式表现出来的设备。（如打印机、触摸屏、绘图仪）输入设备、输出设备和外存储器统称为外部设备。3）存储器：保存数据和程序指令的电子器件。存储器可分为内存储器和外存储器。把与处理器直接相连的存放数据的器件称为内存，不直接与处理器相连的介质如磁盘称为外存储器。•内存储器又包括：随机存储器和只读存储器。•常见的外存储器包括：软盘、硬盘（固定与移动）、光盘和U盘等。•存储器存储容量的基本单位是：字节。（B）最小单位是一个二进制位。（bit）（1B=8bit）•存储器的主要技术指标：容量、速度和价格。分辨率是一个表示平面图像精细程度的概念，通常它是以横向和纵向点的数量来衡量的，表示成水平点数×垂直点数的形式。在一个固定的平面内，分辨率越高，意味着可使用的点数越多，图像越细致。分辨率有多种，在显示器上有表示显示精度的显示分辨率，在打印机上有表示打印精度的打印分辨率，在扫描仪上有表示扫描精度的扫描分辨率。下面分述如下：显示分辨率显示分辨率是显示器在显示图像时的分辨率，分辨率是用点来衡量的，显示器上这个“点”就是指像素(pixel)。显示分辨率的数值是指整个显示器所有可视面积上水平像素和垂直像素的数量。例如800×600的分辨率，是指在整个屏幕上水平显示800个像素，垂直显示600个像素。显示分辨率的水平像素和垂直像素的总数总是成一定比例的，一般为4:3、5:4或8:5。每个显示器都有自己的最高分辨率，并且可以兼容其它较低的显示分辨率，所以一个显示器可以用多种不同的分辨率显示。显示分辨率虽然是越高越好，但是还要考虑一个因素，就是人眼能否识别。例如，在14英寸最高分辨率为1024×768的显示器上800×600是人眼能识别的最高分辨率(我们暂时称为最佳分辨率)，在1024×768这个分辨率下显示器虽然可以精确的显示图像，但人眼已不能准确的识别屏幕信息了。在相同大小的屏幕上，分辨率越高，显示就越小。由于显示器的尺寸有大有小，而显示分辨率又表示所有可视范围内像素的数量，所以相同的分辨率对不同的显示器显示的效果也是不同的，例如：800×600的分辨率，14英寸的显示器比以相同分辨率显示的17英寸显示器的显示精度要高一大截。有些质量较好的显示器(如：Philips15A、14A)，14英寸显示器可达1280×1024，15英寸显示器可达1600×1200。打印分辨率打印分辨率直接关系到打印机输出图像或文字的质量好坏。在这里我们只考虑喷墨打印机和激光打印机的打印分辨率。打印分辨率用dpi(dotperinch)来表示，即指每英寸打印多少个点。喷墨和激光打印的水平分辨率和垂直分辨率通常是相同的。例如：在打印分辨率为600dpi是指打印机在一平方英寸的区域内垂直打印600个点，水平打印600个点，总共可打360000个点。但是，720dpi的喷墨打印机不一定比600dpi的激光打印机产生更好的打印质量。这是因为喷墨打印机打印的每一个墨点只是近似相等，每个墨点在干燥之前还会向四周扩散，没有激光打印机产生的点那样均匀。扫描分辨率决定扫描仪性能的主要因素有三个：扫描分辨率、最大扫描页面、颜色位数。扫描分辨率是一种输入分辨率，而显示分辨率和打印分辨率都是输出分辨率。我们在使用扫描仪扫描图形时可以根据需要调节扫描的精度，不像显示分辨率和打印分辨率是固定的或只有几种可选。扫描分辨率也用dpi来表示，但它不像打印机那样垂直分辨率和水平分辨率是一致的，扫描仪的水平分辨率是垂直分辨率的一半。扫描分辨率分为两种：光学分辨率和插值分辨率。光学分辨率是扫描仪在扫描时读取源图形的真实点数。通常扫描仪的光学分辨率从300×600dpi到1000×2000dpi。另外有些扫描仪的分辨率为1200×1200dpi，这类扫描仪是利用硬件功能提升水平分辨率的精度。插值分辨率是指在真实的扫描点基础上插入有些点后形成的分辨率。它是扫描图像时可以调节的分辨率的最大值，通常是光学分辨率的4－16倍，以4倍、8倍、16倍最常见。例如光学分辨率为300×600dpi的扫描仪插值分辨率可达4800×9600dpi。选购扫描仪时应考虑光学分辨率，而不是插值分辨率。插值分辨率毕竟是生成的点而不是真实的扫描点数，虽然提高分辨率使图像更细致，但细节上跟原来的图形会有一定程度的差异，它并不代表扫描的真实度。而光学分辨率虽然数值较小，但它代表扫描的真实精度。插值分辨率为4800dpi的扫描仪，其光学分辨率可能为300×600dpi，也可能为600×1200dpi，所以选购四一定要弄清光学分辨率的大小，对于扫描要求不高的图形，使用300dpi的精度即可。对于精度要求较高的图形，用使用600dpi以上的精度。分辨率概念释疑•存储器的读写速度比CPU的速度慢。•在存储器中，每一个存放数据的基本单位称为一个存储单元，一个存储器是许许多多存储单元的集合。为了能准确高效地存取数据，每个存储单元都有一个唯一的编号——存储单元的地址。•除此而外，还有虚拟内存、CMOS存储器和高速缓存。如果随机存储器不够用怎么办？操作系统会使用硬盘来扩充内存，即将最近最少使用的程序从内存移动到磁盘上。计算机使用磁盘模拟的内存被称为虚拟内存。CMOS存储器中保存了计算机的配置信息，例如日期和时间、硬盘的容量和内存容量等。4）运算器：进行算术运算和逻辑运算的部件。包括ALU（算术逻辑单元）和寄存器。5）控制器：从存储器中取出操作指令并进行分析，向计算机个各个部件发出控制信息，使计算机按照人们的指令完成任务。（计算机系统的大脑）运算器和控制器合称为中央处理器。（CPU）影响CPU性能的主要技术指标：1）主频，也就是CPU的时钟频率，简单地说也就是CPU的工作频率。CPU的主频表示在CPU内数字脉冲信号震荡的速度。一般说来，一个时钟周期完成的指令数是固定的，所以主频越高，CPU的速度也就越快了。不过由于各种CPU的内部结构也不尽相同，所以并不能完全用主频来概括CPU的性能。关于高速缓存（CACHE）由于CPU的速度比内存和硬盘的速度要快得多，所以在存取数据时会使CPU等待，影响计算机的速度。SRAM的存取速度比其它内存和硬盘都要快，所以它被用作电脑的高速缓存(快存)(Cache)。有了高速缓存，可以先把数据预写到其中，需要时直接从它读出，这就缩短了CPU的等待时间。高速缓存之所以能提高系统的速度是基于一种统计规律，主板上的控制系统会自动统计内存中哪些数据会被频繁的使用，就把这些数据存在高速缓存中，CPU要访问这些数据时，就会先到Cache中去找，从而提高整体的运行速度。一般说来，256K的高速缓存能使整机速度平均提高10%左右。主板上通常都会提供256K到1M的缓存。在CPU内部也有高速缓存，如486CPU有8K的高速缓存，Pentium有16K的高速缓存。PentiumII有32K一级缓存，AMDK6-2中有64K的一级Cache，AMDK6-3中有64K的一级Cache，和256K的二级Cache，CyrixMII中有64K的Cache。为了区分它们，CPU内部的缓存叫内部高速缓存(InternalCache)或一级高速缓存，主板上的缓存叫外部