全国计算机等级考试三级数据库技术笔试要点

第一章 计算机基础知识1 、 计算机的发展阶段：经历了以下 5 个阶段( 它们是并行关系 )：大型机阶段(经历四小阶段它们是取代关系) 、小型机阶段、微型机阶段、客户机/服务器阶段（对等网络与非对等网络的概念）和互联网阶段（Arpanet 是在1983 年第一个使用 TCP/IP 协议的。 在 1991 年 6 月我国第一条与国际互联网连接的专线建成它从中国科学院高能物理研究所接到美国斯坦福大学的直线加速器中心。在 1994 年实现 4 大主干网互连(中国公用计算机互联网 Chinanet、中国科学技术网 Cstnet、中国教育和科研计算机网 Cernet、中国金桥信息网 ChinaGBN)）2 、 计算机种类：按照传统的分类方法：计算机可以分为 6 大类：大型主机、小型计算机、个人计算机、工作站、巨型计算机、小巨型机。按照现实的分类方法：计算机可以分为 5 大类：服务器、工作站、台式机、笔记本、手持设备。3 、 计算机的公共配置： CPU、内存（RAM）、高速缓存（Cache）、硬盘、光驱、显示器(CRT、LCD)、操作系统(OS)4 、 计算机的指标：位数指 CPU 寄存器中能够保存数据的位数、速度 (MIPS、MFLOPS) 指 CPU 每秒钟处理的指令数通常用主频来表示 CPU 的处理速度、容量（B、KB、MB、GB 、TB）、数据传输率（Bps）、版本和可靠性（MTBF 、MTTR）。5 、 计算机的应用领域：科学计算、事务处理、过程控制、辅助工程、人工智能、网络应用。（补充实例）6 、 计算机系统的组成 :硬件系统具有原子特性(芯片、板卡、设备、网络) 与软件系统具有比特特性。且它们具有同步性。7 、奔腾芯片的技术特点: 奔腾 32 位芯片，主要用于台式机和笔记本，奔腾采用了 RISC 和 CISC 技术(技术特点 10 个请看书 P8)8 、安腾芯片的技术特点：安腾是 64 位芯片，主要用于服务器和工作站。安腾采用简明并行指令计算（EPIC）技术9 、主机板与插卡的组成：(1) 主机板简称主板(mainboard)或母板(motherboard)。由 5 部分组成（CPU 、存储器、总线、插槽和电源）与主板的分类(2)网络卡又称为适配器卡代号 NIC，其功能为：（见书 P11）10、软件的基本概念：软件由程序(功能实现部分) 与文档(功能说明部分) 组成。软件是用户与计算机硬件系统之间的桥梁。11、应用软件包括：桌面应用软件、演示出版软件、浏览工具软件、管理效率软件、通信协作软件和系统维护软件。12、程序与文档：程序是由指令序列组成的，告诉计算计如何完成一个具体的任务。文档是软件开发、使用和维护中的必备资料。13、软件开发：软件的生命周期中，通常分为三大阶段，每个阶段又分若干子阶段： 计划阶段：分为问题定义、可行性研究（是决定软件项目是否开发的关键）。 开发阶段：在开发前期分为需求分析、总体设计、详细设计三个子阶段，在开发后期分为编码、测试两个子阶段。前期必须形成的文档有：软件需求说明书，软件设计规格说明书。 运行阶段：主要任务是软件维护。为了排除软件系统中仍然可能隐含的错误，扩充软件功能。14、编程语言：（机器语言与汇编语言都依赖于具体的机器，汇编语言与高级语言都需要编译） 机器语言：能被计算机直接理解和执行，速度快，但该种语言难记、难学、难懂。 汇编语言：用英文助记符和十进制数代替二进制码，使机器语言变成了汇编语言。汇编语言属于低级语言。汇编语言要通过汇编程序把汇编语言翻译成机器语言程序计算机才能执行。 高级语言：高级语言是一种面向问题或过程的语言。它是近似于日常会话的语言。它不但直观、易学，而且通用性强。高级语言要通过编译（或解释）翻译成机器语言才能执行。15、媒体的概念与分类:(1) 媒体的概念:信息的载体(2)媒体的分类：传输媒体、表现媒体、表示媒体、感觉媒体16、多媒体的基本概念：指有声有色的信息处理与利用技术。多媒体技术可划分为偏硬件技术和偏软件技术两部分。17、MPC 的组成：具有 CD-ROM、具有 A/D 和 D/A 转换功能、具有高清晰的彩色显示器、具有数据压缩与解压缩的硬件支持18、多媒体的关键技术：数据压缩与解压缩技术、芯片与插卡技术、多媒体操作系统技术、多媒体数据管理技术。19、超文本与超媒体的概念：(1)超文本是非线性非顺序的而传统文本是线性的顺序的。(2)超文本概念：超文本是收集、存储和浏览离散信息以及建立和表现信息之间关系的技术。(3)超媒体的组成：当信息载体不限于文本时，称之为超媒体。超媒体技术是一种典型的数据管理技术，它是由称之为结点(node)和表示结点之间联系的链 (link)组成的有向图（网络），用户可以对其进行浏览、查询和修改等操作。(4)超媒体系统的组成：编辑器、导航工具、超媒体语言第二章 网络的基本概念1 、信息技术涉及内容：信息的收集、储存、处理、传输与利用。2 、 计算机网络形成与发展大致分为如下 4 个阶段：（1）第一个阶段 20 世纪 50 年代（2） 第二个阶段以 20 世纪 60 年代美国的 APPANET 与分组交换技术为重要标志。（3） 第三个阶段从 20 世纪 70 年代中期开始。（4） 第四个阶段是 20 世纪 90 年代开始。3 、 计算机网络的基本特征：资源共享。4 、 计算机网络的定义：把分布在不同地理位置上的自治计算机通过通信设备和通信协议进行互联实现共享资源信息传输。5 、早期 计算机 网络结构实质上是广域网的结构。 广域网的功能：数据处理与数据通信。逻辑功能上可分为：资源子网与通信子网。资源子网负责全网的数据处理，向网络用户提供各种网络资源与网络服务。主要包括主机和终端。主机通过高速通信线路与通信子网的通信控制处理机相连接。终端是用户访问网络的界面。通信子网由通信控制处理机、通信线路与其他通信设备组成，完成网络数据传输、转发等通信处理任务。通信控制处理机在网络拓扑结构中被称为网络节点。通信线路为通信处理机之间以及通信处理机与主机之间提供通信信道。6 、现代网络机构的特点：微机通过局域网连入广域网，局域网与广域网、广域网与广域网的互联是通过路由器实现的。7 、按传输技术分为： 广播式网络（通过一条公共信道实现）点-点式网络（通过存储转发实现）。采用分组存储转发与路由选择是点-点式网络与广播网络的重要区别之一。8 、按规模分类：局域网（LAN）、城域网（MAN）、广域网（WAN）（1）广域网的通信子网采用分组交换技术，利用公用分组交换网、卫星通信网和无线分组交换网互联。（2）广域网（远程网）以下特点：1 适应大容量与突发性通信的要求。2 适应综合业务服务的要求。3 开放的设备接口与规范化的协议。4 完善的通信服务与网络管理。（3）几种常见的广域网的特点：X 25、FR 、SMDS、B-ISDN 、N-ISDN 、ATM（4）广域网扩大了资源共享的范围，局域网增强了资源共享的深度。（5）期的城域网产品主要是光纤分布式数据接口(FDDI)（6）各种城域网建设方案有几个相同点：传输介质采用光纤，交换接点采用基于 IP 交换的高速路由交换机或ATM 交换机，在体系结构上采用核心交换层，业务汇聚层与接入层三层模式。城域网 MAN 介于广域网与局域网之间的一种高速网络。9 、 计算机网络拓扑是通过网中结点与通信线路之间的几何关系表示网络结构，反映出网络中各实体间的结构关系。主要是指通信子网的拓扑构型。10、网络拓扑可以根据通信子网中通信信道类型分为：（1） 点- 点线路通信子网的拓扑：星型，环型，树型，网状型。（2）广播式通信子网的拓扑：总线型，树型，环型，无线通信与卫星通信型。11、描述数据通信的基本技术参数有两个：数据传输率与误码率。（1）数据传输速率 :在数值上等于每秒钟传输构成数据代码的二进制比特数,单位为比特/秒(bit/second),记作bps.对于二进制数据,数据传输速率为:S1/T(bps), 其中,T 为发送每一比特所需要的时间.（2）奈奎斯特准则：信号在无噪声的信道中传输时,对于二进制信号的最大数据传输率 Rmax 与通信信道带宽B（B=f ，单位是 Hz）的关系可以写为： Rmax=2*f(bps)（3）香农定理：香农定理则描述了有限带宽;有随机热噪声信道的最大传输速率与信道带宽;信号噪声功率比之间的关系.在有随机热噪声的信道上传输数据信号时，数据传输率 Rmax 与信道带宽 B，信噪比 S/N 关系为： Rmax=B*LOG （1+S/N）其中：B 为信道带宽，S 为信号功率， n 为噪声功率。（4）误码率是二进制码元在数据传输系统中被传错的概率，它在数值上近似等于：Pe=Ne/N （传错的除以总的）a 、误码率应该是衡量数据传输系统正常工作状态下传输可靠性的参数.b 、对于一个实际的数据传输系统,不能笼统地说误码率越低越好,要根据实际传输要求提出误码率要求;在数据传输速率确定后,误码率越低,传输系统设备越复杂,造价越高.c、对于实际数据传输系统,如果传输的不是二进制码元,要折合成二进制码元来计算.d 、差错的出现具有随机性,在实际测量一个数据传输系统时,只有被测量的传输二进制码元数越大,才会越接近于真正的误码率值.12、网络协议（1）概念：为网络数据传递交换而指定的规则，约定与标准被称为网络协议。（2）协议分为三部分： (1)语法,即用户数据与控制信息的结构和格式;(2)语义,即需要发出何种控制信息,以及完成的动作与做出的响应;(3)时序,即对事件实现顺序的详细说明.13、计算机网络体系结构（1）概念：将 计算机网络层次模型和各层协议的集合定义为计算机网络体系结构。（体现出的两个内涵请补充）（2）计算机 网络中采用层次结构，可以有以下好处：各层之间相互独立、灵活性好、各层都可以采用最合适的技术来实现各层实现技术的改变不影响其他各层、易于实现和维护、有利于促进标准化。14、ISO/OSI（国际标准化组织 / 开放系统互连参考模型）（1）功能：构建网络和设计网络时提供统一的标准（2）概述：采用分层的体系结构将整个庞大而复杂的问题划分为若干个容易处理的小问题，采用了三级抽象，既体系结构，服务定义，协议规格说明。实现了开放系统环境中的互连性，互操作性与应用的可移植性。（3）ISO 将整个通信功能划分为七个层次,划分层次的原则是:网中各结点都有相同的层次、不同结点的同等层具有相同的功能、同一结点内相邻层之间通过接口通信、每一层使用下层提供的服务,并向其上层提供服务、不同结点的同等层按照协议实现对等层之间的通信（补充服务、接口、协议的概念）.（4）OSI 七层：1 物理层：主要是利用物理传输介质为数据链路层提供物理连接，以便透明的传递比特流。（NIC、HUB ）2 数据链路层：分为 MAC 和 LLC，传送以帧为单位的数据，采用差错控制，流量控制方法。（NIC、SWITCH ）3 网络层：实现路由选择、拥塞控制和网络互连功能，使用 TCP 和 UDP 协议（ROUTER）4 传输层：是向用户提供可靠的端到端服务，透明的传送报文，使用 TCP 协议。5 会话层：组织两个会话进程之间的通信，并管理数据的交换使用 NETBIOS 和 WINSOCK 协议。6 表示层：处理在两个通信系统中交换信息的表示方式。7 应用层：应用层是 OSI 参考模型中的最高层。确定进程之间通信的性质，以满足用户的需要。15、TCP/IP 参考模型（1）TCP/IP 协议的特点：a、开放的协议标准，可以免费使用，并且独立于特定的计算机硬件与操作系统。b 、独立于特定的网络硬件，可以运行在局域网、广域网，更适用于互联网。c、统一的网络地址分配方案，使得整个 TCP/IP 设备在网中都具有唯一的地址。d 、标准化的高层协议，可以提供多种可靠的用户服务。（2）TCP/IP 参考模型可以分为：应用层，传输层，互连层，主机-网络层。（各层功能见教材 P33）（3）应用层协议分为 :a 、依赖于面向连接的 TCP 协议：主要有: 文件传送协议 FTP、电子邮件协议 SMTP 以及超文本传输协议HTTP 等b 、依赖于面向连接的 UDP 协议：主要有简单网络管理协议 SNMP;简单文件传输协议 TFTP.c、既依赖于 TCP 协议，也可以依赖于 UDP 协议：域名服务 DNS 等.16、ISO/OSI 参考模型与 TCP/IP 参考模型的比较17、NSFNET 采用的是一种层次结构，可以分为主干网，地区网与校园网。18、Internet2 的初始运行速率可达 10Gbps.Internet2 在网络层运行的是 IPv4，同时也支持 IPv6 业务.19、移动计算网络 P3920、多媒体网络是指能够传输多媒体数据的通信网络。多媒体网络需要支持多媒体传输所需要的交互性和实时性要求。网络视频会议系统是一种典型的网络多媒体系统。多媒体网络应用对数据通信的要求：1 高传输带宽要求；2 不同类型的数据对传输的要求不同；3 网络中的多媒体流传输的连续性与实时性要求；4 网络中多媒体数据传送的低时延要求；5 网络中的多媒体传输同步要求；6 网络中的多媒体的多方参与通信的特点。改进传统网络的方法是：增大带宽与改进协议。增大带宽可从传输介质和路由器性能两方面入手。改进协议主要表现在支持 IP 多播、资源预留协议、区分服务与多协议标识交换等方面。21、机群系统的分类与计算与存储区域网络 P42-43第三章 局域网基础1 、 局域网主要技术特点是：P452 、共享介质访问控制方式主要为：（1） 带有冲突检测的载波侦听多路访问 CSMA/CD 方法。（2）令牌总线方法（ TOKEN BUS）。（3）令牌环方法（ TOKEN RING）。3 、局域网参考模型（IEEE802）（1）IEEE802 参考模型：IEEE802 参考模型是美国电气电子工程师协会在 1980 年 2 月制订的，称为IEEE802 标准，这个标准对应于 OSI 参考模型的物理层和数据链路层，数据链路层又划分为逻辑链路控制子层（LLC）和介质访问控制子层（MAC ）。（2）IEEE803 标准(P49)（3）IEEE802.2 标准定义的共享局域网有三类：a 、采用 CSMA/CD 介质访问控制方法的总线型局域网。(ETHERNET)b 、采用 TOKEN BUS 介质访问控制方法的总线型局域网。c、采用 TOKEN RING 介质访问控制方法的环型局域网。（4）CSMA/CD 的发送流程可以简单的概括为：先听先发、边听边发、冲突停止、延迟重发。冲突检测是发送结点在发送的同时，将其发送信号波形与接受到的波形相比较。（5）TOKEN BUS（令牌总线方法）是一种在总线拓扑中利用“令牌”作为控制结点访问公共传输介质的确定型介质访问控制方法。所谓正常稳态操作是网络已经完成初始化，各结点进入正常传递令牌与数据，并且没有结点要加入与撤除，没有发生令牌丢失或网络故障的正常工作状态。令牌传递规定由高地址向低地址，最后由低地址向高地址传递。令牌总线网在物理上是总线网，而在逻辑上是环网。交出令牌的条件：1 该结点没有数据帧等待发送。2 该结点已经发完。3 令牌持有最大时间到。环维护工作：1 环初始化 2 新接点加入环 3 接点从环中撤出 4 环恢复 5 优先级（6）TOKEN RING（令牌环方法）4 、 CSMA/CD 与 TOKEN BUS、TOKEN RING 的比较5 、 ETHERNET 物理地址的基本概念（1） 地址与寻址的概念（2） ETHERNET 物理地址的长度（48 位）、构成、表示方法6 、共享介质局域网可分为 Ethernet，Token Bus，Token Ring 与 FDDI 以及在此基础上发展起来的 100Mbps Fast Ethernet、1Gbps 与 10Gbps Gigabit Ethernet。7 、交换式局域网可分为 Switch Ethernet 与 ATM LAN，以及在此基础上发展起来的虚拟局域网。8 、光纤分布式数据接口 FDDI 是一种以光纤作为传输介质的高速主干网。FDDI 主要技术特点:(1)使用基于 IEEE802.5 的单令牌的环网介质访问控制 MAC 协议;(2)使用 IEEE802.2 协议,与符合 IEEE802 标准的局域网兼容;(3)数据传输速率为 100Mbps,连网的结点数小于等于 1000,环路长度为 100km;(4)可以使用双环结构,具有容错能力;(5)可以使用多模或单模光纤;(6)具有动态分配带宽的能力,能支持同步和异步数据传输.9 、快速以太网（100Mbps Fast Ethernet） IEEE802.3U10、千兆位以太网（1Gbps Gigabit Ethernet） IEEE802.3Z Gigabit Ethernet 的传输速率比 Fast Ethernet（100Mbps）快 10 倍，达到 1000Mbps，将传统的 Ethernet 每个比特的发送时间由 100ns 降低到 1ns。11、10Gbps Gigabit Ethernet12、交换机的的帧转发方式：（各自特点）（1） 直接交换方式。（ 2） 存储转发交换方式。 （3） 改进直接交换方式。13、局域网交换机的特性：低交换传输延迟、高传输带宽、允许 10Mbps/100Mbps、局域网交换机可以支持虚拟局域网服务。14、虚拟网络（VLAN）（1）是建立在交换技术基础上（局域网交换机或 ATM 交换机）的，以软件的形式来实现逻辑组的划分与管理，逻辑工作组的结点组成不受物理位置的限制。（2）对虚拟网络成员的定义方法上，有以下 4 种：用交换机端口号定义虚拟局域网、用 MAC 地址定义虚拟局域网、用网络层地址定义虚拟局域网（用 IP 地址来定义）、IP 广播组虚拟局域网这种虚拟局域网的建立是动态的，它代表一组 IP 地址。15、无线局域网（1）无线局域网的应用领域 （P64 ）（2）红外无线局域网的主要特点及数据传输的三种技术 （P65）（3）扩频无线局域网： FHSS、DSSS （P66）（4）无线局域网标准： IEEE802.1116、IEEE 802.3 物理层标准类型 （请补充完整 P67）17、网卡是网络接口卡简称 NIC 是构成网络的基本部件。（1）网卡分类：按网卡支持的计算机种类：标准以太网卡。PCMCIA 网卡（用于便携式计算机）。按网卡支持的传输速率分类：普通的 10Mbps。高速的 100Mbps 网卡。10/100Mbps 自适应网卡。1000Mbps 网卡。按网卡支持的传输介质类型分类：双绞线网卡。粗缆网卡。细缆网卡。光纤网卡。(它们所使用的接口)18、局域集线器(HUB)普通的集线器两类端口：一类是用于连接接点的 RJ-45 端口，这类端口数可以是 8，12 ，16，24 等。另一类端口可以是用于连接粗缆的 AUI 端口，用于连接细缆的 BNC 端口，也可以是光纤连接端口，这类端口称为向上连接端口。按传输速率分类：1。10Mbps 集线器。2。100Mbps 集线器。 3。10Mbps/100Mbps 自适应集线器。按集线器是或能够堆叠分类：1。普通集线器。2 。可堆叠式集线器。按集线器是或支持网管功能：1。简单集线器。2 。带网管功能的集线器。19、局域网交换机（SWITCH）专用端口，共享端口。局域网交换机可以分为：1 简单的 10Mbps 交换机。2 10Mbps/100Mbps 自适应的局域网交换机。3 大型局域网交换机。20、各种组网方法21、结构化布线的地位及与传统布线的区别结构化布线系统与传统的布线系统最大的区别在于：结构化布线系统的结构与当前所连接的设备位置无关。结构化布线系统先预先按建筑物的结构，将建筑物中所有可能放置计算机及其外部设备的位置都布好了线，然后再根据实际所连接的设备情况，通过调整内部跳线装置，将所有计算机设备以及外部设备连接起来。22、智能大楼的组成:结构化布线系统、办公自动化系统（OA）、通信自动化系统（CA）、楼宇自动化系统（BA ）、计算机网络（CN）23、结构化布线系统的应用环境：建筑物综合布线系统、智能大楼布线系统、工业布线系统（各自特点）24、网络互连（1）同种局域网使用网桥就可以将分散在不同地理位置的多个局域网互连起来。（2）异型局域网可以用网桥、路由器或网关互连起来。（3）ATM 局域网与传统共享介质局域网互连必须解决局域网仿真问题。（4）路由器或网关是实现局域网与广域网、广域网与广域网互连的主要设备。（5）数据链路层互连的设备是网桥。网桥在网络互连中起到数据接收，地址过渡与数据转发的作用，它是实现多个网络系统之间的数据交换。（6）网络层互连的设备是路由器。如果网络层协议不同，采用多协议路由器。（7）传输层以上各层协议不同的网络之间的互连属于高层互连。实现高层互连的设备是网关。高层互连的网关很多是应用层网关，通常简称为应用网关。（8）网络互连指将分布在不同地理位置的网络，设备相连接，以构成更大规模的互联网络系统，实现互联系统网络资源的共享。（9）网络互连的要求（ P80）（10）网络互连的问题（P80）（11）网络互连的功能有以下两类：1 基本功能。2 扩展功能。（12）网桥是在数据链路层上实现不同网络互连的设备。（网桥的基本特征（P81）。 网桥在局域网中经常被用来将一个大型局域网分成既独立又能互相通信的多个子网的互连结构，从而可以改善各个子网的性能与安全性。 基于这两种标准的网桥分别是：透明网桥（IEEE802.1 适用于 ETHERNET）、源路选网桥（IEEE802.5 适用于 TOKEN RING）（13）路由器是在网络层上实现多个网络互连的设备。（14）网关可以完成不同网络协议之间的转换。实现协议转换的方法主要是：直接将网络信息包格式转化成输出网络信息包格式 N(N-1)； 将输入网络信息包的格式转化成一种统一的标准网间信息包的格式 2N。一个网关可以由两个半网关构成。第四章 网络操作系统1 、网络操作系统的三大阵营：UNIX、NOVELL 公司 Netware、Microsoft 公司 Windows NT2 、单机操作系统的功能：（1）进程管理 ：对 CPU 的管理，在 DOS 中启动进程机制函数为 EXEC 在 WINDOWS 或 OS/2 中是Createprocess（2）内存管理 ：对 RAM 用户区的管理，DOS 中的内存管理运行在实模式下而 WINDOWS 或 OS/2 中的运行在保护模式下（3）文件 I/O 管理：对硬盘的管理主要涉及文件的保护、保密、共享等。（文件名柄、FAT、VFAT、HPFS）3 、网络操作系统（NOS ）：（1）概述：是网络用户与 计算机之间的接口一般具有硬件独立性的特征即独立于具体的硬件平台支持多平台。（2）概念：能使网络上各个计算机方便而有效的共享网络资源，为用户提供所需要的各种服务的操作系统软件。（3）功能：使连网的 计算机能够方便而有效的共享网络资源，为网络用户提供所需要的各种服务的软件与协议的集合。（4）任务：屏蔽本地资源与网络资源的差异性、为用户提供各种基本网络服务功能、完成网络共享系统资源的管理、提供网络系统的安全性服务。4 、网络操作系统分为两类：面向任务型 NOS 与通用型 NOS。通用型又可以分为：变形系统与基础级系统。5 、网络操作系统的发展经历了从对等结构与非对等结构演变的过程。（1）对等结构网络操作系统的特点、优点、缺点、提供服务（2）非对等结构网络操作系统，将连网结点分为以下两类：1 网络服务器。2 网络工作站。虚拟盘体可以分为以下三类：专用盘体（分配给不同用户，用户通过网络命令将专用盘体链接到工作站）、共用盘体（具有只读属性，允许多用户同时操作）与共享盘体（具有可读可写属性，允许多用户同时操作）（3）基于文件服务的网络操作系统，分为两部分：文件服务器（具有分时系统文件管理的全部功能，能为用户提供数据、文件、目录服务）、工作站软件。6 、局域网软硬件的典型构成典型的局域网可以看成由以下三个部分组成：网络服务器，工作站与通信设备。7 、网络操作系统的基本功能：文件服务、打印服务、数据库服务、通信服务、信息服务、分布式服务、网络管理服务、Internet/Internet 服务（分别用一句话总结其特点）8 、 Windows NT（1）Windows NT Server 是服务器端软件， Windows NT Workstation 是客户机端软件（2）Windows NT 的版本不断变化过程中有两个概念始终没有变那就是工作组模型与域模型（3）域的概念与分类： P94（4）特点（ 5 个）： P94（5）Windows NT 的优缺点 P95第二章 数据结构算法 2.1 基本概率考点 1 数据结构的基本概念1.数据在计算机系统中，数据不仅包含了通常的数值概念，还有更广泛的含义我们把采用计算机对客观事物进行识别、存储和加工所做的描述，统称为数据。简言之，数据就是计算机化的信息数据的基本单位是数据元素。数据元素可由一个或多个数据项组成。数据项是数据的不可分割的最小单位，又称为关键码，其值能够唯一确定一个数据元素的数据项。2.数据结构数据结构包括 3 个方面的内容：数据之间的逻辑关系、数据在计算机中的存储方式，以及在这些数据上定义的运算的集合。(l)数据的逻辑结构。数据的逻辑结构与数据在计算机中的存储方式无关，它用来抽象地反映数据元素之间的逻辑关系。逻辑结构可分为线性结构和非线性结构。最常见的线性结构是线性表，最典型的非线性结构是树型结构。(2)数据的存储结构。数据的存储结构实现了数据的逻辑结构在计算机内的存储问题，存储结构又称为物理结构。存储结构分为顺序存储结构与链式存储结构。(3)数据的运算。数据的各种逻辑结构都有相对应的运算，每一种逻辑结构都有一个运算的集合。数据运算主要包括查找(检索)、排序、插人、更新及删除等。考点 2 主要的数据存储方式实现数据的逻辑结构到计算机存储器的映像有多种不同的方式。顺序存储结构和链式存储结构是两种最主要的存储方式。1.顺序存储结构顺序存储结构是将逻辑上相邻的数据元素存储在物理上相邻的存储单元里，节点之间的关系由存储单元的相邻关系来决定，它主要用于存储线性结构的数据。顺序存储结构的主要特点如下。(1)由于节点之间的关系由物理上的相邻关系决定，所以节点中没有链接信息域，只有自身的信息域，存储密度大，空间利用率高。(2)数据结构中第 i 个节点的存储地址乙可由下述公式计算求得：Li L0(i 1)K L0 为第一个节点存储地址，左为每个节点所占的存储单元数。(3)插人、删除运算会引起相应节点的大量移动各节点的物理地址是相邻的，每一次插人、删除运算会引起相应节点物理地址的重新排列。2.链式存储结构链式存储结构打破了计算机存储单元的连续性，可以将逻辑上相邻的两个数据元素存放在物理上不相邻的存储单元中链式存储结构的每个节点中至少有一个节点域，来体现数据之间逻辑上的联系。链式存储结构的主要特点包括以下几个方面。(1)节点中除自身信自、外，还有表示链接信息的指针域，因此比顺序存储结构的存储密度小，存储空间利用率低。(2)：罗辑上相邻的节点物理上不一定相邻，可用于线性表、树、图等多种逻辑结构的存储表示。(3)插人、删除等操作灵活方便，不需要大量移动节点，只需将节点的指针值修改即可。考点 3 算法设计与分析在计算机领域，一个算法实质上是针对所处理问题的需要，在数据的逻辑结构和存储结构的基础上施加的一种运算，它是解决特定问题的方法。一个算法所占用的计算机资源包括时间代价和空间代价两个方面时间代价的含义是：当问题的规模以某种单位由 1 增至 n 时，解决该问题的算法运行时所耗费的时间也以某种单位由f( 1)增至 f(n)，则称该算法的时间代价为 f(n)。空间代价的含义是：当问题的规模以某种单位由 1 增至 n 时，解决该问题的算法实现时所占用的空间也以某种单位由到 g(1)增至 g(n)，则称该算法的空间代价为 g(n)。2.2 线性表线性表的逻辑结构是由 n 个数据元素组成的一个有限序列。线性表中所包含元素的个数叫线性表的长度它是可变的可同线性表中增加或删除元素。线性表包括顺序表、链表、散列表和串等。线性表的基本运算有：置表空、求表长、读表元素、插人、删除及检索等操作。考点 4 顺序表和一维数组线性表的顺序存储是线性表的一种最简单的存储结构。其存储方法是：在内存中为线性表开辟一块连续的存储空间，该存储空间所包含的存储单元数要大于或等于线性表的长度，让线性表的第一个元素存储在这个存储空间的第一个单元中，第二个元素存储在第二个单元中，其他元素依次类推。一般情况下，若长度为 n 的顺序表，在任何位置土插入或删除的概率相等，元素移动的平均次数均为 n/2。考点 5 链表链表分为线性链表和非线性链表二线性链表是线性表的链式存储表示，非线性链表是非线性数据结构树和图的链式存储表示。1.线性链表线性链表也称为单链表，其每个一节点中只包含一个指针域。对链表进行插人、删除运算时只需改变节点中指针域的值。(1) 在指针一 P 后插人指针 9 的关键运算步骤： q . link：Plink ：p . link：q；(2)删除指针 P 后继节点 q 的关键运算步骤：q：p . link；p. link：qlink；(3)在第一个节点( 或称头节点) 前插人一个指针 P 的关键运算步骤：p. link：head；head：二 P；(4)删除表中头节点的关键运算步骤：head：head . link：2.双链表在双链表中，每个节点中设置有两个指针域，分别用以指向其前驱节点和后继节点。rlink 指向节点的后继，llink 指向节点的前驱，这样的结构方便向后和向前查找。(l)若要在双链表中删除指针 P 所指的节点时，只需修改其前驱的 rlink 字段和后继的 Mink 字段，步骤如下：p . llink. rlink：p. rlink；P Trlink. llink：P llink；(2)如果要在指针 P 后面插人指针 q 所指的新节点，只需修改 P 指针所指节点的 rlink 字段和原来后继均 Ilink 字段，并重新设置 q 所指节点的 Mink 和 rlink 值，步骤如下：q . Mink：P ：qrlink：Prlink;P rlink r. Rink：q；prlink：q;3.可利用空间表可利用空间表的作用是管理可用于链表插人和删除的节点，当链表插人需要一个新节点时，就从可利用空间表中删除第一个节点，用这个节点去做链表插人；当从链表中删除一个节点时，就把这个节点插人到可利用空间表的第一个节点前面。考点 6 栈栈又称为堆栈，它是一种运算受限的特殊的线性表，仅允许在表的一端进行插人和删除运算，可进行运算的一端为栈顶( top)，另一端为栈底( bottom)。表中无任何元素的栈称为空栈。由于栈的插人和删除运算仅在栈顶进行，后进栈的元素必定先被删除，所以又把栈称为“后进先出”(LIFO)表。栈的基本操作有：(1) push(S,X)。往栈 S 中插人(或称推人) 一个新的栈顶元素 x，即进栈。(2)pop(S)。从栈 S 中删除(或称弹出)栈顶元素，即出栈。(3)lop(S，X)：把栈 S 的栈顶元素读到变量 x 中，栈保持不变。(4)empty(S)。判断栈 S 是否为空栈，是则返回值为真。(5)makempty。(S)将栈 S 设置为空。栈既然是一种线性表，所以线性表的存储结构同样也适用于栈。栈通常用顺序存储方式来存储，分配一块连续的存储区域存放栈中元素，用一个变量来指向当前栈顶。考点 7 队列队列简称为队，它也是一种运算受限的线性表，队列的限定是仅允许在表的一端进行插入，而在另一端进行删除。进行删除操作的一端称做队列的头，进行插人操作的一端称为队列的尾.队列的基本操作有：(1) enq(Q, X)。往队列口中插人一个新的队尾元素 x，即人队。(2)deq(口)从队列 Q 中删除队头元素，即出队。(3 ) front 口,x)将队列口的队头元素值读到变量 x 中，队列保持不变。(4)empty ( Q )判断队歹，l 口是否为空，是则返回值为真。(5)makempty(口) 将队列口置为空队列。和线性表一样、队列的存储方式也有顺序存储和链式存储两种。顺序队列在进行人队操作时，会产生假溢出现象解决的办法是让队列首尾相连，构成一个循环队列。考点 8 串串(或字符串)是由零个或多个字符组成的有限序列。零个字符的串是空串。串中字符的个数就是串的长度串中的字符可以是字母、数字或其他字符。串的存储同样也有顺序存储和链式存储两种。顺序存储时，既可以采用非紧缩方式，也可以采用紧缩方式。串的基本运算有连接、赋值、求长度、全等比较、求子串、找子串位置及替换等，其中找子串位置(或称模式匹配) 比较重要。2.3 多维数组、稀疏矩阵和广义表考点 9 多维数组的顺序存储多维数组是一维数组的推广。多维数组的所有元素并未排在一个线性序列里，要顺序存储多维数组就需要按一定次序把所有的元素排在一个线性序列里。常用的排列次序有行优先顺序和列优先顺序两种。考点 10 稀疏矩阵的存储稀疏矩阵是指矩阵中含有大量的 0 元素。对稀疏矩阵可进行压缩存储，即只存储其中的非 0 元素。若非 0 元素分布是有规律的，可用顺序方法存储非 0 元素。对于一般的稀疏矩阵，常见的存储方法还有不元组法和十字链表法，这里就不再介绍了。考点 11 广义表的定义和存储广义表(又称列表)是线性表的另一种推广，是由零个或多个单元素或子表所组成的有限序列。它与线性表的区别在于：线性表中的元素都是结构上不可分的单元素，而广义表中的元素既可以是单元素，又可以是有结构的表广义表与线性表相比，具有如下 3 个方面的特征。(1)广义表的元素可以是子表，而子表的元素还可以是子表。(2)广义表可被其他广义表引用二(3)广义表可以是递归的表，即广义表也可以是自身的一个子表。2.4 树型结构树型结构是节点之间有分支的、层次关系的结构，它类似于自然界中的树，是一类重要的非线性结构常用的树型结构有树和二叉树。考点 12 树的定义树是树型结构的一个重要类型。一棵树或者是没有任何节点的空树，或者是由一个或多个节点组成的有限集合 T，其中：(1)有且仅有一个称为该树根的节点。(2)除根节点外的其余节点可分为。M(m0)个互不相交的有限集 71,，兀，T ，其中每一个集合本身又是一棵树，并且称为根的子树。这是一个递归的定义，即在树的定义中又用到了树的概念。这恰好显示了树的固有特性。考点 13 二叉树定义1.二叉树的定义二叉树是一种最简单而巨重要的树型结构它或者是一棵空树，或者是一棵由一个根节点和两棵互不相交的、分别称为这个根的左子树和右子树的二叉树组成。有两种特殊形态的二叉树，它们是满二叉树一和完全二叉树。2.二叉树与树的区别尽管树和二叉树的概念之间有许多关系，但它们是两个概念二叉树不是树的特殊情况，树和二叉树之间最主要的区别是：二叉树的节点的子树要区分左子树和了。子树，即使在节点只有一棵子树的情况下也要明确指出该子树是左子树还是右子树。 考点 14 树与二叉树之间的转换1.树转换成二叉树将一棵树转换成相应的二叉树应包括以下几个步骤：(1)在兄弟竹点之间加条连线(2)对每一个节点，只保留它与第一个子节点的连线，与其他子节点连线全部抹掉(3)以树根为轴心，顺时针旋转 45。2.森林转换成二叉树如果 F=T1 ，T2 ,Tm是森林，则可按如下规则将其转换乘一棵二叉树 B=(root,LB,RB,)：(1)若 F 为空，即 m0，则 B 为树。(2)若 F 非空，即 m0, 则 B 的跟 root 即为森林中的第一棵树的跟 ROOT(T)；B 的左子树 LB 是从 T、中根节点的子树森林 F1 T11，T，Tm转换而成的二叉树；其右子树 RB 是从森林 FT1,T2,Tm转换而成的二叉树。3.二叉树转换成森林如果 B 二(root，LB，RB)是、棵二叉树，则可按如下规则转换成森林 FT1,T2,Tm： (1)若 B 为空，则 F 为空。(2)若 B 非空，则 F 中第一棵树 T1 的根 ROOT(T1)即为二叉树 B 的根 root; T1 中根节点的子树森林 Fl 是由 B 的左子树LB 转换而成的；F 中除 T1 之外其余树组成的森林 F T1,T2,Tm是由 B 的右子树 RB 转换而成的。考点 15 二叉树和树的周游周游(或称遍历)是树型结构的一种重要运算，是其他运算的基础。周游一棵树就是按一定的次序访问树中听有节点，并且每个节点仅被访问一次的过程。1.周游二叉树二又树的周游主要有以下 3 种方式。(1)前序法(NLR)。访问根，按前序周游左子树，按前序周游右子树。(2)后序法(LRN)。按后序周游左子树，按后序周游右子树，访问根。(3)对称序法(LNR) 。按对称序周游左子树，访问根，按对称序周游右子树。2.周游树和树林对树和树林的周游分为按深度优先和按广度优先两种方式进行。按深度优先方式又可分为按先根次序和按后根次序周游两种方式。(1)先根次序周游访问第一棵树的根，按先根次序周游第一棵树的根子树，按先根次序周游其他的树。(2)后根次序周游按后根次序周游第一棵树的子树，访问第一棵树的根，按后根次序周游其他的树。比较一下树与一又树之间的对应关系，可以看出，按先根次序周游树正好与按前序法周游树对应的二叉树等同，后根次序周游树正好与按对称序法周游对应的二叉树等同。按广度优先方式可以做层次次序周游，首先依次访问层数为 0 的节点，然后依次访问下一层的节点，直至访问完最后一层的节点。考点 16 二叉树的存储和线索l 二叉树的 llink 一 rlink 法存储表示二叉树的存储通常采用链接方式，即每个节点除存储节点自身的信息外再设置两个指针域 llink 和 rlink，分别指向节点的左子女和右子女。当节点的某个子女为空时，则相应的指针值为空。再加上一个指向树根的指针 t，就构成了二叉树的存储表示。这种存储表示法被称为 llink - rlink 表示法。2.线索二叉树在有 n 个节点的二叉树的且 ink - rlink 法存储表示中，必定有 n+1 个空指针域，将这些指针位置利用起来，存储节点在指定周游次序 F 的前驱、后继节点指针，则得到线索二叉树。考点 17 哈夫曼树哈夫曼树是树型结构的一种应用二哈夫曼(Huffman)树又称最优树，是一类带权路径长度最短的树，这种树在信息检索中经常用到。所谓路径长度就是从一个节点到另一个节点所经过的分支总数。树的路径长度是从树的根到每个节点的路径长度之和。完全二叉树就是这种路径长度最短的二叉树。节点的带权路径长度为从该节点到树根之间的路径长度与节点上权的乘积。树的带权路径长度为树中所有叶子节点的带权路径长度之和，WPL 最小的不是完全二叉树，而是权大的叶子离根最近的二叉树。2.5“查找查找是数据结构中一种很常用的基本运算。查找就是在数据结构中找出满足某种条件的节点。所给的条件可以是关键码字段的值，也可以是非关键码字段的值，本节只考虑基于关键码值的查找考点 18 顺序查找顺序查找是线性表的最简单、最基本的查找方法顺序查找的优点是对线性表节点的逻辑次序无要求，对线性表存储结构也无要求顺序查找的缺点是速度较慢，平均检索长度与表中节点个数和 n 成正比，查找成功最多需比较 n 次，平均查找长度为(n +1 )/2 次，约为表长的，半，查找失败需比较 n+l 次顺序查找算法的时间复杂度为 O(n)。考点 19 二分法查找二分法查找是一种效率比较高的查找方法，在进行二分法查找时，线性表节点必须按关键码值排序，且 线性表是以顺序存储方式存储的。二分法查找的优点是比较次数少，查找速度快，平均检索长度小，经过loge n 次比较就可以完成查找过程。缺点是在查找之前要为建立有序表付出代价，同时对有序表的插人和删除都需要平均比较和移动表中 的一半元素。一般情况下，二分查找适应于数据相对固定的情况，且二分法查找只适用于线性表的顺序存储。考点 20 分块查找分块查找又称索引顺序查找，是介于线性查找和二分法查找之间的一种查找方法。它要求把线性表分 成若干块，每一块中的节点不必有序，但块与块之间必须排序，不妨设每一块中各节点的关键码都大于前一块的最大关键码值。另外，还要求将各块中的最大关键码值组成一个有序的索引表。满足上述条件的线性 表称做分块有序表。它的分块检索的过程分以下两步进行。(I)先查索引表(可以用线性检索或二分法检索)，确定要找的记录在哪一块。(2)在相应的块中线性检索待查记录。考点 21 散列表的存储和查找散列存储中使用的函数称为散列(Hash)函数散列表( 又称哈希表) 是线性表的一种重要的存储方式 和检索方法。实现散列技术检索必须解决两个问题：一个是构造一个好的散列函数，尽可能避免冲突现象的发生；另一个是设计有效的解决冲突的方法。1.散列函数常用的散列函数有以下几种。(l)除余法。选择一个适当的正整数川通常选 p 为不大于散列表存储区域大刁、的最大素数)，用 p 去除 关键码值，取其余数作为地址，即 h(key)二 key mod p。(2)数字分析法。当关键码的位数比存储区域地址码位数多时，可以对关键码的各位进行分析，去掉分 布不均匀的位，留下分布均匀的位作为地址。(3)折叠法。将关键码值从某些地方断开，分为几段，折叠相加，作为地址。(4)中平方法。对关键码值求平方，取中间的几位数作为地址。2.处理冲突的方法发生冲突是指由关键字求得的散列地址为 i(O-i-m 一 l)的位置上已存有记录，处理冲突就是为该关健字找到另一个“空”的散列地址。常用的处理冲突的方法有开地址法、拉链法等。3.负载因子(装填因子)和平均检索长度装填因子表示散列表的装满程度，定义为散列表中节点的数目除以基本区域能容纳的节点数所得的商，用 a 表示 a 越小，冲突的可能性越小，a 越大，冲突的可能性越大，检索时需要比较的次数就越多。平均检索长度依赖于散列表的装填因子。2.6 排序排序是数据处理领域经常要使用的一种运算，就是将一组元素按照关键码的递增或递减的顺序来排列为过程按照排序过程中的存储器不同，可将排序方法分为内部排序和外部排序两类。一厂面将介绍插人排序、选择排序、交换排序和归并排序等几种常用的内部排序方法。考点 22 插入排序插人排序的基本思想：每一步将一个待排序的记录按其关键字值的大小插人到一个有序的文件中，插人后该文件仍然是有序文件。l.直接插入排序直接插人排序是一种最简单的排序方法它的基木思想是将一个记录插人到已排好序的有序表中，从而得到一个新的、记录数增 I 的有序表整个排序过程为：先将第一个记录看成是一个有序的子序列，然后从第 2 个记录起依次逐个地插人到这个有序的子序列中去。直接插人排序的时间复杂度为 0(n )。直接插人排序方法不仅适用于顺序表，而且适用于单链表2.二分法插入排序在直接插人排序 ， ，若采用二分法查找而不是顺序查找待插入元素的插人位置，则称为二分法