信息学奥赛基础知识提纲

-/-/信息学奥赛根底学问提纲〔20149月〕1计算机系统1－1概述一个完整的计算机系统包括硬件系统和软件系统数据传送功能、数据存储功能、数据处理功能、操作掌握功能、操作推断功能。它的工作特点是：运算速度快、运算精度高、记忆力量强、通用性广、自动运算。巨型机、大型机、中型机、小型机、微型机、单片机等几种类型。依据用途不同分为通用机和专用机。软件的根底。软件是硬件的扩大与完善。硬件与软件在规律上是等价的。1946年，世界上第一台计算机诞生于宾夕法尼亚大学，称为ENIAC。1949年,EDSAC,英国剑桥大学威尔克斯〔Wilkes〕设计和制造的。1951UNIVAC。第四代1975—第四代1975—至今大规模及超大规模集成电路半导体存储器磁盘、光盘等大容量存储器处理速度〔指令数/秒〕几千条几百万条几千万条数亿条以上第一代其次代第三代主要电子器件1946—1958电子管1958—1964晶体管1964---1975集成电路内存汞延迟线磁芯存储器半导体存储器外存储器穿孔卡片、纸带磁带磁带、磁盘1－2硬件系统1－2－1冯·诺伊曼〔J.vonNeumann〕机：美籍匈牙利数学家现代计算机的根本构造被称为冯·诺伊曼构造。它的主要特点是储存程序的概念：承受二进制形式表示数据和指令。将程序〔包括操作指令和操作数〕事先存入主存储器中，使计算机在工作时能够自动高速地从存储器中取出指令加以执行。由运算器、存储器、掌握器、输入设备、输出设备五大根底部件组成计算机系统。冯·诺伊曼机反响信程 输入设备序控制信号

操作指存储器地存储器地指址控制令器控制台输出设备果控制信号1－2－2计算机的总线构造典型的计算机总线构造由内部总线和系统总线组成。CPU内部的各个模块。系统总线：又称外部总线CPU号线分为三类：数据线、地址线和掌握线。数据线〔a：了在该总线上一次可以传送的二进制位数。地址线s：用以传递地址信息，来指示数据总线上的数据来源和去向。地址线的数目打算了能够访问空间的大小。掌握线〔l：用来掌握数据总线和地址总线。SRAM64K*16位，则该芯片的地址线数目和数据线的数目？1－2－3中心处理器〔CentralProcessorUnit〕1、CPU包含了冯机五大部件中的运算器〔即加法器〕和掌握器。运算器：对信息加工和处理的部件，主要完成各种算术运算和规律运算。掌握器：通过读取各种指令，并进展翻译、分析，而后对各部件作出相应的掌握。2、CPU主要由三大局部组成：存放器组、算术规律单元〔ALU〕和掌握单元〔掌握器。存放器组：分为通用存放器〔通用存放器、数据存放器、地址存放器、标志存放器〕和状态掌握存放器〔程序计数器PC、指令存放器IR、存储器地址存放器MAR、存储器缓冲寄MBR〕PSW。输出门A L U+1输入选择门输出门A L U+1输入选择门………..输入选择门……….通用存放器组.I/OALU。掌握单元：掌握器的根本功能就是时序掌握和执行掌握。依据当前运行的程序，掌握器使CPU按肯定的时序关系执行一序列的微操作从而完成程序。时钟信号：掌握器依据时钟电路产生的时钟信号进展定时，以掌握各种操作按指定的时序进展。计算机的根本功能是执行程序，而程序由一连串的指令组成；计算机的执行过程由一连串的指令周期组成，每一指令周期完成一条指令。这些指令周期又可进一步细分为更小的单元，直到微操作uop-----CPU完成的根本的原子操作。时钟脉冲发生器的晶振频率成为机器的主频，它产生的时钟脉冲信号是整个机器的时间基准，其周期T称为该计算机的时钟周期。完成一CPU〔机器周期执行一条机器指令所需的时间称为一个指令周期。、指令系统〔精简指令系统：操作类指令和掌握类指令一条指令：操作码+地址码 一条机器指令的执行：取指令――分析指令――执行指令4、CPU的主要指标有：字长：CPU一次所能处理的二进制位数。它打算着存放器、加法器、数据总线等的位数主频：计算机的时钟频率〔即内频〕单位：MHzGHz。运算速度：CPUMIPS=1÷执行一条机器指令所需的时间-/1－2－4存储器存储单位：最小单位：位〔，缩写，根本单位：字节〔ByteB〕〔3〕常用单位：1KB(1千字节)=1024B 1MB兆字节)=1024KB1GB(1千兆字节)=1024MB1TB=1024GB存储器的分类关系如图：图2内存储器：又称主存，存储器按字节编址。ROM：断电后信息不会丧失，但是信息只能读出不能写入〔BIOS〕RAM：信息可读出和写入，断电后信息全部丧失〔如“内存”、“显存”等〕外存储器：又称作关心存储器。外存储器是一般容量较大且可以移动。例如：硬盘、软盘、光盘、ZIP盘、MO光磁盘、USB存储器等。计算机硬件系统存取信息的方式如图：CPU Cache(缓存) RAM(主存) Disk(辅存)存储器的主要性能指标是存储容量和存取周期〔存取周期与存取速度成反比〕存储容量：辅存＞主存＞缓存；存取速度：缓存＞主存＞辅存1－2－5输入输出〔I/O〕设备输入设备：键盘、鼠标、光笔、数字化仪、图形扫描仪、摄像机等。输出设备：显示器、打印机、绘图仪、磁盘驱动器等。显示器：分为阴极射线管〔CRT〕和液晶显示〔LCD/TFT〕两种。其主要性能指标是区分率〔其他还有如点距、刷率等。1－2－6非冯·诺伊曼型计算机到目前为止，各种类型的计算机都属于冯·诺伊曼型计算机。正在研制中的第五代智能计算学问更的力量，可望突破当前计算机的构造模式。研制朝两个反向努力：1、创立非诺伊曼式语言： 、 〔人工智能语言，用规律设计取代序设计、F.P.〔供理论争论用的抱负语言〕2、创立以人脑神经系统处理信息原理为根底的非冯·诺伊曼式的计算机生物计算机、光子计算机、量子计算机1－3软件系统：包括系统软件和应用软件。系统软件：系统软件指治理、监控和维护计算机资源〔包括硬件和软件〕的软件，主要包括操作系统、各种程序设计语言及其解释编译系统、数据库治理系统等。系统软件中最重要的是操作系统。应用软件：用户利用计算机及其供给的系统软件为解决各种实际问题而编制的计算机程序。-/-/1－3－1操作系统〔OperatingSystem〕1、常见的操作系统操作系统建立了用户与计算机之间的接口。当前常见的操作系统有DOS〔微软公司，DiskOperatingSystem磁盘操作系统、Windows9x/Me/NT/2000/XP〔微软公司，视窗系列操作系统、UNIX、Linux、SunOS〔升阳公司、IBMOS/2等。DOSWindows95是一个单用户多任务操作系统，WindowsNT/2000/XP等属于多用户多任务操作系统。〔多任务分时操作系统，网络操作系统0世纪0年月初期由美国贝尔试验室用C语言开发的。在全部比微机性能更好的工作站型计算机上，都是使用该操作系统。Linux网络操作系统。是一个与UNIX完全兼容的免费操作系统，它的内核全部重编写，并公布了全部源代码。Linux由芬兰人LinuxTorvalds首创，现在已经成为一个稳定牢靠、功能完善、性能卓越的操作系统。2、操作系统的主要功能包括：处理机治理；存储治理；设备治理；文件治理；作业治理。3、操作系统治理掌握方式：ACPU的运行时间分成很短的CPU安排给各联机作业使用。B、实时操作系统：系统响应速度快，他要求计算机对输入的信息做出准时响应，并在规定时间内完成任务。C、网络操作系统：网络用户与计算机网络之间的接口。通过通信子网实现数据通信，通过资源子网进展数据处理，实现共享。1－3－2程序设计语言世界上第一位程序员：英国著名诗人拜伦的女儿AdaLovelace程序设计语言是用户用来编写程序的语言。它分为机器语言、汇编语言和高级语言。机器语言是最底层的计算机语言。它的特点是用机器语言编写的程序，每条指令都是二进制形式的指令代码，由０和１组成。计算机硬件可以直接识别，机器语言 执行速度快，但不易调试修改，程序的直观性差移植性差。低 所谓指令是指一种规定CPU执行某种特定操作的命令，也级 称为机器指令，它包括操作码和地址码。语 汇编 编言 汇编语言高级语言

译汇编语言或计算机不能直接识别汇解翻译程序翻译成机器语言程序释才能执行，执行效率较高，相对机器语言程序而言，易读、翻译的过程称为，负责翻译的程序称之为汇编程序。构造化程序 面对对象设计语言 编程语言

BasicJavaSmallTalkObjectPascal等。Smalltalk是最早的纯面对对象编程语言之一。构造化程序设计语言构造化程序设计语言：FORTRAN、BASIC、PASCAL、C等。Ada语言于军用系统开发的语言，我国军方也将Ada做为军内开发标准〔GJB1383《程序设计语Ada。1－3－3应用软件由于计算机有大量的应用软件，它在生活、生产中的应用很广泛。特地用途的应用软件如字处理软件〔如、财务软件、图形处理软件〔如〕已经深入了我们的生活。计算机常见的应用还包括计算机关心教学〔、计算机关心制造〔关心设计〔CAD〕等。学问产权1997年《中华人民共和国刑法》界定了计算机犯罪1991年《计算机软件保护条例》 计算机学问产权方面的法律法规200111月《全国青少年网络文明公约》针对青少年使用网络，团中心、教育部等部门2001年12月公布了的《计算机软件保护条例以任凭复制、盗版。1－3－7计算机病毒计算机病毒指的是会影响计算机系统正常工作的一类特别的程序传播性、埋伏性、破坏性与隐蔽性。依据计算机病毒存在的媒体和传播方式分类，可以把它分为文件型、引导区型、网络等。网络病毒通过计算机网络传播感染网络中的可执行文件，文件病毒感染计算机中的文件〔e等，引导型病毒感染启动扇区〕和硬盘的系统引导扇区〔R，还有这三种状况的混合型，例如：多型病毒〔文件和引导型〕感染文件和引导扇区两种目标。计算机病毒通常都具有简单的算法或者很好的心理学特性。1－3－7数据库〔DB--DataBase〕1、数据库的根本概念：在计算机存储设备上存储的数据集合。建立在微型机上的关系型数据库是一张二维表格。2、数据库特性：最小冗余：数据尽可能不重复存储数据共享：数据可以为多个用户程序效劳数据独立性：DB中数据与应用程序不存在依靠关系DB以防止不合法使用DB的过程中要确保其正确性、全都性和有效性。3〔：高档数据库产品〔分布式数据库治理软件，中、低档数据库产品(集中式)：Foxpro，DBASE,Access,数据库开发工具：Access，VisualBasic，PowerBuilder，SQLServer,MySQL。基于〔Client/Server〕客户机/效劳器环境中的数据库开发工具。4、SQL---数据库的构造查询语言select学号，姓名 From学生表insertinto学生表values(学号，姓名)-/1－4计算机中的数据表示1－4－1数据类型及其存储:计算机里用到的数据类型主要可以分为两类表示数量的数值数据和非数值性的符号数据。全部的数据都是以二进制的形式在计算机里处理和存储。1－4－3进制的运算和转换1N0～N－1NN进一的〔即以N为基数的数据〕常见的进制有二进制、八进制、十进制，十六进制。二进制的运算分为算术运算与规律运算两种：常用的算术运算〔进位和借位：① 加法：0＋0＝0 0＋1＝1 1＋0＝1 1＋1＝10② 减法：0－0＝0 10－1＝1 1－0＝1 1－1＝0常用的规律运算〔逐位进展：① 规律或0＝0 0＋＝11＝11＝1② 规律与＝0 ＝0＝0＝12NN取余，小数局部乘N取整①整数局部的转换：除二取余10 例如：(19)＝10

②小数局部的转换：2取整例如：(0.125)10＝(0.001)2并非全部的十进制小数都能用有限位的二进制小数来表示。如(0.63)。3、二进制与十六、八进制的转换1个十六进制位=4个二进制位 个八进制位=3个二进制位二进制0000000100100011010001010110011116进制01234567二进制1000100110101011110011011110111116进制89ABCDEF1二进制与十六进制数字比照表二进制000001010011100101110111八进制012345672二进制与八进制数字比照表4、 N进制数转换成十进制数(各位数字与权植乘积存加)nnnn1+n1－4－2数值数据在计算机中的存储为了解决数据的表示范围问题定点数据和浮点数据两类。-/有固定比例换算的量〔即小数点的位置固定不变。由于定点位置的不同，定点数一般分为两类：整数〔Integer，小数点固定于最低位右边的数〕和小数〔Fraction，小数点固定202－1之间，又称为分数。符号阶码E〔定点整数〕尾数M〔定点小数〕计算机中浮点数据表示的根本原理来源于十进制数中使用的科学记数法。一个数N的科学记数法形式可写成：N＝M·REM代表尾数，E代表阶码，R代表基数。当尾数、阶码承受二进制，基数R＝符号阶码E〔定点整数〕尾数M〔定点小数〕1－4－4定点数据的编码为了解决数据的正、负问题，定点数据引入数据的原码、反码、补码表示。位运算：not二进制按位取反and二进制按位与shr二进制按位右移shl二进制按位左移or二进制按位或xor二进制按位异或承受补码制进展运算，所以必需确定该数存储的字节数，再打算该数的补码。原理一个字节表示的数据范围举例原码用最高位〔最左位〕来表示数的符号，0为正数，1为负数－127～＋127255个数〔＋0〕原＝0000000000101011＝＋43，10101011＝－43。〔－0〕原＝10000000反码正数的反码都与它的原码一样，负数－127～＋127255个数(＋56)原＝(＋56)反＝00111000的反码则是它的逐位取反〔＋0〕反＝00000000〔－0〕反＝11111111(－56)原＝10111000(－56)反＝11000111〔符号位不变〕补码正数的补码也与它－128～＋127256个数(＋56)原=(＋56)反=的原码一样，负数的补码等于它的反(-0)补=11111111+00000001＝〔1〕00000000＝〔＋０〕补(＋56)补＝00111000〔－补码加一(-1)补=11111111〔进位自然舍去〕(-2)补=11111110〔-128〕补=100000001－4－5非数值数据在计算机中的存储1、ASCII〔美国标准信息交换代码〕,7ASCII码表示，最高0，存储需要一个字节。20年，〔，字符集收入常用汉字3个，其中包括一级汉字5个〔按汉语拼音排列，二级汉字8个〔按偏旁部首排列67639494位。汉字在代码表中的区号、区位码〔“”；将汉字的区号、位号各增加2国标〔“”以连续的两个字节来表示。为了和码区分，128－1×28－1＝128×128＝-/16384个汉字，国标汉字在计算机内的编码叫做机内码。3、当前常用的其他汉字字符集编码：国家标准〔GBK〕—汉字扩展内码标准；台湾汉字编码标准〔BIG5〕等4、计算机上字符的输出是通过在计算机中预存字形信息库，简称字库点阵字形库和轮廓字形库。点阵字形库时一点振兴是描述的汉字字形代码，其点阵的密度打算了汉字的美观清楚16×1624×24、32×32、64×64等。点阵16×1616×16位＝32字节，676332×6763＝256KB。由于点阵字形库美观程度差、空间占用大，我们现在所承受的一般都是轮廓字形库〔包括Windows9x内的宋体、楷体、黑体。5、汉字激光照排系统的创始人—王选,“汉字印刷术的其次次制造”。1－5计算机网络、计算机网络：1969ARPANET依据距离分类网络类型局域网LAN城域网MANWAN互联网INTERNET

距离几米——10公里10公里——100公里对一个城市的LAN互联几百公里——几千公里

适合的对象位于一个建筑物或一个单位内位于一座城市中国家，邮电部的CHINANET，CHINAPACCHINADDN网一个洲或洲际〔2〕拓扑构造：总线型，星形，环形，树形、OSI〔开放式系统互连参考模型〕OSI〔开放式系统互连参考模型〕是ISO就网络体系提出的一个参考模型，7层.、TCP/IP协议TCP/IP协议把Internet4个层次功能的网络模型

应用层〔ApplicationLayer)表示层〔PresentationLayer)会话层〔SessionLayer〕传输层〔TransportLayer)网络层(NetworkLayer)数据链路层〔DataLinkLayer)Layer)应用层传输层互连网络层

应用程序间沟通的层，如简洁电子邮件传输〔 SMTP〕、文件传输协议〔FTP〕、网络远程访问协议〔Telnet〕等供给了节点间的数据传送，应用程序之间的通信效劳，主要功能是数据格式化、数据确认和丧失重传等。如传输掌握协议〔 TCP〕、用户数据报协议〔UDP〕等，TCP和UDP给数据包参加传输数据并把它传输到下一层中，这一层负责传送数据，并且确定数据已被送达并接收。负责供给根本的数据封包传送功能，让每一块数据包都能够到达目的主机〔但不检查是否被正确接收〕，如网际协议〔 IP〕-/网络接网络接口层接收IP数据报并进展传输，从网络上接收物理帧，抽取IP数据报转交给下一层，对实际的网络媒体的治理，定义如何使用实际网络〔如Ethernet、Serial Line等〕来传送数据。1-5-6、IP地址与子网掩码IPv4地址：32bit位二进制组成，由类型标志、网络标志和主机标识组成。IP地址分为：A、B、C、D、E五类。常用的是A、B、C。0 1 8 31AA类：0网络号主机号0 1 2 16 31BB类：10网络号主机号0 1 2 3 24 31CC类：110网络号主机号网址范围子网掩码A类l--126.0--255.0--255.1--254255．0．0．0B类128--191.0--255.0--255.1--254255．255．0．0C类192--233.0--255.0--255.1--254255．255．0．0其次代CERNET2CNGI最大的核心网和唯一的全国性学术网，CERNET2全国网络中心位于清华大学。CERNET2具有以下特点：1.是中国第一个IPv6国家主干网。2.是目前世界上规模最大的纯IPv6主干网。.建成中国下一代IPv6网交换中心。.承受了自主开发的关键设备及技术，为下一代互联网带动的产业经济打下了坚实根底。IPV6地址长度为128比特。2004年3月，CERNET2试验网正式向用户供给IPv6下一代互联网效劳。目前，CERNET2已经初具规模。CERNET2已经接入北京大学、清华大学、复旦大学、上海交通大学、浙江大学等100多所国内高校，并与谷歌实现基于 IPv6的1Gbps高速互联。DNS效劳器在Internet网上的主机就可以用主机名．域名的方式唯一的标识。如：为域名，由效劳器治理员申请合法可以使用。DNS效劳器：供给主机域名与IP地址之间相互转换效劳的计算机系统。它保存了一张域名(domainname)和与之相对应的IP地址(IPaddress)的表，以解析消息的域名。WEB效劳器：WEBWWW(WORLDWIDEWEB)效劳器，主要是供给网上信息扫瞄效劳。(1)协议。HTML文档格式：html超文本标记语言，HTML命令可以说明文字、图形、动画、声音、表格、链接等。-/-/网页设计中，超链接：本站点网页之间的联系或指向外部的网络资源。标签：本网页之间的跳转。〔3)扫瞄器统一资源定位器(URL)。常见的协议协议TCP/IP协议FTPSMTPPop3Telnet

中文传输掌握协议/因特网互联协议超文本传输协议文件传输协议简洁电子邮件传输邮局协议,个人计算机连接到互联网上的邮件效劳器收发邮件的协议网络远程访问协议

在网络模型中的层次传输层/互连网络层应用层应用层应用层应用层应用层2、竞赛与编程环境全国青少年信息学奥林匹克竞赛系列活动简介简称NOINOIP冬令营APIO选拔赛〔ctsc〕IOI

描 述全国青少年信息学奥林匹克〔201128届〕全国青少年信息学奥林匹克联赛(201117届)全国青少年信息学奥林匹克竞赛冬令营亚洲与太平洋地区信息学奥赛选拔参与国际信息学奥林匹克中国代表队的竞赛国际信息学奥林匹克竞赛NOI2009、NOIP2009竞赛环境说明软件版本说明NOILinux内核-2.6.24NOILinux操作系统–1.2Gcc4.1.2C编译器G++4.1.2C++编译器Freepascal，Fpc2.0.4Pascal编译器Gdb6.6命令行启动Ddd3.3.11命令行启动分类系统软件分类系统软件编译器调试器集成开发环境GUIDE1.0.0AnjutaLazarus.22IDE〔C/C++/Pascal〕C/C++IDEPascalIDE图灵是英国著名的数学家和规律学家，被称为计算机科学之父、人工智能之父，是计算机规律的奠基者，提出了“图灵机”和“图灵测试”等重要概念。图灵机就是指一个抽象的机器，抱负计算机模型。“是美国计算机协会，nrr〕于1966年设立的，特地嘉奖那些对计算机科学争论与推动计算机技术进展有卓越奉献的出色科学家，它被公认为计算机界的“诺贝尔”奖。2000年，姚期智(AndrewChi-ChihYao获得图灵奖，美籍华人。也是迄今为