初赛的考点笔记

· · 学习·文化课

写在开头：

不知道这份2019年的资料到现在还有没有人来看，虽然比赛题目年年不同，但一般情况下不会离开这些基本内容。

一、硬件

计算机发展可划分：

第一代 1946－1958 电子管

第二代 1959－1964 晶体管

第三代 1965－1970 集成电路

第四代 1971－今 大规模集成电路

1946年2月，在美国宾夕法尼亚大学诞生了世界上第一台电子计算机ENIAC（Electronic Numerical Integrator And Computer），这台计算机占地170平方米，重30吨，用了18000多个电子管，每秒能进行5000次加法运算。

冯·诺依曼理论

1944年，美籍匈牙利数学家 冯·诺依曼 提出计算机基本结构和工作方式的设想，为计算机的诞生和发展提供了理论基础。时至今日，尽管计算机软硬件技术飞速发展，但计算机本身的体系结构并没有明显的突破，当今的计算机仍属于冯·诺依曼架构。 其理论要点如下：

  1. 计算机硬件设备由存储器、运算器、控制器、输入设备和输出设备5部分组成。
  2. 存储程序思想——把计算过程描述为由许多命令按一定顺序组成的程序，然后把程序和数据一起输入计算机，计算机对已存入的程序和数据处理后，输出结果。

    微型机的主要技术指标

    1.字长：知己算计能够直接处理的二进制数据的位数。单位为位（BIT）

2.主频：指计算机主时钟在一秒钟内发出的脉冲数，在很大程度上决定了计算机的运 算速度。

3.内存容量：是标志计算机处理信息能力强弱的一向技术指标。单位为字节（byte）。

8 BIT=1 byte,1024 B=1 KB,1024 KB=1 MB,1024 MB=1 GB,1024 GB=1 TB(理论值，1TB厂家值:1TB=1000G。1TB实际值:1TB=931G)

此处感谢@正义执行的指正

4.外存容量：一般指软盘、硬盘、光盘。

计算机的特点：

2.信息管理：企业管理、物资管理、电算化等

3.过程控制：工业自动化控制，卫星飞行方向控制

4.辅助工程：CAD（计算机辅助设计）、CAM(计算机辅助制造)、CAT（计算机化适应性测验）、CAI（计算机辅助教学） 等

计算机硬件由五大部分组成：运算器、控制器、存储器、输入设备、输出设备。

中央处理器（CPU——Central Processing Unit）

由运算器、控制器和一些寄存器组成； 运算器进行各种算术运算和逻辑运算； 控制器是计算机的指挥系统； CPU的主要性能指标是主频和字长。

存储器

内部存储器

中央处理器能直接访问的存储器称为内部存储器，它包括快速缓冲存储器和主存储器，中央处理器不能直接访问的存储器称为外部存储器，外部存储器中的信息必须调入内存后才能为中央处理器处理。 主存储器：内存也常泛称主存，但严格上说，只有当内存中只有主存，而没有快速缓冲存储器时，才能称为主存。 主存储器按读写功能，可分只读存储器（ROM）和随机存储器(RAM)两种。

外部存储器

外存储器：也称为辅助存储器，一般容量较大，速度比主存较慢。

硬盘（Hard disk）：将盘片、读写磁头及驱动装置精密地组装在一个密封盒里；采用接触式起停，非接触式读写的方式（磁盘不工作时，磁头停在磁盘表面的起停区，一旦加电后，磁头随着盘片旋转的气流“飞”起来，悬浮在磁盘表面，进行读写）。

软盘（Floppy Disk）：目前常见的是3.5英寸/1.44 MB的软盘。

光盘存储器（CD-ROM）：普通的CD-ROM，只能读，不能写； CD盘片的存储量大约是650 MB。

输入设备

二、进制与编码

十进制数转换为二进制数、八进制数、十六进制数的方法： 二进制数、八进制数、十六进制数转换为十进制数的方法：按权展开求和法

二进制与十进制间的转换：

二进制转十进制： 方法：“按权展开求和”

例：

(1011.01)_2$ $=(1×23+0×22+1×21+1×20+0×2-1+1×2-2)_{10} =(8+0+2+1+0+0.25)_{10} =(11.25)_{10}

十进制整数转二进制整数： 方法：“对二求余法”，只要不断除2，然后将余数从后往前连起来就可以。

1234/2 商  617 余数 0
 617/2 商  308 余数 1
 308/2 商  154 余数 0
 154/2 商   77 余数 0
  77/2 商   38 余数 1
  38/2 商   19 余数 0
  19/2 商    9 余数 1
   9/2 商    4 余数 1
   4/2 商    2 余数 0
   2/2 商    1 余数 0
   1/2 商    0 余数 1

结果就是 10011010010‬

十进制小数转二进制小数：采用"乘2取整，顺序排列"法。具体做法是：用2乘十进制小数，可以得到积，将积的整数部分取出，再用2乘余下的小数部分，又得到一个积，再将积的整数部分取出，如此进行，直到积中的小数部分为零，此时0或1为二进制的最后一位。或者达到所要求的精度为止。

如：0.625=（0.101）B
0.625*2=1.25      取出整数部分1
0.25*2=0.5        取出整数部分0
0.5*2=1           取出整数部分1

二进制转八进制： 方法为：3位二进制数按权展开相加得到1位八进制数。 （注意事项，3位二进制转成八进制是从右到左开始转换，不足时补0）。

八进制转成二进制： 方法为：八进制数通过除2取余法，得到二进制数，对每个八进制为3个二进制，不足时在最左边补零。

二进制转十六进制： 方法为：与二进制转八进制方法近似，八进制是取三合一，十六进制是取四合一。（注意事项，4位二进制转成十六进制是从右到左开始转换，不足时补0）。

十六进制转二进制： 方法为：十六进制数通过除2取余法，得到二进制数，对每个十六进制为4个二进制，不足时在最左边补零。

十进制转八进制或者十六进制： 把十进制转八进制或者十六进制按照除8或者16取余，直到商为0为止。

规律：个位上的数字的次数是0，十位上的数字的次数是1，......，依奖递增，而十 分位的数字的次数是-1，百分位上数字的次数是-2，......，依次递减。 注意：不是任何一个十进制小数都能转换成有限位的二进制数。

原码、反码与补码

符号位的表示：最常用的表示方法有原码、反码和补码。

  1. 原码表示法：一个机器数G由符号位和有效数值两部分组成，设符号位为G0，G真值的绝对值|G|=G1G2G3...Gn，则G的机器数原码可表示为： [G]原= ，当G>=0时，G0=0，当G<0时，G0=1。 例如：已知：G1=-1011B，G2= +1001B，则G1，G2有原码分别是 [G1] 原=11011B，[G2]原=01001B 规律：正数的原码是它本身，负数的原码是取绝对值后，在最高位（左端）补“1”。
    1. 反码表示法：一个负数的原码符号位不变，其余各位按位取反就是机器数的反码表示法。正数的反码与原码相同。 按位取反的意思是该位上是1的，就变成0，该位上是0的就变成1。即1=0，0=1
  1. 补码表示法： 首先分析两个十进制数的运算：79-38=41，79+62=141 如果使用两位数的运算器，做79+62时，多余的100因为超出了运算器两位数的范围而自动丢弃，这样在做79-38的减法时，用79+62的加法同样可以得到正确结果。

模是批一个计量系统的测量范围，其大小以计量进位制的基数为底数，位数为指数的幂。如两位十进制数的测量范围是1——9，溢出量是100，模就是102=100，上述运算称为模运算，可以写作：

79+(-38)=79+62   (mod  100)

进一步写为 -38=62，此时就说 –38的补法（对模100而言）是62。计算机是一种有限字长的数字系统，因此它的运算都是有模运算，超出模的运算结果都将溢出。n位二进制的模是2n,

一个数的补码记作[G]补，设模是M，G是真值，则补码的定义如下：

例：设字长n=8位，G=-1011011B，求[G]补。

解：因为 n=8，所以模 M=28=100000000B，G<0，所以 [G]补=M+G=100000000B-1011011B=10100101B

注意：这个G的补码的最高位是“1”，表明它是一个负数。对于二进制数还有一种更加简单的方法由原码求出补码：

  1. 正数的补码表示与原码相同；
  2. 负数的补码是将原码符号位保持“1”之后，其余各位按位取反，末位再加1便得到补码，即取其原码的反码再加“1”：[G]补=[G]反+1。

定点数和浮点数

（一）定点数（Figed-Point Number）

计算机处理的数据不仅有符号，而且大量的数据带有小数，小数点不占有二进制一位而是隐含在机器数里某个固定位置上。通常采取两种简单的约定：一种是约定所有机器数的小数的小数点位置隐含在机器数的最低位之后，叫定点纯整机器数，简称定点整数。另一种约定所有机器数的小数点隐含在符号位之后、有效部分最高位之前，叫定点纯小数机器数，简称定点小数。无论是定点整数，还是定点小数，都可以有原码、反码和补码三种形式。

（二）浮点数（Floating-Point Number）

计算机多数情况下采作浮点数表示数值，它与科学计数法相似，把一个二进制数通过移动小数点位置表示成阶码和尾数两部分：

其中：E——N的阶码（EGpoent），是有符号的整数

S——N的尾数（Mantissa），是数值的有效数字部分，一般规定取二进制定点纯小数形式。

例：1011101B=2+7G0.1011101，101.1101B=2+3G0.1011101，0.01011101B=2-1G0.1011101

浮点数由阶码和尾数两部分组成，底数2不出现，是隐含的。阶码的正负符号E0，在最前位，阶反映了数N小数点的位置，常用补码表示。二进制数N小数点每左移一位，阶增加1。尾数是这点小数，常取补码或原码，码制不一定与阶码相同，数N的小数点右移一位，在浮点数中表现为尾数左移一位。尾数的长度决定了数N的精度。尾数符号叫尾符，是数N的符号，也占一位。

例：写出二进制数-101.1101B的浮点数形式，设阶码取4位补码，尾数是8位原码。

-101.1101=-0.1011101G2+3

浮点形式为：

               阶码0011   尾数11011101

补充解释：阶码0011中的最高位“0”表示指数的符号是正号，后面的“011”表示指数是“3”；尾数11011101的最高位“1”表明整个小数是负数，余下的1011101是真正的尾数。

例：计算机浮点数格式如下，写出G=0.0001101B的规格化形式，阶码是补码，尾数是原码。

G=0.0001101=0.1101G10-3
又[-3]补=[-001B]补=[1011]补=1101B
所以  浮点数形式是  
1   101 0   1101000

ASCII码 ( American Standard Code for Information Interchange )

美国标准信息交换代码 将每个字符用7位的二进制数来表示，共有128种状态.

汉字信息编码

  1. 汉字输入码

汉字输入方法大体可分为：区位码（数字码）、音码、形码、音形码。

汉字交换码是指不同的具有汉字处理功能的计算机系统之间在交换汉字信息时所使用的代码标准。自国家标准GB2312－80公布以来，我国一直延用该标准所规定的国标码作为统一的汉字信息交换码。

GB2312－80标准包括了6763个汉字，按其使用频度分为一级汉字3755个和二级汉字3008个。一级汉字按拼音排序，二级汉字按部首排序。此外，该标准还包括标点符号、数种西文字母、图形、数码等符号682个。

由于GB2312－80是80年代制定的标准，在实际应用时常常感到不够，所以，建议处理文字信息的产品采用新颁布的GB18030信息交换用汉字编码字符集，这个标准繁、简字均处同一平台，可解决两岸三地间GB码与BIG5码间的字码转换不便的问题。

  1. 字形存储码

字形存储码是指供计算机输出汉字（显示或打印）用的二进制信息，也称字模。通常，采用的是数字化点阵字模。一般的点阵规模有16×16，24×24，32×32，64×64等，每一个点在存储器中用一个二进制位（bit）存储。例如，在16×16的点阵中，需16×16bit=32 bPte 的存储空间。在相同点阵中，不管其笔划繁简，每个汉字所占的字节数相等。 为了节省存储空间，普遍采用了字形数据压缩技术。所谓的矢量汉字是指用矢量方法将汉字点阵字模进行压缩后得到的汉字字形的数字化信息.

三、软件与操作系统

计算机软件可分为系统软件和应用软件两大类。

命令后带“…”：执行命令则弹出对话框；

带快捷键：某些菜单命令的后面标有对应的键盘命令，称为该命令的快捷键或热键；

选中标志：某些命令选项的左侧有用打勾表示的选中标志，说明此命令功能正在起作用；

命令后带“►”：级联：此命令后会有下一级的子命令菜单弹出供用户作进一步选择；

★ 快捷菜单——当鼠标位于某个对象上，单击鼠标右键，可打开有关对象的快捷菜单；

  1. 剪贴板：复制（Ctrl+C）、粘贴（Ctrl+V）、剪切（Ctrl+X） 复制屏幕图像：可将当前屏幕图形以BMP格式传送到剪贴板……
  2. 其它：查找、运行、切换Windows、进入DOS环境、文件夹选项 输入法切换，中、英文切换，半角/全角切换 软键盘：是在屏幕上显示的一个键盘图形，用户可用鼠标点击其中某个键以替代实际的按键；

四、信息安全

计算机安全(Computer Security)是指防范与保护计算机系统及其信息资源在生存过程中免受蓄意攻击、人为失误和自然灾害等引起的损失和破坏。

计算机病毒是人类自己想像和发明出来的，它是一种特殊的程序，有着与生物病毒极为相似的特点。一是寄生性，它们大多依附在别的程序上面。二是隐蔽性，它们是悄然进入系统的，人们很难察觉。三是潜伏性，它们通常是潜伏在计算机程序中，只在一定条件下才发作的。四是传染性，它们能够自我复制繁殖，通过传输媒介蔓延。五是破坏性，轻则占用一定数量的系统资源，重则破坏整个系统。

对于计算机病毒，我们不必谈虎变色，而应采取积极的防治态度。首先，要防止“病从口入”，因为病毒不是自生的，而是外来的。另外，要用优秀的防杀病毒软件，对外来的软件和资料要进行严格的检查和杀毒。注意，防杀病毒软件需要及时更新(主要是其中的数据文件)，一般每周一次，不更新基本上等于没有防杀毒功能。

20世纪50、60年代，黑客(hacker)曾是编程高手的代名词。后来，黑客成为一个独特的群体，他们通过各种渠道交流技艺，不少人以攻击计算机及其网络系统为乐趣。黑客们的胆大妄为已经给社会造成了很大的影响，一些黑客已经蜕变为威胁社会安全的罪犯。要防止“黑客”攻击，主要方法是加强安全措施，例如设置防火墙（见下图）。

防火墙是一种计算机设备，它设置在内部网络与外部网络之间，起一个隔离的作用，既可以阻止外部信息非法进入内部系统，也可以阻止内部人员非法访问外部系统。

五.网络

1．关于网络的一些定义：

所谓计算机网络，就是利用通信线路和设备，把分布在不同地理位置上的多台计算机连接起来。 计算机网络是现代通信技术与计算机技术相结合的产物。

网络中计算机与计算机之间的通信依靠协议进行。协议是计算机收、发数据的规则。

1、TCP/IP：用于网络的一组通讯协议。包括IP(Internet Protocol)和TCP(Transmission Control Protocol)。

TCP/IP是一组协议，包括上百个各种功能的协议，其中TCP 和IP是最核心的两个协议。TCP/IP 协议把Internet网络系统描述成具有四个层次功能的网络模型。

  1. 链路层：这是TCP/IP 结构的第一层，也叫网络接口层，其功能是提供网络相邻节点间的信息传输以及网络硬件和设备驱动。
  2. 网络层：（IP协议层）其功能是提供源节点和目的节点之间的信息传输服务，包括寻址和路由器选择等功能。
  3. 传输层：（TCP 协议）其功能是提供网络上的各应用程序之间的通信服务。
  4. 应用层：这是TCP/IP最高层，其功能是为用户提供访问网络环境的手段，主要提供FTP、TELNET、GOPHER等功能软件。

IP协议适用于所有类型网络。TCP 协议则处理IP协议所遗留的通信问题，为应用程序提供可靠的通信连接，并能自动适应网络的变化。TCP/IP 目前成为最为成功的网络体系结构和协议规范。

2、Netbeui：一种非常简单的协议，MICROSOFT开发。

3、IPG：用于NOVELL网络。

4、http:超文本传输协议（Hyper Text Transfer Protocol，HTTP）是一个简单的请求-响应协议，它通常运行在TCP之上。

5、https:以安全为目标的 HTTP 通道，在HTTP的基础上通过传输加密和身份认证保证了传输过程的安全性

2．网络的发展

计算机网络的发展过程大致可以分为三个阶段：

           远程终端联机阶段：主机—终端
           计算机网络阶段：计算机—计算机
           Internet阶段：  Internet

3．网络的主要功能：

（1）资源共享

（2）信息传输

（3）分布处理

（4）综合信息服务

4．网络的分类

计算机网络的分类方式有很多种,可以按地理范围、拓扑结构、传输速率和传输介质等分类。

⑴按地理范围分类

①局域网LAN(Local Area Network)

局域网地理范围一般几百米到10km 之内,属于小范围内的连网。如一个建筑物内、一个学校内、一个工厂的厂区内等。局域网的组建简单、灵活,使用方便。

②城域网MAN(Metropolitan Area Network)

城域网地理范围可从几十公里到上百公里,可覆盖一个城市或地区,是一种中等形式的网络。

③广域网WAN(Wide Area Network)

广域网地理范围一般在几千公里左右,属于大范围连网。如几个城市,一个或几个国家,是网络系统中的最大型的网络,能实现大范围的资源共享,如国际性的Internet 网络。

⑵按传输速率分类

网络的传输速率有快有慢,传输速率快的称高速网,传输速率慢的称低速网。传输速率的单位是b/s(每秒比特数,英文缩写为bps)。 一般将传输速率在Kb/s—Mb/s范围的网络称低速网, 在Mb/s—Gb/s 范围的网称高速网。 也可以将Kb/s 网称低速网,将Mb/s网称中速网,将Gb/s网称高速网。

网络的传输速率与网络的带宽有直接关系。带宽是指传输信道的宽度,带宽的单位是Hz(赫兹)。按照传输信道的宽度可分为窄带网和宽带网。 一般将KHz—MHz带宽的网称为窄带网,将MHz—GHz 的网称为宽带网,也可以将kHz 带宽的网称窄带网,将MHz 带宽的网称中带网,将GHz 带宽的网称宽带网。通常情况下,高速网就是宽带网,低速网就是窄带网。

⑶按传输介质分类

传输介质是指数据传输系统中发送装置和接受装置间的物理媒体,按其物理形态可以划分为有线和无线两大类。

①有线网

传输介质采用有线介质连接的网络称为有线网,常用的有线传输介质有双绞线、同轴电缆和光导纤维。

● 双绞线是由两根绝缘金属线互相缠绕而成,这样的一对线作为一条通信线路,由四对双绞线构成双绞线电缆。双绞线点到点的通信距离一般不能超过100m。目前,计算机网络上使用的双绞线按其传输速率分为三类线、五类线、六类线、七类线,传输速率在10Mbps到600Mbps之间,双绞线电缆的连接器一般为RJ-45。

● 同轴电缆由内、外两个导体组成,内导体可以由单股或多股线组成,外导体一般由金属编织网组成。内、外导体之间有绝缘材料,其阻抗为50Ω。同轴电缆分为粗缆和细缆,粗缆用DB-15连接器,细缆用BNC和T 连接器。

● 光缆由两层折射率不同的材料组成。内层是具有高折射率的玻璃单根纤维体组成,外层包一层折射率较低的材料。光缆的传输形式分为单模传输和多模传输,单模传输性能优于多模传输。所以,光缆分为单模光缆和多模光缆,单模光缆传送距离为几十公里,多模光缆为几公里。光缆的传输速率可达到每秒几百兆位。光缆用ST 或SC 连接器。光缆的优点是不会受到电磁的干扰,传输的距离也比电缆远，传输速率高。光缆的安装和维护比较困难,需要专用的设备。

②无线网

采用无线介质连接的网络称为无线网。目前无线网主要采用三种技术：微波通信,红外线通信和激光通信。这三种技术都是以大气为介质的。其中微波通信用途最广,目前的卫星网就是一种特殊形式的微波通信,它利用地球同步卫星作中继站来转发微波信号,一个同步卫星可以覆盖地球的三分之一以上表面,三个同步卫星就可以覆盖地球上全部通信区域。

⑷按拓扑结构分类

计算机网络的物理连接形式叫做网络的物理拓扑结构。连接在网络上的计算机、大容量的外存、高速打印机等设备均可看作是网络上的一个节点,也称为工作站。计算机网络中常用的拓扑结构有总线型、星型、环型等。

①总线拓扑结构

总线拓扑结构是一种共享通路的物理结构。这种结构中总线具有信息的双向传输功能，普遍用于局域网的连接,总线一般采用同轴电缆或双绞线。

总线拓扑结构的优点是：安装容易,扩充或删除一个节点很容易,不需停止网络的正常工作,节点的故障不会殃及系统。由于各个节点共用一个总线作为数据通路,信道的利用率高。但总线结构也有其缺点：由于信道共享,连接的节点不宜过多，并且总线自身的故障可以导致系统的崩溃。

②星型拓扑结构

星型拓扑结构是一种以中央节点为中心,把若干外围节点连接起来的辐射式互联结构。这种结构适用于局域网,特别是近年来连接的局域网大都采用这种连接方式。这种连接方式以双绞线或同轴电缆作连接线路。

星型拓扑结构的特点是：安装容易,结构简单,费用低,通常以集线器(Hub)作为中央节点,便于维护和管理。中央节点的正常运行对网络系统来说是至关重要的。

③环型拓扑结构

环型拓扑结构是将网络节点连接成闭合结构。信号顺着一个方向从一台设备传到另一台设备,每一台设备都配有一个收发器,信息在每台设备上的延时时间是固定的。

这种结构特别适用于实时控制的局域网系统。

环型拓扑结构的特点是：安装容易,费用较低,电缆故障容易查找和排除。有些网络系统为了提高通信效率和可靠性,采用了双环结构,即在原有的单环上再套一个环,使每个节点都具有两个接收通道。环型网络的弱点是,当节点发生故障时,整个网络就不能正常工作。

5．网络的体系结构

OSI 的七层体系结构：

应用层
表示层
会话层
运输层
网络层
数据链路层
物理层

6．局域网的工作方式

通常有两种：

提供资源并管理资源的计算机称为服务器；使用共享资源的计算机称客户机；

我国Internet的发展情况：

       // 八十年代末，九十年代初才起步。

1989年我国第一个公用分组交换网CNPAC建成运行。

中国公用计算机互联网（CHINANET）、中国金桥信息网（CHINAGBN） 中国教育和科研计算机网（CERNET）、中国科学技术网（CSTNET）

8．IP地址：

我们把整个Internet看作一个单一的、抽象的网络，所谓IP地址，就是为Internet中的每一台主机分配一个在全球范围唯一地址。IP v4地址是由32位二进数码表示的，为方便记记忆，把这32位二进制数每8个一段用“.” 隔开，再把每一段的二进制数化成十进制数，也就得到我们现在所看到的IP地址形式。

IP地址是用“.”隔开地四个十进制整数，每个数字取值为0—255。

IP地址分A、B、C、D；E五类，目前大量使用的是A、B、C三类，D类为Internet体系结构委员会IAB专用，E类保留在今后使用。

最高位1~126为A类，128~191是B类，192~223是C类。
具体地址范围：
A类地址范围：1.0.0.1—126.255.255.255
B类地址范围：128.0.0.1—191.255.255.255
C类地址范围：192.0.0.1—223.255.255.255

9．域名：

域名地址采用层次结构，一个域名一般有3－5个子段，中间用“. ”隔开。IP地址作为Internet 上主机的数字标识，对计算机网络来说是非常有效的。但对于使用者来说，很难记忆这些由数字组成的IP地址了。为此，人们研究出一种字符型标识，在Internet上采用“名称”寻址方案，为每台计算机主机都分配一个独有的“标准名称”，这个用字符表示的“标准名称”就是我们现在所广泛使用的域名（DN，domain name）。因此主机的域名和IP地址一样，也采用分段表示的方法。其结构一般是如下样式：计算机名.组织结构名.网络名.最高层域名。 顶级域名有三类：

有了域名标识，对于计算机用户来说，在使用上的确方便了很多。但计算机本身并不能自动识别这些域名标识，于是域名管理服务器DNS（domain name system）就应运而生了。所谓的域名管理系统DNS（domain name system）就是以主机的域名来代替其在Internet 上实际的IP 地址的系统，它负责将Internet 上主机的域名转化为计算机能识别的IP 地址。从DNS 的组织结构来看，它是一个按照层次组织的分布式服务系统；从它的运行机制来看，DNS 更像一个庞大的数据库，只不过这个数据库并不存储在任一计算机上，而是分散在遍布于整个Internet上数以千计的域名服务器中而已。

通过上面的IP 地址、域名DN 和域名管理系统DNS，就把Internet 上面的每一台主机给予了唯一的定位。三者之间的具体联系过程如下：当连接网络并输入想访问主机的域名后，由本地机向域名服务器发出查询指令，域名服务器通过连接在整个域名管理系统查询对应的IP 地址，如找到则返回相应的IP 地址，反之则返回错误信息。说到这里，想必大家都明白了为什么当我们在浏览时，浏览器左下角的状态条上会有这样的信息：“正在查找GGGGGG”、“GGGGGG已经发现，正在连接GGGGGG”，其实这也就是域名通过DNS 转化为IP地址的过程。

当然域名通过DNS转化为IP地址需要等待一段时间，因为如果你所使用的域名服务器上如果没有你所需要域名的对应IP 地址，它就会向上级域名服务器查询，如此类推，直至查到结果，或返回无效信息。一般而言，这个查询过程都非常短，你很难察觉到。

10．Internet（译为因特网或国际互联网）的服务与工具

Internet的服务有：电子邮件、远程登陆、文件传输、信息服务等；

六、NOIP的常识

全国青少年信息学奥林匹克联赛(National Olympiad in Informatics in Provinces，简称NOIP)自1995年至2018年已举办24次。每年由中国计算机学会（CCF）统一组织。 NOIP在同一时间、不同地点以各省市为单位由特派员组织。全国统一大纲、统一试卷。初、高中或其他中等专业学校的学生可报名参加联赛。联赛分初赛和复赛两个阶段。初赛考察通用和实用的计算机科学知识，以笔试形式进行。复赛为程序设计，须在计算机上调试完成。参加初赛者须达到一定分数线后才有资格参加复赛。联赛分普及组和提高组两个组别，难度不同，分别面向初中和高中阶段的学生。

复赛可使用C、C++、Pascal语言，2022年后将不可使用Pascal、C语言，只能使用C++。

七、数据结构和算法那些事

1. 树

在计算机科学中，二叉树是每个结点最多有两个子树的有序树。通常子树的根被称作“左子树”（left subtree）和“右子树”（right subtree）。二叉树常被用作二叉查找树和二叉堆或是二叉排序树。

二叉树的每个结点至多只有二棵子树(不存在度大于2的结点)，二叉树的子树有左右之分，次序不能颠倒。二叉树的第i层至多有2的i-1次方个结点；深度为k的二叉树至多有2^k -1个结点；对任何一棵二叉树T，如果其终端结点数(即叶子结点数)为n0，度为2的结点数为n_2，则n_0 = n_2 + 1。

树是由一个或多个结点组成的有限集合，其中：

  1. 必有一个特定的称为根(ROOT)的结点；

  2. 剩下的结点被分成n≥0个互不相交的集合T1、T2、......Tn，而且， 这些集合的每一个又都是树。树T1、T2、......Tn被称作根的子树(Subtree)。

树的递归定义如下：

（1）至少有一个结点（称为根）（2）其它是互不相交的子树

  1. 树的度——也即是宽度，简单地说，就是结点的分支数。以组成该树各结点中最大的度作为该树的度，如上图的树，其度为2;树中度为零的结点称为叶结点或终端结点。树中度不为零的结点称为分枝结点或非终端结点。除根结点外的分枝结点统称为内部结点。

  2. 树的深度——组成该树各结点的最大层次。

  3. 森林——指若干棵互不相交的树的集合，如上图，去掉根结点A，其原来的二棵子树T1、T2、T3的集合{T1,T2,T3}就为森林；

性质

(1) 在二叉树中，第i层的结点总数不超过2^{(i-1)}；

(2) 深度为h的二叉树最多有2^h-1个结点(h>=1)，最少有h个结点；

(3) 对于任意一棵二叉树，其所有的叶结点数为：N_0，而度为2的所有结点的数量为：N_2，则：N_0=N_2+1，请观察上图；

(4) 具有n个结点的完全二叉树的深度为int(log_2n)+1

(5)有N个结点的完全二叉树各结点如果用顺序方式存储，则结点之间有如下关系：

若I为结点编号则 如果I≠1，则其父结点的编号为I/2；

如果2×I<=N，则其左儿子（即左子树的根结点）的编号为2×I；若2×I>N，则无左儿子；

如果2×I+1<=N，则其右儿子的结点编号为2×I+1；若2×I+1>N，则无右儿子。

(6)给定N个节点，能构成h(N)种不同的二叉树。

（7）设有i个枝点，I为所有枝点的道路长度总和，J为叶的道路长度总和$J=I+2i

2.图的最短路径算法

Dijkstra（DJ斯特拉/迪杰斯特拉）

求单源、无负权的最短路。时效性较好，时间复杂度为O(V*V+E)。源点可达的话，O(V*lgV+E*lgV)=>O(E*lgV)。 　　当是稀疏图的情况时，此时E=V*V/lgV，所以算法的时间复杂度可为O(V^2)。若是斐波那契堆作优先队列的话，算法时间复杂度，则为O（V*lgV + E）。

Floyd（佛洛依德）

求多源、无负权边的最短路。用矩阵记录图。时效性较差，时间复杂度O(V^3)。 　　Floyd-Warshall算法（Floyd-Warshall algorithm）是解决任意两点间的最短路径的一种算法，可以正确处理有向图或负权的最短路径问题。 Floyd-Warshall算法的时间复杂度为O(N^3)，空间复杂度为O(N^2)。 Floyd-Warshall的原理是动态规划： 　　设Di,j,k为从i到j的只以(1..k)集合中的节点为中间节点的最短路径的长度。 　　若最短路径经过点k，则Di,j,k = Di,k,k-1 + Dk,j,k-1； 　　若最短路径不经过点k，则Di,j,k = Di,j,k-1。 　　因此，Di,j,k = min(Di,k,k-1 + Dk,j,k-1 , Di,j,k-1)。 在实际算法中，为了节约空间，可以直接在原来空间上进行迭代，这样空间可降至二维。 　　Floyd-Warshall算法的描述如下：

　　for k ← 1 to n do
　　for i ← 1 to n do
　　for j ← 1 to n do
　　if (Di,k + Dk,j < Di,j) then
　　Di,j ← Di,k + Dk,j;

　　其中Di,j表示由点i到点j的代价，当Di,j为 ∞ 表示两点之间没有任何连接 [2] 。 Bellman-Ford 求单源最短路，可以判断有无负权回路（若有，则不存在最短路）， 　　时效性较好，时间复杂度O(VE)。 Bellman-Ford算法是求解单源最短路径问题的一种算法。 单源点的最短路径问题是指：

　　给定一个加权有向图G和源点s，对于图G中的任意一点v，求从s到v的最短路径。

与Dijkstra算法不同的是，在Bellman-Ford算法中，边的权值可以为负数。 设想从我们可以从图中找到一个环路（即从v出发，经过若干个点之后又回到v）且这个环路中所有边的权值之和为负。那么通过这个环路，环路中任意两点的最短路径就可以无穷小下去。如果不处理这个负环路，程序就会永远运行下去。 而Bellman-Ford算法具有分辨这种负环路的能力。

SPFA

是Bellman-Ford的队列优化，时效性相对好，时间复杂度O(kE)\;\;\;(k<<V)。 与Bellman-ford算法类似，SPFA算法采用一系列的松弛操作以得到从某一个节点出发到达图中其它所有节点的最短路径。所不同的是，SPFA算法通过维护一个队列，使得一个节点的当前最短路径被更新之后没有必要立刻去更新其他的节点，从而大大减少了重复的操作次数。 SPFA算法可以用于存在负数边权的图，这与dijkstra算法是不同的。 与Dijkstra算法与Bellman-ford算法都不同，SPFA的算法时间效率是不稳定的，即它对于不同的图所需要的时间有很大的差别。 在最好情形下，每一个节点都只入队一次，则算法实际上变为广度优先遍历，其时间复杂度仅为O(E)。另一方面，存在这样的例子，使得每一个节点都被入队(V-1)次，此时算法退化为Bellman-ford算法，其时间复杂度为O(VE)。 SPFA算法在负边权图上可以完全取代Bellman-ford算法，另外在稀疏图中也表现良好。但是在非负边权图中，为了避免最坏情况的出现，通常使用效率更加稳定的Dijkstra算法，以及它的使用堆优化的版本。通常的SPFA算法在一类网格图中的表现不尽如人意。

3.排序算法

（感谢 Stand1210提供的动画演示）

各算法演示：

  1. 插入排序
  2. 冒泡排序
  3. 选择排序
  4. 快速排序
  5. 归并排序 各算法时间复杂度：

八、排列与组合

都在这：排列与组合

九、 写运行结果（阅读程序）

写运行结果的题，大家一定不要错过这个得分点。对于简单的问题（没有循环或者循环次数很少），机械的模拟是可行的，只要仔细即可。

//例1：
#include<iostream>
using namespace std;
int b,c,i,h,a[14];
int main()
{
    for(i=1;i<=10;i++)
    cin>>a[i];
    cin>>h;
    h=h+3;
    for(i=1;i<=10;i++)
     if(h>=a[i])c=c+1;
     cout<<c;
    return 0;
}

输入：

1 3 5 6 7 8 9 10 14 23
3

输出：_____

解析：

这题简单，先输入10个数，再输入h，h加3后再与前10个数比较，h+3>=a[i]的c就加一，最后输出结果。这题用“直接模拟”简单。

答案：4

//例2：
#include<bits/stdc++.h>
using namespace std;
int n,s=0,t=0,i,j,a[10001];
int main()
{
    cin>>n;
    for(i=1;i<=n;i++)
    cin>>a[i];
    for(i=1;i<=n-1;i++)
     for(j=1;j<=n-i;j++)
     if(a[j]>a[j+1])
     {
        swap(a[j],a[j+1]);s++;
     }
     cout<<s;
    return 0;
}

输入：

6
2 1 4 5 3 6

输出：____

解析：

这题就稍微难了，先输入n个数，再二重循环比较。敏锐的同学发现这和冒泡排序很像，只要输出它交换了几次就可以了。这题用“归纳法”解决。

答案：3

//例3：
#include<bits/stdc++.h>
using namespace std;
int n,i,j;
string a[31];
int comp(int a,int b){return a>b;}
int main()
{   
    cin>>n;
    for(i=1;i<=n;i++) cin>>a[i];
   for(i=1;i<n;i++){
        for(j=i+1;j<=n;j++){
            if(a[j]+a[i]>a[i]+a[j]) {swap(a[j],a[i]);}
        }
    }
    for(i=1;i<=n;i++)cout<<a[i];
    return 0;  
}

输入：

6
12 87 34 75 89 800

输出：___

解析：

这题比上一题难，先输入n个数，再进行比较。有同学发现这和冒泡排序也很像，但是数据类型要注意，所以不是简单的比较。仔细带简单的几个数据模拟能发现这题是要求排列这些数字使组成（首尾相接）的数字最大，所以排出来的顺序为：

89 87 800 75 34 12
//排序方法：先比最高位，相同的再比次高位，这样比下去。

这题用“规律法”解决。

（还有，那个comp函数没有用。可以不管，但是初赛中每一行代码可能都有用！）

输出：8987800753412(数字间没有空格分开，这是个坑)

几大方法

a. 直接模拟

b. 先模拟几次循环后找规律

c. 直接看程序了解算法功能

d. 了解程序本质后换一个方法解决

e. 有时不知道算法可以通过观察猜出来

f. 极少数的格子可以放弃

一般做这类题目的核心是找程序目的，即这个程序想干什么。很少有复杂的程序是“乱写”的，总有一点“写作目的”。抓住了它，不仅得出答案变得很容易了，而且对自己的结果也会比较有信心。机械模仿计算机硬算出结果的同学往往做的慢的多，而且容易失误。

十、补全代码

例：木材厂有一些原木，现在想把这些木头切割成一些长度相同的小段木头（木头有可能有 剩余），需要得到的小段的数目是给定的。当然，我们希望得到的小段越长越好，你的任务 是计算能够得到的小段木头的最大长度。木头长度的单位是cm。原木的长度都是正整数， 我们要求切割得到的小段木头的长度也是正整数。

输入:

第一行是两个正整数N和K(1 ≤ N ≤ 10000，1 ≤ K ≤ 10000)，N是原木的数目，

K是需要得到的小段的数目。

接下来的N行，每行有一个1到10000之间的正整数，表示一根原木的长度。

输出:

输出能够切割得到的小段的最大长度。如果连1cm长的小段都切不出来，输出”0”。

输入样例:

3 7
232
124
456

输出样例:

114

程序：

#include<bits/stdc++.h>
using namespace std;
int n,k;
int len[10000];
int i,left,right,mid;
bool isok(int t)
{
    int num=0;
    for(i=1;i<=n;i++)if(num>=k){break;num=__1__;}
    if(__2__)return true;
    else return false;
}  
int main()
{
    cin>>n>>k;right=0;
    for(i=1;i<=n;i++){
        cin>>len[i];
        if(right<len[i])right=len[i];
    }
    right++;__3__;
    while(__4__<right){
        mid=(left+right)/2;
        if(__5__) right=mid;
        else left=mid;
    }
    cout<<left;
    return 0;
}

答案：

1      num + len[i] / t                       　       
2   　 num >= k　　　　                　  
3  　  left = 0  　
4      left + 1               　        　
5   ! isok(mid) （或者 isok(mid) = false）

（就更到这了。。。）

(图片来自：360百科，Stand1210, 百度百科)