计算机等级考试三级数据库复习资料

《计算机等级考试三级数据库复习资料》由会员分享，可在线阅读，更多相关《计算机等级考试三级数据库复习资料（67页珍藏版）》请在装配图网上搜索。

1、计算机等级考试三级数据库复习资料第1章 基 础 知 识 【考点一】 计算机的发展自从1946年2月现代电子计算机的鼻祖ENIAC(electronic numerical integrator and computer)在美国宾夕法尼亚大学问世以后，短短50年里，计算机技术经历了巨大的变革。学术界经常使用器件(硬件)划分计算机的发展史，如第一代电子管计算机(19471957)，第二代晶体管计算机(19581964)，第三代集成电路计算机(19641972)，第四代大规模集成电路计算机(1972)，目前提出了所谓的第五代(或新一代)计算机。从1946年到50年代后期(19461957)为电子管计

2、算机时期。计算机的元器件主要由电子管(vacuum tube)组成。其特点是体积庞大、功耗高、运算速度较低。如ENIAC占地170m2，重达30吨，功耗为140kW，有18000多个电子管，每秒钟能进行5000次加法计算。这一阶段，计算机主要用于军事、国防等尖端技术领域。除了ENIAC以外，1945年左右，冯诺依曼等人在研制EDVAC(electronic discrete variable computer)时，提出了存储程序(stored-program)概念，奠定了以后计算机发展的基石。IBM公司1954年12月推出的IBM650是第一代计算机的代表。从20世纪50年代后期到60年代中期

3、(19581964)为晶体管计算机时期。自从1947年晶体管(transistor)在贝尔实验室诞生后，引发了一场影响深远的电子革命。体积小、功耗低、价格便宜的晶体管取代了电子管，不仅提高了计算机的性能，也使计算机在科研、商业等领域内得到广泛地应用。第二代计算机不仅采用了晶体管器件，而且存储器改用速度更快的磁芯存储器；与此同时高级编程语言和系统软件的出现，也大大提高了计算机的性能和拓宽了其应用领域。这一时期计算机的代表主要有DEC公司1957年推出的PDP-I、IBM公司于1962年推出的7094以及CDC公司1964年研制成功的CDC6600。1969年CDC公司研制的DCD7600平均速度

4、达到每秒千万次浮点运算。从20世纪60年代中期到70年代初期(19651972)为集成电路计算机时代。第一代和第二代计算机均采用分离器件(discrete component)组成。集成电路(integrated circuit)的出现，宣告了第三代计算机的来临。由于采用了集成电路，使得计算机的制造成本迅速下降；同时因为逻辑和存储器件集成化的封装，大大提高了运行速度，功耗也随之下降；集成电路的使用，使得计算机内各部分的互联更加简单和可靠，计算机的体积也进一步缩小。这一时期的代表为IBM的system/360和DEC的PDP-8。从20世纪70年代初期到70年代后期(19721978)为大规模集

5、成电路(LSI)计算机时代。20世纪70年代初半导体存储器的出现，迅速取代了磁芯存储器，计算机的存储器向大容量、高速度的方向飞速发展。存储器芯片从1kbit，4kbit，16kbit，64kbit，256kbit，1Mbit，4Mbit发展到16Mbit(1992年)。接着就进入了超大规模集成电路(VLSI)计算机时代。随着技术的日新月异，软件和通信的重要性也逐步上升，成为和硬件一样举足轻重的因素。同时系统结构的特点对计算机的性能也有巨大的影响(中断系统、Cache存储器、流水线技术等等)。实际上在第三代计算机以后，就很难找到一个统一的标准进行划分。也可以从应用的观点来划分计算机的发展史。最早

6、的应用是军事上的需要，如炮弹弹道计算，核武器的设计等；其次是广泛地用于科学计算，工程设计计算；第三阶段是大量用于管理，现在计算机的80%以上用于管理；再接着是计算机辅助设计(CAD)和辅助制造(CAM)；进入90年代，计算机的应用已趋向于综合化和智能化，例如在一个企业里，计算机不仅用于科学计算、辅助设计和辅助制造，还用于辅助管理和辅助决策(MIS与DSS)，以及办公自动化(OA)等等，使设计、生产自动化和管理自动化融为一体，形成所谓计算机集成制造系统(CIMS-Computer Integrated Manufacturing System)，再发展下去就是工厂自动化(Factory Auto

7、mation)或称无人工厂。DSS(Decision Support System)/ES(Expert System)利用人工智能(AIArtifcation Intelligence)技术，让计算机代替人判断、推理，寻找最优方案，以辅助决策者决策。目前更流行的是认为计算机的发展经过了三次浪潮(wave)。计算机的发展第一个浪潮是单个主机(Mainframe)的时期，以IBM360、370为代表的大型机的出现，其特点是以批处理为主，主要用于大规模科学计算。第二次浪潮为客户机/服务器(Client/Server)的时期，这时期出现了小型机、微型机和局域网。其特点是多用户分时处理。第三个浪潮是7

8、080年代的微型计算机PC(Personal Computer)的出现。现在正处于第三次浪潮，网络计算机的时期，即以网络为中心或以网络为基础的计算机时期。目前计算机向综合的方向发展，将各种计算机的特点和优点综合起来，并结合了多媒体技术、通信技术等，把人类带入了网络社会。【考点二】 计算机的分类及其应用计算机分类的方法大致可分如下几种：1.按信息的形式和处理方式分类计算机按信息的形式和处理方式可分为数字计算机、模拟计算机以及数字混合计算机2.按计算机的用途分类计算机按用途可分为通用计算机和专用计算机。3.按计算机规模分类计算机按规模可划分为巨型机、大型机、中型机、小型机、微型机等。计算机的应用如

9、下：1.在科学计算中的应用2.在实时控制中的应用3.在数据处理中的应用4.计算机在辅助设计和辅助制造(CAD/CAM)中的应用5.办公自动化系统中的应用【考点三】 计算机硬件结构实际应用的计算机系统是由计算机硬件系统、软件系统以及通信网络系统组成的一个整体系统。计算机硬件系统是指构成计算机的所有实体部件的集合，通常这些部件由电路(电子元件)、机械等物理部件组成，它们都是看得见摸得着的，故通常称为“硬件”。计算机硬件结构也可以称为冯诺伊曼结构，它由五大部件组成：主机部分由运算器、控制器、存储器组成，外设部分由输入设备和输出设备组成，其中核心部分部件是运算器。计算机硬件之间的连接线路分为网状结构与

10、总线结构，这里主要介绍总线(BUS)结构。总线结构有如下几种形式：1.以CPU为中心的双总线结构所谓总线实际上是一组并行的导线，导线的数目和计算机字长相同，数据和指令通过总线传送。2.以存储器为中心的双总线结构3.单总线结构主要部件功能：1.运算器运算器是完成二进制编码的算术或逻辑运算的部件。运算器由累加器(用符号LA表示)、通用寄存器(用符号LB表示)和算术逻辑单元(用符号ALU表示)组成，核心是算术逻辑单元。2.存储器在计算机中的存储器包括内存储器(又叫主存储器或随机存储器，简称内存或主存)、外存储器、只读存储器和高速缓冲存储器以及寄存器等。随机存储器是按地址存取数据的，若地址总线共有20

11、条(A0A19)，即有20个二进制位，可形成220=1048576个地址(1兆地址)。3.控制器控制器由三大部件组成，它们是指令部件、时序部件和操作控制部件。(1)指令部件指令部件包括程序计数器PC，指令寄存器IR和指令译码器ID。(2)时序部件时序部件产生定时节拍，一般由时钟信号源、节拍发生器及微操作电路组成4.输出寄存器输出寄存器用于存放输出结果，以便由它通过必要的接口(输出通道)，在输出设备上输出运算结果。5.输入设备目前主要通过CRT终端和键盘实现人机对话。磁性设备阅读机、光学阅读机等也可作为输入设备。【考点四】 计算机软件的功能及分类所谓软件是指为运行、维护、管理、应用计算机所编制的

12、所有程序的总和。软件分为系统软件和应用软件。系统软件包括计算机操作系统(Operation System)、计算机的各种管理程序、监控程序、调试程序、编辑程序以及各种语言的编译或解释程序等。应用软件是为解决各种实际问题而设计的程序。软件系统软件操作系统 编辑程序 语言处理程序汇编程序 编译程序 解释程序 系统实用程序 装配连接程序 应用软件通用软件 用户程序1.操作系统操作系统具有三大功能：管理计算机硬、软件资源，使之有效使用；组织协调计算机的运行，以增强系统的处理能力；提供人机接口，为用户提供方便。操作系统具有的管理：(1)作业管理。(2)资源管理。(3)中断处理。(4)I/O处理。(5)调

13、度。(6)错误处理。(7)保护和保密处理。(8)记帐。操作系统的基本类型：(1)批处理操作系统(2)分时系统。(3)实时系统。操作系统的管理功能主要内容(1)处理机管理。(2)存储管理。(3)文件管理。(4)设备管理。2.数据库管理系统数据库管理系统既可以认为是一个系统软件也可以认为是一个通用的应用软件。目前有三种类型的数据库管理系统，故可存放三种模型的数据，这三种数据库管理系统分别为层次数据库、网状数据库和关系数据库。3.计算机网络软件计算机网络系统是通过通信线路连接的硬件、软件与数据集合的一个计算机系统。从硬件来说，除计算机作为网络的结点以外，还有如服务器(也可是一台计算机)，网络适配器，

14、终端控制器以及网络连接器等硬件设备；从软件来说，有网络操作系统，网络通信及协议软件，网络数据库管理系统等。4.高级语言及语言处理器用户用高级语言编写的程序称源程序，源程序不能由计算机直接执行，必须翻译成机器能执行的语言机器语言，这种翻译是由机器自动翻译的，“译员”称编译程序或编译器，当源程序输入计算机后，调用编译程序编译成机器语言(称目标程序)，然后执行。还有一种语言处理程序叫解释程序，输入一条语句，翻译一条。现在已出现了第4代语言(4GL)和计算机辅助软件工具CASE。5.常用的通用软件在数据处理、事务处理、报表处理中有许多通用软件，如字处理软件WPS、WORD，报表处理软件LOTUS 1-

15、2-3等。【考点五】 计算机网络基础1.计算机网络基本概念(1)计算机网络的形成与发展(2)计算机网络的主要特征资源共享观点将计算机网络定义为“以能够相互共享资源的方式互联起来的自治计算机系统的集合”。资源共享观点的定义符合目前计算机网络的基本特征。2.计算机网络的分类(1)网络分类方法计算机网络的分类方法可以是多样的，其中最主要的两种方法是：根据网络所使用的传输技术(transmission technology)分类。根据网络的覆盖范围与规模(scale)分类。(2)广域网广域网(Wide Area Network,WAN)也称为远程网。目前的广域网具有以下特点：适应大容量与突发性通信的要

16、求；适应综合业务服务的要求；开放的设备接口与规范化的协议；完善的通信服务与网络管理。(3)局域网局域网(Local Area Network, LAN)是继广域网之后又一个网络研究与应用的热点，也是目前技术发展最快的领域之一。局域网的技术特点主要表现在以下几个方面：局域网覆盖有限的地理范围，它满足公司、机关、校园、工厂等有限范围内的计算机、终端与各类信息处理设备联网的需求。局域网提供高数据传输速率(10 Mb/s1 000 Mb/s)、低误码率的高质量数据传输环境局域网一般属于一个单位所有，易于建立、维护与扩展决定局域网特性的主要技术要素为网络拓扑、传输介质与介质访问控制方法。从介质访问控制方

17、法的角度看，局域网可分为共享式局域网与交换式局域网两类。(4)城域网城域网(MAN,Metropolitan Area Network)是介于广域网与局域网之间的一种高速网络。城域网设计的目标是要满足几十公里范围内的大量企业、机关、公司的多个局域网互联的需求，以实现大量用户之间的数据、语音、图形与视频等多种信息的传输功能。早期的城域网产品主要是光纤分布式数据接口(Fiber Distributed Data Interface,FDDI)。3.Internet基础(1)Internet的形成与发展(2)Internet的结构与组成(3)TCP/IP、域名与IP地址TCP/IP的基本概念TCP/

18、IP具有以下几个特点。开放的协议标准，独立于特定的计算机硬件与操作系统。独立于特定的网络硬件，可以运行在局域网、广域网，更适用于互联网中。统一的网络地址分配方案，使得整个TCP/IP设备在网中都具有惟一的IP地址。标准化的高层协议，可以提供多种可靠的用户服务。域名与IP地址4.Internet提供的主要服务(1)WWW服务2)电子邮件服务5.Internet的基本接入方式(1)ISP的作用Internet服务提供者(ISP)是用户接入Internet的入口点。一方面，它为用户提供Internet接入服务；另一方面，它也为用户提供各类信息服务。一般来说，用户计算机接入Internet的方式主要有

19、两种：通过局域网接入Internet；通过电话网接入Internet。(2)通过局域网接入Internet(3)通过电话网接入Internet【考点六】 信息安全基础1.信息安全信息安全从简单的意义来理解，就是要防止非法的攻击和病毒的传播，以保证计算机系统和通信系统的正常运作。而从更全面的意义来理解，就是要保证信息的保密性(confidentiality)、完整性(integrity)、可用性(availability)和可控性(controllability)。综合起来，就是要保障电子信息的有效性。2.信息保密信息的保密是信息安全的重要方面，为保密而进行加密是防止破译信息系统中机密信息的技术

20、手段。加密的办法就是使用数学方法来重新组织数据域信息，使除合法接收者外，其他任何人要想看懂变化后的数据或信息是非常困难的。一般人们将加密前的信息称为明文，而将加密后的称为密文，因此加密的目的就是将明文变为密文。而反过来将密文变为明文的过程则称为解密。加密技术可以使某些重要的数据或信息存放在一般的不安全的计算机上或在一条一般的不安全的信道上传送。只有持有合法解密办法的人才能获取明文。3.信息认证信息认证是信息安全的另一重要方面。信息认证，首先是验证信息的发送者的真实性，即不是假冒的；其次是验证信息的完整性，即验证信息在传送或存储过程中未被篡改、重放或延迟等。认证是防止对系统进行主动攻击，如伪造、

21、篡改的重要技术手段。在有关认证的实用技术中，主要的有数字签名技术、身份识别技术和信息的完整性校验技术等。(1)数字签名(2)身份识别3)消息认证4.密钥管理密钥管理影响到密码系统的安全，而且还会涉及到系统的可靠性、有效性和经济性。密钥管理包括密钥的产生、存储、装入、分配、保护、丢失、销毁以及保密等内容。其中解决密钥的分配和存储是最关键和有技术难点的问题。5.计算机病毒的基本概念计算机病毒是一种特殊的具有破坏性的计算机程序，它具有自我复制能力，可通过非授权入侵而隐藏在可执行程序或数据文件中。当计算机运行时，源病毒能把自身精确拷贝或者有修改地拷贝到其他程序体内，影响和破坏正常程序的执行和数据的正确

22、性。(1)计算机病毒的特征(2)病毒的破坏作用(3)病毒的来源(4)病毒的防治6.网络安全(1)构成对网络安全威胁的主要因素及相关技术(2)网络安全服务的主要内容7.操作系统安全(1)操作系统安全方法(2)操作系统安全措施(3)文件保护与保密8.数据库安全(1)安全性措施的层次(2)权限和授权(3)在SQL中进行安全性说明三级数据库数据结构与算法【考点一】 基本概念1.什么是数据结构数据是描述客观事物的数字、字符以及所有能直接输入到计算机中并被计算机程序处理的符号的集合。数据对象是具有相同性质的数据元素的集合。通常，一个数据对象中的数据元素不是孤立的，而是彼此之间存在着一定的联系，这种联系就是

23、数据结构。数据对象中数据元素之间的联系需要在对数据进行存储和加工中反映出来，因此，数据结构概念一般包括三方面的内容：数据之间的逻辑关系、数据在计算机中的存储方式、以及在这些数据上定义的运算的集合。(1)数据的逻辑结构数据的逻辑结构只抽象地反映数据元素之间的逻辑关系，它与数据的存储无关，是独立于计算机的。数据的逻辑结构分为线性结构和非线性结构两大类。线性结构的逻辑特征是：有且仅有一个开始结点和一个终端结点，并且所有的结点都最多有一个直接前驱和一个直接后继。线性表就是一个典型的线性结构。非线性结构的逻辑特征是：一个结点可能有多个直接前驱和直接后继。树、图等都是非线性结构。(2)数据的存储结构数据的

24、存储结构是数据的逻辑结构在计算机存储器里的实现(亦称为映象)。它是依赖于计算机的，并有四种基本的存储映象方法。它们是：顺序存储方法该方法是把逻辑上相邻的结点存储在物理位置上相邻的存储单元内，结点间的逻辑关系由存储单元的邻接关系来体现。顺序存储方法主要用于线性的数据结构，非线性的数据结构也可以通过某种线性化方法来实现顺序存储链接存储方法在链接存储方法中，逻辑上相邻的结点在物理位置上未必相邻，结点间的逻辑关系是由附加的指针字段表示的。索引存储方法该方法通常是在存储结点信息的同时，还建立一个附加的索引表，索引表中的每一项称为索引项，索引项的一般形式是：关键字，地址。关键字是能唯一标识一个结点的那些数

25、据项。散列存储方法在散列存储方法中，结点的存储地址是根据结点的关键字值直接计算出来的。上述四种基本的存储方法也可以组合起来对数据结构进行存储映象。(3)数据的运算数据的运算定义在数据的逻辑结构之上，每种逻辑结构都有一个运算的集合。常用的运算有：查找、插入、删除、更新、排序等。显然，对数据运算的具体实现方法只有在确定了存储结构之后才能加以考虑。2.算法(1)算法及其特征简单地说，一个算法就是一种解题方法，更严格地说，算法是由若干条指令组成的有穷序列，它必须具有以下特征：有穷性一个算法必须在执行有穷步后结束。确定性算法的每一步必须是确切地定义的，无二义性。可行性算法中的所有待实现的运算必须在原则上

26、能够由人使用笔和纸在做有穷次运算后完成。输入一个算法具有0个或多个输入的外界量，它们是算法开始前对算法最初给出的量。输出一个算法至少产生一个输出，它们是与输入有某种关系的量。算法的含义与程序十分相似，但二者又有区别。一个程序不一定满足有穷性，操作系统就是如此，只要整个系统不被破坏，操作系统就永远不会停止，所以操作系统程序不是一个算法。另外，程序中的指令必须是机器可以执行的，而算法中的指令则无此限制。但是，一个算法如果用机器可执行的语言书写，则它就是一个程序。对一个算法的描述可以采用自然语言、数学语言、约定的符号语言、以及图解等方式。(2)算法的分析求解同一个问题可以有多种不同的算法，评价一个算

27、法的优劣除了正确性和简明性外，主要考虑两点：一是执行算法所耗费的时间，二是执行算法所耗费的存储空间，特别是辅助存储空间的耗费。就这两者而言，前者显得比后者更为重要，在数据结构中往往更注重对算法执行时间的分析。一个算法所耗费的时间是该算法中每条语句的执行时间之和，而每条语句的执行时间是该语句执行次数(频度)与该语句一次执行所需时间的乘积。如果假定每条语句一次执行所需的时间均为单位时间，则一个算法的时间耗费就是该算法中所有语句的频度之和【考点二】 线性表(1)线性表及其基本操作线性表是n0个元素的一个有限序列：(a1，a2，a3，an- 1 ，an)表中元素的个数n称为表的长度，长度n=0的表称为

28、空表。表元素又称为结点，线性表的一个重要特性是可以按照诸元素在表中的位置确定它们在表中的先后次序。若n1，则a1，为第一个元素，an为最后一个元素。元素ai-1先于ai，我们称ai-1为ai的前驱；ai在ai-1之后，则ai为ai-1的后继。除第一个元素外，每个元素都有一个且仅有一个直接前驱；除最后一个元素外，每个元素都有一个且仅有一个直接后继。下面所列的是其中一些常用的运算。查找运算查找线性表的第i(0in-1)个表元；在线性表中查找具有给定键值的表元；插入运算把新表元插在线性表的第i(0in)个位置上；把新表元插在具有给定键值的表元的前面或后面；删除运算删除线性表的第i(0in-1)个表元

29、；删除线性表中具有给定键值的表元；其他运算统计线性表中表元的个数；输出线性表各表元的值；复制线性表；线性表分析；线性表合并；线性表排序；按某种规则整理线性表。(2)线性表的存储有多种存储方式能将线性表存储在计算机内，其中最常用的是顺序存储和链接存储。线性表的顺序存储线性表的顺序存储是最简单的存储方式。程序通常用一个足够大的数组，从数组的第一个元素开始，将线性表的结点依次存储在数组中。即线性表的第i个结点存储在数组的第i(0in-1)个元素中，用数组元素的顺序存储来体现线性表中结点的先后次序关系。用数组存储线性表的最大优点是能直接访问线性表中的任一结点。用数组存储线性表的缺点主要有两个：一是程序

30、中的数组通常大小是固定的，可能会与线性表的结点可以任意增加和减少的要求相矛盾；二是执行线性表的结点插、删操作时要移动存于数组中的其他元素，使插和删操作不够简便线性表的链接存储线性表链接存储是用链表存储线性表，最简单的用单链表。如从链表的第一个表元开始，将线性表的结点依次存储在链表的各表元中。即线性表的第i个结点存储在链表的第i(0in-1)个表元中。链表的每个表元除要存储线性结点的信息外，还要有一个成分用来存储其后继结点的指针。单链表就是通过链接指针来体现线性表中结点的先后次序关系。每个链表还要有一个指向链表的第一个表元的指针，链表的最末一个表元的后继指针值为空。用链表存储线性表的优点是利用线

31、性表的每个表元的后继指针就能完成插或删的操作，不需移动任何表元。其缺点也主要有两条：一是每个表元增加了一个后继指针成分，要花费更多的存储空间；二是不便随机地直接访问线性表的任一结点。(3)线性表上的查找线性表上的查找运算是指在线性表中查找某个链值的结点。根据线性表的存储形式和线性表本身的性质差异，有多种查找算法，如：顺序查找、二分法查找、分块查找、散列查找等。(4)线性表的新结点插入顺序存储线性表的插入：设线性表结点的类型为整型，插入之前有n个结点，把值为x的新结点插在线性表的第i(0in)个位置上。完成插入主要有以下几个步骤：检查插入要求的有关参数的合理性；把原来第n-1个结点至第i个结点依

32、次往后移一个数组元素位置；把新结点放在第i个位置上；修正线性表的结点个数。(5)栈栈的工作原理是采用后进先出(LIFO)技术，栈顶由中央处理器中的栈指示器(SP)指出。在执行PUSH操作中SP减量，而在POP操作中SP增量。下面从数据结构的角度，进一步说明栈的基本概念与操作。需要说明的是，其工作原理与前面所介绍的是一致的，不同的是脱离了硬件背景，例如，栈顶指针不是中央处理器的某个寄存器的内容，而是一个抽象的数据结构。栈是一种特殊的线性表，这种线性表只能在固定的一端进行插入和删除操作。允许插入和删除的一端称为栈顶，另一端称为栈底。一个新元素只能从栈顶一端进入，删除时，只能删除栈顶的元素，即刚刚被

33、插入的元素。由于元素是按后进先出的次序入栈和出栈的，所以栈又称后进先出表(Last In First Out)，简称LIFO表。栈的基本操作有：create(s)建立一个空栈sempty(s)测试栈是否为空栈。full(s)测试栈是否满。push(x,s)将元素x插入栈s的栈顶。top(s)取栈顶元素。pop(s)删除栈顶元素。由于栈是一种特殊的线性表，栈的各种操作实际上是线性表的操作的特殊情形，所以表示线性表的方法同样可以用来表示栈。(6)队列队列可看作是插入在一端进行，删除在另一端进行的线性表，允许插入的一端称为队尾，允许删除的一端称为队头。在队列中，只能删除队头元素。队列的最后一个元素一

34、定是最新入队的元素。因此队列又称先进先出表(First-In-First-Out)。日常生活中排队购物就是队列应用的例子：新来的顾客排在队尾等待，排在队头的顾客购物后离开队伍。队列的基本操作有：create(Q) 建立一个空队列empty(Q)测试队列是否为空队列。full(Q) 测试队列是否为满。front(Q)取队头元素。enq(X,Q)向队列中插入一个元素X。enq(Q)删除队头元素。【考点三】 数组线性表(包括栈和队列)都是线性结构，结构中的每个元素只是无结构的数据元素。我们对线性表作进一步的推广，使结构中的元素本身也可以是具有某种结构(如向量)的数据，从而引出了数组这一种新的数据结构

35、。(1)数组的定义和运算类似于线性表，一个二维数组(或称矩阵)可以看成是由m个行向量所组成的向量，也可以看成是由n个列向量所组成的向量。对于数组的运算，主要有检索和存取数组中某个元素。(2)数组的顺序存储结构由于对数组一般不作插入和删除运算，因此，一旦数组被建立，则结构中的元素个数和元素之间的关系就不再发生变动。对这种情况采用顺序存储结构表示数组是比较恰当的。由于计算机存储单元是一维的结构，而数组是多维的结构，因此就必须把多维结构映射为一维的结构，即把多维结构按一定次序排列成一维的。【考点四】 树型结构线性表、栈和队列等数据结构所表达和处理的数据以线性结构为组织形式。然而，在计算机科学和计算机

36、应用的各个领域中，存在着大量需要用更复杂的逻辑结构加以表示的问题。因此必须研究更复杂的逻辑结构及相应的数据结构。树形结构就是这些更复杂的结构中最重要的一类。1.树的基本概念树是一类重要的树形结构，其定义如下：树是n(n0)个结点的有穷集合，满足：(1)有且仅有一个称为根的结点；(2)其余结点分为m(m0)个互不相交的非空集合，T1，T2，Tm，这些集合中的每一个都是一棵树，称为根的子树。在树上，根结点没有直接前趋。对树上任一结点X来说，X是它的任一子树的根结点的惟一的直接前趋。为了讨论方便，我们引入树的若干习惯术语。树上任一结点所拥有的子树的数目称为该结点的度。度为0的结点称为叶子或终端结点，

37、度大于0的结点称为非终端结点或分支点。一棵树中所有结点的度的最大值称为该树的度。若树中结点A是结点B的直接前趋，则称A为B的双亲或父结点，称B为A的孩子(即“子女”)或子结点。易知任何结点A的孩子B也就是A的一棵子树的根结点，父结点相同的结点互称为兄弟。一棵树上的任何结点(不包括根本身)称为根的子孙。反之若B是A的子孙，则称A是B的祖先。结点的层数(或深度)从根开始算起：根的层数为1，其余结点的层数为其双亲的层数加1。一棵树中所有结点层数的最大值称为该树的高度或深度。树(及一切树形结构)是一种“分支层次”结构。所谓“分支”是指树中任一结点的子孙可以按它们所在的子树的不同而划分成不同的“分支”；

38、所谓“层次”是指树上所有结点可以按它们的层数划分不同的“层次”。在实际应用中，树中的一个结点可用来存储实际问题中的一个数据元素，而结点间的逻辑关系(即父结点与子结点之间的邻接关系)往往用来表示数据元素之间的某种重要的、必须加以表达的关系。用图示法表示任何树形结构时，箭头的方向总是从上到下，即从父结点指向子结点，因此，可以简单地用连线代替箭头。2.树的基本运算包括：求根ROOT(T)，引用型运算，其结果是结点X在树T的根结点。求双亲PARENT(T，X)，引用型运算，其结果是结点X在树T上的双亲结点；若X是树T的根或X不在T上，则结果为一特殊标志。求孩子CHILD(T，X，i)，引用型运算，其结

39、果是树T上的结点X的第i个孩子；若X不在T上或X没有第i个孩子，则结果为一特殊标志。建树CREATE(X，T1，Tk)，k1,加工型运算，其作用是建立一棵以X为根，以T1，Tk为第1，k棵子树的树。剪枝DELETE(T，X，i)，加工型运算，其作用是删除树T上结点X的第i棵子树；若T无第i棵子树，则为空操作。3.二叉树(1)二叉树的基本概念二叉树是结点的有穷集合，它或者是空集，或者同时满足下述两个条件：有且仅有一个称为根的结点：其余结点分为两个互不相交的集合T1、T2，T1与T2都是二叉树，并且T1与T2有顺序关系(T1在T2之前)，它们分别称为根的左子树和右子树。二叉树是一类与树不同的树形结

40、构。它们的区别是：第一，二叉树可以是空集，这种二叉树称为空二叉树；第二，二叉树的任一结点都有两棵子树(当然，它们中的任何一个可以是空子树)，并且这两棵子树之间有次序关系，也就是说，它们的位置不能交换。相应地，二叉树上任一结点左、右子树的根分别称为该结点的左孩子和右孩子。另外，二叉树上任一结点的度定义为该结点的孩子数(即非空子树数)。除这个几个术语之外，树的其它术语也适用于二叉树。特别值得注意的是，由于二叉树上任一结点的子树有左、右之分，因此即使一结点只有一棵非空子树，仍须区别它是该结点的左子树还是右子树，这是与树不同的。二叉树的基本运算包括：初始化INITLATE(BT)，加工型运算，其作用是

41、设置一棵空二叉树BT= 。求根ROOT(BT)，引用型运算，其结果是二叉树BT的根结点；若BT为空二叉树，运算结果为一特殊标志。求双亲PARENT(BT，X)，引用型运算，其结果是结点X在二叉树BT上的双亲；若X是BT的根或X根本不是BT上的结点，运算结果为一特殊标志。求左孩子LCHILD(BT，X)和求右孩子RCHILD(BT，X)，引用型运算，其结果分别为结点X在二叉树BT上的左、右孩子；若X为BT的叶子或X不在BT上，运算结果为一特殊标志。建树CREAT(X，LBT，RBT)，加工型运算，其作用是建立一棵以结点X为根，以二叉树LBT、RBT分别为X的左、右子树的二叉树。剪枝DELLEFT

42、(BT，X)和DELRIGHT(BT，X)，加工型运算，其作用分别为删除二叉树BT上结点X的左、右子树；若X无左或右子树，运算为空操作。与其它数据结构相同，在实际应用中根据需要对基本运算适当增减。(2)二叉树的性质在某些情况下，了解二叉树的下列性质是有帮助的。性质1二叉树第i(i1)层上至多有2i-1个结点。性质2深度为k(k1)的二叉树至多有2k-1个结点。性质3对任何二叉树，若度数为2的结点数为n2，则叶子数n0=n2+1。有两种特殊形态的二叉树在讨论问题时很有用，这就是满二叉树和完全二叉树。深度为k(k1)且有2k-1个结点的二叉树称为满二叉树。由性质2知，满二叉树上各层的结点数已达到了

43、二叉树可以容纳的最大值。如果在一棵深度为k(k1)的满二叉树上删去第k层上最右边的连续j(0j1，则X的双亲PARENT(X)的编号为i/2。(2)若2in，则结点X无左孩子(且无右孩子)；否则，X的孩子LCHILD(X)的编号为2i。(3)若2i+1n，则结点X无右孩子，否则，X的右孩子RCHILD(X)的编号为2i+14.二叉树的存储结构二叉树通常有两类存储结构，顺序存储结构和链式存储结构。(1)二叉树的链式存储结构二叉树有不同的链式存储结构，其中最常用的是二叉树链表与三叉链表。二叉树链表的结点形式如下：lchild data rchild 其中，data域称为数据域，用于存储二叉树结点中

44、的数据元素；lchild域称为左孩子指针域，用于存放指向本结点左孩子的指针(这个指针及指针域有时简称为左指针)。类似地，rchild域称为右孩子指针域，用于存放指向本结点右孩子的指针(简称右指针)。二叉链表中的所有存储结点通过它们的左、右指针的链接而形成一个整体。此外，每个二叉链表还必须有一个指向根结点的指针，该指针称为根指针。根指针具有标识二叉链表的作用，对二叉链表的访问只能从根指针开始。值得注意的是，二叉链表中每个存储结点的每个指针域必须有一个值，这个值或者是指向该结点的一个孩子的指针，或者是空指针NULL。若二叉树为空，则root=NULL。若某结点的某个孩子不存在，则相应的指针为空。具

45、有n个结点的二叉树中，一共有2n个指针域，其中只有n-1个用来指向结点的左右孩子，其余的n+1个指针域为NULL。二叉树的链式存储结构操作方便，表达简明(二叉树的逻辑关系结点间的父子关系在二叉链表和三叉链表中被直接表达成对应存储结点之间的指针)，因而成为二叉树最常用的存储结构。然而在某些情况下，二叉树的顺序存储结构也很有用。(2)二叉树的顺序存储结构二叉树的顺序存储结构由一个一维数组构成，二叉树上的结点按某种次序分别存入该数组的各个单元。显然，这里的关键在于结点的存储次序，这种次序应能反映结点之间的逻辑关系(父子关系)，否则二叉树的基本运算就难以实现。由二叉树的性质5可知，若对任一完全二叉树上

46、的所有结点按层编号，则结点编号之间的数值关系可以准确地反映结点之间的逻辑关系。因此，对于任何完全二叉树来说，可以采用“以编号为地址”的策略将结点存入作为顺序存储结构的一维数组。具体地说就是：将编号为i的结点存入一维数组的第i个单元。在这一存储结构中，由于一结点的存储位置(即下标)也就是它的编号，故结点间的逻辑关系可通过它们下标间的数值关系确定。5.二叉树的遍历由于二叉树的基本运算在链式存储结构上的实现比较简单，无需详加讨论。下面研究二叉树的一种较为复杂的重要运算遍历及其在二叉链表上的实现。遍历一棵二叉树就是按某种次序系统地“访问”二叉树上的所有结点，使每个结点恰好被“访问”一次。所谓“访问”一

47、个结点，是指对该结点的数据域进行某种处理，处理的内容依具体问题而定，通常比较简单。遍历运算的关键在于访问结点的“次序”，这种次序应保证二叉树上的每个结点均被访问一次且仅一次。由定义可知，一棵二叉树由三部分组成：根、左子树和右子树。因此对二叉树的遍历也可相应地分解成三项“子任务”：访问根根点；遍历左子树(即依次访问左子树上的全部结点)；遍历右子树(即依次访问右子树上的全部结点)。因为左、右子树都是二叉树(可以是空二叉树)，对它们的遍历可以按上述方法继续分解，直到每棵子树均为空二叉树为止。由此可见，上述三项子任务之间的次序决定了遍历的次序。若以D、L、R分别表示这三项子任务，则人有六种可能的次序：

48、DLR、LDR、LRD、DRL、RDL和RLD。通常限定“先左后右”，即子任务在子任务之前完成，这样就只剩下前三种次序，按这三种次序进行的遍历分别称为先根遍历(或前序遍历)、中根(或中序)遍历、后根(或后序)遍历。三种遍历方法的定义如下：先根遍历若需遍历的二叉树为空，执行空操作；否则，依次执行下列操作：访问根结点；先根遍历左子树先根遍历右子树。中根遍历若需遍历的二叉树为空，执行空操作，否则，依次执行下列操作：中根遍历左子树；访问根结点；中根遍右子树。后根遍历若需遍历的二叉树为空，执行空操作，否则，依次执行下列操作；后根遍历左子树后根遍历右子树访问根结点。显然，上述三种遍历方法的区别在于执行子任

49、务“访问根结点”的“时机”不同； 最先(最后、在中间)执行此子任务，则为先根(后根、中根)遍历。按某种遍历方法遍历一棵二叉树，将得到该二叉树上所有结点的访问序列6.树树是一种常用的数据结构。为了适应各种应用问题的需要，多种不同的存储结构也相应地建立起来。下面介绍树的三种常用存储结构(1)孩子链表表示法孩子链表表示法是树的一种链式存储结构。与二叉树的二叉链表存储方法类似，孩子链表表示法的基本思想是：树上的一个结点的内容(数据元素)以及指向该结点所有孩子的指针存储在一起以便于运算的实现。由于树上的结点的度(孩子数)没有限制，而且各个结点的度可能相差很大，一种自然的表示方法是为树上的每个结点X建立一

50、个“孩子链表”，以便存储X中的数据元素和指向X的所有孩子的指针。一个孩子链表是一个带头结点的单链表，单链表的头结点含两个域：数据域和指针域。其中，数据域用于存储结点X中的数据元素；指针域用于存储指向该单链表中第一个表结点(首结点)的指针。为了检索方便，所有头结点组织成一个数组，称为表头数组。对每个结点X的孩子链表来说，其中的所有表结点也含两个域，孩子域(即数据域)和指针域。第i个表结点的孩子域存储X的第i个孩子在头结点数组中的下标值。(2)孩子兄弟链表表示法孩子兄弟链表中所有存储结点的形式相同，均含三个域：数据域用于存储树上的结点中的数据元素；孩子域用于存储指向本结点第一个孩子的指针；兄弟域用

51、于存放指向本结点下一个兄弟的指针。值得注意的是，孩子兄弟链表的结构形式与二叉链表完全相同；但存储结点中指针的含义不同。二叉链表中存储结点的左、右指针分别指向左、右孩子；而孩子兄弟链表中存储结点的两个指针分别指向“长子”和“大弟”。在孩子兄弟链表表示法中，结点形式统一，结点间的联系比较简洁。同时，在这种存储结构上容易实现树形数据结构的大多数运算。(3)双亲表示法树上每个结点的孩子可以有任意多个，但双亲只有一个。因此，通过指向双亲的指针而将树中所有结点组织在一起形成一种存储结构是十分简法的。树的这种存储表示方法称为双亲表示法。在双亲表示法下，每个存储结点由两个域组成：数据域用于存储树上结点中的数据

52、元素；“指针”域用于指示本结点之双亲所在的存储结点。值得注意的是，“指针”域的类型定义可以有两种选择。第一种是将其定义为高级语言(如C语句)中的指针类型。通过将存储结点中的指针域定义为高级语言中的指针类型，就得到各种链式存储结构，如单链表、二叉链表、孩子链表等等。第二种选择是将“指针”域定义为整型、子界型等型。严格地说，无论选择上述哪种定义，得到的都是链式存储结构，因为在这两种定义之下，各存储结点之间的联结是通过“指针”完成的，而且这些指针反映了结点之间的逻辑关系。为了区别这两种链式结构，通常将指针域定义为高级语言中的指针类型的各种链式存储结构(如单链表、二叉链表等等)称为“动态链表”，相应的

53、指针称为“动态指针”；将指针域定义为整型、子界型等类型的各种键式存储结构称为“静态链表”，相应的“指针”称为：“静态指针”。动态链表中的结点是通过高级语言中的标准过程例如C语言的库函数malloc(size)动态(即运行期间)生成的(动态链表由此得名)，无需事先规定链表的容量，因此动态链表的大小是动态变化的。相反，静态链有的容量必须事先说明，因而其大小是固定的。然而，在某些情况下，特别是当结点数固定不变且可事先确定时，采用静态链表往往更加方便、直观。静态双亲链表由一个一维数组树成。数组的每个分量包含两个域：数据域和双亲域。数据域用于存储树上一个结点中的数据元素；双亲域用于存放本结点的双亲结点在

54、数组中的序号(下标值)。7.树的遍历与二叉树类似，遍历是树的一种重要运算。树的主要遍历方法有以下三种。(1)先根遍历若树非空，则访问根结点；依次先根遍历根的各个子树T1，Tm。(2)后根遍历若树非空，则依次先根遍历根的各个子树T1，Tm。访问根结点；(3)层次遍历若树非空，访问根结点；若第1，i(i1)层结点已被访问，且第i+1层结点未访问，则从左到右依次访问第i+1层结点。显然，按层次遍历所得的结点访问序列中，各结点的序号与按层编号所得的编号一致。8.树与二叉树之间的转换一般树转换为二叉树的基本思想是：将树中每个结点用两个链接表示就可以了，一个指向它最左边的孩子，另一个指向它右边的一个兄弟，

55、从图形上看，具体步骤是：加线：在兄弟结点间直接加一虚线；抹线：对每个结点，除了其最左的一个孩子外，抹去该结点原来与其余孩子之间的边线；旋转：将新加上的虚线改为实线，并将虚线以及有关的实线顺时针旋转45度。二叉树还原为一般树的步骤是：加线：若某结点是一父结点的左孩子，则将该结点的右孩子以及沿着右链搜索到的所有右孩子结点都用线与那个父结点连接起来；抹线：抹去原二叉树中所有结点与其右孩子的连线；旋转：将虚线及有关实线逆时针旋转约45度，并将几个结点按层次排列9.二叉树与森林之间的转换森林转换为二叉树的步骤是：将森林中的每棵树转换为二叉树；森林中第一棵树的根结点就是转换后二叉树的根结点，依次将后一棵树

56、作为前一棵树根结点的右子树。二叉树转换为森林的步骤是：森林第一棵树的根就是二叉树的根二叉树的左子树转换为森林的第一棵树，二叉树的右子树对应于森林中其余的树二叉树右子树的根结点作为余下树中第一棵树的根结点，以此类推。【考点五】 排序1.直接插入排序直接插入排序的基本思想是把表中元素依次插入一个已排好序的表中，就像人们打扑克摸牌时把牌插入手中的若干张牌里一样。表中n个元素依次插入的比较次数为1+2+3+(n-1)=n(n-1)/2。在插入时，元素的移动次数最多为1+2+3+(n-1)=n(n-1)/2。如果表中元素已排好序，则只需比较n-1次，而移动次数为0。2.直接选择排序直接选择排序的基本思想

57、是在表的n个元素中，经过n-1次比较得到其最大值(或最小值，下同)，这就排好了第一个元素；再经过n-2次比较得到余下元素中的最大值，这就排好了第二个元素直到比较1次后排好第n-1个元素，第n个元素的位置也就自然确定了。所需的比较次数为(n-1)+(n-2)+1=n(n-1)/2。所需移动次数最多也为n(n-1)/2。如果表中元素排好序，也需要比较n(n-1)/2次，而移动次数为0。3.冒泡排序冒泡排序的基本思想是将表中元素两个相邻元素依次比较，若不符合排序要求，则交换位置，这样经过n-1次比较后，将确定出最大(或最小)元素的位置，这称为一趟扫描。经过n-1次扫描后，就完成了整个表的排序。第一趟

58、扫描的比较次数是n-1，第二趟扫描的比较次数是n-2，总的比较次数是(n-1)+(n-2)+1=n(n-1)/2。如果恰好表中元素按反序排列，则需要移动的次数为3n(n-1)/2。如果表中元素已排好序，并采用交换标志来表示并未发生过交换，则只需一趟扫描，只比较n-1次，就够了；当然，移动次数也是0。4.归并排序归并排序的基本思想是表中元素两两比较排序，使表中的n个元素变成n/2个已排序的组，再两两组比较，而变成n/4个已排序的组，直到表中只含有一个已排序的组，即完成排序。所需要的比较次数为nlog2n，移动次数为n。若表已排好序，则比较次数仍为nlog2n，但移动次数为05.快速排序快速排序的

59、基本思想是把表中某元素作为基准，将表划分为大于该值和小于该值的两部分，然后用递归的方法处理这两个子表，直到完成整个表的排序。快速排序的比较次数为(n-1)+(n-2)+1=n(n-1)/2，移动次数最多也是n(n-1)/2。如果每次的基准元素刚好是表的中值，使表分为大小相等的两个子表，则比较次数为nlog2n;如果表已排好序，则移动次数为0。6.常用排序方法的性能比较如下表所示： 常用排序方法的性能比较排 序 方 法 平均时间 最坏情况的时间 辅助存储 冒泡法、直接选择法、直接插入法O(n2) O(n2) O(1) 快速排序 O(nlog2n) O(n2) O(log2n) 堆排序 O(nlo

60、g2n) O(nlog2n) O(1) 归并排序 O(nlog2n) O(nlog2n) O(n) 注：在上表中，我们将n(n-1)/2也记为O(n2)。如果在待排序的表中含有多个码值相同的记录，经过排序后，这些记录的相对次序不变，则称这种排序方法是稳定的，否则是不稳定的。根据上述说法，可以看出直接插入法、归并法是稳定的；而直接选择法、冒泡法、快速排序法、堆排序法是不稳定的。【考点六】 检索1.顺序检索检索又称为查找。顺序检索是将待查找的关键码值与线性表中各结点的关键码值逐一比较，直到找到所需的记录，检索成功；或者在表中找不到所需记录而检索失败。顺序检索不要求线性表事先排序。设线性表有n个元素

61、，则最多检索次数为n，最少检索次数为1。2.二分法检索二分法检索要求线性表结点按关键码值排序且以顺序方式存储。在查找时，首先与表的中间位置上结点的关键值比较，若相等则检索成功；否则根据比较结果确定下一步在表的前半部或后半部中继续进行。二分法检索的效率较高，设线性表有n个元素，则最多的检索次数为大于log2n的最小整数，最少的检索次数为1。3.分块检索分块检索把线性表分成若干块，块内结点不必有序，但块与块之间必须有序，即每一块中各结点的关键值必须大于(或小于，依此类推)前一块最大关键值。为加快查找，还要建立一个索引表，表中给出每一块的最大关键值和指向块内第一个结点的指针。分块检索分两步进行，先查

62、索引表，确定要找的记录在哪一块；然后再在相应的块中检索。分块检索适合于线性表很大，数据又是动态变化的情况。在查索引表时，可采用顺序法或二分法；在块内查找所求记录时，采用顺序法。由于分块而缩小了查找范围，从而加快检索速度。4.散列表检索根据关键值，就可以迅速找到该记录所对应的存储位置，这就是建立在散列函数基础上的散列检索。设记录的关键值为k，则该记录的存储位置可用散列函数H来计算H=H(k)。常用来产生的散列函数的方法是除余法，即取H(k)=k mod p 设散列表长度为n，则取p为小于n的最大素数。一般说来，关键码值的集合比散列表存储位的数目大得多，这正是体现散列表的优势所在，但同时带来了冲突

63、问题，即不同的关键值经散列函数计算，可能得到相同的存储位置。一个好的散列函数应该使冲突的可能性尽量小。最常用的解决冲突的方法是线性探测法，就是在发生冲突时，从H(k)以后的位置逐一探测，直至找到一个空位置，将新记录插入；在检索时，如果H(k)中不是所需关键值的记录，也是从H(k)往下逐一搜索，直到找到所需关键值或查找失败为止。应注意查找次序是：H(k),H(k)+1,H(k)+2,n-1,0,1,2,，H(k)-1 即在n-1以后，又从0开始，因为在位置上是循环的。双重散列技术是对线性探测法的改进。它使用两个散列函数H1和H2。对关键值k，计算H1(k)，求得0到n-1之间的一个散列地址；若在这个地址上冲突，则下一个被探测的地址为(H1(k)+H2(k) mod n，关于选择H2的方法在此不做讨论第3章 操 作 系 统 【考点一】 操作系统的基本概念1.引言现代计算机系统由硬件和软件两部分构成。硬件指的是构成计算机系统的物理设备。操作系统控制和管理所有的系统硬件(如