全国计算机等级考试 三级数据库技术笔记 基础知识

第一章计算机基础知识1、计算机的发展阶段经历了以下5个阶段它们是并行关系大型机阶段经历四小阶段它们是取代关系、小型机阶段、微型机阶段、客户机/服务器阶段（对等网络与非对等网络的概念）和互联网阶段（ARPANET是在1983年第一个使用TCP/IP协议的。在1991年6月我国第一条与国际互联网连接的专线建成它从中国科学院高能物理研究所接到美国斯坦福大学的直线加速器中心。在1994年实现4大主干网互连中国公用计算机互联网CHINANET、中国科学技术网CSTNET、中国教育和科研计算机网CERNET、中国金桥信息网CHINAGBN）2、计算机种类按照传统的分类方法计算机可以分为6大类大型主机、小型计算机、个人计算机、工作站、巨型计算机、小巨型机。按照现实的分类方法计算机可以分为5大类服务器、工作站、台式机、笔记本、手持设备。3、计算机的公共配置CPU、内存（RAM）、高速缓存（CACHE）、硬盘、光驱、显示器CRT、LCD、操作系统OS4、计算机的指标位数指CPU寄存器中能够保存数据的位数、速度MIPS、MFLOPS指CPU每秒钟处理的指令数通常用主频来表示CPU的处理速度、容量（B、KB、MB、GB、TB）、数据传输率（BPS）、版本和可靠性（MTBF、MTTR）。5、计算机的应用领域科学计算、事务处理、过程控制、辅助工程、人工智能、网络应用。（补充实例）6、计算机系统的组成硬件系统具有原子特性芯片、板卡、设备、网络与软件系统具有比特特性。且它们具有同步性。7、奔腾芯片的技术特点奔腾32位芯片，主要用于台式机和笔记本，奔腾采用了RISC和CISC技术技术特点10个请看书P88、安腾芯片的技术特点安腾是64位芯片，主要用于服务器和工作站。安腾采用简明并行指令计算（EPIC）技术9、主机板与插卡的组成1主机板简称主板MAINBOARD或母板MOTHERBOARD。由5部分组成（CPU、存储器、总线、插槽和电源）与主板的分类2网络卡又称为适配器卡代号NIC，其功能为（见书P11）10、软件的基本概念软件由程序功能实现部分与文档功能说明部分组成。软件是用户与计算机硬件系统之间的桥梁。11、应用软件包括桌面应用软件、演示出版软件、浏览工具软件、管理效率软件、通信协作软件和系统维护软件。12、程序与文档程序是由指令序列组成的，告诉计算计如何完成一个具体的任务。文档是软件开发、使用和维护中的必备资料。13、软件开发软件的生命周期中，通常分为三大阶段，每个阶段又分若干子阶段计划阶段分为问题定义、可行性研究（是决定软件项目是否开发的关键）。开发阶段在开发前期分为需求分析、总体设计、详细设计三个子阶段，在开发后期分为编码、测试两个子阶段。前期必须形成的文档有软件需求说明书，软件设计规格说明书。运行阶段主要任务是软件维护。为了排除软件系统中仍然可能隐含的错误，扩充软件功能。14、编程语言（机器语言与汇编语言都依赖于具体的机器，汇编语言与高级语言都需要编译）机器语言能被计算机直接理解和执行，速度快，但该种语言难记、难学、难懂。汇编语言用英文助记符和十进制数代替二进制码，使机器语言变成了汇编语言。汇编语言属于低级语言。汇编语言要通过汇编程序把汇编语言翻译成机器语言程序计算机才能执行。高级语言高级语言是一种面向问题或过程的语言。它是近似于日常会话的语言。它不但直观、易学，而且通用性强。高级语言要通过编译（或解释）翻译成机器语言才能执行。15、媒体的概念与分类1媒体的概念信息的载体2媒体的分类传输媒体、表现媒体、表示媒体、感觉媒体16、多媒体的基本概念指有声有色的信息处理与利用技术。多媒体技术可划分为偏硬件技术和偏软件技术两部分。17、MPC的组成具有CDROM、具有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）几种常见的广域网的特点X25、FR、SMDS、BISDN、NISDN、ATM（4）广域网扩大了资源共享的范围，局域网增强了资源共享的深度。（5）期的城域网产品主要是光纤分布式数据接口FDDI（6）各种城域网建设方案有几个相同点传输介质采用光纤，交换接点采用基于IP交换的高速路由交换机或ATM交换机，在体系结构上采用核心交换层，业务汇聚层与接入层三层模式。城域网MAN介于广域网与局域网之间的一种高速网络。9、计算机网络拓扑是通过网中结点与通信线路之间的几何关系表示网络结构，反映出网络中各实体间的结构关系。主要是指通信子网的拓扑构型。10、网络拓扑可以根据通信子网中通信信道类型分为（1）点点线路通信子网的拓扑星型，环型，树型，网状型。（2）广播式通信子网的拓扑总线型，树型，环型，无线通信与卫星通信型。11、描述数据通信的基本技术参数有两个数据传输率与误码率。（1）数据传输速率在数值上等于每秒钟传输构成数据代码的二进制比特数,单位为比特/秒BIT/SECOND,记作BPS对于二进制数据,数据传输速率为S1/TBPS,其中,T为发送每一比特所需要的时间（2）奈奎斯特准则信号在无噪声的信道中传输时,对于二进制信号的最大数据传输率RMAX与通信信道带宽B（BF，单位是HZ）的关系可以写为RMAX2FBPS（3）香农定理香农定理则描述了有限带宽有随机热噪声信道的最大传输速率与信道带宽信号噪声功率比之间的关系在有随机热噪声的信道上传输数据信号时，数据传输率RMAX与信道带宽B，信噪比S/N关系为RMAXBLOG（1S/N）其中B为信道带宽，S为信号功率，N为噪声功率。（4）误码率是二进制码元在数据传输系统中被传错的概率，它在数值上近似等于PENE/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简单文件传输协议TFTPC、既依赖于TCP协议，也可以依赖于UDP协议域名服务DNS等16、ISO/OSI参考模型与TCP/IP参考模型的比较17、NSFNET采用的是一种层次结构，可以分为主干网，地区网与校园网。18、INTERNET2的初始运行速率可达10GBPSINTERNET2在网络层运行的是IPV4，同时也支持IPV6业务19、移动计算网络P3920、多媒体网络是指能够传输多媒体数据的通信网络。多媒体网络需要支持多媒体传输所需要的交互性和实时性要求。网络视频会议系统是一种典型的网络多媒体系统。多媒体网络应用对数据通信的要求1高传输带宽要求；2不同类型的数据对传输的要求不同；3网络中的多媒体流传输的连续性与实时性要求；4网络中多媒体数据传送的低时延要求；5网络中的多媒体传输同步要求；6网络中的多媒体的多方参与通信的特点。改进传统网络的方法是增大带宽与改进协议。增大带宽可从传输介质和路由器性能两方面入手。改进协议主要表现在支持IP多播、资源预留协议、区分服务与多协议标识交换等方面。21、机群系统的分类与计算与存储区域网络P4243第三章局域网基础1、局域网主要技术特点是P452、共享介质访问控制方式主要为（1）带有冲突检测的载波侦听多路访问CSMA/CD方法。（2）令牌总线方法（TOKENBUS）。（3）令牌环方法（TOKENRING）。3、局域网参考模型（IEEE802）（1）IEEE802参考模型IEEE802参考模型是美国电气电子工程师协会在1980年2月制订的，称为IEEE802标准，这个标准对应于OSI参考模型的物理层和数据链路层，数据链路层又划分为逻辑链路控制子层（LLC）和介质访问控制子层（MAC）。（2）IEEE803标准P49（3）IEEE8022标准定义的共享局域网有三类A、采用CSMA/CD介质访问控制方法的总线型局域网。ETHERNETB、采用TOKENBUS介质访问控制方法的总线型局域网。C、采用TOKENRING介质访问控制方法的环型局域网。（4）CSMA/CD的发送流程可以简单的概括为先听先发、边听边发、冲突停止、延迟重发。冲突检测是发送结点在发送的同时，将其发送信号波形与接受到的波形相比较。（5）TOKENBUS（令牌总线方法）是一种在总线拓扑中利用“令牌”作为控制结点访问公共传输介质的确定型介质访问控制方法。所谓正常稳态操作是网络已经完成初始化，各结点进入正常传递令牌与数据，并且没有结点要加入与撤除，没有发生令牌丢失或网络故障的正常工作状态。令牌传递规定由高地址向低地址，最后由低地址向高地址传递。令牌总线网在物理上是总线网，而在逻辑上是环网。交出令牌的条件1该结点没有数据帧等待发送。2该结点已经发完。3令牌持有最大时间到。环维护工作1环初始化2新接点加入环3接点从环中撤出4环恢复5优先级（6）TOKENRING（令牌环方法）4、CSMA/CD与TOKENBUS、TOKENRING的比较5、ETHERNET物理地址的基本概念（1）地址与寻址的概念（2）ETHERNET物理地址的长度（48位）、构成、表示方法6、共享介质局域网可分为ETHERNET，TOKENBUS，TOKENRING与FDDI以及在此基础上发展起来的100MBPSFASTETHERNET、1GBPS与10GBPSGIGABITETHERNET。7、交换式局域网可分为SWITCHETHERNET与ATMLAN，以及在此基础上发展起来的虚拟局域网。8、光纤分布式数据接口FDDI是一种以光纤作为传输介质的高速主干网。FDDI主要技术特点1使用基于IEEE8025的单令牌的环网介质访问控制MAC协议2使用IEEE8022协议,与符合IEEE802标准的局域网兼容3数据传输速率为100MBPS,连网的结点数小于等于1000,环路长度为100KM4可以使用双环结构,具有容错能力5可以使用多模或单模光纤6具有动态分配带宽的能力,能支持同步和异步数据传输9、快速以太网（100MBPSFASTETHERNET）IEEE8023U10、千兆位以太网（1GBPSGIGABITETHERNET）IEEE8023ZGIGABITETHERNET的传输速率比FASTETHERNET（100MBPS）快10倍，达到1000MBPS，将传统的ETHERNET每个比特的发送时间由100NS降低到1NS。11、10GBPSGIGABITETHERNET12、交换机的的帧转发方式（各自特点）（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）无线局域网标准IEEE8021116、IEEE8023物理层标准类型（请补充完整P67）17、网卡是网络接口卡简称NIC是构成网络的基本部件。（1）网卡分类按网卡支持的计算机种类标准以太网卡。PCMCIA网卡（用于便携式计算机）。按网卡支持的传输速率分类普通的10MBPS。高速的100MBPS网卡。10/100MBPS自适应网卡。1000MBPS网卡。按网卡支持的传输介质类型分类双绞线网卡。粗缆网卡。细缆网卡。光纤网卡。它们所使用的接口18、局域集线器HUB普通的集线器两类端口一类是用于连接接点的RJ45端口，这类端口数可以是8，12，16，24等。另一类端口可以是用于连接粗缆的AUI端口，用于连接细缆的BNC端口，也可以是光纤连接端口，这类端口称为向上连接端口。按传输速率分类1。10MBPS集线器。2。100MBPS集线器。3。10MBPS/100MBPS自适应集线器。按集线器是或能够堆叠分类1。普通集线器。2。可堆叠式集线器。按集线器是或支持网管功能1。简单集线器。2。带网管功能的集线器。19、局域网交换机（SWITCH）专用端口，共享端口。局域网交换机可以分为1简单的10MBPS交换机。210MBPS/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）。网桥在局域网中经常被用来将一个大型局域网分成既独立又能互相通信的多个子网的互连结构，从而可以改善各个子网的性能与安全性。基于这两种标准的网桥分别是透明网桥（IEEE8021适用于ETHERNET）、源路选网桥（IEEE8025适用于TOKENRING）（13）路由器是在网络层上实现多个网络互连的设备。（14）网关可以完成不同网络协议之间的转换。实现协议转换的方法主要是直接将网络信息包格式转化成输出网络信息包格式NN1；将输入网络信息包的格式转化成一种统一的标准网间信息包的格式2N。一个网关可以由两个半网关构成。第四章网络操作系统1、网络操作系统的三大阵营UNIX、NOVELL公司NETWARE、MICROSOFT公司WINDOWSNT2、单机操作系统的功能（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、WINDOWSNT（1）WINDOWSNTSERVER是服务器端软件，WINDOWSNTWORKSTATION是客户机端软件（2）WINDOWSNT的版本不断变化过程中有两个概念始终没有变那就是工作组模型与域模型（3）域的概念与分类P94（4）特点（5个）P94（5）WINDOWSNT的优缺点P95第二章数据结构算法21基本概率考点1数据结构的基本概念1数据在计算机系统中，数据不仅包含了通常的数值概念，还有更广泛的含义我们把采用计算机对客观事物进行识别、存储和加工所做的描述，统称为数据。简言之，数据就是计算机化的信息数据的基本单位是数据元素。数据元素可由一个或多个数据项组成。数据项是数据的不可分割的最小单位，又称为关键码，其值能够唯一确定一个数据元素的数据项。2数据结构数据结构包括3个方面的内容数据之间的逻辑关系、数据在计算机中的存储方式，以及在这些数据上定义的运算的集合。L数据的逻辑结构。数据的逻辑结构与数据在计算机中的存储方式无关，它用来抽象地反映数据元素之间的逻辑关系。逻辑结构可分为线性结构和非线性结构。最常见的线性结构是线性表，最典型的非线性结构是树型结构。2数据的存储结构。数据的存储结构实现了数据的逻辑结构在计算机内的存储问题，存储结构又称为物理结构。存储结构分为顺序存储结构与链式存储结构。3数据的运算。数据的各种逻辑结构都有相对应的运算，每一种逻辑结构都有一个运算的集合。数据运算主要包括查找检索、排序、插人、更新及删除等。考点2主要的数据存储方式实现数据的逻辑结构到计算机存储器的映像有多种不同的方式。顺序存储结构和链式存储结构是两种最主要的存储方式。1顺序存储结构顺序存储结构是将逻辑上相邻的数据元素存储在物理上相邻的存储单元里，节点之间的关系由存储单元的相邻关系来决定，它主要用于存储线性结构的数据。顺序存储结构的主要特点如下。1由于节点之间的关系由物理上的相邻关系决定，所以节点中没有链接信息域，只有自身的信息域，存储密度大，空间利用率高。2数据结构中第I个节点的存储地址乙可由下述公式计算求得LIL0I1KL0为第一个节点存储地址，左为每个节点所占的存储单元数。3插人、删除运算会引起相应节点的大量移动各节点的物理地址是相邻的，每一次插人、删除运算会引起相应节点物理地址的重新排列。2链式存储结构链式存储结构打破了计算机存储单元的连续性，可以将逻辑上相邻的两个数据元素存放在物理上不相邻的存储单元中链式存储结构的每个节点中至少有一个节点域，来体现数据之间逻辑上的联系。链式存储结构的主要特点包括以下几个方面。1节点中除自身信自、外，还有表示链接信息的指针域，因此比顺序存储结构的存储密度小，存储空间利用率低。2罗辑上相邻的节点物理上不一定相邻，可用于线性表、树、图等多种逻辑结构的存储表示。3插人、删除等操作灵活方便，不需要大量移动节点，只需将节点的指针值修改即可。考点3算法设计与分析在计算机领域，一个算法实质上是针对所处理问题的需要，在数据的逻辑结构和存储结构的基础上施加的一种运算，它是解决特定问题的方法。一个算法所占用的计算机资源包括时间代价和空间代价两个方面时间代价的含义是当问题的规模以某种单位由1增至N时，解决该问题的算法运行时所耗费的时间也以某种单位由F1增至FN，则称该算法的时间代价为FN。空间代价的含义是当问题的规模以某种单位由1增至N时，解决该问题的算法实现时所占用的空间也以某种单位由到G1增至GN，则称该算法的空间代价为GN。22线性表线性表的逻辑结构是由N个数据元素组成的一个有限序列。线性表中所包含元素的个数叫线性表的长度它是可变的可同线性表中增加或删除元素。线性表包括顺序表、链表、散列表和串等。线性表的基本运算有置表空、求表长、读表元素、插人、删除及检索等操作。考点4顺序表和一维数组线性表的顺序存储是线性表的一种最简单的存储结构。其存储方法是在内存中为线性表开辟一块连续的存储空间，该存储空间所包含的存储单元数要大于或等于线性表的长度，让线性表的第一个元素存储在这个存储空间的第一个单元中，第二个元素存储在第二个单元中，其他元素依次类推。一般情况下，若长度为N的顺序表，在任何位置土插入或删除的概率相等，元素移动的平均次数均为N/2。考点5链表链表分为线性链表和非线性链表二线性链表是线性表的链式存储表示，非线性链表是非线性数据结构树和图的链式存储表示。1线性链表线性链表也称为单链表，其每个一节点中只包含一个指针域。对链表进行插人、删除运算时只需改变节点中指针域的值。1在指针一P后插人指针9的关键运算步骤QLINKPLINKPLINKQ；2删除指针P后继节点Q的关键运算步骤QPLINK；PLINKQLINK；3在第一个节点或称头节点前插人一个指针P的关键运算步骤PLINKHEAD；HEAD二P；4删除表中头节点的关键运算步骤HEADHEADLINK2双链表在双链表中，每个节点中设置有两个指针域，分别用以指向其前驱节点和后继节点。RLINK指向节点的后继，LLINK指向节点的前驱，这样的结构方便向后和向前查找。L若要在双链表中删除指针P所指的节点时，只需修改其前驱的RLINK字段和后继的MINK字段，步骤如下PLLINKRLINKPRLINK；PTRLINKLLINKPLLINK；2如果要在指针P后面插人指针Q所指的新节点，只需修改P指针所指节点的RLINK字段和原来后继均ILINK字段，并重新设置Q所指节点的MINK和RLINK值，步骤如下QMINKPQRLINKPRLINKPRLINKRRINKQ；PRLINKQ3可利用空间表可利用空间表的作用是管理可用于链表插人和删除的节点，当链表插人需要一个新节点时，就从可利用空间表中删除第一个节点，用这个节点去做链表插人；当从链表中删除一个节点时，就把这个节点插人到可利用空间表的第一个节点前面。考点6栈栈又称为堆栈，它是一种运算受限的特殊的线性表，仅允许在表的一端进行插人和删除运算，可进行运算的一端为栈顶TOP，另一端为栈底BOTTOM。表中无任何元素的栈称为空栈。由于栈的插人和删除运算仅在栈顶进行，后进栈的元素必定先被删除，所以又把栈称为“后进先出”LIFO表。栈的基本操作有1PUSHS,X。往栈S中插人或称推人一个新的栈顶元素X，即进栈。2POPS。从栈S中删除或称弹出栈顶元素，即出栈。3LOPS，X把栈S的栈顶元素读到变量X中，栈保持不变。4EMPTYS。判断栈S是否为空栈，是则返回值为真。5MAKEMPTY。S将栈S设置为空。栈既然是一种线性表，所以线性表的存储结构同样也适用于栈。栈通常用顺序存储方式来存储，分配一块连续的存储区域存放栈中元素，用一个变量来指向当前栈顶。考点7队列队列简称为队，它也是一种运算受限的线性表，队列的限定是仅允许在表的一端进行插入，而在另一端进行删除。进行删除操作的一端称做队列的头，进行插人操作的一端称为队列的尾队列的基本操作有1ENQQ,X。往队列口中插人一个新的队尾元素X，即人队。2DEQ口从队列Q中删除队头元素，即出队。3FRONT口,X将队列口的队头元素值读到变量X中，队列保持不变。4EMPTYQ判断队歹，L口是否为空，是则返回值为真。5MAKEMPTY口将队列口置为空队列。和线性表一样、队列的存储方式也有顺序存储和链式存储两种。顺序队列在进行人队操作时，会产生假溢出现象解决的办法是让队列首尾相连，构成一个循环队列。考点8串串或字符串是由零个或多个字符组成的有限序列。零个字符的串是空串。串中字符的个数就是串的长度串中的字符可以是字母、数字或其他字符。串的存储同样也有顺序存储和链式存储两种。顺序存储时，既可以采用非紧缩方式，也可以采用紧缩方式。串的基本运算有连接、赋值、求长度、全等比较、求子串、找子串位置及替换等，其中找子串位置或称模式匹配比较重要。23多维数组、稀疏矩阵和广义表考点9多维数组的顺序存储多维数组是一维数组的推广。多维数组的所有元素并未排在一个线性序列里，要顺序存储多维数组就需要按一定次序把所有的元素排在一个线性序列里。常用的排列次序有行优先顺序和列优先顺序两种。考点10稀疏矩阵的存储稀疏矩阵是指矩阵中含有大量的0元素。对稀疏矩阵可进行压缩存储，即只存储其中的非0元素。若非0元素分布是有规律的，可用顺序方法存储非0元素。对于一般的稀疏矩阵，常见的存储方法还有不元组法和十字链表法，这里就不再介绍了。考点11广义表的定义和存储广义表又称列表是线性表的另一种推广，是由零个或多个单元素或子表所组成的有限序列。它与线性表的区别在于线性表中的元素都是结构上不可分的单元素，而广义表中的元素既可以是单元素，又可以是有结构的表广义表与线性表相比，具有如下3个方面的特征。1广义表的元素可以是子表，而子表的元素还可以是子表。2广义表可被其他广义表引用二3广义表可以是递归的表，即广义表也可以是自身的一个子表。24树型结构树型结构是节点之间有分支的、层次关系的结构，它类似于自然界中的树，是一类重要的非线性结构常用的树型结构有树和二叉树。考点12树的定义树是树型结构的一个重要类型。一棵树或者是没有任何节点的空树，或者是由一个或多个节点组成的有限集合T，其中1有且仅有一个称为该树根的节点。2除根节点外的其余节点可分为。MM0个互不相交的有限集71,，兀，T，其中每一个集合本身又是一棵树，并且称为根的子树。这是一个递归的定义，即在树的定义中又用到了树的概念。这恰好显示了树的固有特性。考点13二叉树定义1二叉树的定义二叉树是一种最简单而巨重要的树型结构它或者是一棵空树，或者是一棵由一个根节点和两棵互不相交的、分别称为这个根的左子树和右子树的二叉树组成。有两种特殊形态的二叉树，它们是满二叉树一和完全二叉树。2二叉树与树的区别尽管树和二叉树的概念之间有许多关系，但它们是两个概念二叉树不是树的特殊情况，树和二叉树之间最主要的区别是二叉树的节点的子树要区分左子树和了。子树，即使在节点只有一棵子树的情况下也要明确指出该子树是左子树还是右子树。考点14树与二叉树之间的转换1树转换成二叉树将一棵树转换成相应的二叉树应包括以下几个步骤1在兄弟竹点之间加条连线2对每一个节点，只保留它与第一个子节点的连线，与其他子节点连线全部抹掉3以树根为轴心，顺时针旋转45。2森林转换成二叉树如果FT1，T2,TM是森林，则可按如下规则将其转换乘一棵二叉树BROOT,LB,RB,1若F为空，即M0，则B为树。2若F非空，即M0,则B的跟ROOT即为森林中的第一棵树的跟ROOTT；B的左子树LB是从T、中根节点的子树森林F1T11，T，TM转换而成的二叉树；其右子树RB是从森林FT1,T2,TM转换而成的二叉树。3二叉树转换成森林如果B二ROOT，LB，RB是、棵二叉树，则可按如下规则转换成森林FT1,T2,TM1若B为空，则F为空。2若B非空，则F中第一棵树T1的根ROOTT1即为二叉树B的根ROOTT1中根节点的子树森林FL是由B的左子树LB转换而成的；F中除T1之外其余树组成的森林FT1,T2,TM是由B的右子树RB转换而成的。考点15二叉树和树的周游周游或称遍历是树型结构的一种重要运算，是其他运算的基础。周游一棵树就是按一定的次序访问树中听有节点，并且每个节点仅被访问一次的过程。1周游二叉树二又树的周游主要有以下3种方式。1前序法NLR。访问根，按前序周游左子树，按前序周游右子树。2后序法LRN。按后序周游左子树，按后序周游右子树，访问根。3对称序法LNR。按对称序周游左子树，访问根，按对称序周游右子树。2周游树和树林对树和树林的周游分为按深度优先和按广度优先两种方式进行。按深度优先方式又可分为按先根次序和按后根次序周游两种方式。1先根次序周游访问第一棵树的根，按先根次序周游第一棵树的根子树，按先根次序周游其他的树。2后根次序周游按后根次序周游第一棵树的子树，访问第一棵树的根，按后根次序周游其他的树。比较一下树与一又树之间的对应关系，可以看出，按先根次序周游树正好与按前序法周游树对应的二叉树等同，后根次序周游树正好与按对称序法周游对应的二叉树等同。按广度优先方式可以做层次次序周游，首先依次访问层数为0的节点，然后依次访问下一层的节点，直至访问完最后一层的节点。考点16二叉树的存储和线索L二叉树的LLINK一RLINK法存储表示二叉树的存储通常采用链接方式，即每个节点除存储节点自身的信息外再设置两个指针域LLINK和RLINK，分别指向节点的左子女和右子女。当节点的某个子女为空时，则相应的指针值为空。再加上一个指向树根的指针T，就构成了二叉树的存储表示。这种存储表示法被称为LLINKRLINK表示法。2线索二叉树在有N个节点的二叉树的且INKRLINK法存储表示中，必定有N1个空指针域，将这些指针位置利用起来，存储节点在指定周游次序F的前驱、后继节点指针，则得到线索二叉树。考点17哈夫曼树哈夫曼树是树型结构的一种应用二哈夫曼HUFFMAN树又称最优树，是一类带权路径长度最短的树，这种树在信息检索中经常用到。所谓路径长度就是从一个节点到另一个节点所经过的分支总数。树的路径长度是从树的根到每个节点的路径长度之和。完全二叉树就是这种路径长度最短的二叉树。节点的带权路径长度为从该节点到树根之间的路径长度与节点上权的乘积。树的带权路径长度为树中所有叶子节点的带权路径长度之和，WPL最小的不是完全二叉树，而是权大的叶子离根最近的二叉树。25“查找查找是数据结构中一种很常用的基本运算。查找就是在数据结构中找出满足某种条件的节点。所给的条件可以是关键码字段的值，也可以是非关键码字段的值，本节只考虑基于关键码值的查找考点18顺序查找顺序查找是线性表的最简单、最基本的查找方法顺序查找的优点是对线性表节点的逻辑次序无要求，对线性表存储结构也无要求顺序查找的缺点是速度较慢，平均检索长度与表中节点个数和N成正比，查找成功最多需比较N次，平均查找长度为N1/2次，约为表长的，半，查找失败需比较NL次顺序查找算法的时间复杂度为ON。考点19二分法查找二分法查找是一种效率比较高的查找方法，在进行二分法查找时，线性表节点必须按关键码值排序，且线性表是以顺序存储方式存储的。二分法查找的优点是比较次数少，查找速度快，平均检索长度小，经过LOGEN次比较就可以完成查找过程。缺点是在查找之前要为建立有序表付出代价，同时对有序表的插人和删除都需要平均比较和移动表中的一半元素。一般情况下，二分查找适应于数据相对固定的情况，且二分法查找只适用于线性表的顺序存储。考点20分块查找分块查找又称索引顺序查找，是介于线性查找和二分法查找之间的一种查找方法。它要求把线性表分成若干块，每一块中的节点不必有序，但块与块之间必须排序，不妨设每一块中各节点的关键码都大于前一块的最大关键码值。另外，还要求将各块中的最大关键码值组成一个有序的索引表。满足上述条件的线性表称做分块有序表。它的分块检索的过程分以下两步进行。I先查索引表可以用线性检索或二分法检索，确定要找的记录在哪一块。2在相应的块中线性检索待查记录。考点21散列表的存储和查找散列存储中使用的函数称为散列HASH函数散列表又称哈希表是线性表的一种重要的存储方式和检索方法。实现散列技术检索必须解决两个问题一个是构造一个好的散列函数，尽可能避免冲突现象的发生；另一个是设计有效的解决冲突的方法。1散列函数常用的散列函数有以下几种。L除余法。选择一个适当的正整数川通常选P为不大于散列表存储区域大刁、的最大素数，用P去除关键码值，取其余数作为地址，即HKEY二KEYMODP。2数字分析法。当关键码的位数比存储区域地址码位数多时，可以对关键码的各位进行分析，去掉分布不均匀的位，留下分布均匀的位作为地址。3折叠法。将关键码值从某些地方断开，分为几段，折叠相加，作为地址。4中平方法。对关键码值求平方，取中间的几位数作为地址。2处理冲突的方法发生冲突是指由关键字求得的散列地址为IOIM一L的位置上已存有记录，处理冲突就是为该关健字找到另一个“空”的散列地址。常用的处理冲突的方法有开地址法、拉链法等。3负载因子装填因子和平均检索长度装填因子表示散列表的装满程度，定义为散列表中节点的数目除以基本区域能容纳的节点数所得的商，用A表示A越小，冲突的可能性越小，A越大，冲突的可能性越大，检索时需要比较的次数就越多。平均检索长度依赖于散列表的装填因子。26排序排序是数据处理领域经常要使用的一种运算，就是将一组元素按照关键码的递增或递减的顺序来排列为过程按照排序过程中的存储器不同，可将排序方法分为内部排序和外部排序两类。一厂面将介绍插人排序、选择排序、交换排序和归并排序等几种常用的内部排序方法。考点22插入排序插人排序的基本思想每一步将一个待排序的记录按其关键字值的大小插人到一个有序的文件中，插人后该文件仍然是有序文件。L直接插入排序直接插人排序是一种最简单的排序方法它的基木思想是将一个记录插人到已排好序的有序表中，从而得到一个新的、记录数增I的有序表整个排序过程为先将第一个记录看成是一个有序的子序列，然后从第2个记录起依次逐个地插人到这个有序的子序列中去。直接插人排序的时间复杂度为0N。直接插人排序方法不仅适用于顺序表，而且适用于单链表2二分法插入排序在直接插人排序，若采用二分法查找而不是顺序查找待插入元素的插人位置，则称为二分法插入排序这种插人排序可减少比较次数，使排序速度有所提高，但提高不会太多，因为移动记录的总次数不受改变，其时间复杂度仍为0N2。直接插人和二分法插入排序方法都是稳定的，因为它们不会改变原序列中具有相同关键字记录的相对次序。3希尔排序希尔排序又称缩小增量排序，它是对直接插人排序的一种改进方法希尔排序的基本思路对相隔较大距离的记录进行比较，就能使记录在比较后移动较大的距离这样能使较小的记录尽快往前移，较大的记录尽快往后移，从而提高排序的速度希尔排序是一种不稳定的排序过程考点23选择排序选择排序的基木思想是每次从待排序的记录中选出关键码值最小或最大的记录放在已排好序的记录序列后面，直至排序完毕。1直接选择排序直接选择排序也是一种简单的排序方法。选择排序的基本方法是每次从待排序的区间中选择出具有最小排序码的元素。把该元素与该区间的第一个元素交换位置。第一次待排序区间为A1AN，经过选择和交换后，A1为最小排序码的元素。第二次待排序区间为A2AN，经过选择和交换后，A2为仅次于A1的具有最小排序码的元素，依次类推，经过N1次选择和交换后，排序完毕。直接选择排序方法的时间复杂度为ON2，此方法是不稳定的。2堆排序堆的定义如下N个元素序列K1,K2，KN，当且仅当满足下列关系时，称之为堆。人毛人KIK2I,KIK2I1，I1，2，N/2堆排序的基本思想对一组待排序的关键码，首先把它们按堆的定义排列成一个序列，找到其中最小的关键码接着将最小的关键码取出，然后将剩下的关键码再建堆排序，依次进行，直到将全部关键码排好为止。建堆的基本方法是将大的元素下沉，小的元素上浮，即所谓的筛选法。在最坏的情况下，堆排序时间复杂度为ONLOG2N。堆排序仅需一个记录大小的辅助存储空间。堆排序是不稳定的。考点24交换排序交换排序的基本思想两两比较待排序记录的关键字值，并交换不满足顺序要求的那些记录，直到全部记录满足关键字值排序要求为止。1起泡排序起泡排序又称为冒泡排序，其基本思想是通过相邻记录之间关键字的比较和交换，使关键字值较小的记录逐渐从底部移向顶部，即从下标较大的单元移向下标较小的单元，关键字较大的记录从顶部移向底部。从起泡排序算法可以看出，若初始序列为“正序”序列，则只需进行一趟排序；反之，若初始序列为“逆序”序列，则需进行。一I趟排序。因此，总的时间复杂度为。矿。起泡排序是一种稳定的排序过程。2快速排序快速排序是口前内部排序中速度最快的一种排序算法，其实质是对起泡排序的改进在快速排序中，记录的比较和交换是从两端向中间进行的，排序码较大的记录一次就能够从前面交换到后面单元，排序码较小的记录一次就能够从后面交换到前面单元，记录每次移动的距离较远，总比较和移动次数较少。快速排序是不稳定的排序。排序速度最快时，其时间复杂度为0NLOG,N；排序速度最慢时，其时间复杂度为。N快速排序的平均时间复杂度为0NLOG2N。快速排序除了需要一个记录的辅助空间来存放每次选取的基准记录外，还需要一个栈空间来实现递归。考点25归并排序归并是将两个或者多个有序表合并成一个有序表归井排序要求待排序文件已经部分排序。归并排序的基本思想是将这些已排过序的文件进行合并，得到完全排序的文件。假设初始序列含有N个记录，则可看成是N个有序的子序列，每个子序列的长度为1，然后两两归并，得到N/2个长度为2或I的