信息学奥赛基础知识
§ 1 计算机概述 世界第一台电子数字式计算机于1946年美国宾夕法尼亚大学正式投入运行，它的名称叫ENIAC (埃尼阿克)，是电子数值积分计算机的缩写。它使用了17468个真空电子管，耗电174千瓦，占地170平方，重30吨，每秒钟可进行5000次加法运算。 被西方人誉为“计算机之父”的美籍匈牙利科学家、数学家冯·诺依曼于1945年发表了一个全新的"存储程序通用电子计算机方案"—EDVAC 。EDVAC 方案提出了著名的“冯·诺依曼体系结构”理论： (1)采用二进制形式表示数据和指令 在存储程序的计算机中，数据和指令都是以二进制形式存储在存储器中的。从存储器存储的内容来看两者并无区别．都是由0和1组成的代码序列，只是各自约定的含义不同而已。计算机在读取指令时，把从计算机读到的信息看作是指令；而在读取数据时，把从计算机读到的信息看作是操作数。数据和指令在软件编制中就已加以区分，所以正常情况下两者不会产生混乱。有时我们也把存储在存储器中的数据和指令统称为数据，因为程序信息本身也可以作为被处理的对象，进行加工处理，例如对照程序进行编译，就是将源程序当作被加工处理的对象。 (2)采用存储程序方式 这是冯·诺依曼思想的核心内容。如前所述，它意味着事先编制程序，事先将程序(包含指令和数据)存入主存储器中，计算机在运行程序时就能自动地、连续地从存储器中依次取出指令且执行。这是计算机能高速自动运行的基础。计算机的工作体现为执行程序，计算机功能的扩展在很大程度上也体现为所存储程序的扩展。计算机的许多具体工作方式也是由此派生的。 冯·诺依曼机的这种工作方式，可称为控制流(指令流)驱动方式。即按照指令的执行序列，依次读取指令，然后根据指令所含的控制信息，调用数据进行处理。因此在执行程序的过程中，始终以控制信息流为驱动工作的因素，而数据信息流则是被动地被调用处理。为了控制指令序列的执行顺序，设置一个程序(指令)计数器PC(ProgramCounter)，让它存放当前指令所在的存储单元的地址。如果程序现在是顺序执行的，每取出一条指令后PC 内容加l ，指示下一条指令该从何处取得。如果程序将转移到某处，就将转移的目标地址送入PC ，以便按新地址读取后继指令。所以，PC 就像一个指针，一直指示着程序的执行进程，就是指示控制流的形成。虽然程序与数据都采用二进制代码，仍可按照PC 的内容作为地址读取指令，再按照指令给出的操作数地址去读取数据。由于多数情况下程序是顺序执行的，所以大多数指令需要依次地紧挨着存放，除个别即将使用的数据可以紧挨着指令存放外、一般将指令和数据分别存放在该程序区的不同区域内。 (3)由运算器、存储器、控制器、输入设备和输出设备五大部件组成计算机系统，并规定了这五部分的基本功能。 上述这些概念奠定了现代计算机的基本结构思想，到目前为止，绝大多数计算机仍沿用这一体制，即冯·诺依曼型计算机体制。
巨型化、微型化、多媒体化、网络化、智能化 计算机的特点： 1.运算速度快：最快可以达到上万亿次/s 。 2.精确度高：微型机可达到十几位有效数字。 3.存储功能（有记忆功能）：能存储程序和数据。 4.能进行逻辑运算。 5.在程序的控制下能自动工作。 计算机的主要应用： 1、科学计算：密码破译，天气预报，地质勘探， 卫星轨道计算 2、数据处理：数据库管理，企业信息管理， 统计汇总、办公自动化 3、自动控制：机器人以及各种自动化装备
4、计算机辅助设计/分析/制造/教学：机械CAD ，建筑CAD ，计算机辅助教学CAI
5、智能模拟：人工智能、专家系统、自学习
6、电子商务：
7、休闲娱乐： 计算机分类：
1、按规模分：巨型机、大型机、中型机、小型机、
微型机
2、按用途分：专用机、通用机
3、按处理方式分：模拟计算机、数字计算机以
及数字模拟混合计算机 4、照其工作模式分：服务器、工作站 计算机的主要性能技术指标
1.字长
字长是计算机运算部件一次能处理的二进制数据的位数。字长愈长，计算机的处理能力就愈强。 早期的微型计算机的字长为16位，如：80286等。 现在的微型计算机的字长为32位，如80386， 80486，PIV 等。对于数据，字长愈长，运算精度愈高；对于指令，字长愈长，则功能愈强，而寻址的存储空间也愈大。 2.速度 不同配置微型计算机按相同的算法执行相同的任务所需要的时间可能是不同的，这和微型计算机的速度有关。 微型计算机速度指标可以用主频和运算速度来评价。主频也称时钟频率，是指CPU 工作时的频率。主频是衡量微型机运行速度的主要参数，主频越高，执行一条指令的时间就越短，因而速度就愈快。主频一般以兆赫兹（MHz ）为单位。目前的微机的主频在500MHz 左右，高的可达1000MHz 左右，甚至更高。 运算速度是以每秒百万指令数（MIPS ）为单位。这个指标较主频更能直观的反映微型计算机的运算速度。 速度是一个综合指标，影响微型计算机速度的因素还有许多，如存储器的存取时间系统总线的时钟频率等。 3.存储系统容量 存储系统主要包括主存储器（也称内存）和辅助存储器（也称外存）。内存储器容量是指为计算机系统所配置的内存总字节数，CPU 可直接访问的大部分存储空间。
存储容量以字节（B ）为单位，一个字节由8位二进制位组成。用KB ，MB ，GB ，TB
等表示，具体换算公式为： 目前，软件系统的体积越来越大，对存储空间要求也越来越高，很多复杂的软件，要有足够大的硬盘空间才能装得下，要有足够大的内存空间才能运行。
4.系统可靠性
计算机的可靠性以平均无故障时间（MTBF ）表示： 其中：Ti ：第i 次无故障时间；N ：故障总次数。MTBF 愈大，系统性能愈好。 5.系统可维护性 计算机的可维护性以平均修复时间（MTTR ）表示： 其中：Ti ：第i 次故障修复时间; M ：修复总次数。MTTR 愈大，系统性能愈好。 6.性价比 性价比是用来衡量计算机产品优劣的概括性指标。性：指性能，代表计算机的使用价值，它包括计算机的运算速度、存储器容量、存取周期。通道信息流量速率、输入输出设备的配置和计算机的可靠性。 价：指价格，代表计算机的售价。 性价比愈大，表明计算机系统愈好。 §2计算机系统的基本组成 完整的计算机系统系统包括：硬件系统和软件系统。两个部分又由若干个部件组成(如图）。 硬件系统是计算机的“躯干”，是物质基础。而软件系统则是建立在这个“躯干”上的“灵魂”。 （一）计算机硬件 计算机硬件系统由五大部分组成：运算器、控制器、存储器、输入设备、输出设备。（如下图所示）
*中央处理器（CPU ——CentralProcessingUnit ） CPU
由运算器、控制器和一些寄存器组成； 1.运算器 运算器是计算机中进行算术运算和逻辑运算的部件，通常由算术逻辑运算部件（ALU ）、累加器及通用寄存器组成。 2.控制器 控制器用以控制和协调计算机各部件自动、连续地执行各条指令，通常由指令部件、时序部件及操作控制部件组成。 运算器和控制器是计算机的核心部件，这两部分合称中央处理单元（CentreProcessUnit ，简称CPU ），如果将CPU 集成在一块芯片上作为一个独立的部件，该部件称为微处理器（Microprocessor ，简称MP ）。 运算器进行各种算术运算和逻辑运算；控制器是计算机的指挥系统； CPU 的主要性能指标是主频和字长。 字长表示CPU 每次计算数据的能力。如80486及Pentium 系列CPU 一次可处理32位二进制数据。 时钟频率主要以MHz 为单位来度量，通常时钟频率越高，其处理速度也越快。目前的主流CPU 的时钟频率已发展到500MHz 以上甚至达２GHz 以上。 *存储器 存储器的主要功能是用来保存各类程序的数据信息。 存储器可分为主存储器和辅助存储器两类。 ①主存储器（也称内存储器），属于主机的一部分。用于存放系统当前正在执行的数据和程序，属于临时存储器。 ①辅助存储器（也称外存储器），它属于外部设备。用于存放暂不用的数据和程序，属于永久存储器。存储器与CPU 的关系可用(图1）来表示。
（1）内存储器 一个二进制位（bit ）是构成存储器的最小单
位。实际上，常将每8位二进制位组成一个存储
单位，简称字节（Byte ）。字节是数据存储的基
本单位。为了能存取到指定位置的数据，给每个存储单元编上一个号码，该号码称为内存地址。 度量内存主要性能指标是存储容量和存取时间。 存储容量是指存储可容纳的二进制信息量，描述存储容量的单位是字节。 存取时间指存储器收到有效地址到在输出端
出现有效数据的时间间隔。存取时间用纳秒为单位。时间愈短，其性能愈好。 内存储器按其工作方式可分为随机存储器（RandomAcessMemory ，简称RAM ）和只读存储器（ReadOnlyMemory ，简称Rom ）两类。 ①RAM RAM 在计算机工作时，既可从中读出信息，也可随时写入信息，所以，RAM 是一种在计算机正常工作时可读/写的存储器。在随机存储器中，以任意次序读写任意存储单元所用时间是相同的。目前所有的计算机大都使用半导体随机存储器。半导体随机存储器是一种集成电路，其中有成千上万个存储单元。 根据元器体结构的不同，随机存储器又可分为静态随机存储器（StaticRAM ，简称SARM ）和动态随机存储器（DynamicRAM ，简称DRAM ）两种。 静态随机存储器（SARM ）集成度低，价格高。但存取速度快，它常用作高速缓冲存储器（Cache ）。 Cache 是指工作速度比一般内存快得多的存储器，它的速度基本上与CPU 速度相匹配，它的位置在CPU 与内存之间(如图2所示）。在通常情况下，Cache 中保存着内存中部分数据映像。CPU 在读写数据时，首先访问Cache 。如果Cache 含有所需的数据，就不需要访问内存；如果Cache 中不含有所需的数据，才去访问内存。设置Cache 的目的，就是为了提高机器运行速度。 动态随机存储器使用半导体器件中分布电容上有无电荷来表示“0”和“1”的，因为保存在分布电容上的电荷会随着电容器的漏电而逐步消失，所以需要周期性的给电容充电，称为刷新。这类存储器集成度高、价格低、存储速度慢。 随机存储器存储当前使用的程序和数据，一旦机器断电，就会丢失数据，而且无法恢复。因此，用户在操作计算机过程中应养成随时存盘的习惯，以免断电时丢失数据。
(图2）
②ROM 只读存储器（ROM ）只能做读出操作而
不能做写入操作。只读存储器中的信息是在制造
时用专门的设备一次性写入的，只读存储器用来
存放固定不变重复执行的程序，只读存储器中的
内容是永久性的，即使关机或断电也不会消失。
目前，有多种形式的只读存储器，常见的有如下几种： PROM ：可编程的只读存储器。 EPROM ：可擦除的可编程只读存储器。 EEPROM ：可用电擦除的可编程只读存储器。 CPU （运算器和控制器）和主存储器组成了计算机的主机部分。 （2）外存储器 外存储器大都采用磁性和光学材料制成。与内存储器相比，外存储器的特点是存储容量大，价格较低，,而且在断电的情况下也可以长期保存信息，所以称为永久性存储器。缺点是存取速度比内存储器慢，常见的外存储器有以下几种： 磁盘磁盘是微型计算机系统中最重要的外部存储器,同时定它又是重要的输入输出设备，它即可作为输入设备，又可作为输出设备。它一般包括软磁盘存储器和硬磁盘存储器。磁盘属于磁表面存
储设备。它的信息存储是一种电磁转换过程，它
是通过磁头与磁盘片的相对运动来实现。
软盘驱动器
软盘驱动器简称软驱。软驱是数据和程序进
入微型计算机的门户。软驱所用的软盘直径通常
有3.5英寸和5.25英寸两中.现在的微型计算机
一般都配置3.5英寸驱动器一个，其容量为
1.44MB ，盘符为“A：”。
软盘存储信息是按磁道和扇区组织存储的，
软盘在使用前必须进行格式化。格式化就是对软
磁盘划分磁道和扇区。格式化时将磁盘面划分成
若干个同心圆,每个同心圆称为一个磁道，3.5英
寸的软盘有80个磁道，磁道的编址是由外向内的
编号的，最外层的一个同心圆为0号磁道，最内
层的同心圆为第79磁道，每个磁道又被划分为若干区域，每个区域称为扇区(如图3所示），目前常用的软盘都划分为18个扇区，每个扇区可存放512个字节，每张盘片又可分为A 、B 两面。因此，可以得出
512*80*18*1=1474560(B)=1.44(MB) (图3） 软盘在格式化后会产生四个区:引导区(BOOT)、文件分配表(FAT)、文件目录表和数据区。 引导区用于存放引导程序。 文件分配表用于描述文件在磁盘上存放的位置以及整个软盘扇区的使用情况。 文件目录表区用来存放软盘根目录下所有子目录文件文件属性、文件在软盘上的存放的开始位置、文件长度以及文件建立和修改的日期和时间。 数据区是存放文件内容的区域。 引导区和文件分配表这些供系统使用和管理
软盘的重要信息存放在软盘的0磁道上，所以如
果磁盘的0磁道损坏会导致整个软盘无法使用。
软盘的特点是成本低，重量轻，价格便宜，便于携带，缺点是存储容量小，且软盘容易损坏。硬盘硬盘也称固定盘。硬盘的存储容量，读/写速度均比软盘高得多。磁盘是按柱面磁头号和扇区的格式组织存取信息的，(如图4所示)的柱面由一组盘片的同一磁道在纵向上所形成的同心圆柱面构成。柱面从外想内编号，同一柱面上的各个磁道和扇区的划分与软盘基本相同。
数据在硬盘上的位置通过柱面号，磁头号和扇区号三个参数来确定的，硬盘与硬盘驱动器固定在一起，硬盘格式化后，其使用方式与软盘一样，也是通过盘符标识符来确认。硬盘的盘符通常为“C：”，若系统配有多个硬盘或将一个物理硬盘划分为多个逻辑硬盘，则盘符可依次为“C：”、“D”、“E”、“F”等。
(图4)
目前微型计算机中普遍使用了3英寸和5英寸硬盘，大都采用温切斯特（wenchester）技术，所以有时称这类硬盘为温盘。
硬盘的特点是可靠性高，存储容量大，读写速度快，对环境要求不高。缺点是不便于携带，切工作时应避免振动。
光盘光盘是用光学的方式制成的，光盘盘片上有一层可塑材料。写入数据时，永高能激光束照射光盘片，可在可塑层上灼出极小的坑，并以有无小坑表示数字“0”和“1”，当数据全部写入光盘后，再在可塑层上喷涂一层金属材料，这样光盘就不能再写入数据。再读出数据时，永低能激光束入射光盘，利用盘表面上的小坑和平面处的不同反射来区分“0”和“1”。目前微型计算机中大都配有只读式光盘
（COMPACTDISKREADONLYMEMORY，简称CD-ROM），每张关盘容量可达650MB，可存放程序，文本，图象，音乐和电影等各种信息。
光盘需要语光盘驱动器配合使用。光盘驱动器（简称光驱）是多媒体电脑的重要输入设备。光驱的盘符一般为紧邻着硬盘盘符后的那一个英文字母来表示。
根据使用方式及性能不同，光盘分为三类：①只读式关盘（CD-ROM）：用户只能读取而无法修改其中的数据。
②一次性写入光盘（WriteOnceReadManytime,简称WORM）：用户可以写入一次，但可多次读取。
③可擦除光盘：用户可以像用软盘一样对其进行多次读/写操作。
④光盘的特点:
1)存储容量大,价格低;
2)不怕电磁干扰,存储密度高,可靠性高;
3)存取速度在不断增高。
＊输入设备
键盘（Keyboard）：104、107键盘
鼠标（Mouse）:机械和光电鼠标两种
手写笔触摸屏麦克风扫描仪（Scanner）
视频输入设备条形码扫描
＊输出设备显示器：CRT和液晶显示器。
打印机：针式、喷墨、激光打印机。
绘图仪音箱
＊总线
计算机总线是一组连接各个部件的公共通信线。计算机中的各个部件是通过总线相连的，因此各个部件间通信关系变成面向总线的单一关系(如图所示）。但是任一瞬间总线上只能出现一个部件发往另一个部件的信息，这意味着总线只能分时使用，而这是需要加以控制的。总线使用权的控制是设计计算机系统时要认真考虑的重要问题。总线是一组物理导线，并非一根。根据总线上传送的信息不同，分为地址总线、数据总线和控制总线。
①地址总线
地址总线传送地址信息。地址是识别信息存
放位置的编号，主存储器的每个存储单元及I/O
接口中不同的设备都有各自不同的地址。地址总
线是CPU向主存储器和I/O接口传送地址信息的
通道，它是自CPU向外传输的单向总线。
②数据总线
数据总线传送系统中的数据或指令。数据总
线是双向总线，一方面作为CPU向主存储器和I/O
接口传送数据的通道。另一方面，是主存储器和
I/O接口向CPU传送数据的通道，数据总线的宽度
与CPU的字长有关。
③控制总线
控制总线传送控制信号。控制总线是CPU向
主存储器和I/O接口发出命令信号的通道，又是
外界向CPU传送状态信息的通道。
我们通常用总线宽度和总线频率来表示总线
的特征。总线宽度为一次能并行传输的二进制位
数，即32位总线一次能传送32位数据，64位一
次能传送64位数据。总线频率则用来表示总线的
速度，目前常见的总线频率为66MHZ，100MHZ，
133MHZ或更高。
总线在发展过程中已逐步标准化，常见总线
标准有ISA总线PCI总线、EISA总线和AGP总线。
·ISA（IndustryStandardArchiitecture，工业
标准）总线是一种16位的总线结构，适用范围广，
因为很多的接口卡都是根据ISA标准生产的。
·PCI（PeripheralComponentInterconnection，
外部设备互连）总线是一种32位的高性能总线，
可扩展到64位，与ISA总线兼容。目前，高性能
微型机主板上都设有PCI总线。该总线标准性能
先进，成本较低，可扩充性好，特别是对于微软
提出的“即插即用”方案的很好支持，现已成为
奔腾级以上普遍采用的外设接插总线。
·AGP（AcceleratedGraphicsport，图形加速接
口）总线是随着三维图形的应用而发展起来的一
种总线标准。三维图形对计算机速度提出了很高
的要求，使得PIC总线传送速度变得很紧张，AGP
在图形与内存之间提供了一条直接的访问途径。
·EISA
（ExtendedIndustryStandardArchitecture，扩
展工业标准结构）总线是对ISA总线的扩展。
（二）计算机软件
计算机软件可分为系统软件和应用软件两大类。
·系统软件：系统软件是计算机必备的，用以实
现计算机系统的管理、控制、运行、维护，并完
成应用程序的装入、编译等任务的程序。系统软
件与具体应用无关，是在系统一级上提供的服务。
常用的系统软件：操作系统、编译程序、语
言处理程序和数据库管理系统等。例如：
操作系统：DOS、Windows95/98/2000、Unix、
Linux、WindowsNT；
编译系统：机器语言，汇编语言和高级语言
数据库系统：Foxpro，Access，Orale，Sybase，
DB2和Informix
·应用软件：应用软件是为了解决计算机应用中
的实际问题而编制的程序。它包括商品化的通用
软件和实用软件，也包括用户自己编制的各种应
用程序。
按照应用软件的应用领域与开发方式，可以
把应用软件分为三类：
①定制软件
定制软件是针对某些具体应用问题而研制的
软件。这类软件完全按照用户自己的特定需求而
专门进行开发的，应用面相对较窄，运行效率较
高。如:股票分析软件、工资管理软件、学籍管理
软件和企业经营管理软件等。
②应用软件包
在某个应用领域中有一定通用性的软件，称
为应用软件。应用软件包可能不能满足该领域内
的所有用户的需要，通常用户购买这类软件后，
需要经过二次开发后才能投入实际使用。如财务
管理软件包、统计软件包和生物医用软件包等。
③流行应用软件
在一些相对广泛使用的领域中有着相当多用
户的流行应用软件，这些软件不断推出新的版本，
不断改进其功能，效率和使用的方便性。如：文
字处理软件、电子表格软件和绘图软件等。
§3信息数字化 ＊进位计数制的基本概念 将数字符号按序排列成数位，并遵照某种由低位到高位的进位方式计数表示数值的方法，称作进位计数制。 1.十进制 十进制计数制由0、1、2、3、4、5、6、7、8、9共10个数字符号组成。相同数字符号在不同的数位上表示不同的数值，每个数位计满十就向高位进一，即“逢十进一”。 如：555.5可以表示成 555.5＝5×100+5×10+5×1+5×（1/10） 一个任意的十进制数都可以表示成： 2.八进制 八进制计数制由0、1、2、3、4、5、6、7共8个数字符号组成。相同数字符号在不同的数位上表示不同的数值，每个数位计满八就向高位进一，即“逢八进一”。如：（555.5）8可以表示成 （555.5）8＝5×16+5×8+5×1+5×（1/8） 一个任意的十进制数都可以表示成： 3.二进制 二进制计数制由0和1共2个数字符号组成。相同数字符号在不同的数位上表示不同的数值，每个数位计满二就向高位进一，即“逢二进一”。 如：(1011.1)2＝1×8+0×4+1×2+1×1+1×(1/2) 一个任意的二进制数都可以表示成： 4.其他进制 在日常生活和日常工作中还使用其他进制数如：十二进制数、十六进制数、百进制数和千进制数等。无论哪种进制数，表示的方法都是类似的。如：十六进制数由0、1、2、3、4、5、6、7、8、9、A 、B 、C 、D 、E 和F 共十六个符号组成，“逢十六进一”。不同的是用A 、B 、C 、D 、E 和F 分别表示10、11、12、13、14和15六个数字符号。 5.基数与权 某进制计数制允许选用的基本数字符号的个数称为基数。一般而言，J 进制数的基数为J ，可供选用的基本数字符号有J 个，分别为0到J －1，每个数位计满J 就向高位进一，即“逢J 进一”。 某进制计数制中各位数字符号所表示的数值表示该数字符号值乘以一个与数字符号有关的常数，该常数称为“位权”（简称“权”）。位权的大小是以基数为底，数字符号所处的位置的序号为指数的整数次幂。 十进制数允许使用十个基本数字符号，所以基数为10，每位数字符号代表的位数的大小是以10为底，数字符号所处位置的序号为指数的整数次幂。
(如图所示）给出了任意进制数（K2K1K0K-1K-2），当J 分别为：2，8，10和16时各位权值对照。
＊数制之间的转换： 计算机内部使用的数字符号只有“0”和“1”两个。也就是说计算机内部使用的是二进制数所有的数值数据和非数值数据，都是由“0”和“1”这两个数字符号加以组合而成的，我们称之为“二进制代码”。 1．为什么要采用二进制 尽管二进制数不符合人们的习惯。但是计算机内部仍采用二进制表示信息，主要原因有以下几点： 1）容易实现 计算机是由逻辑电路组成，逻辑电路通常只有两种状态。例如：开关的接通与断开，电压电平的高与低等。这两种状态正好用来表示二进制数的两个数码0和1。 2）工作可靠 两个状态代表的两个数码在数字传输和处理中不容易出错，因而电路更加稳定可靠。 3）简化运算 二进制运算法则简单。两个一位二进制数的求和、求积运算组合仅有三种，即0＋0＝0，0＋1＝1，1＋0＝1，1＋1＝0（向高位进一）及0*0＝0，
0*1＝1，1*0＝0，1*1＝1。而求两个一位十进制
的和与积的运算组合则各有55种之多，让计算机
去实现就困难的多。
4）逻辑性强 计算机的工作是建立在逻辑运算基础上的，逻辑代数是逻辑运算的理论依据。二进制只有两个数码，正好代表逻辑代数中的“真”与“假”。 5）易于转换 二进制数与十进制数之间可以互相转换。这样，既有利于充分发挥计算机的特点，又不影响人们使用十进制数的习惯。 2．数值间的转换 计算机只用二进制的两个数码“0”和“1”来实现算术和逻辑运算，而人们仍然用十进制的形式向计算机中输入原始数据，并让计算机也用
十进制形式显示和打印运算结果。所以必须有一
种自动转换方法，即让数据输入计算机后，将十
进制转换成对应的二进制数，并在处理完毕后，再自动将二进制结果转换为十进制数。
为了表达方便起见，常在数字后加一缩写字母后缀作为不同进制数的标识。各种进制数的后缀字母分别为：
B ：二进制数。 Q ：八进制数。
D ：十进制数。 H ：十六进制数。 对于十进制数通常不加后缀，也即十进制数后的字母D 可省略。
（1）将二进制数转换成对应的十进制数 将二进制数转换成对应的十进制数的方法是“按权展开求和”：
利用二进制数按权展开的多项式之和的表达式，取基数为2，逐项相加，其和就是对应的十进
制数。
例1：将二进制数1011.1转换成对应的十进制
解：
1011.1B=1×23+0×22+1×21+1×20+1×2-1
=8+0+2+1+0.5
=11.5D
例２：
（2）将十进制数转换成对应的二进制数 将十进制数转换为对应的二进制数的方法是：
对于整数部分，用被除数反复除以2，除第一次外，每次除以2均取前一次商的整数部分作被
除数并依次记下每次的余数。另外，所得到的商
的最后一位余数是所求二进制数的最高位。
对于小数部分，采用连续乘以基数2，并依次
取出的整数部分，直至结果的小数部分为0为止。故该法称“乘基取整法”。
例：将十进制117.625D 转换成二进制数 解：整数部分：“除以2取余，逆序输出”
小数部分:“乘以2取整，顺序输出”
所以117.625D＝1110101.101B
例２：
例３：
特别提示：将十进制数转换成其他进制数方法与次上述方法类似。
（3）将二进制数转换为对应的八进制数
由于1位八进制数对应3位二进制数，所以
二进制数转换成八进制数时，只要以小数点为界，
整数部分向左，小数部分向右每3位分成一组，
各组用对应的1位八进制数字表示，即可得到对
应的八进制数值。最左最右端分组不足3位时，
可用0补足。例：将1101101.10101B转换成对应
的八进制数。解：
所以，1101101.10101B＝155.52Q。
同理，用相反的方法可以将八进制数转换成
对应的二进制数。
（4）将二进制数转为对应的十六进制数
由于1位十六进制数对应4位二进制数，所
以二进制数转换为十六进制时，只要以小数点为
界，整数部分向左，小数部分向右每4位分成一
组，各组用对应的1位十六进制数字表示，即可
得到对应的十六进制数值。两端的分组不足4位
时，用0补足。
例：将1101101.10101B转换成对应的十六进制数
解：
所以1101101.10101B＝6D.8AH。
同理，用相反的方法可以将十六进制数转换
成对应的二进制数。
例：将十六进制数5DF.9转换成二进制：
例：将二进制数1100001.111转换成十六进制：
至于其他的转换方法，如八进制到十进制，
十六进制到十进制之间的转换，同样可用按权展
开的多项式之和及整数部分用“除基取整数”来
实现的。只不过此时基数分别为8和16。当然，
更简单实用的方法是借用二进制数做桥梁，用
“八——二——十”或“十六——二——八”的
转换方法来实现。
＊数据的编码表示
1．基本概念
（1）编码
计算机要处理的数据除了数值数据以外，还
有各类符号、图形、图像和声音等非数值数据。
而计算机只能识别两个数字。要使计算机能处理
这些信息，首先必须将各类信息转换成“0”和
“1”表示的代码，这一过程成为编码。
（2）数据能被计算机接受和处理的符号的集
合都称为数据。
数据和信息是一对比较容易混淆的术语。
数据是计算机处理的对象，是信息载体，或
称编码了的信息；
信息是数据经过加工处理以后的结果，是有意
义的数据的内容。
（3）比特比特（Bit：BinaryDigit——二
进制数位）是指1位二进制的数码（即0或1
比特是计算机中表示信息的数据编码中的最小单
位。
（4）字节
字节表示被处理的一组连续的二进制数字。通常
用8位二进制数字表示一个字节，即一个字节由
个比特组成。
字节是存储器系统的最小存取单位。
2．数值数据的表示
数值数据有大小和正负之分。
＝128种国际上最通用的西文字符，是目前计算机中，特别是微型计算机中使用最普遍的字符编码集。详见表1.2。 ASCII 编码包括4类最常用的字符。 ①数字“0”-“9”。ASCII 编码的值分别为0110000B ～0111001B ，对应十六进制数为30H ～39H 。 ②26个英文字母。大写字母“A”～“Z”的ASCII 编码值为41H ～5AH ，小写字母“a”～“z”的ASCII 编码值为61H ～7AH 。 ③用字符。如“＋”、“－”、“＝”、“*”和“/”等共32个。 ④制符号。如空格符和车符等共34个。 ASCII 码是一种7位编码，它存时必须占全一个字节，也即占用8位：b7b6b5b4b3b2b1b0，其中b7恒为0，其余几位为ASCII 码值。 （2）汉字编码 国家标准汉字编码集（GB2312-80）共收集和定义了7445个基本汉字。其中，使用频度较高的3755个汉字定义为一级汉字。使用频率较低的3008个汉字定义为二级汉字，共有6763个汉字。另外还定义了拉丁字母、俄文字母、汉语拼音字母、数字和常用符号等682个。 GB2312－80规定每个汉字用2个字节的二进制编码，每个字节最高位为0，其余7位用于表示汉字信息。 例如，汉字“啊”的国标码的2个字节的二进制编码00110000B 和00100001B ，对应的十六进制数为30H 和21H 。 另外，计算机内部使用的汉字机内码的标准方案是将汉字国标码的2个字节二进制代码的最高位置为1，从而得到对应的汉字机内码。 如汉字“啊”的机内码为10110000B 、10100001B （即B0H 、A1H ）。 计算机处理字符数据时，当遇到最高位为1的字节，便可将该字节连同其后续最高位也为1的另一个字节看作1个汉字机内码；当遇到最高位为0的字节，则可看作一个ASCII 码西文字符，这样就实现了汉字、西文字符的共存与区分。 2000年3月17日，国家信息产业部和国家质量技术监督局联合颁布了GB18030－2000《信息技术信息交换用汉字编码字符集基本集的扩充》。在新标准中采用了单、双、四字节混合编码，收录了27000多个汉字和藏、蒙、维吾尔等主要的少数民族文字，总的编辑空间超过了150万个码位。新标准适用于图形字符信息的处理、交换、存储、传输、显示、输入和输出，并直接与GB2312－80信息处理交换码所对应的事实上的内码标准相兼容。所以，新标准与现有的绝大多数操作系统、中文平台兼容，能支持现有的各种应用系统。 ＊汉字交换码 汉字交换码是指不同的具有汉字处理功能的计算机系统之间在交换汉字信息时所使用的代码标准。自国家标准GB2312－80公布以来，我国一直延用该标准所规定的国标码作为统一的汉字信息交换码。 GB2312－80标准包括了6763个汉字，按其使用频度分为一级汉字3755个和二级汉字3008个。一级汉字按拼音排序，二级汉字按部首排序。此外，该标准还包括标点符号、数种西文字母、图形、数码等符号682个。 区位码的区码和位码均采用从01到94的十进制，国标码采用十六进制的21H 到73H （数字后加H 表示其为十六进制数）。区位码和国标码的换算关系是：区码和位码分别加上十进制数32。如“国”字在表中的25行90列，其区位码为2590，国标码是397AH 。 *由于GB2312－80是80年代制定的标准，在实际应用时常常感到不够，所以，建议处理文字信息的产品采用新颁布的GB18030信息交换用汉字编码字符集，这个标准繁、简字均处同一平台，可解决两岸三地间GB 码与BIG5码间的字码转换不便的问题。 ＊汉字输入码 汉字输入方法很多，如区位、拼音、五笔字型等。不同输入法有自己的编码方案，所采用的编码方案统称为输入码。输入码进入机器后必须转换为机内码进行存储和处理。 汉字输入方法大体可分为：区位码（数字码）、音码、形码、音形码。 区位码：优点是无重码或重码率低，缺点是难于记忆； 音码：优点是大多数人都易于掌握，但同音字多，重码率高，影响输入的速度； 形码：根据汉字的字型进行编码，编码的规则较多，难于记忆，必须经过训练才能较好地掌握；重码率低 音形码：将音码和形码结合起来，输入汉字，减少重码率，提高汉字输入速度； 如，以全拼输入方案键入“neng”，或以五笔字型输入方案“ce”，都能得到“能”这个汉字所对应的机内码。这个工作由汉字代码转换程序依靠事先编制好的输入码对照表完成转换。 ＊汉字字形码（字形存储码） 字形存储码是指供计算机输出汉字（显示或打印）用的二进制信息，也称字模。通常，采用的是数字化点阵字模。 汉字字形码是一
种用点阵表示字形的码，是汉字的输出形式。它把汉字排成点阵。常用的点阵由16×16、24×24、32×32或更高。每一个点在存储器中用一个二进制位（bit ）存储。例如，在16×16的点阵中，需8×32bit 的存储空间，每8bit 为1字节，所
以，需32字节的存储空间；24×24点阵要占72
个字节（为什么？）。在相同点阵中，不管其笔
划繁简，每个汉字所占的字节数相等。
为节省存储空间，普遍采用了字形数据压缩技
术。所谓的矢量汉字是指用矢量方法将汉字点阵
字模进行压缩后得到的汉字字形的数字化信息。 所有不同的汉字字体的字形构成汉字库，一般存储在硬盘上，当要显示输出时，才调入内存，检索到要输出的字形送到显示器输出。 （３）其他信息的编码 ＊图像的表示
一幅图像可认为是由一个个像点构成的，这些像点称为像素。每个像素必须用若干二进制位进行编码，才能表示出现实世界中的五彩缤纷的图像。
当将图像分解成一系列像点、每个点用若干bit 表示时，我们就把这幅图象数字化了。 数字图像数据量特别巨大，假定画面上有
150000个点，每个点用24个bit 来表示，则这幅画面要占用450000个字节。如果想在显示器上播放视频信息，一秒钟需传送25幅画面，相当与11250000个字节的信息量。因此，用计算机进行图像处理，对机器性能要求是很高的。
图像文件的后缀名有：bmp 、gif 、jpg 等； ＊声音的表示
声音是一种连续变化的模拟量，我们可以通过“模/数”转换器对声音信号按固定的时间进行采样，把它变成数字量。一旦转变成数字形式，便可把声音储存在计算机中并进行处理了。 声音文件的后缀名有：wav 、mp3等； ＊视频信息的数字化
视频信息可以看成连续变换的多幅图像构成，播放视频信息，每秒需传输和处理25幅以上的图像。视频信息数字化后的存储量相当大，所以需要进行压缩处理。
视频文件后缀名有：avi 、mpg 等；
§4操作系统（OS ——OperatingSystem ） 操作系统是控制与管理计算机系统资源的软件，是硬件的第一层扩充，任何应用软件的运行都必须依靠操作系统的支持。
微机的
OS
Windows 系列操作系统 Windows 是Microsoft 公司开发的图形化界面的操作系统。 ·基本概念： 图标、任务栏、标题栏、菜单栏、滚动条、工具栏、对话框、开始菜单……
·基本操作：
（1）鼠标单击、双击、拖动，左键、右键功能； （2）窗口操作：最大（小）化、大小调整、拖动、
关闭、排列、切换； （3）菜单操作： 激活、选择；
★命令项的约定——
正常显示和灰色显示；
命令后带“…”：执行命令则弹出对话框； 带快捷键：某些菜单命令的后面标有对应的键盘命令，称为该命令的快捷键或热键； 选中标志：某些命令选项的左侧有用打勾表示的选中标志，说明此命令功能正在起作用； 命令后带“▲”：级联：此命令后会有下一级的子命令菜单弹出供用户作进一步选择； ★快捷菜单——当鼠标位于某个对象上，单击鼠标右键，可打开有关对象的快捷菜单； （4）剪贴板：复制（Ctrl －C ）、粘贴（Ctrl －V ）、剪切（Ctrl －X ） 复制屏幕图像：可将当前屏幕图形以BMP 格式传送到剪贴板…… （5）其它：查找、运行、切换Windows 、进入DOS 环境、文件夹选项 输入法切换，中、英文切换，半角/全角切换 软键盘：是在屏幕上显示的一个键盘图形，用户可用鼠标点击其中某个键以替代实际的按键； ·各种文件的后缀名： com 、exe 、sys 、tmp 、zip 、…… doc 、xls 、txt 、htm 、…… bmp 、gif 、jpg 、psd 、…… wav 、avi 、mp3、swf…… （三）DOS （DiskOperatingSystem ）操作系统 由美国Microsoft 公司发行的DOS 称为MS －DOS ，主要由IO.sys 、MSDOS.sys 、COMMAND.sys 三个基本文件和几十个内、外部命令文件组成。 *主要命令：
§5网络 *什么是计算机网络 1.基本概念： 计算机网络是指将不同地理位置且各自具备独立功能的计算机，通过传输介质互相连接起来，按照一定的网络协议相互通讯，并能够实现资源（软件、硬件）共享。如图1-13所示。 图1-1 计算机网络 计算机网络是计算机技术与通信技术紧密结合而形成的一门交叉学科。计算机网络的应用与发展已经成为当今发展最为快速的一个领域。计算机网络的通信范围已覆盖全球，成为重要的信息基础之一。广泛地应用于军事、教育、科研、信息服务、金融、电子商务等各个方面。目前，世界上许多国家都在加紧建设和提高信息基础设施，人们通俗地称之为信息高速公路。 计算机网络是现代通信技术与计算机技术相结合的产物。 ＊网络的发展 计算机网络的发展过程大致可以分为三个阶段： ＊计算机网络的主要功能 计算机网络的主要功能有四个方面，最基本功能资源共享和实现数据通信。 （1）资源共享 资源共享是人们建立计算机网络的主要目的之一。计算机资源包括有硬件资源、软件资源和
数据资源。硬件资源的共享可以提高设备的利用率，避免设备的重复投资。如利用计算机网络建立网络打印机。软件资源和数据资源的共享可以充分利用已有的信息资源，减少软件开发过程中的劳动，避免大型数据库的重复设置。 （2）数据通讯 数据通讯是指利用计算机网络实现不同地理位置的计算机之间的数据传送。如人们通过电子邮件（E-Mail ）发送和接收信息，使用IP 电话进行相互交谈等。 （3）均衡负荷与分布处理 是指当计算机网络中的某个计算机系统负荷过重时，可以将其处理的任务传送到网络中的其它计算机系统中，以提高整个系统的利用率。对于大型的综合性的科学计算和信息处理，通过适当的算法，将任务分散到网络中不同的计算机系统上进行分布式的处理。如通过国际互联网中的计算机分析地球以外空间的声音等。 （4）综合信息服务 在当今的信息化社会中，各行各业每时每刻都要产生大量的信息需要及时的处理，而计算机网络在其中起着十分重要的作用。 ＊计算机网络的应用 计算机网络在资源共享和信息交换方面所具有的功能，是其它系统所不能替代的。计算机网络所具有的高可靠性、高性能价格比和易扩充性等优点，使得它在工业、农业、交通运输、邮电通信、文化教育、商业、国防以及科学研究等各个领域、各个行业获得了越来越广泛的应用。我国有关部门也已制订了"金桥"、"金关"和"金卡"三大工程，以及其它的一些金字号工程，这些工程都是以计算机网络为基础设施，为促使国民经济早日实现信息化的主干工程，也是计算机网络的具体应用。计算机网络的应用范围实在太广泛，本节仅能涉及一些带有普遍意义和典型意义的应用领域。 （1）办公自动化OA （OfficeAutomation ） 办公自动化系统，按计算机系统结构来看是一个计算机网络，每个办公室相当于一个工作站。它集计算机技术、数据库、局域网、远距离通信技术以及人工智能、声音、图像、文字处理技术等综合应用技术之大成，是一种全新的信息处理方式。办公自动化系统的核心是通信，其所提供的通信手段主要为数据/声音综合服务、可视会议服务和电子邮件服务。
（2）电子数据交换EDI 电子数据交换，是将贸易、运输、保险、海关等行业信息用一种国际公认的标准格式，通过计算机网络通信，实现各企业之间的数据交换，并完成以贸易为中心的业务全过程。EDI 在发达国家应用已很广泛，我国的"金关"工程就是以EDI 作为通信平台的。 （3）远程交换（Telecommuting ）
远程交换是一种在线服务（OnlineServing ）系统，原指在工作人员与其办公室之间的计算机通信形式，按通俗的说法即为家庭办公。
一个公司内本部与子公司办公室之间也可通
过远程交换系统，实现分布式办公系统。远程交换的作用也不仅仅是工作场地的转移，它大大加强了企业的活力与快速反应能力。近年来各大企业的本部，纷纷采用一种被之为"虚拟办公室"（VirtualOffice ）的技术，创造出一种全新的商业环境与空间。远程交换技术的发展，对世界的整个经济运作规则产生了巨大的影响。 （4）远程教育（DistanceEducation ） 远程教育是一种利用在线服务系统，开展学历或非学历教育的全新的教学模式。远程教育几乎可以提供大学中所有的课程，学员们通过远程教育，同样可得到正规大学从学士到博士的所有学位。这种教育方式，对于已从事工作而仍想完成高学位的人士特别有吸引力。 远程教育的基础设施是电子大学网络EUN （ElectronicUniversityNetwork ）。EUN 的主要作用是向学员提供课程软件及主机系统的使用，支持学员完成在线课程，并负责行政管理、协作合同等。这里所指的软件除系统软件之外，包括CAI 课件，即计算机辅助教学（ComputerAidedInstruction ）软件。CAI 课件一般采用对话和引导式的方式指导学生学习发现学生错误还具有回溯功能，从本质上解决了学生学习中的困难。 （5）电子银行 电子银行也是一种在线服务系统，是一种由银行提供的基于计算机和计算机网络的新型金融服务系统。电子银行的功能包括：金融交易卡服务、自动存取款作业、销售点自动转帐服务、电子汇款与清算等，其核心为金融交易卡服务。金
融交易卡的诞生，标志了人类交换方式从物物交换、货币交换到信息交换的又一次飞跃。 围绕金融交易卡服务，产生了自动存取款服务，自动取款机（CD ）及自动存取款机（ATM ）也应运而生。自动取款机与自动存取款机大多采用联网方式工作，现已由原来的一行联网发展到多行联网，形成覆盖整个城市、地区，甚至全国的网络，全球性国际金融网络也正在建设之中。 电子汇款与清算系统可以提供客户转帐、银行转帐、外币兑换、托收、押汇信用证、行间证券交易、市场查证、借贷通知书、财务报表、资产负债表、资金调拨及清算处理等金融通信服务。由于大型零售商店等消费场所采用了终端收款机（POS ），从而使商场内部的资金即时清算成为现实。销售点的电子资金转帐是POS 与银行计算机系统联网而成的。 当前电子银行服务又出现了智能卡（IC ）。IC 卡内装有微处理器、存储器及输入输出接口，实际上是一台不带电源的微型电子计算机。由于采用IC 卡，持卡人的安全性和方便性大大提高了， （6）电子公告板系统BBS （BulletinBoardSystem ） 电子公告板是一种发布并交换信息的在线服务系统。BBS 可以使更多的用户通过电话线以简单的终端形式实现互联，从而得到廉价的丰富信息，并为其会员提供网上交谈、发布消息、讨论问题、传送文件、学习交流和游戏等的机会和空间。 （7）证券及期货交易 证券及期货交易是由于其获利巨大、风险巨大，且行情变化迅速，投资者对信息的依赖格外显得重要。金融业通过在线服务计算机网络提供证券市场分析、预测、金融管理、投资计划等需要大量计算工作的服务，提供在线股票经纪人服务和在线数据库服务（包括最新股价数据库、历史股价数据库、股指数据库以及有关新闻、文章、股评等）。 （8）广播分组交换 广播分组交换实际上是由一种无线广播与在线系统结合的特殊服务，该系统使用户在任何地点都可使用在线服务系统。广播分组交换可提供电子邮件、新闻、文件等传送服务，无线广播与在线系统通过调制解调器，再通过电话局可以结合在一起。移动式电话也属于广播系统。 （9）校园网（CampusNetwork ） 校园网是在大学校园区内用以完成大中型计算机资源及其它网内资源共享的通信网络。一些发达国家已将校园网确定为信息高速公路的主要分支。无论在国内还是国外，校园网的存在与否，是衡量该院校学术水平与管理水平的重要标志，也是提高学校教学、科研水平不可或缺的重要支撑环节。 共享资源是校园网最基本的应用，人们通过网络更有效地共享各种软、硬件及信息资源，为众多的科研人员提供一种崭新的合作环境。校园网可以提供异型机联网的公共计算环境、海量的用户文件存储空间、昂贵的打印输出设备、能方便获取的图文并茂的电子图书信息，以及为各级行政人员服务的行政信息管理系统和为一般用户服务的电子邮件系统。 （10）信息高速公路 如同现代信息高速公路的结构一样，信息高速公司也分为主干、分支及树叶。图像、声音、文字转化为数字信号在光纤主干线上传送，由交换技术再送到电话线或电缆分支线上，最终送到具体的用户"树叶"。主干部分由光纤及其附属设备组成，是信息高速公路的骨架。 我国政府也十分重视信息化事业，为了促进国家经济信息化，提出个"金桥"工程--国家公用经济信息网工程、"金关"工程--外贸专用网工程、"金卡"工程--电子货币工程。这些工程是规模宏大的系统工程，其中的"金桥工程"是国民经济的基础设施，也是其它"金"字系列工程的基础。 "金桥"工程包含信息源、信息通道和信息处理三个组成部分，通过卫星网与地面光纤网开发，并利用国家及各部委、大中型企业的信息资源为经济建设服务。"金卡"工程是在金桥网上运行的重要业务系统之一，主要包括电子银行及信用卡等内容。"金卡"工程又称为无纸化贸易工程，其主要实现手段为EDI ，它以网络通信和计算机管理系统为支撑，以标准化的电子数据交换替代了传统的纸面贸易文件和单证。其它的一些"金"字系列工程，如"金税"工程、"金智"工程、"金盾"工程等亦在筹划与运作之中。这些重大信息工程的全面实施，在国内外引起了强烈反响，开创了我国信息化建设事业的新纪元。 （11）企业网络 集散系统和计算机集成制造系统是两种典型的企业网络系统。 集散系统实质上是一种分散型自动化系统，又称做以微处理机为基础的分散综合自动化系统。集散系统具有分散监控和集中综合管理两方面的特征，而更将"集"字放在首位，更注重于全系统信息的综合管理。80年代以来，集散系统逐渐取代常规仪表，成为工业自动化的主流。工业自动化不仅体现在工业现场，也体现在企业事务行政管理上。集散系统的发展及工业自动化的需求，导致了一个更庞大、更完善的计算机集成制造系统CIMS 的诞生。 集散系统一般分为三级：过程级、监控级和管理信息级。集散系统是将分散于现场的以微机为基础的过程监测单元、过程控制单元、图文操作站及主机（上位机）集成在一起的系统。它采用了局域网技术，将多个过程监控、操作站和上位机互连在一起，使通信功能增强，信息传输速度加快，吞吐量加大，为信息的综合管理提供了基础。因为CIMS 具有提高生产率、缩短生产周期等一系列极具吸引力的优点，所以已经成为未来工厂自动化的方向。 （12）智能大厦和结构化综合布线系统 智能大厦（IntelligentBuilding ）是近十年来新兴的高技术建筑形式，它集计算机技术、通信技术、人类工程学、楼宇控制、楼宇设施管理为一体，使大楼具有高度的适应性（柔性），以适应各种不同环境与不同客户的需要。智能大厦是以信息技术为主要支撑的，这也是其具有"智能"之名称的由来。有人认为具有三A 的大厦，可视为智能大厦。所谓三A 就是CA （通信自动化）、OA （办公自动化）和BA （楼宇自动化）。概括起来，可以认为智能大厦除有传统大厦功能之外，主要必须具备下列基本构成要素：高舒适的工程环境、高效率的管理信息系统和办公自动化系统、先进的计算机网络和远距离通信网络及楼宇自动化。 智能大厦及计算机网络的信息基础设施是结构化综合布线系统SCS （StructureCablingSystem ）。在建设计算机网络系统时，布线系统是整个计算机网络系统设计中不可分割的一部分，它关系到日后网络的性能、投资效益、实际使用效果以及日常维护工作。结构化布线系统是指在一个楼宇或楼群中的通信传输网络能连接所有的话音、数字设备，并将它们与交换系统相连，构成一个统一、开放的结构化布线系统。在综合布线系统中，设备的增减、工位的变动，仅需通过跳线简单插拔即可，而不必变动布线本身，大大方便了管理、使用和维护。 ＊网络的分类
按照网络的类型特征，对网络进行分类是了解网络、学习网络技术的重要基础之一。从不同的角度对网络分类则有不同的分类方法。常见的分类方法有以下几种：
1．按分布地理范围分类
按分布地理范围分类，计算机网络可以分为广域网、局域网和城域网三种。
广域网（WideAreaNetwork ，简称WAN ）又称远程网，其分布范围可达数百公里乃至更远，可以覆盖一个地区，一个国家，更至全世界。 局域网（LocalAreaNetwork ，简称LAN ）是将小区域内的计算机及各种通信设备互连在一起的网络，其分布范围局限在一个办公室、一个建筑
物或一个企业内。
城域网（MetropolitanAreaNetwork ，简称MAN ）的分布范围介于局域网与广域网之间，其目的是在一个较大的地理区域内提供数据、声音和图像的传输。
2．按交换方式分类
按网络的交换方式分类，计算机网络可以分
为电路交换网，报文交换网和分组交换网三种。 电路交换（CircuitSwitching ）方式类似于传统的电话交换方式，用户在开始通信之前，必须申请建立一条从发送端到接收端的物理通道，并且在双方通信期间始终占用该信道。
报文交换（MessageSwitching ）方式的数据单元是要发送一个完整报文，其长度不受限制。报文交换采用存储转发原理，这点像古代的邮政通信，邮件由途中的驿站逐个存储转发一样。每
个报文中含有目的地址，每个用户节点要为途径的报文选择适当的路径，使其能最终达到目的端。 分组交换（PacketSwitching ）方式也称包交换方式，1969年首次在ARPANET 上使用，现在人们都公认ARPANET 是分组交换网之父，并将分组交换网的出现作为计算机网络新时代的开始。采用分组交换方式通信前，发送端先将数据划分为
一个个等长的单位（即分组），这些分组逐个由各中间节点采用存储转发方式进行传输，最终达到目的端。由于分组长度有限，可以在中间节点机的内存中进行存储处理，其转发速度可大大提高。 3．按拓扑结构分类 按拓扑结构分类，计算机网络可分为星形网、总线网、环形网、树型网和网形网。 星形网是最早采用的拓扑结构形式，其每个站点都通过连接电缆与主控机相联，相关站点之间的通信都由主控机进行，所以要求主控机有很高的可靠性，这种结构是一种集中控制方式。 环形网中各工作站依次相互连接组成一个闭合的环形，信息可以沿着环形线路单向（或双向）传输，由目的站点接收。环形网适合那些数据不需要在中心主控机上集中处理而主要在各站点进行处理的情况。 总线结构网中各个工作站通过一条总线连接，信息可以沿着两个不同的方向由一个站点传向另一个站点，是目前局域网中普遍采用的一种网络拓扑结构情形。 除了以上分类方法以外，还可按所采用的传输媒体分为双绞线网，同轴电缆网、光纤网、无线网；按信道的带宽分为窄带网和宽带网；按不同用户分为科研网、教育网、商业网和企业网等。 ＊计算机网络的拓扑结构和传输媒体 1．网络的拓扑结构 "拓扑"这个名词是从几何学中借用来的。网络拓扑是指网络形状，或者是它在物理上的连通性。下面介绍几种最为主要的网络拓扑结构。 （1）星形拓扑 星形拓扑是由中央节点和通过点到点通信链路接到中央节点的各个站点组成，如图7.5所示。中央节点执行集中工通信控制策略，因此中央节点相当复杂，而各个站点的通信处理负担都很小。星形网采用的交换方式有电路交换和报文交换，尤以电路交换方式更为普遍。这种结构一旦建立通道连接，就可以无延迟地在连通的两个站点之间传送数据。目前流行的专用交换机PBX （PrivateBrancheXchange ）就是星形拓扑结构的典型实例。
星形拓扑结构有以下优点： ①控制简单。在星形网络中，任何一个站点只和中央节点相连接，因而媒体访问控制方法很简单，致使访问协议也十分简单。 ②故障诊断和隔离容易。在星形网络中，中央节点对网络连接线路可以逐一地隔离开来进行故障检测和定位，单个连节点的故障只影响一个设备，不会影响整个网络。
③方便服务。中央节点可方便地对各个站点提供服务和网络重新配置。
星形拓扑结构的缺点
①电缆长度和安装工作量相当可观。因为每个站点都要和中央节点直接连接，需要耗费大量的电缆、安装、维护的工作量也剧增。 ②中央节点的负担较重，易形成瓶颈。一旦发生故障，则全网受影响，因而对中央节点的可靠性和冗余度方面的要求很高。 ③各站点的分布处理能力较低。
星形拓扑结构广泛应用于网络智能集中于某个中央站点的场合。从目前的趋势看，计算机的发展已从集中的主机系统发展到大量功能很强的微型机和工作站，在这种形势下，传统的星形拓扑使用会有所减少。 （2）总线拓扑
总线拓扑结构采用一个信道作为传输媒体，所有站点都通过相应的硬件接口直接连到这一公共传输媒体上，该公共传输媒体即称为总线。任何一个站发送的信号都沿着传输媒体传播，而且能被所有的其它站点所接收。总线拓扑结构见图7.6所示。
因为所有站点共享一条公用的通信信道，所
以一次只能有一个设备传输信号。通常采用分布
式控制策略来确定哪个站点可以发送。发送时，发送站将报文分成分组，然后逐个依次发送这些分组，有时还要与其它站来的分组交替地在传输媒体上传输。当分组经过各站时，其中的目的站会识别到分组所携带的目的地址，然后复制下这些分组的内容。
总线拓扑结构的优点： ①总线结构所需要的电缆数量少。 ②总线结构简单，又无源工作，有较高的可靠性。
③易于扩充，增加和减少用户比较方便。
总线拓扑结构的缺点： ①总线传输距离有限，通信范围受限制。 ②故障诊断和隔离比较困难。 ③分布式协议不能保证信息的及时传输。 ④不具有实时功能，站点必须是智能的，要有媒体访问控制功能，从而增加了站点的硬件和软件开销。 （3）环形拓扑 环形拓扑网络由站点和连接站点的链路组成一个闭合环，如图7.7所示，每个站点能够接收从一链路传来的数据，并以同样的速率串行地把该数据沿环送到另一链路上。这种链路可以是单向的，也可以是双向的。数据以分组形式发送，如果环上A 站希望发送一个报文到C 站，就先要把报文分成若干个分组，每个分组除了数据还要加上某些控制信息，其中包括C 站的地址。A 站依次把每个分组送到环上，开始沿环传输，C 站识别到带有它自己地址的分组时，便将其中的数据复制下来。由于多个设备连接在一个环上，因此需要用分布式控制策略来进行控制。
环形拓扑结构的优点：
①电缆的长度短。环形拓扑结构的网络所需的电缆长度和总线拓扑网络相似，但比起星形拓扑结构的网络要短得多。
②减少或增加工作站时，仅需简单的连接操作。
③可使用光纤。光纤的传输速度率很高，十分适合于环形拓扑的单向传输。
环形拓扑结构的缺点：
①节点故障会引起全网络的故障。这是因为环上的数据传输要通过接在环上的每一个节点，一旦环中某个节点发生故障就会引起全网络的故障。 ②故障检测困难。这与总线拓扑结构相似，因为不是集中控制，故障检测需要在网上各个节点进
行，因此故障检测就较为困难。
③环形拓扑结构的媒体访问控制协议都采用令牌
传送的方式，在负载很轻时，信道利用率相对来说比较低。 总的来说，不管局域网或广域网，网络的拓扑选择，需要考虑诸多因素，网络要既利于安装，
又有利于扩展，网络的可靠性也是要考虑的重要
因素，以外网络拓扑结构的选择还会影响传输媒体的选择和媒体访问控制方法的确定。 2．传输媒体
传输媒体是通信网中发送方和接收方之间的
物理通路，计算机网络中采用的传输媒体可以分为有线和无线两大类。双绞线、同轴电缆和光纤
是常用的三种有线传输媒体，无线电通信、微波通信、红外线通信以及激光通信的信息载体都属于无线传输媒体。
传输媒体的特性对网络数据通信质量有很大的影
响，这些特性是：
①物理特性，说明传输媒体的特征。
②传输特征，包括信号形式、调制技术、传输速度及频带宽度等内容。 ③连通性，采用点到点连接还是多点连接。 ④地域范围，网上各点间的最大距离。 ⑤抗干扰性，防止噪声、电磁干扰对数据传输影响的能力。
⑥相对价格，以元件、安装和维护的价格为基础。 以下分别介绍其中最为常用的传输媒体的特性。 （1）双绞线 由螺旋状扭在一起的两根绝缘导线组成，线对扭在一起可以减少相互间的辐射电磁干扰。双
绞线是最常用的传输媒体，早就用于电话通信中的模拟信号传输，也可用于数字信号的传输。双绞线一般是铜质的，能提供良好的传导率。双绞线既可用于传输模拟信号，也可用于传输数字信号。对于模拟信号来说，大约每5-6km 需要一个放大器；对于数字信号来说，每2-3km 使用一个中继器。 双绞线也可用于局域网，如10BASE-T 和100BASE-T 总线，可分别提供10Mbit/s 和100Mbit/s 的数据传输速率。通常将多对双绞线封装于一个绝缘套里组成双绞线电缆，局域网中常用的3类双绞线和5类双绞线，均由4对双绞线组成，其中3类双绞线常用于10BASE-T 总线局域网，5类双绞线常用于100BASE-T 总线局域网。 双绞线普遍话用于点到点的连接，双绞线可以很容易地在15km 或更大范围内提供数据传输。局域网的双绞线主要用于一个建筑物或几个建筑物间的通信，但在10Mbit/s 和100Mbit/s 传输速率的10BASE-T 和100BASE-T 的总线传输距离都不超过100m 。 双绞线的抗干扰性能不如同轴电缆，但价格比同轴电缆要便宜。 （2）同轴电缆 同轴电缆也像双绞线一样由一对导体组成，但它们是按"同轴"的形式构成线对，其最里层是内芯，向外依次为绝缘层、屏蔽层，最外则是起保护作用的塑料外套，内芯和屏蔽层构成一对导体。 同轴电缆分为基带同轴电缆和宽带同轴电缆。基带同轴电缆又可以分为粗缆和细缆两种，都用于直接传送数字信号；宽带同轴电缆用于频分多路复用的模拟信号传输，也可用于不使用频分多路复用的高速数据通信和模拟信号的传输，闭路电视所使用的CATV 电缆就是宽带同轴电缆。 同轴电缆适用于点到点连接和多点连接，基带电缆每段可支持几百台设备，在大系统中还可以用转接器将各段连接起来；宽带同轴电缆可支持数千台设备，但在高数据传输速率（50Mbit/s ）下使用宽带电缆时，设备数目限制在20-30台。 同轴电缆的传输距离取决于传输信号的形式和传输的速率，典型基带电缆的电大距离限制在几公里。在相同速率条件下，粗缆传输距离较细缆长。 同轴电缆的抗干扰性能比双绞线好，但在价格上较双绞线贵，但比光纤要便宜。 （3）光纤 光纤是光纤纤维的简称，它由能传导光波的石英玻璃纤维外加保护层构成。相对于金属导线来说具有重量轻、线径细的特点。用光纤传输信号时，在发送端先要将电信号转换成光信号，而在接收端要由光检测器还原成电信号。 光纤在计算机网络中普遍采用点到点连接，从地域范围来看可以在6-8km 的距离内不用中继器传输，因此光纤适合于在几个建筑物之间通过点到点的链路连接局域网。由于光纤具有不受电磁干扰和噪音影响的独有特征，适宜在长距离内保持高速数据传输率，而且能提供很好的安全性。 网络除了有线媒体以外，还可通过无线传输媒体进行无线传输，目前常用技术有无线电波、微波、红外线和激光。随着便携式计算机的出现和普及，以及在军事、野外等特殊场合下移动产品的通信联网需要，促进了无线通信网络的发展，出现了无线网络产品。 ＊计算机网络的协议及其作用 两个计算机间通信时对传输信息内容的理解、信息表示形式以及各种情况下的应答信号都必需进行一个共同的约定，我们称为协议（Protocol ）。一般来说，协议要由如下三个要素组成： （1）语义（Semantics ）。涉及用于协调和差错处理的控制信息。 （2）语法（Syntax ）。涉及数据及控制信息的格式、编码及信号电平等。 （3）定时（Timing ）。涉及速度匹配和排序等。 协议本质上无非是一种网上交流的约定，由于联网的计算机类型可以各不相同，各自使用的操作系统和应用软件也不尽相同，为了保持彼此之间实现信息交换和资源共享，它们必须具有共同的语言，交流什么、怎样交流及何时交流，都必须遵行某种互相都能够接受的规则。 目前，全球最大的网络是因特网（Internet ），它所采用的网络协议是TCP/IP 协议。它是因特网的核心技术。TCP/IP 协议，具体的说就是传输控制协议（TransmissionControlProtocol ，即TCP ）和网际协议（InternetProtocol ，即IP ）。其中TCP 协议用于负责网上信息的正确传输，而IP 协议则是负责将信息从一处传输到另一处。 TCP/IP 协议本质上是一种采用分组交换技术的协议。其基本思想是把信息分割成一个个不超过一定大小的信息包来传送。目的是：一方面可以避免单个用户长时间地占用网络线路；另一方面，可以在传输出错时不必重新传送全部信息，只需重传出错的信息包就行了。 TCP/IP 协议组织信息传输的方式是一种4层的协
模型中，最底层为TCP/IP 的实现基础，主要用于访问具体局域网，如以大网等。中间两层为TCP/IP 协议，其中的UDP 为一种建立在IP 协议基础上的用户数据协议（UserDatagramProtocol ，即UDP ）。最上层为建立在TCP/IP 协议基础上的一些服务：TELNET （远程登录），允许某个用户登录到网上的其它计算机上（要求用户必须拥有该机帐号），然后像使用自己的计算机一样使用远端计算机：FTP （FileTransferProtocol ，文件传输协议），允许用户在网上计算机之间传送程序或文件；SMTP
（SimpleMessageTransferProtocol ，简单邮件传送协议），允许网上计算机之间互通信函；DNS （DomainNameService ，域名服务协议），用于将域名地址转换成IP 地址等。
*因特网（Internet ）及其应用 ? 因特网概述
因特网（Internet ）是一个建立在网络互连基础上的最大的、开放的全球性网络。因特网拥有数千万台计算机和上亿个用户，是全球信息资源的超大型集合体。所有采用TCP/IP 协议的计算机都可以加入因特网，实现信息共享和互相通信。与传统的书籍、报刊、广播、电视等传播媒体相比，因特网使用更方便，查阅更快捷，内容更丰富。今天，因特网已在世界范围内得到了广泛的普及与应用，并正在迅速地改变人们的工作方式和生活方式。 因特网起源于20世纪60年代中期由美国国防部高级研究计划局（ARPA ）资助的ARPANET ，此后提出的TCP/IP 协议为因特网的发展奠定了基础。1986年美国国家科学基金会（NSF ）的NSFNET 加入了因特网主干网，由此推动了因特网的发展。但是，因特网的真正飞跃发展应该归功于20世纪90年代的商业化应用。此后，世界各地无数的企业和个人纷纷加入，终于发展演变成今天成熟的因特网。
我国正式接入因特网是在1994年4月，当时为了发展国际科研合作的需要，中国科学院高能物理研究所和北京化工大学开通了到美国的因特网专线，并有千余科技界人士使用了因特网。此后，科学院网络中心的中国科学技术网（CSTNET ）、教育部的中国教育科研网（CERNET ）和邮电部的中国公用信息网（CHINANET ）也都分别开通了到美国的因特网专线，并与原电子工业部的中国金桥信息网（CHINAGBN ）并称为四大骨干网。其中，邮电部建设的CHINANET 能提供全部的因特网服务，并面向全社会提供因特网的接入服务。由此，因特网的应用终于在我国蓬勃发展起来。 ? 域名和网址
1．网址
所谓网址是指接入因特网的计算机被分配的网络地址，有时又被人们叫做IP 地址。因特网上的计算机就是根据其IP 地址来互相识别和互相通信的，正好比是电话系统每门电话电话号码一样。 IP 地址由32位（即4个字节）二进制数组成，为了书写方便起见，常将每个字节作为一段并以十进制数来表示，每段间用"."分隔。例如，"202.96.209.5"就是一个合法的IP 地址。 IP 地址由网络标识和主机标识两部分组成。 2．域名 32位二进制数IP 地址对计算机来说是十分有效的，但记忆一组并无意义的且无任何特征的UP 地址是困难的，为此，因特网引进了字符形式的IP 地址，即域名。域名采用层次结构的基于"域"的命名方案，每一层由一个子域名组成，子域名间用"."分隔，其格为：
机器名 网络名 机构名 最高域名 因特网上的域名由域名系统
（DomainNameSystem ，简称DNS ）统一管理。DNS 是一个分布式数据库系统，由域名空间、域名服
务器和地址转换请求程序三部分组成。有了NDS ，凡域名空间中有定义的域名都可以有效地转换为对应的IP 地址，同样，IP 地址也可通过DNS 转换成域名。 在因特网上，域名和IP 地址一样都是唯一的。 通常，最高域名可以是国名（或地区名）或领域名。国家名（或地区名）有如：CN 代表中国、JP 代表日本、UK 代表英国、HK 代表中国香港地区、TW 代表中国台湾地z 区；领域名有如：GOV 代表政府机构、COM 代表商业机构、EDU 代表教育机构、AC 代表科研机构等。另外，由于因特网起源于美国，所以美国的域名没有国家部分。 以WWW 服务器为例，我们列举几个域名： 美国微软公司：https://www.wendangku.net/doc/7a15868652.html, 中国清华大学：https://www.wendangku.net/doc/7a15868652.html, 中国科学院：https://www.wendangku.net/doc/7a15868652.html, ? 因特网的接入方式 要使用因特网，首先必须接入因特网。接入因特网的方式有很多，从大的方面来说，可以分成两大类，即专用线路接入方式和用电话线拨号方式。 1．专用线路接入方式 所谓专用线路接入方式就是指用户使用专用的高速线路将自己的内部网或局域网永久性地接入因特网。在因特网和内部网或局域网的接口处一般需要配备专用的网络接入设备，如路由器等。 这种方式接入因特网是最为快捷和可靠的连接方式。但是，这种方式投资成本大，使用费用高，有的还要有专业人员专门维护，一般适合于一定规模的单位和机构使用。 2．电话线拨号方式 这种入网方式费用低廉，适合于传输信息量较小的个人或小团体用户，也是目前个人上网最为普遍的一种方式。 分类 采用电话拨号上网，又可以细分为如下两种方式： 1）仿真终端方式（TENNET ） 这种方式上网时，通过拨号建立连接后，用相应的仿真软件，就能像真正的终端一样实现与因特网服务提供者（InternetServiceProvider ，简称ISP ）的主机连接。用这种方式上网，用户计算机和因特网的连接其实是一种间接的方式，用户没有IP 的连接性，没有IP 地址，无法运行高级接口软件，传给用户的各类文件和电子邮件均存放在ISP 的主机上，影响了上网速度和时间。 2）PPP/SLIP 方式 PPP （PointtoPointProtocol ，即点一点协议）和SLIP （SerialLineIP ，即串行网间协议）是在串行链路（如电话线）上实现TCP/IP 连接的两上通信协议。采用这种方式上网，用户有独立的IP 地址，用户可以使用自己的环境和用户界面（如Windows 、Unix 、Macintosh 等）进行联网操作，各类文件和电子邮件均可直接传送到用户计算机上。目前，大多数的个人用户采用这种上网方式。由于用户计算机要运行大量的接口软件，所以要求用户计算机的配置相对较高。 但采用这种方式上网时，虽然用户有自己的IP 地址，但是IP 地址不是固定的，它是由用户拨入建立连接时由ISP 的主机动态分配给用户的。 ? 因特网提供的服务 1．万维网（WWW ） 万维网（WorldWideWeb ，简称WWW ）是瑞士日内瓦欧洲粒子实验室最先开发的一个分布式超媒体信息查询系统，目前它是因特网上最为先进、交互性能最好、应用最为广泛的信息检索工具，万维网包括各种各样的信息，如：文本、声音、图像、视频等。万维网采用了"超文本"的技术，使得用户以通用而简单的办法就可获得因特网上的各种信息。 2．电子邮件（E-mail ） 电子邮件（Electronicmail ，简写为E-mail ）是因特网上使用最广泛的一种服务。用户只要能与因特网连接，具有能收发电子邮件程序及个人的电子邮件地址，就可以与因特网上具有电子邮件地址的所有用户方便、快捷、经济地交换电子邮件。电子邮件可以在两个用户间交换，也可以向多个用户发送同一封邮件，或将收到的邮件转发给其它用户。电子邮件中除文本外，还可包含声音、图像、应用程序等各类计算机文件。此外，用户还可以以邮件方式在网上订阅电子杂志、获取所需文件、参与有关的公告和讨论组等。 3．文本传输协议（FTP ） 文本传输协议（FileTransferProtocol ，简称FTP ）是因特网上文件传输的基础，通常所说的FTP 是基于该协议的一种服务。FTP 文本传输服务允许因特网上的用户将一台计算机上的文件传输到另一台上，几乎所有类型的文件，包括文本文件、二进制可执行文件、声音文件、图像文件、数据压缩文件等，都可以用FTP 传送。 FTP 实际上是一套文件服务软件，它以文件传输为界面，使用简单的get 和put 命令就可以进行文件的下载和上传，如同在因特网上执行文件复制命令一样。大多数FTP 服务器主机都采用UNIX 操作系统，但普通用户通过Windows98和WindowsXP 也能方便地使用FTP 和UNIX 主机进行文件的传输。 FTP 最大的特点是用户可以使用因特网上众多的匿名FTP 服务器。所谓匿名服务器，指的是不需要专门的用户名和口令就可以进入的系统。用户连接匿名服务器时，都可以用"Anonymous"（匿名）作为用户名、以自己的电子邮件地址作为口令登录。登录成功后，用户便可从匿名服务器上下载文件。匿名服务器的标准目录为pub ，用户通常可以访问该目录下所有子目录中的文件。考虑到安全问题，大多数匿名服务器不允许用户上传文件。 4．远程登录（Telnet ） Telnet 是远程登录服务的一个协议，该协议定义远程登录用户与服务器交互的方式。允许用户在一台联网的计算机登录到一个远程分时系统时，然后像使用自己的计算机一样使用该远程系统。 要使用远程登录服务，必须在本地计算机上启动一个客户应用程序，指定远程计算机的名字，并通过因特网与之建立连接。一旦连接成功，本地计算机就像通常的终端一样，直接访问远程计算机系统的资源。远程登软件允许用户直接与远程计算机交互，通过键盘或鼠标操作，客户应用程序将有关的信息发送给远程计算机，再由远程计算机将输出结果返回给用户。用户退出远程登录后，用户的键盘、显示控制权又回到本地计算机。一般用户可通过WindowsXP 的Telnet 客房程序进行远程登录。 5．专题讨论（Usenet ） Usenet 是一个有众多趣味相投的用户共同组织起来的各种专题讨论组的集合。通常也将之称为全球性的电子公告板系统（BBS ）。Usenet 用于发布公告、新闻、评论及各种文章供网上用户使用和讨论。讨论内容按不同的专题分类组织，每一类为一个专题组，称为新闻组，其内部还可以分出更多的子专题。 Usenet 的每个新闻组都由一个区分类型的标记引导，每新闻组围绕一个主题，如comp.（计算机方面的内容）、news.（Usenet 本身的新闻与消息）、rec.（体育、艺术及娱乐活动）、sci.（科学技术）、soc.（社会问题）、talk.（讨论交流）、misc.（其它杂项话题）、biz.（商业问题）等。 用户除了可以选择参加感兴趣的专题小组外，也可以自己开设新的专题组。只要有人参加该专题组就可以一直存在下去；若一段时间无人参加，则这个专题组会被自动删除。
6．Internet 闲谈
Internet 闲谈就是我们熟悉的IRC ，即
InternetRelayChat 。如果说电子邮件、网络新闻是因特网上的存储转发的通信业务，即可以使接收者在适当的时候看到的话，那么，IRC 就是因特网上的一个实时通信业务，它可以使接收者和发
送者都处于联机状态，使他们直接在因特网上进行交谈。可以利用这种方式召开网上会议，使网络上的相关用户可以直接实时地就某些问题进行讨论，并提出解决方案。目前国内较著名的中文
聊天软件有藤讯公司的OICQ 等。
*浏览网页的相关概念
1．WWW 与HTML
万维网（WorldWideWeb ，简称WWW ）是因特网上集文本、声音、图像、视频等多媒体信息于一身的全球信息资源网络，是因特网上的重要组成部分。浏览器（Browser ）是用户通向WWW 的桥梁和获取WWW 信息的窗口，通过浏览器，用户可以在浩瀚的因特网海洋中漫游，搜索和浏览自己感
兴趣的所有信息。
WWW 的网页文件是用超文本标记语言HTML
（HyperTextMarkupLanguage ）编写，并在超文本传输协议HTTP
（HyperTextTransmissionProtocol ）支持下运行的。超文本中不仅含有文本信息，还包括图形、声音、图像、视频等多媒体信息（故超文本又称
超媒体（，更重要的是超文本中隐含着指向其它超文本的链接，这种链接称为超链（HyperLinks ）。利用超文本，用户能轻松地从一个网页链接到其它相关内容的网页上，而不必关心这些网页分散在何处的主机中。
HTML 并不是一种一般意义上的程序设计语言，它将专用的标记嵌入文档中，对一段文本的语义进
行描述，经解释后产生多媒体效果，并可提供文本间的超链。 2．URL 简单讲，URL ，统一资源定位器）就是因特网上的资源地址。每个Web 页面，包括主页都有一个唯一的地址，其格式为： 协议名：//IP 地址或域名 协议名表示所提供的服务，如https://www.wendangku.net/doc/7a15868652.html, （上海热线）就是我们常用的万维网服务的URL 地址。ftp://https://www.wendangku.net/doc/7a15868652.html, 就是因特网上文件传输服务的URL 地址。 3．浏览器 WWW 浏览器是一个客户端的程序，主要功能是使用户获取因特网上的各种资源。常用浏览器有微软的IE 和Netscape 的Navigator/Communicator 。SUN 公司也开发了一个用Java 编写的浏览器HotJava 。Java 是一种新型的、独立于各种操作系统和平台的动态解释性语言，Java 使浏览器具有动画效果，为联机用户提供了实时交互功能。目前常用的浏览器均支持Java 。 *电子邮件的相关概念 1．电子邮件概述 电子邮件（Electronicmail ，简写为E-mail ）是因特网上使用最广泛的一种服务。电子邮件是以电子方式存放在计算机中，称为报文。计算机网络传送报文的方式与普通邮电系统传递信件的方式类似，采用的是存储转发方式。就如信件从源地到达目的地址要经过许多邮局转发一样。报文从源节点出发后，也要经过若干网络节点的接收和转发，最后到达目的节点，而且接收方收到电子报文阅读后，还可以以文件的方式保存下来，供今后查阅。由于报文是经过计算机网络传送的，其速度要比普通邮政快得多，收费也相对低廉，因而为人们提供了一种人际通信的良好手段。电子邮件报文中除了可包含文字信息外，还可以包含声音、图形和图像等多媒体形式的信息。 2．电子邮件使用的协议 邮件服务器使用的协议有简单邮件传输协议SMTP （SimpleMessageTransferProtocol ）、电子邮件扩弃协议MIME （MultipurposeInternetMailExtensions ）和POP 协议（PostOfficeProtocol ）。POP 服务需要一个邮件服务器来提供，用户必须在该邮件服务器上取得帐号才可使用这种服务。目前使用较普遍的POP 协议为第三版，故又称为POP3协议。 3．信箱地址及其格式 使用电子邮件系统的用户首先要有一个电子邮件信箱，该信箱在因特网上有唯一的地址，以便识别。电子邮件信箱和普通的邮政信箱一样也是私有，任何人可以将邮件投递到该信箱，但只有信箱的主人才能够阅读信箱中的邮件内容，或从中删除和复制邮件。 像传统信件的信封有格式要求一样，电子邮件也有规范的地址格式。电子邮件的信箱地址由字符串组成，该字符串被字符"@"分成两部分（字符"@"在英语中可以读作"at"），前一部分为用户标识，可以使用该用户在该计算机上的登录名或其它标识，只要能够区分该计算机上的不同用户即可，如"zhangshan"；后一部分用户信箱所在的计算机的域名，如https://www.wendangku.net/doc/7a15868652.html, （华东理工大学网络中心邮件服务器主机域名）。像zhangshan@https://www.wendangku.net/doc/7a15868652.html, 就是一个电子邮件地址 所以，电子邮件地址的一般格式为： 〈用户标识〉@〈主机域名〉。 4．电子邮件的格式 一封完整的电子邮件都有两个基本部分组成：信头和信体。 （1）信头一般有下面几个部分： 收信人：即收信人的电子邮件地址； 抄送：表示同时可以收到该邮件的其它人的电子邮件地址； 主题：是概括地描述该邮件内容。 （2）信体 信体是希望收件人看到的信件内容，有时信体还可以包含附件。附件是含在一封信件里的一个或多个计算机文件，附件可以从信件上分离出来，成为独立的计算机文件。 *计算机网络的安全 ? 影响网络安全的因素 影响计算机网络的因素很多，有些因素可能是有意的，也可能是无意的；可能是人为的，也可能是非人为的；归结起来，针对网络安全的威胁主要有如下几点。 1．人为的无意失误 如操作员安全配置不当造成的安全漏洞，用户安全意识不强，用户口令选择不慎，用户将自己的帐号随意转借他人或与别人共享等都会对网络安全带来威胁。 2．人为的恶意攻击 这是计算机网络所面临的最大威胁，主要有两个方面。 （1）来自黑客的攻击 目前，黑客在网上的攻击活动正以磕?0倍的速度增长，黑客的行动几乎涉及了所有的操作系统，黑客利用网上的任何漏洞和缺陷修改网页、非法进入主机、进入银行盗取和转移资金、窃取军事机密、发送假冒的电子邮件等，造成无法挽回的政治、经济和其它方面的损失。 （2）来自计算机病毒 计算机网络的出现和发展，也伴随着计算机网络病毒的出现。病毒可以按指数增长方式进行传染，其传播速度是非网络环境下的几十倍，一旦计算机网络染上病毒，远比一台单机染上病毒的危害性、破坏性大。总的来说，网络病毒较传统的单机病毒具有破坏性大、传播性强、扩散面广、针对性强、传染方式多、清除难度大等特点。 3．网络软件的漏洞和"后门" 网络软件不可能是百分之百的无缺陷和无漏洞的，然而，这些漏洞和缺陷恰恰是黑客进行攻击的首先目标，曾经出现过的黑客攻入网络内部的事件大部分就是因为安全措施不完善所招致的苦果。软件的"后门"则是软件公司的设计编程人员为了自便而设置的，一般不为外人所知，但一旦"后门"洞开，其造成后果将不堪设想。 另外，特洛伊木马程序（TrojanHorses ）的出现，也属于此类安全问题。"特洛伊木马"这个名称来源于古希腊的历史故事，其寓意是把有预谋的功能藏在公开的功能之中，掩盖其真实的企图。而"木马程序"泛指那些内容包含有为完成特殊任务而编制的代码的程序，而这些特殊的代码一般处于隐藏状态。一旦你的计算机被种上"木马程序"，你的计算机在接入因特网时，可能会被人秘密地完全控制。 ? 防范措施 1．加强教育，增强网络安全防范措施 加强教育、提高网络安全防范意识是解决安全问题的根本。要大力加强对国家有关网络信息法律法规和网络信息安全的讲解和宣传，加强对计算机网络管理人员、应用人员的职业道德教育，努力提高业务素质和工作责任感，加强对入网用户的教育和管理。计算机网络管理部门和机房应制定各种安全措施、管理规则、用户入网协议和
不定期的检查制度等。
进入网络的用户主要是获取有利于科技、教育等有用的信息，一旦发现了不良的信息，或误入了未授权的信息场所，则应自觉遵守有关规则，迅速采取措施，并及时向有关部门汇报。总之，只要人人都具有网络信息安全的意识和高度的责任感，加上利用防范设备以保证网络安全，那么网络的不安全因素和不良信息就会大大减少。 2．身份验证和访问控制策略
身份验证是向计算机系统证明自己的身份，如通过口令。身份验证主要包括验证依据、验证系统和安全要求。访问控制则规定何种主体对何种客体具有何种操作权力。访问控制是内部网安全理论的重要方面，主要包括人员限制、数据标识、权限控制、控制类型和风险分析。
身份验证和访问控制的主要任务是保证网络资源不被非法使用和非正常访问。它也是维护网络系统安全、保护网络资源的重要手段。各种安全策略必须相互配合才能真正起到保护作用，但
身份验证和访问控制可以说是保证网络安全最重要的核心策略之一。
3．防火墙控制
防火墙是近期发展起来的一种保护计算机网络安全的技术性措施，它是一个用以阻止网络中的黑客访问某个机构网络的屏障，也可称之为控制进/出两个方向通信的门槛。在网络边界上通过建立起来的相应网络通信监控系统来隔离内部和外部网络，以阻挡外部网络的侵入。
4．信息加密策略
信息加密的目的是保护网内的数据、文件、口令和控制信息，保护网上传输的数据。
信息加密过程是由形形色色的加密算法来个体实施，它以很小的代价提供很大的安全保护。在多数情况下，信息加密是保证信息机密性的唯
一方法。据不完全统计，到目前为止，已经公开发表的各种加密算法多达数百种。如果按照收发双方密钥是否相同来分类，可以将这些加密算法分为常规密码算法和公钥密码算法。
A：被西方人誉为“计算机之父”的
利科学家、数学家冯·诺依曼于1945
表了一个全新的"
"—EDVAC。EDVAC 方案提出了著名的“ 冯·依曼体系结构”理论：（1）采用二进制
据和指令（2）采用存储程序方式（3
组成计算机系统
B：“图灵机”与“冯·诺伊曼机”
载入计算机的发展史中。1950年10
发表了另一篇题为“机器能思考吗”的论文，
时代之作。也正是这篇文章，为图灵赢得了“
智能之父”
灵奖”。
A：信息学奥赛相关的软件有：anjuta 版； Red Hat 9.0 自带了gcc/g++ 3.2.2版； Lazarus 0.9.10版；free pascal编译器
版； gdb 6.3版；RHIDE
B：我国信息学奥赛的起源：
1、1984年2月16日，
摸着正在用苹果电脑演示basic小程序的13
生李劲的头说了一句话“计算机普及要从娃娃抓起”！
当年即有中国科协和教育部联合举办了首届全国青少年计算机程序设计竞赛活动——这就是信息学奥赛的前身！
2、为了与国际信息学奥林匹克竞赛活动接轨，全国青少年计算机程序设计竞赛从1988
为“全国青少年信息学（计算机）奥林匹克竞赛”，简称信息学奥赛！已举办12届。
C：国际信息学奥林匹克竞赛( 简称IOI)
由联合国教科文组织于1988
各地20
的一项重要国际赛事，它的宗旨是在青少年中普及计算机科学，给来自世界各地的年轻人提供一个交流机会，并通过比赛和访问加深对主办国的了解。IOI首次比赛于1989年在保加利亚举行，至今已举办18届。
(NOIP)
从
山东赛区的复赛在
Smalltalk
”
（0101001）
汇编语言，
，FORTRAN
非过程化语言
，PROLOG
，SIMULA。
算法的改进，在很大程度上
为主要操作的算法是：冒泡、
21 XOR 2）
a不等于0且b
条件表达式是（a<>0）
队列是先进
“进、
。假
1，2，3，4，5，6，7则车
4，3，7，6）。
如果去掉
N-1的满
11）。
一个结点的子树数目称
。图中，结点
2，结点b的度为1。显然，
2）树的度：所有结点中最大
。（3）树的深度（高度）：
自然界的树形表示法外（画
图）还有括号表示法：先将根结点放入一对圆括
号中，然后把它的子树按由左而右的顺序放入括
号中，而对子树也采用同样方法处理：同层子树
与它的根结点用圆括号括起来，同层子树之间用
逗号隔开，最后用闭括号括起来。例如图可写成
如下形式（r（a（w，x（d（h），e）），b（f），c
（s，t（i（m，o，n），j），u）））
E：二叉树的递归定义和基本形态：二叉树
是以结点为元素的有限集，它或者为空，或者满
足以下条件：⑴有一个特定的结点称为根；⑵余
下的结点分为互不相交的子集L和R，其中L是
根的左子树；R是根的右子树；L和R又是二叉
树；
F：二叉树的两个特殊形态：
⑴满二叉树：若深度为K的二叉树，共有
2K-1个结点，即第I层有2I-1的结点，称为满二
叉树。
⑵完全二叉树：如果一棵二叉树最多只有
最下面两层结点度数可以小于2，并且最下面一层
的结点都集中在该层最左边的若干位置上，则称
此二叉树为完全二叉树
G：二叉树的三个主要性质：
性质1：在二叉树的第i（≥1）层上，最多
有2i-1个结点
性质2：在深度为k(k≥1)的二叉树中最多
有2k-1个结点。
性质3：在任何二叉树中，叶子结点数总比
度为2的结点多1。n0=n2+1
H：二叉树的遍历是不重复地访问二叉树中
的每一个结点。在访问到每个结点时，可以取出
结点中的信息，或对结点作其它的处理。如果用L、
D、R分别表示遍历左子树、访问根结点、遍历右
子树，限定先左后右的次序，三种组合DLR、LDR、
LRD；这三种遍历规则分别称为先（前）序遍历、
中序遍历和后序遍历（以根为标准）。
样题：1、给出一棵二叉树的先序遍历：
ABCDEFGH中序遍历：CBEDAGHF并写出后序
遍历结果。
2、已知一棵二叉树，其中序与后序遍历为：中序
遍历:CBGEAFHDIJ后序遍历:CGEBHFJIDA 求先序
前序遍历
前序遍历的规则如下：
若二叉树为空，则退出。否则
⑴访问处理根结点；⑵前序遍历左子树；
⑶前序遍历右子树；
a b d e h i c f g
中序遍历
中序遍历的规则如下：
若二叉树为空，则退出；否则
⑴中序遍历左子树；⑵访问处理根结点；
⑶中序遍历右子树；
若中序遍历上图中的二叉树，可以得到如下的中序序列： d b h e i a f c g
后序遍历
后序遍历的规则如下：
若二叉树为空，则退出；否则
⑴后序遍历左子树；⑵后序遍历右子树；
⑶访问处理根结点；
若后序遍历上图中的二叉树，可以得到如下的
d h i
e b
f
g c a
个整体。在pascal中，一个集合是由具有同一有序类型的一组数据元素所组成，这一有序类型称为该集合的基类型。
（一）集合类型的定义和变量的说明
集合类型的一般形式为：
set of <基类型>;
说明：①基类型可以是任意顺序类型，而不能
是实型或其它构造类型；同时，基类型的数据的
序号不得超过255。例如下列说明是合法的
type letters=set of "A".."Z";
numbers=set of 0..9;
s1=set of char;
ss=(sun,mon,tue,wed,thu,fri,sat);
s2=set of ss;
②与其它自定义类型一样，可以将类型说明
与变量说明合并在一起。如：
type numbers=set of 0..9;
var s:numbers;
与var s:set of 0..9;等价。
（二）集合的值
集合的值是用"［"和"］"括起来，中间为用逗
号隔开的若干个集合的元素。如：
[] 空集
[1,2,3]
["a","e","i","o","u"]
都是集合。
说明：①集合的值放在一对方括号中，各元素
之间用逗号隔开
②在集合中可以没有任何元素，这样的
集合称为空集
③在集合中，如果元素的值是连续的，
则可用子界型的表示方法表示。例如：
［1,2,3,4,5,7,8,9,10,15］
可以表示成：
［1..5,7..10,15］
④集合的值与方括号内元素出现的次序
无关。例如，［1,5,8 ］和［5,1,8］的值相等。
⑤在集合中同一元素的重复出现对集合
的值没有影响。例如，［1,8,5,1,8］与［1,5,8］的
值相等。
⑥每个元素可用基类型所允许的表达式
来表示。如［1,1+2,4］、［ch］、［succ(ch)］。
（三）集合的运算
１、赋值运算：只能通过赋值语句给集合变
量赋值，不能通过读语句赋值，也不能通过
write(或writeln)语句直接输出集合变量的值
２、集合的并、交、差运算：可以对集合进
行并、交、差三种运算，每种运算都只能有一个
运算符、两个运算对象，所得结果仍为集合。三
种运算符分别用"＋"、"＊"、"－"表示
与算术运算的区别
３、集合的关系运算：集合可以进行相等或不相等、包含或被包含的关系运算，还能测试一
＜＞、＞＝、＜＝、ｉｎ
它们都是二目运算，且前４个运算符的运算对象都是相容的集合类型，最后一个运算符的右边为集合，左边为与集合基类型相同的表达式。
【例4】设有如下说明：
type
weekday=(sun,mon,tue,wed,thu,fri,sat);
week=set of weekday;
subnum=set of 1..50;
写出下列表达式的值:
⑴［sun,sat］+［sun,tue,fri］
⑵［sun,fri］*［mon,tue］
⑶［sun,sat］*［sun..sat］
⑷［sun］-［mon,tue］
⑸［mon］-［mon,tue］
⑹［sun..sat］-［mon,sun,sat］
⑺［1,2,3,5］=［1,5,3,2］
⑻［1,2,3,4］<>［1..4］
⑼［1,2,3,5］>=［1..3］
⑽［1..5］<=［1..4］
⑾［1,2,3］<=［1..3］
⑿2 in［1..10］
答：表达式的值分别是:
⑴［sun,sat,tue,fri］
⑵［］
⑶［sun,sat］
⑷［sun］
⑸［］
⑹［tue..fri］
⑺TRUE
⑻FALSE
⑼TRUE
⑽FALSE
⑾TRUE
⑿TRUE then id:=id+1
else io:=io+1;
份可能具有
字符串类型
字符串类型
整型
字符型
实型数组
在pascal 中，记录由一组称为“域”的分量组成，每个域可以具有不同的类型，记录类型定义的一般形式： record <域名1>:<类型1>; <域名2>:<类型2>; : : : : <域名n>:<类型n>; end; 说明：①域名也称域变量标识符， 应符合标识符的语法规则；在同一个记录中类型中，各个域不能取相同的名，但在不同的记录类型中，两个类型中的域名 可以相同 ②记录类型的定义和记录变量可以合并为一个定义，如： type date=record year:1900..1999; month:1..12; day:1..31 end; var x:date; 可以合并成: var x: record year:1900..1999; month:1..12; day:1..31 end; ③对记录的操作,除了可以进行整体赋值， 只能对记录的分量──域变量进行。 ④域变量的表示方法如下： 记录变量名.域名 如前面定义的记录X,其3个分量分别为:x.year ；x.month ；x.day ⑤域变量的使用和一般的变量一样, 即域变量是属于什么数据类型，便可以进行那种数据类型所允许的操作。 （二）记录的嵌套 当一个记录类型的某一个域类型也是记录类型的时候，我们说发生了记录的嵌套，看下面的例子： 【例6】某人事登记表可用一个记录表示，其中各项数据具有不同的类型，分别命名一个标识符。而其中的“出生年月日”又包括三项数据，还可
以用一个嵌套在内层的记录表示。
具体定义如下:
type sexs=(male,female);
date=record
year:1900..1999;
month:1..12;
day:1..31;
end;
personal=record
name:string[15];
sex:sexs;
birthdate:date;
home:string[40];
end;
【例7】设计一个函数比较两个dates 日期类型
记录变量的迟早。
设函数名、形参及函数类型定义为：
AearlyB(A,B:dates):boolean;
函数的形参为两个dates 类型的值参数。当
函数值为true 时表示日期A 早于日期B,否则日期
A 迟于日期
B 或等于日期B 。显然不能对Ａ、Ｂ
两个记录变量直接进行比较，而要依具体的意义
逐域处理。
源程序如下：
program ex6_7;
type dates=record
year:1900.1999;
month:1..12;
day:1..31
end;
var x,y:dates;
function AearlyB(A,B:dates):boolean;
var earln:boolean;
begin
early:=false;
if (A.year if (A.year=B.year)and(A.month then early:=true; if (A.year=B.year)and(A.month=B.month)and(A.da y end. （三）开域语句 在程序中对记录进行处理时，经常要引用同一记录中不同的域，每次都按6.4.1引用，非常乏味。为此Pascal 提供了一个with 句，可以提供引用域的简单形式。 形式： with <记录变量名表> do <语句> 功能：在do 后的语句中使用with 域时, 只要直接写出域名即可，即可以省略图10.2.2中的记录变量名和"."。 说明：①一般在with 后只使用一个记录变量名。如： write("Input year:"); readln(x.year); write("Input month:"); readln(x.month); write("Input day:"); readln(x.day); 可以改写成: with x do begin write("Input year:");readln(year); write("Input month:");readln(month); write("Input day:");readln(day); end; ②设x,y 是相同类型的记录变量，下列语句是非法的： with x,y do...; ,应是嵌套succ 、pred 、ord begin for letter:="a" to "z" do if (ord(letter)-ord("a"))mod 2=0 then write(letter:3); writeln; for letter:="z" downto "a" do if (ord(letter)-ord("z"))mod 2 =0 then write(letter:3); writeln; end. 分析：程序中，我们利用了字符类型是顺序类型这一特性，直接将字符类型变量作为循环变量，使程序处理起来比较直观。 （二）字符串类型 字符串是由字符组成的有穷序列，字符串类型定义： type <字符串类型标识符>=string[n]; var 字符串变量:字符串类型标识符; 其中：n是定义的字符串长度，必须是0~255之间的自然整数，第0号单元中存放串的实际长度，程序运行时由系统自动提供，第1~n号单元中存放串的字符，若将string[n]写成string，则默认n值为255。 例如：type man=string[8]; line=string; var name:man; screenline:line; 另一种字符类型的定义方式为把类型说明的变量定义合并在一起。 例如：VAR name:STRING[8]; screenline:STRING; Turbo Pascal中，一个字符串中的字符可以通过其对应的下标灵活使用。 例如：var name：string； begin readln（nsme）； for i:=1 to ord(name[0]) do writeln(name[i]); end. 语句writeln(name[i])输出name串中第i个字 符。 【例2】求输入英文句子单词的平均长度 程序如下： program ex8_2; var ch:string; s,count,j:integer; begin write("The sentence is :"); readln(ch); s:=0; count:=0; j:=0; repeat inc(j); if not (ch[j] in [":",",",";","""","!","?","."," "]) then inc(s); if ch[j] in[" ",".","!","?"] then inc(count); until (j=ord（ch[0])) or (ch[j] in [".","!","?"]); if ch[j]<>"." then writeln("It is not a sentence.") else writeln("Average length is ",s/count:10:4); end. 分析：程序中，变量s用于存句子中英文字母 的总数，变量count用于存放句子中单词的个数， ch[j]表示ch串中的第j个位置上的字符，ord （ch[0]）为ch串的串长度。程序充分利用Turbo Pascal允许直接通过字符串下标得到串中的字符 这一特点，使程序比较简捷。 二、字符串的操作 （一）字符串的运算和比较 由字符串的常量、变量和运算符组成的表达式 称为字符串表达式，字符串运算符包括： +：连接运算符 例如："Turbo "+"PASCAL"的结果是"Turbo PASCAL" 若连接的结果字符串长度超过255，则被截成 255个字符；若连接后的字符串存放在定义的字符 串变量中，当其长度超过定义的字符串长度时， 超过部份字符串被截断。 例如：var str1,str2,str3:string[8]; begin str1:="Turbo "; str2:="PASCAL"; str3:=str1+str2; end. 则str3的值为："Turbo PA" =、<>、<、<=、>、>=：关系运算符 两个字符串的比较规则为，从左到右按照ASC Ⅱ码值逐个比较，遇到ASCⅡ码不等时,规定ASC Ⅱ码值大的字符所在的字符串为大。 例如："AB"<"AC" 结果为真 "12"<"2" 结果为真 "PASCAL "="PASCAL" 结果为假 【例3】对给定的10个国家名，按其字母的顺序 输出 程序如下： program ex8_3; var i,j,k:integer; t:string[20]; cname:array[1..10] of string[20]; begin for i:=1 to 10 do readln(cname[i]); for i:=1 to 9 do begin k:=i; for j:=i+1 to 10 do if cname[k]>cname[j] then k:=j; t:=cname[i];cname[i]:=cname[k];cname[k]:=t; end; for i:=1 to 10 do writeln(cname[i]); end. 分析：程序中，当执行到if cname[k]>cname[j] 时，自动将cname[k]串与cname[j]串中的每一个 字符逐个比较，直至遇到不等而决定其大小。这 种比较方式是计算机中字符串比较的一般方式。 三、字符串的函数和过程 Turbo Pascal提供了八个标准函数和标准过 程，见下表，利用这些标准函数与标准过程，一 些涉及到字符串的问题可以灵活解决。 函数和过程名功能说明 CONCAL(ST1,...,STN) 将N个字符串连接起来 等效于ST1+...+ST2，是函数 COPY(S,M,N) 取S中第M个字符开始的N个字 符若M大于S的长度，则返回空串；否则， 若M+N大于s的长度，则截断，是函数 LENGTH(S) 求s的动态的长度返回值为 整数，是函数 POS(SUB,S) 在S中找子串SUB 返回值为 SUB在S中的位置，为byte型，是函数 UPCASE(CH) 将字母CH转换成大写字母 若CH不为小写字母，则不转换，是函数 INSERT(SOUR,S,M) 在S的第M个字符位置处 插入子串SOUR 若返回串超过255，则截断， 是过程 DELETE(S,M,N) 删除S中第M个字符开始的N 个字符串若M大于S的长度，则不删除； 否则，若M+N大于S的长度，则删除到结尾，是 过程 STR(X[:W[:D]],S) 将整数或实数X转换成字符 串S W和D是整型表达式，意义同带字宽的 write语句，是过程 VAL(S,X,CODE) 将字符串S转换成整数或实数 X 若S中有非法字符，则CODE存放非法字 符在S中的下标；否则，CODE为零,CODE为整 型，是过程 FILLCHAR(S,N,CH) 给S填充N个相同的CH 用于初始化数组或字符串，N常用SIZEOF(S)代 替，是过程 注：关于字符串的几点说明 ①空串表示为""，其长度为０，不等于含有一个空 格的串""，它的长度为１；如：A:="";就是将A 字符串置空 ②FILLCHAR可以用于字符串变量和任何类型数 组变量的初始化，比如： FILLCHAR(A,SIZEOF(A),0)将整型数组 A全置０ FILLCHAR(B,SIZEOF(B),TRUE)将布尔型数组B全置０ FILLCHAR(C,SIZEOF(C),"A")将整型字符串C全置"A" 【例4】校对输入日期(以标准英语日期，月/日/年)的正确性，若输入正确则以年．月．日的方式输出。 程序如下: program ex8_4; const max:array[1..12] of byte =(31,29,31,30,31,30,31,31,30,31,30,31); var st:string; p,w,y,m,d:integer; procedure err; begin write("Input Error!"); readln; halt; end; procedure init(var x:integer); begin p:=pos("/",st); if (p=0) or (p=1) or (p>3) then err; val(copy(st,1,p-1),x,w); if w<>0 then err; delete(st,1,p); end; begin write("The Date is :"); readln(st); init(m); init(d); val(st,y,w); if not (length(st)<>4) or (w<>0) or (m>12) or (d>max[m]) then err; if (m=2) and (d=29) then if y mod 100=0 then begin if y mod 400<>0 then err; end else if y mod 4<>0 then err; write("Date : ",y,".",m,".",d); readln; end. 分析：此题的题意很简单，但在程序处理时还需考虑以下几方面的问题。 1．判定输入的月和日应是１位或２位的数字，程序中用了一个过程inst，利用串函数pos，求得分隔符/所在的位置而判定输入的月和日是否为１位或２位，利用标准过程val判定输入的月和日是否为数字； 2．判定月和日是否规定的日期范围及输入的年是否正确； 3．若输入的月是2月份，则还需考虑闰年的情况。 【例5】对输入的一句子实现查找且置换的功能（找到某个子串并换成另一子串）。 程序如下: program ex8_5; var s1,s,o:string; i:integer; begin write("The text:"); readln(s1); write("Find:");readln(s); write("Replace:");readln(o); i:=pos(s,s1); while i<>0 do begin delete(s1,i,length(s)); insert(o,s1,i); i:=pos(s,s1); end; writeln(s1); readln; end. 分析：程序中，输入要查找的字符串及要置换的字符串，充分用上了字符串处理的标准过程delete、insert及标准函数pos。 信息学奥赛一本通算法（C++版）基础算法：高精度计算 高精度加法(大位相加) #include 第19届全国青少年信息学（计算机）奥林匹克BASIC 试题说明： 请考生注意，所有试题的答案要求全部做在答题纸上。 一、基础知识单项选择题（共10题，每小题3分，共计30分） 1、存储容量2GB相当于（） A、2000KB B、2000MB C、2048MB D、2048KB 2、输入一个数（可能是小数），再按原样输出，则程序中处理此数的变量最好使用（） A、字符串类型 B、整数类型 C、实数类型 D、数组类型 3、下列关于计算机病毒的说法错误的是（） A、尽量做到使用正版软件，是预防计算机病毒的有效措施。 B、用强效杀毒软件将U盘杀毒后，U盘就再也不会感染病毒了。 C、未知来源的程序很可能携带有计算机病毒。 D、计算机病毒通常需要一定的条件才能被激活。 4、国标码的“中国”二字在计算机内占（）个字节。 A、2 B、4 C、8 D、16 5、在计算机中，ASCⅡ码是( )位二进制代码。 A、8 B、7 C、12 D、16 6、将十进制数2013转换成二进制数是( )。 A、11111011100 B、11111001101 C、11111011101 D、11111101101 7、现有30枚硬币(其中有一枚假币，重量较轻)和一架天平，请问最少需要称几次，才能找出假币( )。 A、3 B、4 C、5 D、6 8、下列计算机设备中，不是输出设备的是（）。 A、显示器 B、音箱 C、打印机 D、扫描仪 9、在windows窗口操作时，能使窗口大小恢复原状的操作是（） A、单击“最小化”按钮 B、单击“关闭”按钮 C、双击窗口标题栏 D、单击“最大化”按钮 10、世界上第一台电子计算机于1946年诞生于美国，它是出于（）的需要。 A、军事 B、工业 C、农业 D、教学二、问题求解（共2题，每小题5分，共计10分） 1、请观察如下形式的等边三角形： 边长为 2 边长为4 当边长为２时，有4个小三角形。 问：当边长为6时，有________个小三角形。 当边长为n时，有________个小三角形。 2、A、B、C三人中一位是工人，一位是教师，一位是律师。已知：C比律师年龄大，A和教师不同岁，B比教师年龄小。问：A、B、C分别是什么身分？ 答：是工人，是教师，是律师。 三、阅读程序写结果（共4题，每小题8分，共计32分） 1、REM Test31 FOR I =1 TO 30 S=S+I\5 NEXT I PRINT S END 本题的运行结果是：( １) 2、REM Test32 FOR I =1 TO 4 PRINT TAB (13-3*I)； N=0 FOR J =1 TO 2*I-1 N=N+1 PRINT N； NEXT J PRINT NEXT I END 本题的运行结果是：( ２) NOIP 2017全国青少年信息学奥林匹克联赛提高组初赛试题答案 一、单项选择题（共 15 题，每题 1.5 分，共计 22.5 分；每题有且仅有一个正确选项） 1. 从( )年开始，NOIP 竞赛将不再支持 Pascal 语言。 A. 2020 B. 2021 C. 2022 D. 2023 2.在 8 位二进制补码中，10101011 表示的数是十进制下的( )。 A. 43 B. -85 C. -43 D.-84 3.分辨率为 1600x900、16 位色的位图，存储图像信息所需的空间为( )。 A. 2812.5KB B. 4218.75KB C. 4320KB D. 2880KB 4. 2017年10月1日是星期日，1949年10月1日是( )。 A. 星期三 B. 星期日 C. 星期六 D. 星期二 5. 设 G 是有 n 个结点、m 条边(n ≤m)的连通图，必须删去 G 的( )条边，才能使得 G 变成一棵树。 A.m–n+1 B. m-n C. m+n+1 D.n–m+1 6. 若某算法的计算时间表示为递推关系式： T(N)=2T(N/2)+NlogN T(1)=1 则该算法的时间复杂度为( )。 A.O(N) B.O(NlogN) C.O(N log2N) D.O(N2) 7. 表达式a * (b + c) * d的后缀形式是()。 A. abcd*+* B. abc+*d* C. a*bc+*d D. b+c*a*d 8. 由四个不同的点构成的简单无向连通图的个数是( )。 A. 32 B. 35 C. 38 D. 41 9. 将7个名额分给4个不同的班级，允许有的班级没有名额，有( )种不同的分配方案。 A. 60 B. 84 C. 96 D.120 10. 若f[0]=0, f[1]=1, f[n+1]=(f[n]+f[n-1])/2，则随着i的增大，f[i]将接近与( )。 A. 1/2 B. 2/3 D. 1 11. 设A和B是两个长为n的有序数组，现在需要将A和B合并成一个排好序的数组，请问任何以元素比较作为基本运算的归并算法最坏情况下至少要做( )次比较。 A. n2 B. nlogn C. 2n D.2n-1 12. 在n(n>=3)枚硬币中有一枚质量不合格的硬币（质量过轻或质量过重），如果只有一架天平可以用来称重且称重的硬币数没有限制，下面是找出这枚不合格的硬币的算法。请把 a-c三行代码补全到算法中。 a. A XUY b. A Z c. n |A| 算法Coin(A,n) 1. k n/3 2. 将A中硬币分成X,Y,Z三个集合，使得|X|=|Y|=k, |Z|=n-2k 3. if W(X)≠W(Y) //W(X), W(Y)分别为X或Y的重量 4. then_______ 5. else_______ 6. __________ 7. if n>2 then goto 1 8. if n=2 then 任取A中1枚硬币与拿走硬币比较，若不等，则它不合格；若相等，则A 中剩下的硬币不合格 9. if n=1 then A中硬币不合格 正确的填空顺序是( )。 A. b,c,a B. c,b,a C. c,a,b D.a,b,c 13. 在正实数构成的数字三角形排列形式如图所示，第一行的数为a11；第二行的数从左到右依次为a21,a22;…第n行的数为an1,an2,…，ann。从a11开始，每一行的数aij只有两条边可以分别通向下一行的两个数a(i+1)j和a(i+1)(j+1)。用动态规划算法找出一条从a11向下通到an1,an2,…,ann中某个数的路径，使得该路径上的数之和达到最大。 信息学奥赛基础知识习题(答案版) 一、选择题（下列各题仅有一个正确答案，请将你认为是正确的答案填在相应的横线上） 1．我们把计算机硬件系统和软件系统总称为 C 。 (A)计算机CPU (B)固 件 (C)计算机系统 (D)微处 理机 2．硬件系统是指 D 。 (A)控制器，器运算 (B)存储器，控制器 (C)接口电路，I/O设备 (D)包括(A)、(B)、(C) 3. 计算机软件系统包括 B 。 A) 操作系统、网络软件 B) 系统软件、应用软件 C) 客户端应用软件、服务器端系统软件 D) 操作系统、应用软件和网络软件4．计算机硬件能直接识别和执行的只有 D 。 (A)高级语言 (B)符号语言 (C)汇编语言 (D)机器语言 5．硬盘工作时应特别注意避免 B 。 (A)噪声 (B)震动 (C)潮 湿 (D)日光 6．计算机中数据的表示形式是 C 。 (A)八进制 (B)十进制 (C)二进 制 (D)十六进制 7．下列四个不同数制表示的数中，数值最大的是 A 。 (A)二进制数11011101 (B)八进制数334 (C)十进制数219 (D)十六进制 数DA 8．Windows 9x操作系统是一个 A 。 (A)单用户多任务操作系统 (B)单用户单任务操 作系统 (C)多用户单任务操作系统 (D)多用户多任务操 作系统 9．局域网中的计算机为了相互通信，必须安装___B__。 （A）调制解调器（B）网卡（C）声卡（D）电视卡 10．域名后缀为edu的主页一般属于__A____。 （A）教育机构（B）军事部门（C）政府部门（D）商业组织 11. 在世界上注册的顶级域名是__A____。 （A）hk（B）cn（C）tw（D） 12．计算机能够自动、准确、快速地按照人们的意图进行运行的最基本思想是（ D ）。 （A）采用超大规模集成电路（B）采用CPU作为中央核心部件 （C）采用操作系统（D）存储程序和程序控制 13．设桌面上已经有某应用程序的图标，要运行该程序，可以 C 。 (A)用鼠标左键单击该图标 (B)用鼠标右键单击该 图标 (C)用鼠标左键双击该图标 (D)用鼠标右键双击该 图标 信息学奥赛基础知识提纲 （2014年9月） 1 计算机系统 1－1概述 一个完整的计算机系统包括硬件系统和软件系统两大部分，必须具有五大功能：数据传送功能、数据存储功能、数据处理功能、操作控制功能、操作判断功能。它的工作特点是：运算速度快、运算精度高、记忆能力强、通用性广、自动运算。 计算机按照规模可分为：巨型机、大型机、中型机、小型机、微型机、单片机等几种类型。根据用途不同分为通用机和专用机。 硬件指的是计算机的设备实体；软件通常泛指各类程序和文件。软硬件的关系：硬件是软件的基础。软件是硬件的扩充与完善。硬件与软件在逻辑上是等价的。 1946年，世界上第一台计算机诞生于宾夕法尼亚大学，称为ENIAC 。 1949年,第一台存储计算机EDSAC,英国剑桥大学威尔克斯（Wilkes ）设计和制造的。 1951年，第一台商用计算机是UNIVAC 。 1－2 硬件系统 1－2－1 冯·诺伊曼（J.von Neumann ）机：美籍匈牙利数学家 现代计算机的基本结构被称为冯·诺伊曼结构。它的主要特点是储存程序的概念： （1） 采用二进制形式表示数据和指令。 （2） 将程序（包括操作指令和操作数）事先存入主存储器中，使计算机在工作时能够自 动高速地从存储器中取出指令加以执行。 （3） 由运算器、存储器、控制器、输入设备、输出设备五大基础部件组成计算机系统。 冯·诺伊曼机 运 算 器存 储 器 输出设备 输入设备 控 制 器控 制 台 控制信号请 求 信 号 请 求 信 号 控制信号结 果 程序 反馈信息 操作指令 地址 指令 1－2－2 计算机的总线结构 计算机的各个部件需要以某种方式互联，进行数据交换。最常见的互联结构就是总线互联结构和多总线互联结构。总线是一种连接多种设备的信息传递通道，实际上是一组信号线。 典型的计算机总线结构由内部总线和系统总线组成。 （1） 内部总线：用于连接CPU 内部的各个模块。 （2） 系统总线：又称外部总线，用于连接CPU 、存储器和输入输出设备。系统总线的信 号线分为三类：数据线、地址线和控制线。 数据线（Data Bus ）：数据总线的宽度就是指组成数据总线的信号线的数目，它决定了在该总线上一次可以传送的二进制位数。 地址线（Address Bus ）：用以传递地址信息，来指示数据总线上的数据来源和去向。地址线的数目决定了能够访问空间的大小。 控制线（Control Bus ）：用来控制数据总线和地址总线。 某SRAM 芯片，其存储容量为64K*16位，则该芯片的地址线数目和数据线的数目？ 1－2－3 中央处理器（Central Processor Unit ） 1、CPU 包含了冯机五大部件中的运算器（即加法器）和控制器。 运算器：对信息加工和处理的部件，主要完成各种算术运算和逻辑运算。 控制器：通过读取各种指令，并进行翻译、分析，而后对各部件作出相应的控制。 2、CPU 主要由三大部分组成：寄存器组、算术逻辑单元（ALU ）和控制单元（控制器）。 寄存器组：分为通用寄存器（通用寄存器、数据寄存器、地址寄存器、标志寄存器）和状态控制寄存器（程序计数器PC 、指令寄存器IR 、存储器地址寄存器MAR 、存储器缓冲寄存器MBR ）以及程序状态字PSW 。 算术逻辑单元ALU ： 寄存器、存储器、I/O 设备把待处理的数据输入到ALU 。 控制单元：控制器的基本功能就是时序控制和执行控制。根据当前运行的程序，控 制器使CPU 按一定的时序关系执行一序列 的微操作从而完成程序。 时钟信号：控制器根据时钟电路产生的时钟信号进行定时，以控制各种操作按指定的时序进行。计算机的基本功能是执行程序，而程序由一连串的指令组成；计算机的执行过程由一连串的指令周期组成，每一指 令周期完成一条指令。这些指令周期又可进一步细分为更小的单元，直到微操作uop-----CPU 完成的基本的原子操作。 时钟脉冲发生器的晶振频率成为机器的主频，它产生的时钟脉冲信号是整个机器的时间基准，其周期T 称为该计算机的时钟周期。 完成一个微操作的时间就称为CPU 周期（机器周期）。执行一条机器指令所需的时间称为一个指令周期。 3、指令系统（精简指令系统）：操作类指令和控制类指令 一条指令：操作码 + 地址码 一条机器指令的执行：取指令――分析指令――执行指令 4、CPU 的主要指标有： 字长：CPU 一次所能处理的二进制位数。它决定着寄存器、加法器、数据总线等的位数。主频：计算机的时钟频率。（即内频）单位：MHz 或GHz 。 运算速度：CPU 每秒钟能完成的指令数MIPS 。运算速度=1÷ 执行一条机器指令所需的时间 1．已知，按中序遍历二叉树的结果为：abc 问：有多少种不同形态的二叉树可以得到这一遍历结果，并画出这些二叉树。 2．有2×n的一个长方形方格，用一个1×2的骨牌铺满方格。例如n=3时，为2×3方格。 此时用一个1×2的骨牌铺满方格，共有3种铺法： 试对给出的任意一个n（n>0），求出铺法总数的递推公式。 3．设有一个共有n级的楼梯，某人每步可走1级，也可走2级，也可走3级，用递推公式给出某人从底层开始走完全部楼梯的走法。例如：当n=3时，共有4种走法，即1+1+1,1+2,2+1,3。 4.在a,b,c,d,e,f六件物品中，按下面的条件能选出的物品是： (1)a,b两样至少有一样 (2)a,d不能同时取 (3)a,e,f中必须有2样 (4)b,c要么都选，要么都不选 (5)c,d两样中选一样 (6)若d不选，则e也不选 5.平面上有三条平行直线，每条直线上分别有7，5，6个点，且不同直线上三个点都不在 同一条直线上。问用这些点为顶点，能组成多少个不同三角形？ 6.已知一棵二叉树的结点名为大写英文字母，其中序与后序遍历的顺序分别为：CBGEAFHDIJ与CGEBHFJIDA则该二叉树的先序遍历的顺序为： 7.平面上有三条平行直线，每条直线上分别有7，5，6个点，且不同直线上三个点都不在同一条直线上。问用这些点为顶点，能组成多少个不同四边形？ 8.如下图,有一个无穷大的的栈S,在栈的右边排列着1,2,3,4,5共五个车厢。其中每个车厢可以向左行走,也可以进入栈S让后面的车厢通过。现已知第一个到达出口的是3号车厢，请 写出所有可能的到达出口的车厢排列总数(不必给出每种排列)。 出口←← 1 2 3 4 5 S↓ 9..将N个红球和M个黄球排成一行。例如:N=2,M=3可得到以下6种排法: 红红黄黄黄红黄红黄黄红黄黄红黄黄红红黄黄黄红黄红黄黄黄黄红红 问题:当N=4,M=3时有多少种不同排法?(不用列出每种排法) 10．在书架上放有编号为1 ，2 ，．．．，n的n本书。现将n本书全部取下然后再放回去，当放回去时要求每本书都不能放在原来的位置上。例如：n = 3时： 原来位置为：1 2 3 放回去时只能为：3 1 2 或 2 3 1 这两种 问题：求当n = 5时满足以上条件的放法共有多少种？（不用列出每种放法） 11.现在市场上有一款汽车A很热销，售价是2万美元。汽车A每加仑汽油可以行驶20英里。普通汽车每年大约行驶12000英里。油价是每加仑1美元。不久我公司就要推出新款节油汽车B，汽车B每加仑汽油可以行驶30英里。现在我们要为B制定价格(它的价格略高于A)：我们预计如果用户能够在两年内通过节省油钱把B高出A的价钱弥补回来，则他们就会购买B，否则就不会购买B。那么B的最高价格应为万美元。 12. 某年级学生共选修6门课程，期末考试前，必须提前将这6门课程考完，每人每天只在下午至多考一门课程，设6门课程为C1，C2，C3，C4，C5，C6，S(Ci)为学习Ci 的学生集合。已知S(Ci)∩S(C6)≠ф，i=1，2，...，5，S(Ci)∩S(Ci+1)≠ф，i=1，2，3，4，S(C5)∩S(C1)≠ф，问至少安排_____天才能考完这6门课程。 13、一个家具公司生产桌子和椅子。现有113个单位的木材。每张桌子要使用20个单位的木材，售价是30元；每张椅子要用16个单位的木材，售价是20元。使用已有的木材生 全国青少年信息学奥林匹克联赛 排序算法 一、插入排序(Insertion Sort) 1. 基本思想： 每次将一个待排序的数据元素，插入到前面已经排好序的数列中的适当位置，使数列依然有序；直到待排序数据元素全部插入完为止。 2. 排序过程： 【示例】： [初始关键字] [49] 38 65 97 76 13 27 49 J=2(38) [38 49] 65 97 76 13 27 49 J=3(65) [38 49 65] 97 76 13 27 49 J=4(97) [38 49 65 97] 76 13 27 49 J=5(76) [38 49 65 76 97] 13 27 49 J=6(13) [13 38 49 65 76 97] 27 49 J=7(27) [13 27 38 49 65 76 97] 49 J=8(49) [13 27 38 49 49 65 76 97] Procedure InsertSort(Var R : FileType); //对R[1..N]按递增序进行插入排序, R[0]是监视哨// Begin for I := 2 To N Do //依次插入R[2],...,R[n]// begin R[0] := R[I]; J := I - 1; While R[0] < R[J] Do //查找R[I]的插入位置// begin R[J+1] := R[J]; //将大于R[I]的元素后移// J := J - 1 end R[J + 1] := R[0] ; //插入R[I] // end End; //InsertSort // 信息学奥赛（NOIP）必看经典书目汇总！ 小编整理汇总了一下大神们极力推荐的复习资料！（欢迎大家查漏补缺） 基础篇 1、《全国青少年信息学奥林匹克分区联赛初赛培训教材》（推荐指数：4颗星） 曹文，吴涛编著，知识点大杂烩，部分内容由学生撰写，但是对初赛知识点的覆盖还是做得相当不错的。语言是pascal的。 2、谭浩强老先生写的《C语言程序设计（第三版）》（推荐指数：5颗星） 针对零基础学C语言的筒子，这本书是必推的。 3、《骗分导论》（推荐指数：5颗星） 参加NOIP必看之经典 4、《全国信息学奥林匹克联赛培训教程（一）》（推荐指数：5颗星） 传说中的黄书。吴文虎，王建德著，系统地介绍了计算机的基础知识和利用Pascal语言进行程序设计的方法 5、《全国青少年信息学奥林匹克联赛模拟训练试卷精选》 王建德著，传说中的红书。 6、《算法竞赛入门经典》（推荐指数：5颗星） 刘汝佳著，算法必看经典。 7、《算法竞赛入门经典:训练指南》（推荐指数：5颗星） 刘汝佳著，《算法竞赛入门经典》的重要补充 提高篇 1、《算法导论》（推荐指数：5颗星） 这是OI学习的必备教材。 2、《算法艺术与信息学竞赛》（推荐指数：5颗星） 刘汝佳著，传说中的黑书。 3、《学习指导》（推荐指数：5颗星） 刘汝佳著，《算法艺术与信息学竞赛》的辅导书。（PS：仅可在网上搜到，格式为PDF）。 4、《奥赛经典》（推荐指数：5颗星） 有难度，但是很厚重。 5、《2016版高中信息学竞赛历年真题解析红宝书》（推荐指数：5颗星） 历年真题，这是绝对不能遗失的存在。必须要做！ 三、各种在线题库 1、题库方面首推USACO（美国的赛题），usaco写完了一等基本上就没有问题，如果悟性好的话甚至能在NOI取得不错的成绩. 2、除此之外Vijos也是一个不错的题库，有很多中文题. 3、国内广受NOIP级别选手喜欢的国内OJ（Tyvj、CodeVs、洛谷、RQNOJ） 4、BJOZ拥有上千道省选级别及以上的题目资源，但有一部分题目需要购买权限才能访问。 5、UOZ 举办NOIP难度的UER和省选难度的UR。赛题质量极高，命题人大多为现役集训队选手。 2015 年第二十一届全国青少年信息学奥林匹克联赛初赛普及组 C++语言试题竞赛日寸间： 2015 年 10 月 l 1 日 14:30~16:30 选手注意： ?试题纸共有 7 页，答题纸共有 2 页，满分 100 分。请在答题纸上作答，写在试题纸上的一律无效。?不得使用任何电子设备(如计算器、手机、电子词典等)或查阅任何书籍资料。 一、单项选择题(共 20 题，每题 1.5 分，共计 30 分；每题有且仅有一个正确选项) 1.1MB 等于( ) 。 A ．1000 字节 B ．1024 字节 C ． 1000X 1000 字节 D ．1024X 1024 字节 2．在 PC机中， PENTIUM(奔腾)、酷睿、赛扬等是指 ( ) 。 A ．生产厂家名称 B ．硬盘的型号 C ．CPU的型号 D ．显示器的型号 3．操作系统的作用是( ) 。 A ．把源程序译成目标程序 B ．便于进行数据管理 C ．控制和管理系统资源 D ．实现硬件之间的连接 4．在计算机内部用来传送、存贮、加工处理的数据或指令都是以( ) 形式进行的。 A ．二进制码 B ．八进制码 C ．十进制码 D ．智能拼音码 5．下列说法正确的是 ( ) 。 A ． CPU的主要任务是执行数据运算和程序控制 B ．存储器具有记忆能力，其中信息任何时候都不会丢失 C ．两个显示器屏幕尺寸相同，则它们的分辨率必定相同 D ．个人用户只能使用 Wifi 的方式连接到 Internet 6．二进制数 00100100 和 00010100 的和是 ( ) 。 A.00101000 B. 01001001 C. 01000100 D.00111000 7．与二进制小数 0.1 相等的十六进制数是( ) 。 A ． 0.8 B ． 0.4 C ． 0.2 D ． 0.1 8．所谓的“中断”是指 ( ) 。 A ．操作系统随意停止一个程序的运行 B ．当出现需要时， CPU暂时停止当前程序的执行转而执行处理新情况的过程 C ．因停机而停止一个程序的运行 D ．电脑死机 9．计算机病毒是 ( ) 。 A ．通过计算机传播的危害人体健康的一种病毒 B ．人为制造的能够侵入计算机系统并给计算机带来故障的程序或指令集合 C ．一种由于计算机元器件老化而产生的对生态环境有害的物质 D ．利用计算机的海量高速运算能力而研制出来的用于疾病预防的新型病毒 10． FTP可以用于 ( ) 。 A ．远程传输文件 B ．发送电子邮件 C ．浏览网页 D ．网上聊天 11．下面哪种软件不属于即时通信软件 ( ) 。 A ．QQ B ． MSN C ．微信 D ． P2P 12.6 个顶点的连通图的最小生成树，其边数为 ( ) 。 A ． 6 B ． 5 C ． 7 D ． 4 13. 链表不具备的特点是 ( ) 。 A ．可随机访问任何一个元素 B ．插入、删除操作不需要移动元素 C ．无需事先估计存储空间大小 D ．所需存储空间与存储元素个数成正比 14. 线性表若采用链表存储结构，要求内存中可用存储单元地址( ) 。 A ．必须连续 B ．部分地址必须连续 c ．一定不连续 D ．连续不连续均可 15．今有一空栈 S，对下列待进栈的数据元素序列 a,b ，c， d，e，f 依次进行进栈，进栈，出栈，进栈，进栈，出栈的操作，则此操作完成后，栈S 的栈顶元素为 ( ) 。 A． f B ．c C ．a D ． b 信息学奥赛一本通题解目录:信息学奥赛取消 第1章 数论1．1 整除1．2 同余1．3 最大公约数1．3．1 辗转相除法1．3．2 进制算法1．3．3 最小公倍数1．3．4 扩展欧几里得算法1．3．5 求解线性同余方程1．4 逆元1．5 中国剩余定理1．6 斐波那契数1．7 卡特兰数1．8 素数1．8．1 素数的判定1．8．2 素数的相关定理1．8．3 Miller-Rabin素数测试1．8．4 欧拉定理1．8．5 PollardRho算法求大数因子1．9 Baby-Step-Giant-Step及扩展算法1．10 欧拉函数的线性筛法1．11 本章习题第2章群论2．1 置换2．1．1 群的定义2．1．2 群的运算2．1．3 置换2．1．4 置换群2．2 拟阵2．2．1 拟阵的概念2．2．2 拟阵上的最优化问题2．3 Burnside引理2．4 Polya定理2．5 本章习题第3章组合数学3．1 计数原理3．2 稳定婚姻问题3．3 组合问题分类3．3．1 存在性问题3．3．2 计数性问题3．3．3 构造性问题3．3．4 最优化问题3．4 排列3．4．1 选排列3．4．2 错位排列3．4．3 圆排列3．5 组合3．6 母函数3．6．1 普通型母函数3．6．2 指数型母函数3．7 莫比乌斯反演3．8 Lucas定理3．9 本章习题第4章概率4．1 事与概率4．2 古典概率4．3 数学期望4．4 随机算法4．5 概率函数的收敛性4．6 本章习题第5章计算几何5．1 解析几何初步5．1．1 平面直角坐标系5．1．2 点5．1．3 直线5．1．4 线段5．1．5 多边形5．1．6 [信息学奥赛基础知识讲义] 基础部分 一、进制：2进制数与8进制、10进制、16进制数的换算 换算1：将N进制数换算成10进制数（N可以为2,8,16或其它自然数） 换算2：将10进制数换算成N进制数（N可以为2,8,16或其它自然数） 1.下列无符号数中，最小的数是（） A.（11011001）2 B.（75）10 C.（37）8 D.（2A）16 7、小张用十六进制，八进制和十进制写下了如下一个等式： 52-19=33 式中三个数是各不相同进位制的数，试问52,19,33，分别为______。 （A）8，10， 16 （B）10, 16, 8 (c) 8, 16, 10 (D) 10, 8, 16 二、数据的存储和编码 所有的数据都是以二进制存储在计算机的存储器中的，数据的传送、存储、加工、处理或指令都是以二进制形式进行的。 对于数值:弄清原码、反码、补码以及定点数和浮点数。负数在计算机中以补码形式存放，小数在计算机中是以浮点数形式存放。 0的原码表示法有两种，+0和—0 8位定点整数的补码表示范围为-128_____+127 14、计算机中的数有浮点数与定点数两种，其中用浮点数表示的数，通常由（）这两部分组成。 A.指数与基数 B. 尾数与小数 C. 阶码与尾数 D.整数与小数 8、如果用一个字节表示一个整数，最高位用作符号位，其他位表示数值，例如 00000001表示+1，10000001表示-1 （1）试问这样表示法的整数a的范围应是———————— A、-127<=a<=127 B、-128<=a<=128 C、-128<=a<127 D、-128 高中信息学竞赛各种问题求解试题及 答案 第1题(5分)，将n个不同颜色的球放人k个无标号的盒子中( n>=k，且盒子不允许为空)的方案数 为S(n，k)，例如：n=4，k=3时，S(n，k)=6。当n=6，k=3时，S(n，k)=________。 答案：0 k < n S(n,k)= 1 k = 1 S(n-1,k-1)+k*S(n-1,k) n >= k >= 2 第2题(5分)，有5本不同的数学书分给5个男同学，有4本不同的英语书分给4个女同学，将全部书 收回来后再从新发给他们，与原方案都不相同的方案有________种。 答案： 5!*4!+D(5)*D(4)=1140480 其中：D(n)=(n-1)*(D(n-1)+D(n-2)) (n > 2) D(1)=0 D(2)=1 第3题(6分)，把三角形各边分成n等分，过每一分点分别做各边的平行线，得到一些由三角形的边 和这些平行线所组成的平行四边形。n为已知整数，能组成_______个平行四边形。 答案： 3*C(n+2,4) 第4题(6分)，由a，b，c3个不同的数字组成一个N 位数，要求不出现两个a相邻，也不出现两个b 相邻，这样的N位数的个数为AN，用AN-1和AN-2表示AN的关系式为：AN＝_______________。 答案： AN= 2*AN-1+AN-2 第5题(6分)，在m*n的棋盘上，每个方格(单位正方形，即边长为1的正方形)的顶点称为格点。以格点 为顶点的多边形称为格点多边形。若设格点凸N边形面积的最小值为gn，格点凸N边形内部(非顶点的)格点的个数的最小值为fn，则gn和fn的关系式为： gn=___________。 答案： Gn= fn+N/2-1 ( N >= 3 ) 第6题(4分)，编号为1到13的纸牌顺时针排成一 圈，有人从编号为1的牌从数字1开始顺时针数下去， 1、2、3、…、20、21、…，一圈又一圈。问：当数到数字N 时，所在纸牌的编号为多少? 答案： 1+(N-1) mod 13 第7题(8分)，有位小同学喜欢在方阵中填数字，规则 是按下图示例从右上角开始，按斜线填数字， 碰到边界就重新。显然，数字1在坐标(1，5)位置，数字 25在坐标(5，1)位置。后来这位小朋友想知道， 对于N阶的方阵，随机取一个位置(x，y)，并规定x≤y，问 这个位置上应该填的数字是多少?5阶方阵的 示例图如下： 11 7 4 2 1 16 12 8 5 3 20 17 13 9 6 23 21 18 14 10 25 24 22 19 15 答案： (N-y+x)*(N-y+x-1)/2+x 第8题(5分)，设有质量为1、3、9、27、81、…3n g... 的砝码各一枚，如果砝码允许放在天平的两边， 则用它们来称物体的质量，最多可称出1g到3n+3n/2g之间 的所有质量，如n=4时，可称出18到121g之间的 所有质量；当物体质量为M=14时，有14+9+3+1=27，即天 平一端放M=14g的物体和9g、3g、1g的砝码，另一 端放27g的砝码，即可称出M的质量。当M=518g时，请 你写出称出该物体的质量的方法，并用上述所示的 等式来表示。 答案： 518+243+3+1= 729+27+9 第9题(7分)，在圆周上有N个点(N>=6)，在任意两个 点之间连一条弦，假设任何3条弦在圆的内部 都没有公共点，问这些弦彼此相交能在圆内构成多少个三 角形(只要求写出三角形总数的表示式而无需化 简)? 提示：下图是N=6的情况，图中所示的4个三角形从 某种意义上说具有一定的代表性。 答案： C(N,3)+4*C(N,4)+5*C(N,5)+6*C(N,6) 第10题(6分)，用1个或多个互不相同的正整数之和 表示1～511之间的所有整数 ①至少要多少个不同的正整数_________________; ②这些正整数是_______________ 答案： ①9 ②1,2,4,6,16,32,64,128,256 第11题(7分)，在有m行n列格子的棋盘内，一枚棋 子从棋盘的左上角格子沿上、下、左、右方向行走， 最后走到棋盘的右下角格子。该棋子走过的格子数为奇数 的充分必要条件是________________ 答案：m+n为偶数 完善程序试题及其答案 第1题(14分)以下程序是将一组整数按从小到大的顺 序排列。排序的方法是将长度为n的数a分为两个长度分 别为(n div 2)与(n-n div 2)的子数组a1，a2。然后递归调用排 序过程，将a1，a2分别排序，最后将a1，a2归并成数组 a。例如a=(3，1，2，4)，那么a1=(3，1)，a2=(2，4)。调用 排序过程将a1，a2排序，得到a1=(1，3)，a2=(2，4)，然 后进行合并排序。 从键盘输入数的长度n以及n个整数，存在数组a中，调 用子过程sort进行排序，最后输 出排序结果。 program wsh； const maxn=100；． 各种问题 1 历届“问题求解”解析（2013竞赛辅导） 问题求解是信息学竞赛初赛中常见题型，它共两题，每题5分，共10分，十六届增加了比重，有三题，占15分。诸如寻找假币、博弈原理、抽屉原理、容斥问题、排列组合、逻辑推理、递推关系等问题出现在问题求解中。（相关问题的具体讲解根据需要考虑发讲义） 第一届（逻辑推理问题） 1. 有标号为A 、B 、C 、D 和1、2、3、4的8个球，每两个球装一盒，分装4盒。标号为字母的球与标号 为数字的球有着某种一一对应的关系（称为匹配），并已知如下条件： ① 匹配的两个球不能在一个盒子内。 ② 2号匹配的球与1号球在一个盒子里。 ③ A 号和2号球在一个盒子里。 ④ B 匹配的球和C 号球在一个盒子里。 ⑤ 3号匹配的球与A 号匹配的球在一个盒子里。 ⑥ 4号是A 或B 号球的匹配球。 ⑦ D 号与1号或2号球匹配。 请写出这四对球匹配的情况。 第四届（递推、树、图） 1. 已知一个数列U 1，U 2，U 3，…，U N ，… 往往可以找到一个最小的K 值和K 个数a 1，a 2，…,a n 使得数列从某项开始都满足： U N+K =a 1U N+K-1+a 2U N+K-2+……+a k U N (A) 例如对斐波拉契数列1，1，2，3，5，…可以发现：当K=2，a 1 =1，a 2 =1时，从第3项起（即N>=1） 都满足U n+2 =U n+1+U n 。试对数列13，23，33，…，n 3,…求K 和a 1,a 2, …,a K 使得（A ）式成立。 当K= 4，a 1,a 2,…,a k 为a 1=4, a 2=6, a 3=4，a 4=-1对数列132333,…,n 3,…（A ）成立。 2．给出一棵二叉树的中序遍历：DBGEACHFI 与后序遍历：DGEBHIFCA 画出此二叉树。 3．用邻接矩阵表示下面的无向图： 表示该无向图的邻接矩阵为 0 1 0 0 0 0 0 1 0 1 1 0 0 0 0 1 0 1 0 0 0 0 1 1 0 1 1 1 0 0 0 1 0 0 1 0 0 0 1 0 0 1 0 0 0 1 1 1 0 第五届（递推） 将Ln 定义为求在一个平面中用n 条直线所能确定的最大区域数目。例如：当n=1时，L1=2,进一步考虑，用n 条折成角的直线（角度任意），放在平面上，能确定的最大区域数目Zn 是多少？例如：当n=1时，Z1=2（如下图所示） 当给出n 后，请写出以下的表达式：Ln = ______________ 2、Zn = _______________ 答案为：Ln=n(n+1)/2+1(n ≥0) Zn=L2n-2n=2n2-n+1 解析：本题实质是求直线或折线将一个平面分成的最大区域数，从两个方面考虑： （1）求在一个平面中用n 条直线所能确定的最大区域数； n=1,L1=2, F(1)=2 n=2,L2=4, F(2)=F(1)+2 n=3,L3=7, F(3)=F(2)+3 n=4,L4=11, F(4)=F(3)+4 …… 所以， F(n)=F(n-1)+n 把上面的n 个等式左右相加，化简得出：F （n ）=2+2+3+4+……+n 即：L （n ）=n*(n+1)/2+1 信息学奥赛基础知识习题(答案版） 一、选择题（下列各题仅有一个正确答案，请将你认为是正确的答案填在相应的横线上) 1. 我们把计算机硬件系统和软件系统总称为 C 。 (A)计算机CPU （B）固 件 (C）计算机系统 (Ｄ）微处理机 2．硬件系统是指 D 。 (A）控制器,器运算 (B）存储器,控制器 (C)接口电路,I/O设备（D)包括(A)、(B）、(C） 3．计算机软件系统包括 B 。 A) 操作系统、网络软件Ｂ）系统软件、应用软件 C）客户端应用软件、服务器端系统软件 D) 操作系统、应用软件和网络软件 4.计算机硬件能直接识别和执行的只有Ｄ。 (A)高级语言(B)符号语言 (Ｃ)汇编语言(D)机器语言 5.硬盘工作时应特别注意避免Ｂ。 (A)噪声 (B)震动 (C)潮 湿（Ｄ)日光 6．计算机中数据的表示形式是Ｃ。 （Ａ)八进制(B)十进制 (C)二进 制 (D)十六进制 ７．下列四个不同数制表示的数中，数值最大的是 A 。 （A）二进制数11０11１01 （B）八进制数３３4 (C）十进制数２１９（D)十六进制数DA 8.Wｉnｄowｓ９ｘ操作系统是一个 A 。 (Ａ)单用户多任务操作系统(Ｂ)单用户单任务操作系统 （C)多用户单任务操作系统 (D）多用户多任务操作系统 ９．局域网中的计算机为了相互通信,必须安装_＿＿B__。 (A）调制解调器(B)网卡(Ｃ)声卡（Ｄ)电视卡 １0．域名后缀为ｅdu的主页一般属于_＿A____。 (A）教育机构(B）军事部门（C）政府部门（D）商业组织 １1．香港在世界上注册的顶级域名是_＿A____。 （A)ｈk(B)ｃn(Ｃ）tw(D）cｏm 12.计算机能够自动、准确、快速地按照人们的意图进行运行的最基本思想是（ D )。 （A）采用超大规模集成电路 (B)采用CPＵ作为中央核心部件 （C)采用操作系统（D)存储程序和程序控制 1３.设桌面上已经有某应用程序的图标，要运行该程序，可以 C 。 青少年信息学奥林匹克竞赛情况简介 信息学奥林匹克竞赛是一项旨在推动计算机普及的学科竞赛活动，重在培养学生能力，使得有潜质有才华的学生在竞赛活动中锻炼和发展。近年来，信息学竞赛活动组织逐步趋于规范和完善，基本上形成了“地级市——省(直辖市)——全国——国际”四级相互接轨的竞赛网络。现把有关赛事情况简介如下： 全国青少年信息学（计算机）奥林匹克分区联赛： 在举办1995年NOI活动之前，为了扩大普及的面，并考虑到多数省、直辖市、自治区已经开展了多年省级竞赛，举办了首届全国青少年信息学（计算机）奥林匹克分区联赛。考虑到不同年级学生的知识层次，也为了鼓励更多的学生积极参与，竞赛设提高组、普及组，并分初、复赛进行，这样可以形成一个梯队，确保每年的竞赛活动有比较广泛扎实的基础。 从1995年起，至2001年共举办了七届全国青少年信息学奥林匹克分区联赛，每年举办一次，有选手个人奖项（省、国家级）、选手等级证书、优秀参赛学校奖项。 广东省青少年信息学（计算机）奥林匹克决赛（简称GDOI）： 省级信息学奥赛是一个水平较高的、有较大影响力的学科竞赛。由各市组织代表队参赛，参赛名额实行动态分配制度，每年举办一次。从1984年起广东省奥林匹克竞赛活动得到了蓬勃发展。奖项有个人一、二、三等奖，女选手第一、二、三名，奖励学校团体总分1-8名、市团体总分1-8名。 全国青少年信息学（计算机）奥林匹克竞赛（简称NOI）： 由中国算机学会主办的、并与国际信息学奥林匹克接轨的一项全国性青少年学科竞赛活动。1984年举办首届全国计算机竞赛。由各省市组织参赛，每年举办一次。奖项有个人一、二、三等奖，女选手第一、二、三名，各省队团体总分名次排队。 国际青少年信息学（计算机）奥林匹克竞赛（简称IOI）： 每年举办一次，由各参赛国家组队参赛。 全国青少年信息学（计算机）奥林匹克分区联赛竞赛大纲 一、初赛内容与要求：（#表示普及组不涉及，以下同） 信息学奥赛计算机基础知识复习材料 第一章计算机的概念、诞生与发展、应用、分类 一、计算机的概念：是一种能迅速而高效的自动完成信息处理的电子设备，它能按照程序对信息进行加工、处理、存储。 三、计算机的主要特点 1、惊人的运算速度； 2、很高的计算机精度； 3、超强的存储能力； 4、准确的逻辑判断能力； 5、自动控制能力。 四、计算机的主要应用： 1、数值计算： 2、数据和信息处理：其特点是数据量大，但计算相对简单。其中数据泛指计算机能处理的各种数字、图形、文字，以及声音、图像等信息。数据处理指对数据的收集、存储、加工、分析和传送的全过程。 3、过程控制：是生产自动化的重要技术内容和手段，是由计算机对所采集到的数据按一定方法经过计算，然后输出到指定执行机构去控制生产的过程。 4、计算机辅助系统：是指利用计算机帮助人们完成各种任务，包括计算机辅助设计(CAD)、计算机辅助制造(CAM)、计算机辅助测试(CAT)、计算机辅助教学(CAI)等。 CAD：即Computer Aided Design的缩写，名称为：计算机辅助设计。 CAM：即Computer Aided Manufacturing的缩写,名称为：计算机辅助制造。 CAI：Computer Aided Instruction的缩写，名称为：计算机辅助教学。 CAT：即Computer Aided Testing的缩写，名称为：计算机辅助测试。 CAE：即Computer Aided Engineering的缩写，名称为：计算机辅助工程。 5、人工智能：是指用计算机模拟人脑的思维过程，是计算机应用的重要领域。 五、计算机分类： 1、按规模分：巨型、大型、中型、小型、微型计算机。我们学校和家庭使用的计算机都微型计算机，简称微机，又称个人计算机，或简称PC机。 2、按用途分：专业计算机、通用计算机。 3、按原理分：模拟计算机、数字计算机。 六、微型机的主要技术指标 1、字长：指计算机能够直接处理的二进制数据的位数。单位为位（BIT）。 2、主频：指计算机主时钟在一秒钟内发出的脉冲数，在很大程度上决定了计算机的运算速度。 3、内存容量：是标志计算机处理信息能力强弱的一向技术指标。单位为字节（BYTE）。 8BIT=1BYTE 1024B=1KB 1024KB=1MB 4、外存容量：一般指软盘、硬盘、光盘。 七、微型计算机时代 1、第一代微型计算机通常把IBM-PC/XT及其兼容机称为第一代微型计算机。 2、第二代微型计算机286 AT机及其兼容机被称为第二代微型计算机。 3、第三代微型计算机 386微机被称为第三代微型计算机。信息学奥赛一本通算法(C 版)基础算法：高精度计算资料
信息学奥赛试题
NOIP2017全国青少年信息学奥林匹克联赛提高组初赛试题卷答案解析
信息学奥赛基础知识习题(答案版)
信息学奥赛基础知识提纲
信息学奥赛问题求解(带答案)资料
信息学奥赛——排序算法
(完整)信息学奥赛(NOIP)必看经典书目汇总,推荐文档
noip205信息学奥赛普及组初赛c++试题
信息学奥赛一本通题解目录-信息学奥赛取消
信息学奥赛基础知识讲义
高中信息学奥林匹克竞赛各种问题求解试题及参考答案集锦
信息学奥赛普及组1-18届问题求解题解析
信息学奥赛基础知识习题(标准答案版)
青少年信息学奥林匹克竞赛情况简介
信息学奥赛初赛题型、考试范围与基础知识复习材料
- 信息学奥赛简介NOIP及C基础知识第一讲PPT课件
- 信息学奥赛简介
- 信息学奥赛NOIP初赛复习知识点
- 信息学奥赛NOIP初赛复习知识点
- 信息学奥赛基础知识讲义
- 信息学奥赛考试大纲
- 信息学奥赛中解题思路重点
- noip2015信息学奥赛初赛试题
- 信息学奥赛概述
- 信息学奥赛简介NOIP及C++基础知识第一讲
- 信息学奥赛基础知识讲义全
- (完整)信息学奥赛(NOIP)必看经典书目汇总,推荐文档
- 信息学奥赛(NOIP)必看经典书目汇总
- 1信息学奥赛概述
- 信息学奥赛基础知识提纲
- 信息学奥赛基础知识习题答案版
- 信息学奥赛NOIP初赛复习知识点+基本函数
- 信息学奥赛讲义重点
- 信息学奥赛NOIP初赛复习知识点
- 第一讲_信息学奥林匹克竞赛简介