第四章、计算机网络

1.网络功能和分类

• 计算机网络是计算机技术与通信技术相结合的产物，它实现了远程通信、远程信息处理和资源共享。 计算机网络的功能：数据通信、资源共享、负载均衡、高可靠性。

• 计算机网络按分布范围和拓扑结构划分如下图所示：

• 个域网 家庭 3-5M

  

• 总线型（利用率低、干扰大、价格低）、星型（交换机形成的局域网、中央单元负荷大）、环型（流动方向固定、效率低扩充难）、树型（总线型的扩充、分级结构）、分布式（任意节点连接、管理难成本高）

  

OSI七层模型

局域网和广域网协议

以太网规范IEEE 802.3是重要的局域网协议，包括：

IEEE 802.3 标准以太网 10Mb/s 传输介质为细同轴电缆 IEEE 802.3u 快速以太网 100Mb/s 双绞线 IEEE 802.3z 千兆以太网 1000Mb/s 光纤或双绞线 IEEE 802.Зaе 万兆以太网 10Gb/s 光纤

无线局域网WLAN技术标准：IEEE 802.11

广域网协议包括：PPP点对点协议、ISDN综合业务数字网、xDSL（DSL数字用户线路的统称：HDSL、SDSL、MVL、ADSL）、DDN数字专线、x.25、FR帧中继、ATM异步传输模式。

TCP/IP协议

• 网络协议三要素：语法、语义、时序，其中语法部分规定传输数据的格式，语义部分规定所要完成的功能，时序部分规定执行各种操作的条件、顺序关系等。

  

网络层协议：

• IP：网络层最重要的核心协议，在源地址和目的地址之间传送数据报，无连接、不可靠。
• ICMP：因特网控制报文协议，用于在IP主机、路由器之间传递控制消息。控制消息是指网络通不通、主机是否可达、路由是否可用等网络本身的消息。 址。
• ARP和RARP：地址解析协议，ARP是将IP地址转换为物理地址，RARP是将物理地址转换为IP地IGMP：网络组管理协议，允许因特网中的计算机参加多播，是计算机用做向相邻多目路由器报告多目组成员的协议，支持组播。

传输层协议：

• TCP：整个TCP/IP协议族中最重要的协议之一，在IP协议提供的不可靠数据数据基础上，采用了重发技术，为应用程序提供了一个可靠的、面向连接的、全双工的数据传输服务。一般用于传输数据量比较少，且对可靠性要求高的场合。
• UDP：是一种不可靠、无连接的协议，有助于提高传输速率，一般用于传输数据量大，对可靠性要求不高，但要求速度快的场合。

应用层协议：基于TCP的FTP、HTTP等都是可靠传输。基于UDP的DHCP、DNS等都是不可靠传输。

• FTP：可靠的文件传输协议，用于因特网上的控制文件的双向传输。
• HTTP：超文本传输协议，用于从wwW服务器传输超文本到本地浏览器的传输协议。使用SSL加密后的安全网页协议为HTTPS。
• SMTP和POP3：简单邮件传输协议，是一组用于由源地址到目的地址传送邮件的规则，邮件报文采用ASC11格式表示。
• Telnet：远程连接协议，是因特网远程登录服务的标准协议和主要方式。
• TFTP：不可靠的、开销不大的小文件传输协议。
• SNMP：简单网络管理协议，由一组网络管理的标准协议，包含一个应用层协议、数据库模型和一组资源对象。该协议能够支持网络管理系统，泳衣监测连接到网络上的设备是否有任何引起管理师行关注的情况。
• DHCP：动态主机配置协议，基于UDP，基于C/S模型，为主机动态分配IP地址，有三种方式：固定分配、动态分配、自动分配。
• DNS：域名解析协议，通过域名解析出IP地址。

协议端口号对照表

考试真题

• 在OSI参考模型中能实现路由选择、拥塞控制与互连功能的层是（）。 A.传输层 B.应用层 C.网络层 D.物理层

  答案：C

• 在TCP/IP体系结构中，将IP地址转化为MAC地址的协议是（）。

  A、RARP B、ARP C、ICMP D、TCP

  答案：B

• 下列网络互连设备中，属于物理层的是（）。

  A.交换机 B.中继器 C.路由器 D.网桥

  答案：B

2.传输介质

• 双绞线：将多根铜线按规则缠绕在一起，能够减少干扰；分为无屏蔽双绞线UTP和屏蔽双绞线STP，都是由一对铜线簇组成。也即我们常说的网线；双绞线的传输距离在100m以内。

• 无屏蔽双绞线UTP：价格低，安装简单，但可靠性相对较低，分为CAT3（3类UTP，速率为1OMbps）、CAT4（4类UTP，与3类差不多，无应用）、CAT5（5类UTP，速率为10OMbps，用于快速以太网）、CAT5E（超5类UTP，速率为1000Mbps）、CAT6（6类UTP，用来替代CAT5E，速率也是1000Mbps）

• 屏蔽双绞线STP：比之UTP增加了一层屏蔽层，可以有效的提高可靠性，但对应的价格高，安装麻烦，一般用于对传输可靠性要求很高的场合。

• 网线有如下两种安装标准：都是八根不同颜色的网线，按照不同的顺序排序，插入水晶头中，区分在第1236四根网线的位置不同。

  

• 光纤：由纤芯和包层组成，传输的光信号在纤芯中传输，然而从PC端出来的信号都是电信号，要经过光纤传输的话，就必须将电信号转换为光信号。

• 多模光纤MMF：纤芯半径较大，因此可以同时传输多种不同的信号，光信号在光纤中以全反射的形式传输，采用**发光二极管LED为光源，成本低，但是传输的效率和可靠性都较低，适合于短距离传输，**其传输距离与传输速率相关，速率为100Mbps时为2KM，速率为1000Mbps时为550m。

  

• 单模光纤SMF：纤芯半径很小，**一般只能传输一种信号，采用激光二极管LD作为光源，并且只支持激光信号的传播，同样是以全反射形式传播，只不过反射角很大，看起来像一条直线，成本高，但是传输距离远，可靠性高。**传输距离可达5KM。

  

• 无线信道：分为无线电波和红外光波

  

通信方式和交换方式

• 通信方向：数据通信是指发送方发送数据到接收方，这个传输过程可以分类如下：

  • 单工：只能由设备A发给设备B，即数据流只能单向流动。
  • 半双工：设备A和设备B可以互相通信，但是同一时刻数据流只能单向流动。
  • 全双工：设备A和设备B在任意时刻都能互相通信。

  

同步方式

• 异步传输：发送方每发送一个字符，需要约定一个起始位和停止位插入到字符的起始和结尾处，这样当接收方接收到该字符时能够识别，但是这样会造成资源浪费，传输效率降低。
• 同步传输：以数据块为单位进行传输，当发送方要发送数据时，先发送一个同步帧，接收方收到后做好接收准备，开始接收数据块**，结束后又会有结束帧确认**，这样一次传输一个数据块，效率高。
• 串行传输：只有一根数据线，数据只能1bit挨个排队传送，适合低速设备、远距离的传送，一般用于广域网中。
• 并行传输：有多根数据线，可以同时传输多个bit数据，适合高速设备的传送，常用语计算机内部各硬件模块之间。

交换方式

• 电路交换：通信一方进行呼叫，另一方接收后，在二者之间会建立一个专用电路，特点为面向连接、实时性高、链路利用率低，一般用于语音视频通信。
• 报文交换：以报文为单位，存储转发模式，接收到数据后先存储，进行差错校验，没有错误则转发，有错误则丢弃，因此会有延时，但可靠性高，是面向无连接的。
• 分组交换：**以分组为单位，也是存储转发模式，**因为分组的长度比报文小，所以时延小于报文交换，又可分为三种方式：
  • 数据报：是现在主流的交换方式，各个分组携带地址信息，自由的选择不同的路由路径传送到接收方，接收方接收到分组后再根据地址信息重新组装成原数据，是面向无连接的，但是不可靠的。
  • 虚电路：发送方发送一个分组，接收方收到后二者之间就建立了一个虚拟的通信线路，二者之间的分组数据交互都通过这条线路传送，在空闲的时候这条线路也可以传输其他数据，是面向连接的，可靠的。
  • 信元交换：异步传输模式ATM采用的交换方式，本质是按照虚电路方式进行转发，只不过信元是固定长度的分组，共53B，其中5B为头部，48B为数据域，也是面向连接的，可靠的。.

考试真题

• 以下关于光纤的说法中，错误的是（）

  A.单模光纤的纤芯直径更细

  B.单模光纤采用LED作为光源

  C.多模光纤比单模光纤的传输距离近

  D.多模光纤中光波在光导纤维中以多种模式传播

  答案 ：B

• 数据通信模型按照数据信息在传输链路上的传送方向，可以分为三类。下列选项中，（）不属于这三类传输方式。

  A、单工通信：信号只能向一个方向传送

  B、半双工通信：信息的传递可以是双向的

  C、全双工通信：通信的双方可以同时发送和接收信息

  D、全单工通信：信号同时向两个方向传输

  答案：D

3.IP地址表示

• 机器中存放的IP地址是32位的二进制代码，每隔8位插入一个空格，可提高可读性，为了便于理解和设置，一般会采用点分十进制方法来表示：将32位二进制代码每8位二进制转换成十进制，就变成了4个十进制数，而后在每个十进制数间隔中插入.，如下所示，最终为128.11.3.31：

• 因为每个十进制数都是由8个二进制数转换而来，因此每个十进制数的取值范围为0-255（掌握二进制转十进制的快速计算方法，牢记2的幂指数值，实现快速转换）。

• 分类IP地址：IP地址分四段，每段八位，共32位二进制数组成。 在逻辑上，这32位IP地址分为网络号和主机号，依据网络号位数的不同，可以将IP地址分为以下几类：

  

• 无分类编址：即不按照A B C类规则，自动规定网络号，无分类编址格式为：IP地址/网络号，示例： 128.168.0.11/20表示的IP地址为128.168.0.11，其网络号占20位，因此主机号占32-20=12位，也可以划分子网。

• 特殊IP地址

  • 公有地址：通过它直接访问因特网。是全网唯一的IP地址。
  • 私有地址：属于**非注册地址，专门为组织机构内都使用，**不能直接访问因特网，下表所示为私有地址范围。

  

• 其他特殊地址如下表所示：

  

子网划分

• 子网划分：一般公司在申请网络时，会直接获得一个范围很大的网络，如一个8类地址，因为主机数之间相差的太大了，不利于分配，我们一般采用子网划分的方法来划分网络，即自定义网络号位数，就能自定义主机号位数，就能根据主机个数来划分出最适合的方案，不会造成资源的浪费。
• 因此就有子网的概念，一般的IP地址按标准划分为ABC类后，可以进行再一步的划分，将主机号拿出几位作为子网号，就可以划分出多个子网，此时IP地址组成为：网络号+子网号+主机号。
• 网络号和子网号都为1，主机号都为0，这样的地址为子网掩码。
• 要注意的是：子网号可以为全0和全1，**主机号不能为全0或全1，因此，主机数需要-2，**而子网数不用。
• 还可以聚合网络为超网，就是划分子网的逆过程，将**网络号取出几位作为主机号，**此时，这个网络内的主机数量就变多了，成为一个更大的网络。

考试真题

• 把网络117.15.32.0/23划分为117.15.32.0/27，得到的子网是（）个，每个子网中可使用的主机地址是（）个 A.4 B.8 C.16 D.32 A.30 B.31 C.32 D.34

  答案：C A

• 分配给某公司网络的地址块是220.17.192.0/20，该网络被划分为（）个C类子网，不属于该公司网络的子网地址是（）

  A.4 B.8 C.16 D.32 A.220.17.203.0 B.220.17.205.0 C.220.17.207.0 D.220.17.213.0

  答案：C D

4.IPv6-网络规划

• 主要是为了解决IPv4地址数不够用的情况而提出的设计方案，IPv6具有以下特性：

• IPv6地址长度为128位，地址空间增大了2^96倍；

• 灵活的IP报文头部格式，使用一系列固定格式的扩展头部取代了IPv4中可变长度的选项字段。IPv6中选项部分的出现方式也有所变化，使路由器可以简单撸过选项而不做任何处理，加快了报文处理速度；

• IPv6简化了报文头部格式，加快报文转发，提高了吞吐量；

• 提高安全性，身份认证和隐私权是IPv6的关键特性；支持更多的服务类型；

• 允许协议继续演变，增加新的功能，使之适应未来技术的发展。

• IPv4和IPv6的过渡期间，主要采用三种基本技术：

  （1）双协议栈：主机同时运行IPv4和IPv6两套协议栈，同时支持两套协议，一般来说IPv4和IPv6地址之间存在某种转换关系，如IPv6的低32位可以直接转换为IPv4地址，实现互相通信。 （2）隧道技术：这种机制用来在IPv4网络之上建立一条能够传输IPv6数据报的隧道，例如可以将IPv6数据报当做IPv4数据报的数据部分加以封装，只需要加一个IPv4的首部，就能在1Pv4网络中传输IPv6报文。 （3）翻译技术：利用一台专门的翻译设备（如转换网关），在纯IPv4和纯1Pv6网络之间转换IP报头的地址，同时根据协议不同对分组做相应的语义翻译，从而使纯1Pv4和纯1Pv6站点之间能够透明通信。

网络规划与设计

• 三层模型将网络划分为核心层、汇聚层和接入层，每一层都有着特定的作用。

• 核心层提供不同区域之间的最佳路由和高速数据传送；

• 汇聚层将网络业务连接到接入层，并且实施与安全、流量、负载和路由相关的策略；

• 接入层为用户提供了在本地网段访问应用系统的能力，还要解决相邻用户之间的互访需要，接入层要负责一些用户信息（例如用户IP地址、MAC地址和访问日志等）的收集工作和用户管理功能（包括认证和计费等）。

  

• 建筑物综合布线系统PDS： （1）工作区子系统：实现工作区终端设备到水平子系统的信息插座之间的互联。 （2）水平布线子系统：实现信息插座和管理子系统之间的连接。 （3）设备间子系统：实现中央主配线架与各种不同设备之间的连接。 （4）垂直干线子系统：实现各楼层设备间子系统之间的互连。 （5）管理子系统：连接各楼层水平布线子系统和垂直干缆线，负责连接控制其他子系统为连接其他子系统提供连接手段。 （6）建筑群子系统：各个建筑物通信系统之间的互联。

  

考试真题

• 以下关于层次化局域网模型中核心层的叙述，正确的是（）。

  A.为了保障安全性，对分组要进行有效性检查

  B.将分组从一个区域高速地转发到另一个区域

  C.由多台二、三层交换机组成

  D.提供多条路径来缓解通信瓶颈

  答案: B

• 结构化布线系统分为六个子系统，其中水平子系统（）。

  A.由各种交叉连接设备以及集线器和交换机等设备组成

  B.连接了干线子系统和工作区子系统，

  C.由终端设备到信息插座的整个区域组成

  D.实现各楼层设备间子系统之间的互连

  答案：B

5.磁盘冗余阵列

• RAID即磁盘冗余阵列技术，将数据分散存储在不同磁盘中，可并行读取，可冗余存储，提高磁盘访问速度，保障数据安全性。

• RAID0将数据分散的存储在不同磁盘中，磁盘利用率100%，访问速度最快，但是没有提供冗余和错误修复技术；

• RAID1在成对的独立磁盘上产生互为备份的数据，增加存储可靠性，可以纠错，但磁盘利用率只有50%；

  

• RAID2将数据条块化的分布于不同硬盘上，并使用海明码校验；

• RAID3使用奇偶校验，并用单块磁盘存储奇偶校验信息（可靠性低于RAID5）；

• RAID5在所有磁盘上交叉的存储数据及奇偶校验信息（所有校验信息存储总量为一个磁盘容量，但分布式存储在不同的磁盘上），读/写指针可同时操作；

  

• RAID0+1（是两个RAIDO，若一个磁盘损坏，则当前RAIDO无法工作，即有一半的磁盘无法工作）；

• RAID1+0（是两个RAID1，不允许同一组中的两个磁盘同时损坏）与RAID1原理类似，磁盘利用率都只有50%，但安全性更高。

  

网络存储技术

• 1，直接附加存储（DAS）：是指将存储设备通过SCS1接口直接连接到一台服务器上使用，其本身是硬件的堆叠，存储操作依赖于服务器，不带有任何存储操作系统。

  • 存在问题：在传递距离、连接数量、传输速率等方面都受到限制。容量难以扩展升级；数据处理和传输能力降低；服务器异常会波及存储器。

• 2，网络附加存储（NAS）：**通过网络接口与网络直接相连，由用户通过网络访问，**有独立的存储系统。 如下图所示。NAS存储设备类似于一个专用的文件服务器，去掉了通用服务器大多数计算功能，而仅仅提供文件系统功能。以数据为中心，将存储设备与服务器分离，其存储设备在功能上完全独立于网络中的主服务器。客户机与存储设备之间的数据访问不再需要文件服务器的干预，同时它允许客户机与存储设备之间进行直接的数据访问，所以不仅响应速度快，而且数据传输速率也很高。

  • NAS的性能特点是进行小文件级的共享存取；支持即插即用；可以很经济的解决存储容量不足的问题，但难以获得满意的性能。

  

• 3，存储区域网（SAN）：SAN是通过专用交换机将磁盘阵列与服务器连接起来的高速专用子网。它没有采用文件共享存取方式，而是采用块（block）级别存储。SAN是通过专用高速网将一个或多个网络存储设备和服务器连接起来的专用存储系统，其最大特点是将存储设备从传统的以太网中分离了出来，成为独立的存储区域网络SAN的系统结构。根据数据传输过程采用的协议，其技术划分为FC SAN（光纤通道）、IP SAN（IP网络）和IB SAN（无线带宽）技术。

6.其他考点

• 网络地址翻译NAT：公司内有很多电脑，在公司局域网内可以互联通信，但是要访问外部因特网时，只提供固定的少量IP地址能够访问因特网，将公司所有电脑这个大的地址集合映射到能够访问因特网的少量IP地址集合的过程就称为NAT。 很明显，使用了NAT后，一个公司只有少量固定IP地址可以上网，大大减少了IP地址的使用量。
• 默认网关：一台主机可以有多个网关。默认网关的意思是一台主机如果找不到可用的网关，就把数据包发给默认指定的网关，由这个网关来处理数据包。现在主机使用的网关，一般指的是默认网关。默认网关的IP地址必须与本机IP地址在同一个网段内，即同网络号。
• 虚拟局域网VLAN：是一组逻辑上的设备和用户，这些设备和用户并不受物理位置的限制，可以根据功能、部门及应用等因素将它们组织起来，相互之间的通信就好像它们在同一个网段中一样。
• VLAN工作在OSI参考模型的第2层和第3层，一个VLAN就是一个广播域，VLAN之间的通信是通过第3层的路由器来完成的。
• 与传统的局域网技术相比较，VLAN技术更加灵活，它具有以下优点：网络设备的移动、添加和修改的管理开销减少；可以控制广播活动；可提高网络的安全性。
• 虚拟专用网VPN/是在公用网络上建立专用网络的技术。其之所以称为虚拟网，主要是因为整个VPN网络的任意两个节点之间的连接并没有传统专网所需的端到端的物理链路，而是架构在公用网络服务商所提供的网络平台，如Internet、ATM（异步传输模式〉、Frame Relay（帧中继）等之上的逻辑网络，用户数据在逻辑链路中传输。
• PPP：安全认证介绍：PPP的NCP可以承载多种协议的三层数据包。PPP使用LCP控制多种链路的参数（建立、认证、压缩、回拨）。
• PPP的认证类型：pap认证是通过二次握手建立认证（明文不加密），chap挑战握手认证协议，通过三次握手建立认证（密文采用MD5加密）。PPP的双向验证，采用的是chap的主验证风格。PPP的加固验证，采用的是两种（pap，chap）验证同时使用
• 冲突域和广播域：路由器可以阻断广播域和冲突域，交换机只能阻断冲突域，因此一个路由器下可以划分多个广播域和多个冲突域；一个交换机下整体是一个广播域，但可以划分多个冲突域；而物理层设备集线器下整体作为一个冲突域和一个广播域。

考试真题

• VLANZ一个虚拟局域网是一个（）

  A.广播城 B.冲突域 C.组播域 D.物理上隔离的区域

  答案 ：A

• 以下关于URL的说法中，错误的是（）

  A.使用www.abC.com和abC.com打开的是同一个页面

  B.在地址栏中输入www.abC.com默认使用http协议

  C.www.abC.com中的"www"是主机名

  D.www.abC.com中的"abC.com"是域名

  答案：A

第五章、信息安全技术

1.信息安全和信息系统安全

• 信息安全系统的体系架构 x轴是“安全机制”，为提供某些安全服务，利用各种安全技术和技巧，所形成的一个较为完善的机构体系。 Y轴是“OSI网络参考模型”。 z轴是“安全服务”。就是从网络中的各个层次提供给信息应用系统所需要的安全服务支持。 由X、Y、z三个轴形成的信息安全系统三维空间就是信息系统的“安全空间”。

• 随着网络逐层扩展，这个空间不仅范围逐步加大，安全的内涵也就更丰富，达到具有认证、权限、完整、加密和不可否认五大要素，也叫作“安全空间"的五大属性。

  

• 信息安全含义及属性：保护信息的保密性、完整性、可用性，另外也包括其他属性，如：真实性、可核查性、不可抵赖性和可靠性。

• 保密性：信息**不被泄漏给未授权的个人、实体和过程或不被其使用的特性。**包括：（1）最小授权原则（2）防暴露（3）信息加密（4）物理保密

• 完整性：信息**未经授权不能改变的特性。**影响完整性的主要因素有设备故障、误码、人为攻击和计算机病毒等。保证完整性的方法包括： （1）协议：通过安全协议检测出被删除、失效、被修改的字段。 （2）纠错编码方法：利用校验码完成检错和纠错功能。 （3）密码校验和方法。 （4）数字签名：能识别出发送方来源。 （5）公证：请求系统管理或中介机构证明信息的真实性。

• 可用性：**需要时，授权实体可以访问和使用的特性。**一般用系统正常使用时间和整个工作时间之比来度量。

其他属性：

• 真实性：指对信息的来源进行判断，能对伪造来源的信息予以鉴别。
• 可核查性：系统实体的行为可以被独一无二的追溯到该实体的特性，这个特性就是要求该实体对其行为负责，为探测和调查安全违规事件提供了可能性。
• 不可抵赖性：是指建立有效的责任机制，防止用户否认其行为，这一点在电子商务中是极其重要的。
• 可靠性：系统在规定的时间和给定的条件下，无故障地完成规定功能的概率。

安全需求

• 可划分为**物理线路安全、网络安全、系统安全和应用安全；**从各级安全需求字面上也可以理解：
  • 物理线路就是物理设备、物理环境；
  • 网络安全指网络上的攻击、入侵；
  • 系统安全指的是操作系统漏洞、补丁等；
  • 应用安全就是上层的应用软件，包括数据库软件。

考试真题

• 在网络安全管理中，加强内防内控可采取的策略有（）。 ①控制终端接入数量 ②终端访问授权，防止合法终端越权访问 ③加强终端的安全检查与策略管理 ④加强员工上网行为管理与违规审计 A.②③ C.①②③④ B.②④ D.②③④

  答案：C

• 在网络设计和实施过程中要采取多种安全措施，其中（）是针对系统安全需求的措施。 A.设备防雷击 B.入侵检测 C.漏洞发现与补丁管理 D.流量控制

  答案：C

2.信息安全技术

加密技术

• 一个密码系统，通常简称为密码体制（Cryptosystem），由五部分组成：

  （1）明文空间M，它是全体明文的集合。

  （2）密文空间C，它是全体密文的集合。

  （3）密钥空间k，它是全体密钥的集合。其中每一个密钥K均由加密密钥Ke和解密密钥Kd组成，即K-< Ke，Kd>

  （4）加密算法E，它是一组由M至C的加密变换。

  （5）解密算法D，它是一组由C到M的解密变换。

• 对于明文空间M中的每一个明文M，加密算法E在密钥Ke的控制下将明文M加密成密文C：C-E（M，Ke）

• 而解密算法D 在密钥kd的控制下将密文C解密出同一明文M：M=D（C，Kd）=D（E（M，Ke），Kd）

  

对称加密技术

• 数据的加密和解密的密钥（密码）是相同的，属于不公开密钥加密算法。其缺点是加密强度不高（因为密钥位数少），且密钥分发困难（因为密钥还需要传输给接收方，也要考虑保密性等问题）。优点是加密速度快，适合加密大数据。

• 常见的对称密钥加密算法如下：

  3DES：三重DES，两个56位密钥K1、K2。

  DES：替换+移位、56位密钥、64位数据块、速度快，密钥易产生。

  • 加密：K1加密->K2解密->K1加密。
  • 解密：K1解密->K2加密->K1解密

• AES：是美国联邦政府采用的一种区块加密标准，这个标准用来替代原先的DES。对其的要求是“至少像3DES一样安全”。

• RC-5：RSA数据安全公司的很多产品都使用了RC-5。

• IDEA：128位密钥，64位数据块，比DES的加密性好，对计算机功能要求相对低。

非对称加密技术

• 数据的加密和解密的密钥是不同的，分为公钥和私钥。是公开密钥加密算法。 其缺点是加密速度慢。优点是安全性高，不容易破解。

• 非对称技术的原理是：发送者发送数据时，使用接收者的公钥作加密密钥，私钥作解密密钥，这样只有接收者才能解密密文得到明文。安全性更高，因为无需传输密钥。但无法保证完整性。如下：

  

• 常见的非对称加密算法如下:

  • RSA：512位（或1024位）密钥，计算机量极大，难破解。
  • Elgamal，ECC（椭圆曲线算法）、背包算法、Rabin，D-H等。

• 相比较可知，对称加密算法密钥一般只有56位，因此加密过程简单，适合加密大数据，也因此加密强度不高；而非对称加密算法密钥有1024位，相应的解密计算量庞大，难以破解，却不适合加密大数据，一般用来加密对称算法的密钥，这样，就将两个技术组合使用了，这也是数字信封的原理：

• 数字信封原理：信是对称加密的密钥，**数字信封就是对此密钥进行非对称加密，**具体过程：发送方将数据用对称密钥加密传输，而将对称密钥用接收方公钥加密发送给对方。接收方收到数字信封，用自己的私钥解密信封，取出对称密钥解密得原文。

• 数字信封运用了对称加密技术和非对称加密技术，本质是使用对称密钥加密数据，非对称密钥加密对称密钥，解决了对称密钥的传输问题。

信息摘要

• 所谓信息摘要，就是一段数据的特征信息，当数据发生了改变，信息摘要也会发生改变，发送方会将数据和信息摘要一起传给接收方，接收方会根据接收到的数据重新生成一个信息摘要，若此摘要和接收到的摘要相同，则说明数据正一确。信息摘要是由哈希函数生成的。
• 信息摘要的特点：不算数据多长，都会产生固定长度的信息摘要；任何不同的输入数据，都会产生不同的信息摘要；单向性，即只能由数据生成信息摘要，不能由信息摘要还原数据。
• 信息摘要算法：MD5（产生128位的输出）、SHA-1（安全散列算法，产生160位的输出，安全性更高）。

数字签名：唯一标识一个发送方。

• 发送者发送数据时，使用发送者的私钥进行加密，接收者收到数据后，只能使用发送者的公钥进行解密，这样就能唯一确定发送方，这也是数字签名的过程。但无法保证机密性。如下：

  

• 公钥基础设施PKI：是以不对称密钥加密技术为基础，以数据机密性、完整性、身份认证和行为不可抵赖性为安全目的，来实施和提供安全服务的具有普适性的安全基础设施。

• （1）数字证书：一个数据结构，是一种由一个可信任的权威机构签署的信息集合。在不同的应用中有不同的证书。如X.509证书必须包含下列信息：

  • （1）版本号（2）序列号（3）签名算法标识符（4）认证机构（5）有效期限（6）主题信息（7）认证机构的数字签名（8）公钥信息。

  **公钥证书主要用于确保公钥及其与用户绑定关系的安全。这个公钥就是证书所标识的那个主体的合法的公钥。**任何一个用户只要知道签证机构的公钥，就能检查对证书的签名的合法性。如果检查正确，那么用户就可以相信那个证书所携带的公钥是真实的，而且这个公钥就是证书所标识的那个主体的合法的公钥。例如驾照。

• （2）签证机构CA：负责签发证书、管理和撤销证书。是所有注册用户所信赖的权威机构，CA在给用户签发证书时要加上自己的数字签名，以保证证书信息的真实性。任何机构可以用CA的公钥来验证该证书的合法性。

考试真题

• 数字签名技术属于信息系统安全管理中保证信息（）的技术。

  A、保密性 B、可用性 C、完整性 D、可靠性

  答案：C

• 为保障数据的存储和运输安全，防止信息泄露，需要对一些数据进行加密。由于对称密码算法()，所以特别适合对大量的数据进行加密。

  A、比非对称密码算法更安全

  B、比非对称密码算法密钥更长

  C、比非对称密码算法效率更高

  D、还能同时用于身份认证

  答案：C

• 假设A和B之间要进行加密通信，则正确的非对称加密流程是（）。 ①A和B都要产生一对用于加密和解密的加密密钥和解密密钥 ②A将公钥传送给B，将私钥自己保存，B将公钥传送给A，将私钥自己保存 ③A发送消息给B时，先用B的公钥对信息进行加密，再将密文发送给B ④B收到A发来的消息时，用自己的私钥解密

  A.①②③④ C.③①②④ B.①③④② D.②③①④

  答案：A

• 甲向乙发送其数据签名，要验证该签名，乙可使用（）对该签名进行解密。

  A.甲的私钥 B.甲的公钥 C.乙的私钥 D.乙的公钥

  答案：B

3.网络安全技术

防火墙

• 防火墙是在内部网络和外部因特网之间增加的一道安全防护措施，分为网络级防火墙和应用级防火墙。
• 网络级防火墙层次低，但是效率高，因为其使用包过滤和状态监测手段，一般只检验网络包外在（起始地址、状态）属性是否异常，若异常，则过滤掉，不与内网通信，因此对应用和用户是透明的。
• 但是这样的问题是，如果遇到伪装的危险数据包就没办法过滤，此时，就要依靠应用级防火墙，层次高，效率低，因为应用级防火墙会将网络包拆开，具体检查里面的数据是否有问题，会消耗大量时间，造成效率低下，但是安全强度高。

入侵检测系统IDS

• 防火墙技术主要是分隔来自外网的威胁，却对来自内网的直接攻击无能为力，此时就要用到入侵检测IDS技术，位于防火墙之后的第二道屏障，作为防火墙技术的补充。
• 原理：监控当前系统/用户行为，使用入侵检测分析引擎进行分析，这里包含一个知识库系统，囊括了历史行为、特定行为模式等操作，将当前行为和知识库进行匹配，就能检测出当前行为是否是入侵行为，如果是入侵，则记录证据并上报给系统和防火墙，交由它们处理。
• 不同于防火墙，IDS入侵检测系统是一个监听设备，没有跨接在任何链路上，无须网络流量流经它便可以工作。因此，对IDS的部署，唯一的要求是：IDS应当挂接在所有所关注流量都必须流经的链路上。因此，IDS在交换式网络中的位置一般选择在：（1）尽可能靠近攻击源（2）尽可能靠近受保护资源

入侵防御系统IPS

• IDS和防火墙技术都是在入侵行为已经发生后所做的检测和分析，而IPS是能够提前发现入侵行为，在其还没有进入安全网络之前就防御。 **在安全网络之前的链路上挂载入侵防御系统IPS，可以实时检测入侵行为，并直接进行阻断，**这是与IDS的区别，要注意。

杀毒软件

• 用于检测和解决计算机病毒，与防火墙和DS要区分，计算机病毒要靠杀毒软件，防火墙是处理网络上的非法攻击。

蜜罐系统

• **伪造一个蜜罐网络引诱黑客攻击，**蜜罐网络被攻击不影响安全网络，并且可以借此了解黑客攻击的手段和原理，从而对安全系统进行升级和优化。

网络攻击和威胁

计算机病毒和木马

• 病毒：编制或者在计算机程序中插入的破坏计算机功能或者破坏数据，影响计算机使用并且能够自我复制的一组计算机指令或者程序代码。
• 木马：是一种后门程序，常被黑客用作控制远程计算机的工具，隐藏在被控制电脑上的一个小程序监控电脑一切操作并盗取信息。
• 代表性病毒实例 蠕虫病毒（感染EXE文件）：熊猫烧香，罗密欧与朱丽叶，恶鹰，尼姆达，冲击波，欢乐时光。 木马：QQ消息尾巴木马，特洛伊木马，x卧底。 宏病毒（感染word、excel等文件中的宏变量）：美丽沙，台湾1号。 CIH病毒：史上唯一破坏硬件的病毒。 红色代码：蠕虫病毒+木马。

考试真题

• 随着互联网的发展，网络安全越来越受到人们的重视，其中能够鉴别什么样的数据包可以进出组织内部网络的安全技术称为（）

  A、入侵检测 B.防病毒软件 C、安全审计系统 D、防火墙

  答案：D

• 计算机病毒的特征不包括（）。

  A.传染性 B.触发性 C.隐蔽性 D.自毁

  答案：D

• 攻击者通过发送一个目的主机已经接收过的报文来达到攻击目的，这种攻击方式属于（）攻击。

  A.重放 B.拒绝服务 C.数据截获 D.数据流分析

  答案：A

• 下列攻击方式中，流量分析属于（）方式。

  A.被动攻击 B.主动攻击 C.物理攻击 D.分发攻击

  答案：A

4.网络安全协议

• 物理层主要使用物理手段，隔离、屏蔽物理设备等，其它层都是靠协议来保证传输的安全，具体如下图所示：

  

• SSL协议：安全套接字协议，被设计为加强Web安全传输（HTTP/HTTPS/）的协议，安全性高，和HTTP结合之后，形成HTTPS安全协议，端口号为443.

• SSH协议：安全外壳协议，被设计为加强Telnet/FTP安全的传输协议。

• SET协议：安全电子交易协议主要应用于**B2C模式（电子商务）中保障支付信息的安全性。**SET协议本身比较复杂，设计比较严格，安全性高，它能保证信息传输的机密性、真实性、完整性和不可否认性。SET协议是PKI框架下的一个典型实现，同时也在不断升级和完善，如SET 2.0将支持借记卡电子交易。

• Kerberos协议：是一种**网络身份认证协议，该协议的基础是基于信任第三方，它提供了在开放型网络中进行身份认证的方法，**认证实体可以是用户也可以是用户服务。这种认证不依赖宿主机的操作系统或计算机的IP地址，不需要保证网络上所有计算机的物理安全性，并且假定数据包在传输中可被随机窃取和篡改。

• PGP协议：使用RSA公钥证书进行身份认证，使用IDEA（128位密钥）进行数据加密，使用MD5进行数据完整性验证。

  发送方A有三个密钥：A的私钥、B的公钥、A生成的一次性对称密钥：

  接收方B有两个密钥：B的私钥、A的公钥。

  

考试真题

• 下面可提供安全电子邮件服务的是（）。

  A.RSA B.SSL C.SET D.S/MIME

  答案：D

• 以下关于第三方认证服务的叙述中，正确的是（）。

  A.Kerberos认证服务中保存数字证书的服务器叫CA

  B.第三方认证服务的两种体制分别是Kerberos和PKI

  C.PKI体制中保存数字证书的服务器叫KDC

  D.Kerberos的中文全称是“公钥基础设施”

  答案：B

• 网络管理员通过命令行方式对路由器进行管理，要确保ID，口令和会话内容的保密性，应采取的访问方式是（）。 A.控制台 B.AUX C.TELNET D.SSH

  答案：D

第六章、知识产权和标准化

1.知识产权概述

• 知识产权是指公民、法人、非法人单位对自己的创造性智力成果和其他科技成果依法享有的民事权。是智力成果的创造人依法享有的权利和在生产经营活动中标记所有人依法所享有的权利的总称。包含著作权、专利权、商标权、商业秘密权、植物新品种权、集成电路布图设计权和地理标志权等。
• 无体性：知识产权的对象是没有具体形体，是智力创造成果，是一种抽象的财富。
• 专有性：指除权利人同意或法律规定外，权利人以外的任何人不得享有或使用该项权利。
• 地域性：指知识产权只在授予其权利的国家或确认其权利的国家产生，并且只能在该国范围内受法律保护，而其他国家则不受保护。
• 时间性：**仅在法律规定的期限内受到保护，**一旦超过期限，权利自行消灭，相关知识产品即成为整个社会的共同财富，为全人类所共同使用。

保护期限

• 知识产权具有地域限制，保护期限各种情况如下表所示：

  

2.知识产权人的确定

• （1）职务作品

  

• （2）委托作品

  • 单位和委托的区别在于，当合同中未规定著作权的归属时，著作权默认归于单位，而委托创作中，著作权默认归属于创作方个人，具体如下：

  

侵权判定

• 中国公民、法人或者其他组织的作品，不论是否发表，都享有著作权。开发软件所用的思想、处理过程、操作方法或者数学概念不受保护。

• 著作权法不适用于下列情形：

  法律、法规、国家机关的决议、决定、命令和其他具有立法、行政、司法性质的文件，及其官方正式译文；时事新闻；历法、通用数表、通用表格和公式。

• 侵权判定

  

考试真题

• 关于知识产权的理解，不正确的是（）。

  A、知识产权的客体不是有形物，而是知识，信息等抽象物

  B、知识产权具有地域性，即在本国获得承认的和保护的知识，知识产权不具有域外效力

  C、对于专利权的域外效力，可以依赖国际公约或者双边协定取得

  D、知识产权具有一定的有效期限，无法永远存续

  答案：C

• 李某购买了一张有注册商标的应用软件光盘，则李某享有（）。

  A.注册商标专用权 B.该光盘的所有权

  C.该软件的著作权 D.该软件的复制权

  答案：B

• 根据著作权法规定，当著作权属于公民时，著作权人署名权的保护期为（）。

  A.永久 B.100年 C.50年 D.20年

  答案：A

• 甲乙两人分别独立开发出相同主题的阀门，但甲完成在先，乙完成在后。依据专利法规定，（）。

  A、甲享有专利申请权，乙不享有

  B、甲不享有专利申请权，乙享有

  C、甲、乙都享有专利申请权

  D、甲、乙都不享有专利申请权

  答案：C

标准划分

• 根据标准制定机构和适用范围的不同，可分为国际标准、国家标准、行业标准、区域/地方标准和企业标准
• （1）国际标准：是指国际标准化组织（ISO）、国际电工委员会（IEC）和国际电信联盟（ITU）制定的标准，以及国际标准化组织确认并公布的其他国际组织制定的标准。国际标准在世界范围内统一使用，提供各国参考。
• （2）国家标准：是指由**国家标准化主管机构制定或批准发布，在全国范围内统一适用的标准。**比如：GB--- 中华人民共和国国家标准；强制性国家标准代号为GB，推荐性国家标准代号为GB/T，国家标准指导性文件代号为GB/Z，国军标代号为GJB，ANSI（American Natonal Standards Institute）-美国国家标准协会标准；
• （3）行业标准：是由**某个行业机构、团体等制定的，适用于某个特定行业业务领域的标准。**比如：IEEE-一美国电气电子工程师学会标准；GA-公共安全标准；YD-通信行业标准；
• （4）区域/地方标准：是由某一区域/地方内的标准化主管机构制定、批准发布的，适用于某个特定区域/地 **方的标准。**比如：EN--欧洲标准；
• （5）企业标准：是**企业范围内根据需要协调、统一的技术要求、管理要求和工作要求所制定的标准，适用于本企业内部的标准。**一般以Q字开头，比如Q/320101 RER O07-2012，其中320101代表地区，RER代表企业名称代号，001代表该企业该标准的序号，2012代表年号。

第七章、程序语言基本概念

1.程序设计语言的基本概念

• 程序设计语言是为了书写计算机程序而人为设计的符号语言，用于对计算过程进行描述、组织和推导。

• 低级语言：机器语言（计算机硬件只能识别0和1的指令序列），汇编语言。

• 高级语言：功能更强，抽象级别更高，与人们使用的自然语言比较接近。

• 各程序设计语言特点：

  Fortran语言：科学计算，执行效率高。 Pascal语言：为教学开发，表达能力强。 C语言：指针操作能力强，可以开发系统级软件，高效。 **C++**语言：面向对象，高效。 Java语言：面向对象，中间代码，跨平台。 C#语言：面向对象，中间代码，.Net框架。 Python是一种面向对象、解释型计算机程序设计语言。 Prolog是逻辑型程序设计语言。

• 汇编：将汇编语言翻译成目标程序执行。

• 解释和编译：将高级语言编译成执行。不同之处在于编译程序生成独立的可执行文件，直接运行，运行时无法控制源程序，效率高。而解释程序不生成可执行文件，可以逐条解释执行，用于调试模式，可以控制源程序，因为还需要控制程序，因此执行速度慢，效率低。

• 程序设计语言定义三要素：语法、语义、语用。

• 语法是指由程序设计语言的基本符号组成程序中的各个语法成分（包括程序）的一组规则，其中由基本字符构成的符号（单词）书写规则称为词法规则，由符号基构成语法成分的规则称为语法规则。

• 语义是程序设计语言中**按语法规则构成的各个语法成分的含义，**可分为静态语义和动态语义。**静态语义指编译时可以确定的语法成分的含义，而运行时刻才能确定的含义是动态语义。**一个程序的执行效果说明了该程序的语义，它取决于构成程序的各个组成部分的语义。

• 语用表示了构成语言的各个记号和使用者的关系，涉及符号的来源、使用和影响。

• 语言的实现则有个语境问题。语境是指理解和实现程序设计语言的环境，包括编译环境和运行环境。

• 程序设计语言的分类 （1）命令式和结构化程序设计语言，包括Fortran，PASCAL和C语言。 （2）面向对象程序设计语言，包括C++、JAVA和Smalltalk语言。 （3）函数式程序设计语言，包括LISP，Haskell，Scala，Scheme，APL等。 （4）逻辑型程序设计语言，包括PROLOG。

• 程序设计语言的基本成分

  • 数据成分：指一种程序设计语言的数据和数据类型。数据分为常量（程序运行时不可改变）、变量（程序运行时可以改变）、全局量（存储空间在静态数据区分配）、局部量（存储空间在堆栈区分配）。数据类型有整型、字符型、双精度、单精度浮点型、布尔型等。

  • 运算成分：指明**允许使用的运算符号及运算规则。**包括算术运算、逻辑运算、关系运算、位运算等。

  • 控制成分：**指明语言允许表述的控制结构。**包括顺序结构、选择结构、循环结构。

  • 传输成分：**指明语言允许的数据传输方式。**如赋值处理、数据的输入输出等。

  • 函数：C程序由一个或多个函数组成，每个函数都有一个名字，其中**有且仅有一一个名字为main的函数作为程序运行时的起点。**函数的使用涉及3个概念：函数定义、函数声明和函数调用。

  • 函数的定义包括两部分：函数首部和函数体。函数的定义描述了函数做什么和怎么做。函数定义的一般形式为：

    返回值的类型 函数名（形式参数表）//函数首部
    {
    函数体；
    }
    

  • 函数首部说明了函数返回值的数据类型、函数的名字和函数运行时所需的参数及类型。函数所实现的功能在函数体部分进行描述。

  • 函数应该**先声明后引用。**如果程序中对一个函数的调用在该函数的定义之前进行，则应该在调用前对被调用函数进行声明。函数原型用于声明函数。函数声明的一般形式为：

    返回值类型 函数名（参数类型表）；
    

  • 函数调用的一般形式为： 函数名（实参表）；

  • 函数调用时实参与形参间交换信息的方法有值调用和引用调用两种。 （1）值调用（Call by Value）。若实现函数调用时将实参的值传递给相应的形参，则称为是传值调用。在这种方式下形参不能向实参传递信息。 在C语言中，要实现被调用函数对实参的修改，必须用指针作为参数。即调用时需要先对实参进行取地址运算，然后将实参的地址传递给指针形参。其本质上仍属于值调用。这种方式实现了间接内存访问。 就是针对相应实参所做的访问和改变。 （2）引用调用（Call by Reference）。引用是C++中引入的概念，当形式参数为引用类型时，形参名实际上是实参的别名，函数中对形参的访问和修改实际上就是针对相应实参所做的访问和改变。

考试真题

• 将高级语言源程序翻译为可在计算机上执行的形式有多种不同的方式，其中（）。

  A.编译方式和解释方式都生成逻辑上与源程序等价的目标程序

  B.编译方式和解释方式都不生成逻辑上与源程序等价的目标程序

  C.编译方式生成逻辑上与源程序等价的目标程序，解释方式不生成

  D.解释方式生成逻辑上与源程序等价的目标程序，编译方式不生成

  答案：C

• 以下关于程序设计语言的叙述中，不正确的是（）。

  A.脚本语言中不使用变量和函数

  B.标记语言常用于描述格式化和链接

  C.脚本语言采用解释方式实现

  D.编译型语言的执行效率更高

  答案：

• 函数f，g的定义如下，执行表达式"y=f（2）"的运算时，函数调用g（la）分别采用引用调用（call by reference）方式和值调用（call by value）方式，则该表达式求值结束后y的值分别为（）。

  

  A.9、6 B.20、6 C.20,9 D.30,9

  答案：B

• 通用的高级程序设计语言一般都会提供描述数据、运算、控制和数据传输的语言成分，其中，控制包括顺序、（）和循环结构。

  A.选择 B.递归 C.递推 D.函数

  答案：A

2.编译程序基本原理

• 编译程序对高级语言源程序进行编译的过程中，要不断收集、记录和使用源程序中一些相关符号的类型和特征等信息，并将其存入符号表中，编译过程如下：

• 词法分析：是编译过程的第一个阶段。这个阶段的任务是从左到右一个字符一个字符地读入源程序，即对构成源程序的字符流进行扫描然后根据构词规则识别单词（也称单词符号或符号）。

• 语法分析：是编译过程的一个逻辑阶段。语法分析的任务是在词法分析的基础上将单词序列组合成各类语法短语，如“程序”，“语句”，“表达式”等等.语法分析程序判断源程序在结构上是否正确.

• 语义分析：是编译过程的一个逻辑阶段.语义分析的任务是对结构上正确的源程序进行上下文有关性质的审查，进行类型审查。如类型匹配、除法除数不为0等。又分为静态语义错误（在编译阶段能够查找出来）和动态语义错误（只能在运行时发现）。

  

• 中间代码和目标代码：中间代码是根据语义分析产生的，需要经过优化链接，最终生成可执行的目标代码。引入中间代码的目的是进行与机器无关的代码优化处理。常用的中间代码有后缀式（逆波兰式）、三元式（三地址码）、四元式和树等形式。需要考虑三个问题（一是如何生成较短的目标代码；二是如何充分利用计算机中的寄存器，减少目标代码访问存储单元的次数；三是如何充分利用计算机指令系统的特点，以提高目标代码的质量）。

• 前缀表达式：+ab 中缀表达式：a+b 后缀表达式：ab+

• 

• 主要掌握上述三种表达式即可，其实就是树的三种遍历，一般正常的表达式是中序遍历，即中缀表达式，根据其构造出树，再按题目要求求出前缀或后缀式。

• 简单求法：后缀表达式是从左到右开始，先把表达式加上括号，再依次把运算符加到本层次的括号后面。

考试真题.

• 将编译器的工作过程划分为词法分析，语法分析，语义分析，中间代码生成，代码优化和目标代码生成时，语法分析阶段的输入是（）若程序中的括号不配对，则会在（）阶段检查出错误。

  A、记号流 B.字符流 C、源程序 D、分析树

  A、词法分析 B.语法分析 C、语义分析 D、目标代码生成

  答案：A B

• 以编译方式翻译C/C++源程序的过程中，（）阶段的主要任务是对各条语句的结构进行合法性分析。

  A.词法分析 B.语义分析 C.语法分析 D.目标代码生成

  答案：C

• 表达式（a-b） * （c+d）的后缀式（逆波兰式）是（）

  A，abcd-+*

  B，ab-c+d*

  C、abc-d/-*

  D，ab-cd+*

  答案：D

3.文法定义

• 文法G是一个四元组，可表示为G-（V，T，P，S），其中：

  V：非终结符，不是语言组成部分，不是最终结果，可以推导出其他元素。 T：终结符，是语言的组成部分，是最终结果，不能再推导其他元素。 S：起始符，是语言的开始符号。 P：产生式，用终结符代替非终结符的规则，例如a->b。

• 乔姆斯基（Chomsky）把文法分成4种类型，即0型、1型、2型和3型。0型文法也称为短语文法，其功能相当于图灵机，任何0型语言都是递归可枚举的；反之，递归可枚举集也必定是一个0型语言。 1型文法也称为上下文有关文法，这种文法意味着对非终结符的替换必须考虑上下文，并且一般不允许替换成e串。例如，若aAβ-ayβ是1型文法的产生式，a和β不全为空，则非终结符A只有在左边是a，右边是β的上下文中才能替换成y。 2型文法就是上下文无关文法，非终结符的替换无须考虑上下文。程序设计语言中的大部分语法都是上下文无关文法，当然语义上是相关的，要注意区分语法和语义。 3型文法等价于正规式，因此也被称为正规文法或线性文法。

• 语言中具有独立含义的最小语法单位是符号（单词），如标识符、无符号常数与界限符等。词法分析的任务是把构成源程序的字符串转换成单词符号序列。

• 词法规则可用3型文法（正规文法）或正规表达式描述，它产生的集合是语言规定的基本字符集Σ（字母表）上的字符串的一个子集，称为正规集。

• 正规式和正规集：

  

  

考试真题

答案 ：D A

答案：B

有限自动机

• （2）不确定的有限自动机（NFA）。一个不确定的有限自动机也是一个五元组，它与确定有限自动机的区别如下。 ①f是S×2→2S上的映像。对于s 中的一个给定状态及输入符号，返回一个状态的集合。即当前状态的后继状态不一定是唯一的。 ②有向弧上的标记可以是。 确定的有限自动机和不确途的有限自动机：输入一个字符，看是否能得出唯一的后继，若能，则是确定的，否则若得出多个后继，则是不确定的。

  

考试真题

答案：C A

语法分析方法

• **自上而下语法分析：最左推导，从左至右。**给定文法G和源程序串r。从G的开始符号s出发，通过反复使用产生式对句型中的非终结符进行替换（推导），逐步推导出r。
• 递归下降思想：原理是利用函数之间的递归调用模拟语法树自上而下的构造过程，是一种自上而下的语法分析方法。
• 自下而上语法分析：**最右推导，从右至左。**从给定的输入串r开始，不断寻找子串与文法G中某个产生式P的候选式进行匹配，并用P的左部代替（归约）之，逐步归约到开始符号s。
• 移进-规约思想：设置一个栈，将输入符号逐个移进栈中，栈顶形成某产生式的右部时，就用左部去代替，称为归约。很明显，这个思想是通过右部来推导出左部，因此是自下而上语法分析的核心思想。

第八章、数据结构

1.线性结构

• 线性结构：每个元素最多只有一个出度和一个入度，表现为一条线状。线性表按存储方式分为顺序表和链表。存储结构。

• 顺序存储：用一组地址连续的存储单元依次存储线性表中的数据元素，使得逻辑上相邻的元素物理上也相邻。

• 链式存储：存储各数据元素的结点的地址并不要求是连续的，数据元素逻辑上相邻，物理上分开。

  

• 顺序存储和链式存储的对比如下图所示：

  

• 在空间方面，因为链表还需要存储指针，因此有空间浪费存在。

• 在时间方面，当需要对元素进行破坏性操作（插入、删除）时，链表效率更高，因为其只需要修改指针指向即可，而顺序表因为地址是连续的，当删除或插入一个元素后，后面的其他节点位置都需要变动。

• 而当需要对元素进行不改变结构操作时（读取、查找），顺序表效率更高，因为其物理地址是连续的，如同数组一般，只需按索引号就可快速定位，而链表需要从头节点开始，一个个的查找下去。

• 栈和队列 队列、栈结构如下图，队列是先进先出，分队头和队尾；栈是先进后出，只有栈顶能进出。

  

• 循环队列 设循环队列Q的容量为MAXSIZE，初始时队列为空，且Q.rear和Q.front都等于0. 元素入队时修改队尾指针，即令Q.rear=（Q.rear+1）%MAXSIZE。 元素出队时修改队头指针，即令Q.front=（Q.front+1）%MAXSIZE。

  根据队列操作的定义，当出队操作导致队列变为空时，有Q.rear == Q.front；若入队操作导致队列满，则Q.rear == Q.front。

• 在队列空和队列满的情况下，循环队列的队头、队尾指针指向的位置是相同的，此时仅仅根据Q.rear和Q.front之间的关系无法断定队列的状态。为了区别队空和队满的情况，可采用以下两种处理方式：其一是设置一个标志，以区别头、尾指针的值相同时队列是空还是满；其二是牺牲一个存储单元，约定以**"队列的尾指针所指位置的下一个位置是队头指针时"表示队列满，如图所示，而头、尾指针的值相同时表示队列为空。**

  

考试真题.

• 对于线性表，相对于顺序存储，采用链表存储的缺点是（）。

  A.数据元素之间的关系需要占用存储空间，导致存储密度不高

  B.表中结点必须占用地址连续的存储单元，存储密度不高

  C.插入新元素时需要遍历整个链表，运算的时间效率不高

  D.删除元素时需要遍历整个链表，运算的时间效率不高

  答案：A

• 若一个栈初始为空，其输入序列是1，2，3，...，n-1，n，其输出序列的第一个元素为k（1<=k<=[n/2」），则输出序列的最后一个元素是（）。

  A.值为n的元素

  B.值为1的元素

  C.值为n-k的元素

  D.不确定的

  答案：D

• 某双端队列如下图所示，要求元素进出队列必须在同一端口，即从A端进入的元素必须从A端出、从B端进入的元素必须从B端出，则对于4个元素的序列e1、e2、e3、e4，若要求前2个元素（e1、e2）从A端口按次序全部进入队列，后两个元素（e3、e4）从B端口按次序全部进入队列，则可能得到的出队序列是（）。

  

  A. e1、 e2、 e3、 e4

  B. e2、 e3、 e4、e1

  C. e3、 e4、 e1、 e2 D. e4、e3、 e2、 e1

  答案：D

• 设循环队列的定义中有front和size两个域变量，其中Front表示队头元素的指针，SIZE表示队列的长度，如下图所示（队列长度为3，队头元素X，队尾元素为2）。设队列的存储空间容量为M，则队尾元素的指针为（）。

  

  A. (Q. front+ Q. size-1)

  B. (Q. front+ Q. size-1+ M)%M

  C. (Q. front-Q. size) D. (Q. front-Q. size+M)%M

  答案：B.

• 字符串是一种特殊的线性表，其数据元素都为字符。

  • 空串：长度为0的字符串，没有任何字符。
  • 空格串：**由一个或多个空格组成的串，**空格是空白字符，占一个字符长度。
  • 子串：串中任意长度的连续字符构成的序列称为子串。含有子串的串称为主串，空串是任意串的子串。
  • 串的模式匹配：子串的定泣操作，用于查找子串在主串中第一次出现的位置的算法。

• 模式匹配算法朴素的模式匹配算法：也称为布鲁特一福斯算法，其基本思想是从主串的第1个字符起与模式串的第1个字符比较，若相等，则继续逐个字符进行后续的比较否则从主串中的第2个字符起与模式串的第1个字符重新比较，直至模式串中每个字符依次和主串中的一个连续的字符序列相等时为止，此时称为匹配成功，否则称为匹配失败。

• KMP算法：对基本模式匹配算法的改进，其改进之处在于：每当匹配过程中出现相比较的字符不相等时，不需要回溯主串的字符位置指针，而是利用已经得到的"部分匹配”结果将模式串向右"滑动"尽可能远的距离，再继续进行比较。

• 当模式串中的字符pj与主串中相应的字符si 不相等时，因其前j个字符（"po...pj-1"）已经获得了成功的匹配，所以若模式串中"po...pk-1"与"pj-k...pj-1"相同，这时可令pk与si进行比较，从而使i无须回退。

• 在KMP 算法中，依据模式串的next函数值实现子串的滑动。若令next[j]=k，则next[j]表示当模式串中的pj与主串中相应字符不相等时，令模式串的next[j]与主串的相应字符进行比较。

考试真题

• 在字符串的KMP模式匹配算法中，需先求解模式串的next函数值，其定义如下式所示，j表示模式串中字符的序号（从1开始）。若模式串p为"abaac"，则其next函数值为（）。 答案：B

  

  A. 01234 B. 01122 C. 01211 D. 01111

2.数组

• 数组是定长线性表在维度上的扩展，即线性表中的元素又是一个线性表。N维数组是一种“同构”的数据结构，其每个数据元素类型相同、结构一致。

  

• 其可以表示为行向量形式或者列向量形式线性表，单个关系最多只有一个前驱和一个后继，本质还是线性的。

• 数组结构的特点：数据元素数目固定；数据元素类型相同；数据元素的下标关系具有上下界的约束且下标有序。

• 数组数据元素固定，一般不做插入和删除运算，适合于采用顺序结构，

• 数组存储地址的计算，特别是二维数组，要注意理解，假设每个数组元素占划用存储长度为len，起始地址为a，存储地址计算如下（默认从0开始编号）：

  

3.矩阵

• 特殊矩阵：矩阵中的元素（或非0元素）的分布有一定的规律。常见的特殊矩阵有对称矩阵、三角矩阵和对角矩阵。
• 稀疏矩阵：在一个矩阵中，若非零元素的个数远远少于零元素个数，且非零元素的分布没有规律。
• 存储方式为三元组结构，即存储每个非零元素的（行，列，值）。

考试真题

• 设某n阶三对角矩阵Anxn的示意图如下图所示。若将该三对角矩阵的非零元素按行存储在一维数组B[k]（1sks3*n-2）中，则k与i、j的对应关系是（）。 答案：A

  

• 

  答案：C

4.广义表

• 广义表是线性表的推广，是由0个或多个单元素或子表组成的有限序列。
• 广义表与线性表的区别：线性表的元素都是结构上不可分的单元素，而广义表的元素既可以单元素，也可以是有结构的表。
• 广义表一般记为：LS=（a1，a2，.，an） 其中LS是表名，ai是表元素，它可以是表（称为子表），也可以是数据元素（称为原子）。其中n是广义表的长度（也就是最外层包含的元素个数），n=0的广义表为空表；而递归定义的重数就是广义表的深度，即定义中所含括号的重数（单边括号的个数，原子的深度为0，空表的深度为1）。
• head（）和tail（）：取表头（广义表第一个表元素，可以是子表也可以是单元素） 和**取表尾（广义表中，除了第一个表元素之外的其他所有表元素构成的表，**非空广义表的表尾必定是一个表，即使表尾是单元素）操作。

5.数与二叉树

• 树是n个节点的有限集合（n>=0），当n=0时称为空树，在任一颗非空树中，有且仅有一个根节点。其余结点可分为m（m20）个互不相交的有限子集T1，T2，...，Tm，其中，每个Ti又都是一棵树，并且称为根结点的子树。

• 树的基本概念如下： （1）双亲、孩子和兄弟。结点的子树的根称为该结点的孩子；相应地，该结点称为其子结点的双亲。具有相同双亲的结点互为兄弟。 （2）结点的度。一个结点的子树的个数记为该结点的度。例如A的度为3，B的度为2，C的度为0，D 的度为1。 （3）叶子结点。叶子结点也称为终端结点，指度为0的结点。例如，E、F、C、G都是叶子结点。 （4）内部结点。度不为0的结点，也称为分支结点或非终端结点。除根结点以外，分支结点也称为内部结点。例如，B、D都是内部结点。 （5）结点的层次。根为第一层，根的孩子为第二层，依此类推，若某结点在第i层，则其孩子结点在第i+1层。例如，A 在第1 层，B、C、D 在第2 层，E、F 和G 在第3 层。 （6）树的高度。一棵树的最大层数记为树的高度（或深度）。例如，图中所示树的高度为3。 （7）有序（无序）树。若将树中结点的各子树看成是从左到右具有次序的，即不能交换，则称该树为有序树，否则称为无序树。

  

• 二叉树是n个节点的有限集合，它或者是空树，或者是由一个根节点及两颗互不相交的且分别称为左、右子树的二叉树所组成。

  

• 两种特殊的二叉树如下图所示：

  

• 二叉树有一些性质如下，要求掌握，在实际考试中可以用特殊值法验证。 （1）二叉树第i层（i>=1）上至多有2^（i-1）个节点。

  （2）深度为k的二叉树至多有2^k-1个节点（k>=1）。 （3）对任何一棵二叉树，若其终端节点数为n0，度为2 的节点数为n2，则n0=n2 +1

• 此公式可以画一个简单的二叉树使用特殊值法快速验证，也可以证明如下：设一棵二叉树上叶结点数为n0，单分支结点数为n1，双分支结点数为n2，则总结点数=n0+n1+n2。在一棵二叉树中，所有结点的分支数（即度数）应等于单分支结点数加上双分支结点数的2倍，即总的分支数=n1+2n2。由于二叉树中除根结点以外，每个结点都有唯一的一个分支指向它，因此二叉树中：总的分支数=总结点数-1。 （4）具有n个节点的完全二叉树的深度为[log2 n]+ 1。

二叉树的顺序存储结构

• 顺序存储，就是用一组连续的存储单元存储二叉树中的节点，按照从上到下，从左到右的顺序依次存储每个节点。
• 对于深度为k的完全二叉树，除第k层外，其余每层中节点数都是上一层的两倍，由此，从一个节点的编号可推知其双亲、左孩子、右孩子结点的编号。假设有编号为i的节点，则有：
  • 若i=1，则该节点为根节点，无双亲；若i>1，则该节点的双亲节点为[i/2]。
  • 若2i<=n，则该节点的左孩子编号为2i，否则无左孩子。
  • 若2i+1<=n，则该节点的右孩子编号为2i+1，否则无右孩子。
• 显然，顺序存储结构对完全二叉树而言既简单又节省空间，而对于一般二叉树则不适用。因为在顺序存储结构中，以节点在存储单元中的位置来表示节点之间的关系，那么对于一般的二叉树来说，也必须按照完全二叉树的形式存储，也就是要添上一些实际并不存在的“虚节点”，这将造成空间的浪费。

二叉树的链式存储结构

• 由于二叉树中节点包含有数据元素、左子树根、右子树根及双亲等信息，因此可以用三叉链表或二叉链表（即一个节点含有三个指针或两个指针）来存储二叉树，链表的头指针指向二叉树的根节点

• 一颗非空的二叉树由根节点、左子树、右子树三部分组成，遍历这三部分，也就遍历了整颗二叉树。这三部分遍历的基本顺序是先左子树后右子树，但根节点顺序可变，以根节点访问的顺序为准有下列三种遍历方式：先序（前序）遍历：根左右。中序遍历：左根右。后序遍历：左右根。 示例：前序：12457836中序：42785136后序：48752631

  

• 层次遍历：按层次，从上到下，从左到右。

• 反向构造二叉树： 仅仅有前序和后序是无法构造二叉树的，必须要是和中序遍历的集合才能反向构造出二叉树。 构造时，**前序和后序遍历可以确定根节点，中序遍历用来确定根节点的左子树节点和右子树节点，**而后按此方法进行递归，直至得出结果。

考试真题

• 一个高度为h的满二叉树的结点总数为2^h-1，从根结点开始，自上而下、同层次结点从左至右，对结点按照顺序依次编号，即根结点编号为1，其左、右孩子结点编号分别为2和3，再下一层从左到右的编号为4，5，6，7，依此类推。那么，在一棵满二叉树中，对于编号为m和n的两个结点，若n=2m+1，则（）答案：D

  A.m是n的左孩子 B.m是n的右孩子 C.n是m的左孩子 D.n是m的右孩子

• 某二叉树如图所示，若进行顺序存储（即用一维数组元素存储该二叉树中的结点且通过下标反映结点间的关系，例如，对于下标为i的结点，其左孩子的下标为2i、右孩子的下标为2i+1），则该数组的大小至少为（）；若采用三叉链表存储该二叉树（各个结点包括结点的数据、父结点指针、左孩子指针、右孩子指针），则该链表的所有结点中空指针的数目为（）。答案：D B

  Α.6 B.10 C.12 D.15 Α.6 B.8 C.12 D.14

• 引入线索二叉树是为了保存二叉树遍历时某节点的前驱节点和后继节点的信息，二叉树的链式存储只能获取到某节点的左孩子和右孩子结点，无法获取其遍历时的前驱和后继节点，因此可以在链式存储中再增加两个指针域，使其分别指向前驱和后继节点，但这样太浪费存储空间，考虑下述实现方法：

• 若**n个节点的二叉树使用二叉链表存储，则必然有n+1个空指针域，**利用这些空指针域来存放节点的前驱和后继节点信息，为此，需要增加两个标志，以区分指针域存放的到底是孩子结点还是遍历节点，如下：

  

• 若二叉树的二叉链表采用上述结构，则称为线索链表，其中指向前驱、后继节点的指针称为线索，加上线索的二叉树称为线索二叉树。

  

• 最优二叉树又称为哈夫曼树，是一类带权路径长度最短的树，相关概念如下：

• 路径：树中一个结点到另一个结点之间的通路。

• 结点的路径长度：路径上的分支数目。

• 树的路径长度：根节点到达每一个叶子节点之间的路径长度之和。

• 权：节点代表的值。

• 结点的带权路径长度：该结点到根结点之间的路径长度乘以该节点的权值。

• 树的带权路径长度（树的代价）：树的所有叶子节点的带权路径长度之和。

• 哈夫曼树的求法：给出一组权值，将其中**两个最小的权值作为叶子节点，其和作为父节点，组成二叉树，而后删除这两个叶子节点权值，并将父节点的值添加到该组权值中。**重复进行上述步骤，直至所有权值都被使用完。

  

• 若需要构造哈夫曼编码（要保证左节点值小于右节点的值，才是标准的哈夫曼树），将标准哈夫曼树的左分支设为0，右分支设为1，写出每个叶节点的编码，会发现，哈夫曼编码前缀不同，因此不会混淆，同时也是最优编码。

考试真题

• 下表为某文件中字符的出现频率，采用霍夫曼编码对下列字符编码，则字符序列"bee"的编码为 （）；编码："110001001101"的对应的字符序列（）答案：AC

  

  A. 10111011101 В. 10111001100 C. 001100100 D. 110011011 A. bad B. bee C. face D. bace

• 查找二叉树上的每个节点都存储一个值，且每个节点的所有左孩子结点值都一小于父节点值，而所有右孩子结点值都大于父节点值，是一个有规律排列的二叉树，这种数据结构可以方便查找、插入等数据操作。

• 二叉排序树的查找效率取决于二叉排序树的深度，对于结点个数相同的二叉排序树，平衡二叉树的深度最小，而单枝树的深度是最大的，故效率最差。

• 平衡二叉树又称为AVL树，它或者是一棵空树，或者是具有下列性质的二叉树。 它的左子树和右子树都是平衡二叉树，且左子树和右子树的高度之差的绝对值不超过1，若将二叉树结点的**平衡因子（Balance Factor，BF）定义为该结点左子树的高度减去其右子树的高度，**则平衡二叉树上所有结点的平衡因子只可能是-1、0和1，只要树上有一个结点的平衡因子的绝对值大于1，则该二叉树就是不平衡的。

考试真题

• 某二叉树的先序遍历列为cabfedg，中序遍历序列为abcdefg，则二叉树是（C）。

  A.完全二叉树 B.最优二叉树 C.平衡二叉树 D.满二叉树

• 设有二叉排序树（或二叉查找树）如下图所示，建立该二叉树的关键码序列不可能是（C）。

  A. 23 31 17 19 11 27 13 90 61

  B. 23 17 19 31 27 90 61 11 13 C. 23 17 27 19 31 13 1190 61 D. 23 31 90 61 27 17 19 11 13

  

6.图

• 无向图：图的结点之间连接线是没有箭头的，不分方向。
• 有向图：图的结点之间连接线是箭头，区分A到B，和B到A是两条线。
• 完全图：无向完全图中，节点两两之间都有连线，n个结点的连线数为（n-1）+（n-2）+...+1= n （n-1）/2*；有向完全图中，节点两两之间都有互通的两个箭头，n个节点的连线数为n*（n-1）.
• 度、出度和入度：顶点的度是关联与该顶点的边的数目。在有向图中，顶点的度为出度和入度之和。
• 路径：存在一条通路，可以从一个顶点到达另一个顶点。
• 子图：有两个图G=（V，E）和G'=（V'，E'），如果V属于V且E'属于E，则称G'为G的子图。
• 连通图和连通分量：针对无向图。若从顶点v到顶点u之间是有路径的，则说明v和u之间是连通的，若无向图中任意两个顶点之间都是连通的，则称为连通图。无向图G的极大连通子图称为其连通分量。
• 强连通图和强连通分量：针对有向图。若有向图任意两个顶点间都互相存在路径，即存在v到u，也存在u到v的路径，则称为强连通图。有向图中的极大连通子图称为其强连通分量。
• 网：边带权值的图称为网。

图的存储

• 邻接矩阵：假设一个图中有**n个节点，则使用n阶矩阵来存储这个图中各节点的一关系，规则是若节点倒节点有连线，则矩阵Ri，j-1，否则为0，**示例如下图所示：

  

• 邻接链表：用到了两个数据结构，先用一个一维数组将图中所有顶点存储起来，而后，对此一维数组的每个顶点元素，使用链表挂上其出度到达的结点的编号和权值，示例如下图所示：

  

• 存储特点：图中的顶点数决定了邻接矩阵的阶和邻接表中的单链表数目，边数的多少决定了单链表中的结点数，而不影响邻接矩阵的规模，因此采用何种存储方式与有向图、无向图没有区别，要看图的边数和顶点数，完全图适合采用邻接矩阵存储。

• 图的遍历是指从图的任意节点出发，沿着某条搜索路径对图中所有节点进行访问且只访问一次，分为以下两种方式：

• 深度优先遍历：从**任一顶点出发，遍历到底，直至返回，再选取任一其他节点出发，**重复这个过程直至遍历完整个图；

• 广度优先遍历：先访问完一个顶点的所有邻接顶点，而后再依次访问其邻接顶点的所有邻接顶点，类似于层次遍历。

  

• 图的最小生成树

• 假设有n个节点，那么这个图的最小生成树有n-1条边（不会形成环路，是树非图），这n-1条边应该会将所有顶点都连接成一个树，并且这些边的权值之和最小，因此称为最小生成树。共有下列两种算法：

• 普里姆算法：从任意顶点出发，找出与其邻接的边权值最小的，此时此边的另外一个顶点自动加入树集合中，而后再从这这个树集合的所有顶点中找出与其邻接的边权值最小的，同样此边的另外一个顶点加入树集合中，依次递归，直至图中所有顶点都加入树集合中，此时此树就是该图的最小生成树。普里姆算法的时间复杂度为0（n^2），与图中的边数无关，因此该算法适合于求边稠密的网的最小生成树。

  

• 克鲁斯卡尔算法（推荐）：这个算法是从边出发的，因为本质是选取权值最小的n-1条边，因此，就**将边按权值大小排序，依次选取权值最小的边，直至囊括所有节点，**要注意，每次选边后要检查不能形成环路。****克鲁斯卡尔算法的时间复杂度为0（eloge），与图中的顶点数无关，因此该算法适合于求边稀疏的网的最小生成树。

  

拓扑序列

• 若图中一个节点入度为0，则应该最先执行此活动，而后删除掉此节点和其关联的有向边，再去找图中其他没有入度的结点，执行活动，依次进行，示例如下（有点类似于进程的前趋图原理）：

  

考试真题

• 对于如下所示的有向图，其邻接矩阵是一个（A）的矩阵，采用邻接链表存储时顶点1的表结点个数为2，顶点5的表结点个数为0，顶点2和3的表结点个数分别为（B）

  

  A、5 * 5 B. 5 * 7 C、 7 * 5 D. 7 * 7

  A. 2.1 B. 2.2 C、 3.4 D, 4.3

• 设一个包含n个顶点、e条弧的简单有向图采用邻接矩阵存储结构（即矩阵元素A[i] [j]等于1或0，分别表示顶点与顶点之间有弧或无弧），则该矩阵的非零元素数目为（A）。

  A.e B.2e C.n-e D. n+e

• Prim算法和Kruscal算法都是无向连通网的最小生成树的算法，Prim算法从一个顶点开始，每次从剩余的顶点中加入一个顶点，该顶点与当前的生成树中的顶点的连边权重最小，直到得到一颗最小生成树；Kruscal算法从权重最小的边开始，每次从不在当前的生成树顶点中选择权重最小的边加入，直到得到一颗最小生成树，这两个算法都采用了（B）设计策略，且（A）。

  A.分治 B.贪心 C.动态规划 D.回溯 A.若网较稠密，则Prim算法更好

  B.两个算法得到的最小生成树是一样的

  C.Prim算法比Kruscal算法效率更高

  D.Kruscal算法比Prim算法效率更高

• 拓扑排序是将有向图中所有顶点排成一个线性序列的过程，并且该序列满足：若在AOV网中从顶点vi到vj有一条路径，则顶点vi必然在顶点vj之前。对于下面所示的有向图，（C）是其拓扑序列。

  

  A. 1234576 B. 1235467 C. 2135476 D. 2134567

查找

1.顺序查找

• 顺序查找的思想：将待查找的关键字为key的元素从头到尾与表中元素进行比较，如果中间存在关键字为key的元素，则返回成功；否则，则查找失败。

  

• 时间复杂度为0（n）。

2.折半查找

• 只适用于待查找序列中的元素是有序排列的情况。
• 设查找表的元素存储在一维数组r[1..n]中，在表中元素已经按照关键字递增（或递减）方式排序的情况下，进行折半查找的方法是： 1、首先将待查元素的关键字（key）值与表r中间位置上（下标为mid）记录的关键字进行比较，若相等，则查找成功； 2、若key>r[mid].key，则说明待查记录只可能在后半个子表r[mid+1..n]中，下一步应在后半个子表中查找； 3、若key<r[mid].key，说明待查记录只可能在前半个子表r[1..mid-1]中，下一步应在r的前半个子表中查找； 4、重复上述步骤，逐步缩小范围，直到查找成功或子表为空失败时为止。
• 要注意两点：中间值位置求出若为小数，应该向下取整，即4.5=4，非四舍五入；中间值已经比较过不相等，在划分下一次比较区间时，无需将中间值位置再纳入下一次比较区间。
• 折半查找的时间复杂度为O（log2n）。

3.哈希表

• 哈希表通过一个以记录的关键字为自变量的函数（称为哈希函数）得到该记录的存储地址，所以在哈希表中进行查找操作时，需要用同一哈希函数计算得到待查记录的存储地址，然后到相应的存储单元去获得有关信息再判定查找是否成功。

哈希函数产生了冲突的解决方法如下：

• 2.链地址法。它在查找表的每一个记录中增加一个链域，链域中存放**下一个具有相同哈希函数值的记录的存储地址。利用链域，就把若干个发生冲突的记录链接在一个链表内。**当链域的值为NULL时，表示已没有后继记录了。因此，对于发生冲突时的查找和插入操作就跟线性表一样了。
• 3·再哈希法：在**同义词发生地址冲突时计算另一个哈希函数地址，**直到冲突不再发生。这种方法不易产生聚集现象，但增加了计算时间。
• 4.建立一个公共溢出区。无论由哈希函数得到的哈希地址是什么，一旦发生冲突，都填入到公共溢出区中。

考试真题

• 在13个元素构成的有序表M[1..13]中进行折半查找（向下取整），若找到的元素为M[4]，则被比较的元素依次为（A） A.M[7]、M[3]、M[5]、M[4] B.M[7]、M[5]、M[4]

  C.M[7]、M[6]、M[4] D.M[7]、M[4]

• 设散列函数为H（key）=key%11，对于关键字序列（23，40，91，17，19，10，31，65，26），用线性探测法解决冲突构造的哈希表为（B）。

排序

1.直接插入排序

• 要注意的是，前提条件是前i-1个元素是有序的，第i个元素依次从第i-1个元素往前比较，直到找到一个比第i个元素值小的元素，而后插入，插入位置及其后一的元素依次向后移动。

• 当给出一队无序的元素时，首先，应该将第1个元素看做是一个有序的队列，而后从第2个元素起，按插入排序规则，依次与前面的元素进行比较，直到找到一个小于他的值，才插入。示例如下图所示：

• 下图中，59依次向前比较，先和68比较，再和57比较，发现57比他小，才插入。

  

2.希尔排序

• 希尔排序又称**“缩小增量排序”，是对直接插入排序方法的改进。**

• 希尔排序的基本思想是：先将整个待排记录序列分割成若干子序列，然后分别进行直接插入排序，待整个序列中的记录基本有序时，再对全体记录进行一次直接插入排序。

• 具体做法是：先取一个小于n的整数d1作为第一个增量，把文件的全部记录分成d1个组，将所有距离为d1 倍数的记录放在同一个组中，在各组内进行直接插入排序；然后取第二个增量d2（d2 <d1），重复上述分组和排序工作，依此类推，直至所取的增量di=1（di < di-1 <...<d2 <d1），即所有记录放在同一组进行直接插入排序为止。

• 按上述，希尔排序实际是为了解决大数据的排序问题，当待排序的数据很多时，使用直接插入排序效率很低，因此，采取分组的方法，使问题细化，可以提高效率，适用于多数据。

  

3.简单选择排序

• n个记录进行简单选择排序的基本方法是：通过n-i（1<=i <= n）次关键字之间的比较，从n-i+1个记录中选出关键字最小的记录，并和第i个记录进行交换，当i等于n 时所有记录有序排列。

• 按上述，**本质就是每次选择出最小的元素进行交换，**主要是选择比较过程，交换过程只有一次。示例如下：

  

4.堆排序

• 对于n个元素的关键字序列{Ki，K2，…，Kn），当且仅当满足下列关系时称其为堆，其中2i 和 2i+1 需不大于 n。

  

• 堆排序的基本思想是：对一组待排序记录的关键字，首先按堆的定义排成一个序列（即建立初始堆），从而可以输出堆顶的最大关键字（对于大根堆而言），然后将剩余的关键字再调整成新堆，便得到次大的关键字，如此反复，直到全部关键字排成有序序列为止。

  

• 为序列（55，60，40，10，80，65，15，5，75）建立初始大根堆的过程如图所示：

  

• 由上图可知，首先将给出的数组按完全二叉树规则建立，而后，找到此完全二叉树的最后一个非叶子节点（也即最后一颗子树），比较此非叶子节点和其一两个孩子结点的大小，若小，则与其孩子结点中最大的结点进行交换；依据此规则再去找倒数第二个非叶子节点，这是只有一层的情况，当涉及到多层次时,又打破了之前的堆，因此，又要进行变换。

• 建立初始堆后，开始排序，每次取走堆顶元素（必然是最大的），而后将堆中最后一个元素移入堆顶，**而后按照初始建堆中的方法与其孩子结点比较大小，依次向下判断交换成为一个新的堆，**再取走堆顶元素，重复此过程。

• 堆排序**适用于在多个元素中找出前几名的方案设计，**因为堆排序是选择排序，而且选择出前几名的效率很高。

  

5.冒泡排序

• n个记录进行冒泡排序的方法是：首先将第一个记录的关键字和第二个记录的关键字进行比较，若为逆序，则交换这两个记录的值，然后比较第二个记录和第三个记录的关键字，依此类推，直至第n-1个记录和第n个记录的关键字比较过为止。上述过程称为一趟冒泡排序，其结果是关键字最大的记录被交换到第n个记录的位置上。然后进行第二趟冒泡排序，对前n-1个记录进行同样的操作，其结果是关键字次大的记录被交换到第n-1个记录的位置上。最多进行n-1趟，所有记录有序排列。若在某趟冒泡排序过程没有进行相邻位置的元素交换处理，则可结束排序过程。

• 示例给的是从后往前排序，也是可以的，需要**从最后两个元素开始进行比较，将较小的元素交换到前面去，**依次进行比较交换。比较是为了交换，交换次数很多。区分冒泡排序和简单选择排序。

  

6.快速排序

• 快速排序是将n个记录分成两块，再递归，实际分成两块的方法如图所示：设定一个基准为57，设定两个指针high=1，low=n，从low指向的第n个元素开始，与基准值进行比较，若小于基准值，则与基准进行交换low--，此时，转而从high指向的第1个元素开始和基准值进行比较，若大于基准值，则和基准值进行交换，此时，又转而从low一指向的值和基准进行比较，重复上述过程。

• 要注意的是：每次都是和基准值进行比较，因此最终是以基准值为中间，将队列分成两块。只有当和基准值发生了交换，才变换high和low指针的计数，否则，会一直low--下去。

• 上图中，最终以57为界，左边都是小于57的元素，右边都是大于57的元素，完成一次快速排序，接着对两块再分别进行递归即可。

  

7.归并排序

• 所谓"归并，是将两个或两个以上的有序文件合并成为一个新的有序文件。归并排序的一种实现方法是把一个有n个记录的无序文件看成是由n个长度为1的有序子文件组成的文件，然后进行两两归并，得到[n/2]个长度为2或1的有序文件，再两两归并，如此重复，直至最后形成包含n个记录的有序文件为止。这种反复将两个有序文件归并成一个有序文件的排序方法称为两路归并排序。

• 要仔细理解上述过程，一般归并排序都是用来合并多个线性表的，对单列数据，二路归并排序可以对元素进行两两合并，示例如下：

• 对第三次归并，将52与28比较，28小，放入新表头，52再与33比较，33放入新表，52再与72比较，52放入新表，57再与72比较，57放入新表…..

  

8.基数排序

• 基数排序是基于多个关键字来进行多轮排序的，本质也是将问题细分，如图例子，分别按个位、十位、百位的大小作为关键字进行了三轮排序，最终得出结果。

9.内部排序算法总结

（1）若待排序的记录数目n 较小，可采用直接插入排序和简单选择排序。由于直接插入排序所需的记录移动操作较简单选择排序多，因此当记录本身信息量较大时，用简单选择排序方法较好。 （2）若待排序记录按关键字基本有序，则宜采用直接插入排序或冒泡排序。 （3）当n 很大且关键字的位数较少时，采用链式基数排序较好。 （4）若n较大，则应采用时间复杂度为0（nlogn）的排序方法，例如快速排序、堆排序或归并排序。

考试真题

• 将数组{1，1，2，4，7，5}从小到大排序，若采用（A）排序算法，则元素之间需要进行的比较次数最少，共需要进行（B）次元素之间的比较。

  A.直接插入 B.归并 C.堆 D.快速 A.5 B.6 C.7 D.8

• 在n个数的数组中确定其第i（1<=i<=n）小的数时，可以采用快速排序算法中的划分思想，对n个元素划分，先确定第k小的数，根据i和k的大小关系，进一步处理，最终得到第i小的数。划分过程中，最佳的基准元素选择的方法是选择待划分数组的（C）元素。此时，算法在最坏情况下的时间复杂度为（不考虑所有元素均相等的情况）（D）。

  A.第一个 B.最后一个 C.中位数 D.随机一个

  Α.Θ(n) B.Θ(Ign) C.Θ(nlgn) D.Θ(n^2)

• 对N个数排序，最坏情况下时间复杂度最低的算法是（C）排序算法.

  A.插入 B、冒泡 C、归并 D、快速