2023年全国三级数据库笔试部分

第一章计算机基础知识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）令牌总线方法（TOKENBUS）。（3）令牌环方法（TOKENRING）。3、局域网参考模型（IEEE802）（1）IEEE802参考模型：IEEE802参考模型是美国电气电子工程师协会在1980年2月制订的，称为IEEE802标准，这个标准相应于OSI参考模型的物理层和数据链路层，数据链路层又划分为逻辑链路控制子层（LLC）和介质访问控制子层（MAC）。（2）IEEE803标准(P49)（3）IEEE802.2标准定义的共享局域网有三类：a、采用CSMA/CD介质访问控制方法的总线型局域网。(ETHERNET)b、采用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)使用基于IEEE802.5的单令牌的环网介质访问控制MAC协议;(2)使用IEEE802.2协议,与符合IEEE802标准的局域网兼容;(3)数据传输速率为100Mbps,连网的结点数小于等于1000,环路长度为100km;(4)可以使用双环结构,具有容错能力;(5)可以使用多模或单模光纤;(6)具有动态分派带宽的能力,能支持同步和异步数据传输.9、快速以太网（100MbpsFastEthernet）IEEE802.3U10、千兆位以太网（1GbpsGigabitEthernet）IEEE802.3ZGigabitEthernet的传输速率比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）无线局域网标准：IEEE802.1116、IEEE802.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互换机。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）。网桥在局域网中经常被用来将一个大型局域网提成既独立又能互相通信的多个子网的互连结构，从而可以改善各个子网的性能与安全性。基于这两种标准的网桥分别是：透明网桥（IEEE802.1合用于ETHERNET）、源路选网桥（IEEE802.5合用于TOKENRING）（13）路由器是在网络层上实现多个网络互连的设备。（14）网关可以完毕不同网络协议之间的转换。实现协议转换的方法重要是：直接将网络信息包格式转化成输出网络信息包格式N(N-1)；将输入网络信息包的格式转化成一种统一的标准网间信息包的格式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第二章数据结构算法2.1基本概率考点1数据结构的基本概念1.数据在计算机系统中，数据不仅包含了通常的数值概念，尚有更广泛的含义我们把采用计算机对客观事物进行辨认、存储和加工所做的描述，统称为数据。简言之，数据就是计算机化的信息数据的基本单位是数据元素。数据元素可由一个或多个数据项组成。数据项是数据的不可分割的最小单位，又称为关键码，其值可以唯一拟定一个数据元素的数据项。2.数据结构数据结构涉及3个方面的内容：数据之间的逻辑关系、数据在计算机中的存储方式，以及在这些数据上定义的运算的集合。(l)数据的逻辑结构。数据的逻辑结构与数据在计算机中的存储方式无关，它用来抽象地反映数据元素之间的逻辑关系。逻辑结构可分为线性结构和非线性结构。最常见的线性结构是线性表，最典型的非线性结构是树型结构。(2)数据的存储结构。数据的存储结构实现了数据的逻辑结构在计算机内的存储问题，存储结构又称为物理结构。存储结构分为顺序存储结构与链式存储结构。(3)数据的运算。数据的各种逻辑结构都有相相应的运算，每一种逻辑结构都有一个运算的集合。数据运算重要涉及查找(检索)、排序、插人、更新及删除等。考点2重要的数据存储方式实现数据的逻辑结构到计算机存储器的映像有多种不同的方式。顺序存储结构和链式存储结构是两种最重要的存储方式。1.顺序存储结构顺序存储结构是将逻辑上相邻的数据元素存储在物理上相邻的存储单元里，节点之间的关系由存储单元的相邻关系来决定，它重要用于存储线性结构的数据。顺序存储结构的重要特点如下。(1)由于节点之间的关系由物理上的相邻关系决定，所以节点中没有链接信息域，只有自身的信息域，存储密度大，空间运用率高。(2)数据结构中第i个节点的存储地址乙可由下述公式计算求得：L?i＝L?0＋(i－1)×KL?0为第一个节点存储地址，左为每个节点所占的存储单元数。(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后插人指针q的关键运算环节：q↑.link：＝P↑．link：p↑.link：＝q；(2)删除指针P后继节点q的关键运算环节：q：＝p↑.link；p↑.link：＝q↑．link；(3)在第一个节点(或称头节点)前插人一个指针P的关键运算环节：p↑.link：＝head；head：二P；(4)删除表中头节点的关键运算环节：head：＝head↑.link：2.双链表在双链表中，每个节点中设立有两个指针域，分别用以指向其前驱节点和后继节点。rlink指向节点的后继，llink指向节点的前驱，这样的结构方便向后和向前查找。(l)若要在双链表中删除指针P所指的节点时，只需修改其前驱的rlink字段和后继的Mink字段，环节如下：p↑.llink↑.rlink：＝p↑.rlink；P↑T．rlink↑.llink：＝P↑．llink；(2)假如要在指针P后面插人指针q所指的新节点，只需修改P指针所指节点的rlink字段和本来后继均Ilink字段，并重新设立q所指节点的Mink和rlink值，环节如下：q↑.Mink：＝P：q↑．rlink：＝P↑．rlink;P↑．rlinkr.Rink：＝q；p↑．rlink：＝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(m≥0)个互不相交的有限集71,，兀，…，T，其中每一个集合自身又是一棵树，并且称为根的子树。这是一个递归的定义，即在树的定义中又用到了树的概念。这恰好显示了树的固有特性。考点13二叉树定义1.二叉树的定义二叉树是一种最简朴而巨重要的树型结构它或者是一棵空树，或者是一棵由一个根节点和两棵互不相交的、分别称为这个根的左子树和右子树的二叉树组成。有两种特殊形态的二＿叉树，它们是满二叉树一和完全二叉树。2.二叉树与树的区别尽管树和二叉树的概念之间有许多关系，但它们是两个概念二叉树不是树的特殊情况，树和二叉树之间最重要的区别是：二叉树的节点的子树要区分左子树和了。子树，即使在节点只有一棵子树的情况下也要明确指出该子树是左子树还是右子树。考点14树与二叉树之间的转换1.树转换成二叉树将一棵树转换成相应的二叉树应涉及以下几个环节：(1)在兄弟竹点之间加条连线(2)对每一个节点，只保存它与第一个子节点的连线，与其他子节点连线所有抹掉(3)以树根为轴心，顺时针旋转45。2.森林转换成二叉树假如F={T?1??，T?2,…Tm}是森林，则可按如下规则将其转换乘一棵二叉树B=(root,LB,RB,)：(1)若F为空，即m＝0，则B为树。(2)若F非空，即m≠0,则B的跟root即为森林中的第一棵树的跟ROOT(??T)；B的左子树LB是从T、中根节点的子树森林F1＝｛T11，T?，…，T?m｝转换而成的二叉树；其右子树RB是从森林Fˊ＝{T?1,T2,…Tm}转换而成的二叉树。3.二叉树转换成森林假如B二(root，LB，RB)是、棵二叉树，则可按如下规则转换成森林F＝{T?1,T2,…Tm}：(1)若B为空，则F为空。(2)若B非空，则F中第一棵树T1的根ROOT(T1)即为二叉树B的根root;T1中根节点的子树森林Fl是由B的左子树LB转换而成的；F中除T1之外其余树组成的森林Fˊ＝{T?1,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二分法查找二分法查找是一种效率比较高的查找方法，在进行二分法查找时，线性表节点必须按关键码值排序，且线性表是以顺序存储方式存储的。二分法查找的优点是比较次数少，查找速度快，平均检索长度小，通过｛＿logen次比较就可以完毕查找过程。缺陷是在查找之前要为建立有序表付出代价，同时对有序表的插人和删除都需要平均比较和移动表中的一半元素。一般情况下，二分查找适应于数据相对固定的情况，且二分法查找只合用于线性表的顺序存储。考点20分块查找分块查找又称索引顺序查找，是介于线性查找和二分法查找之间的一种查找方法。它规定把线性表分成若干块，每一块中的节点不必有序，但块与块之间必须排序，不妨设每一块中各节点的关键码都大于前一块的最大关键码值。此外，还规定将各块中的最大关键码值组成一个有序的索引表。满足上述条件的线性表称做分块有序表。它的分块检索的过程分以下两步进行。(I)先查索引表(可以用线性检索或二分法检索)，拟定要找的记录在哪一块。(2)在相应的块中线性检索待查记录。考点21散列表的存储和查找散列存储中使用的函数称为散列(Hash)函数散列表(又称哈希表)是线性表的一种重要的存储方式和检索方法。实现散列技术检索必须解决两个问题：一个是构造一个好的散列函数，尽也许避免冲突现象的发生；另一个是设计有效的解决冲突的方法。1.散列函数常用的散列函数有以下几种。(l)除余法。选择一个适当的正整数川通常选p为不大于散列表存储区域大刁、的最大素数)，用p去除关键码值，取其余数作为地址，即h(key)二keymodp。(2)数字分析法。当关键码的位数比存储区域地址码位数多时，可以对关键码的各位进行分析，去掉分布不均匀的位，留下分布均匀的位作为地址。(3)折叠法。将关键码值从某些地方断开，分为几段，折叠相加，作为地址。(4)中平方法。对关键码值求平方，取中间的几位数作为地址。2.解决冲突的方法发生冲突是指由关键字求得的散列地址为i(O-i-m一l)的位置上已存有记录，解决冲突就是为该关健字找到另一个“空”的散列地址。常用的解决冲突的方法有开地址法、拉链法等。3.负载因子(装填因子)和平均检索长度装填因子表达散列表的装满限度，定义为散列表中节点的数目除以基本区域能容纳的节点数所得的商，用a表达a越小，冲突的也许性越小，a越大，冲突的也许性越大，检索时需要比较的次数就越多。平均检索长度依赖于散列表的装填因子。2.6排序排序是数据解决领域经常要使用的一种运算，就是将一组元素按照关键码的递增或递减的顺序来排列为过程按照排序过程中的存储器不同，可将排序方法分为内部排序和外部排序两类。一厂面将介绍插人排序、选择排序、互换排序和归并排序等几种常用的内部排序方法。考点22插入排序插人排序的基本思想：每一步将一个待排序的记录按其关键字值的大小插人到一个有序的文献中，插人后该文献仍然是有序文献。l.直接插入排序直接插人排序是一种最简朴的排序方法它的基木思想是将一个记录插人到已排好序的有序表中，从而得到一个新的、记录数增I的有序表整个排序过程为：先将第一个记录当作是一个有序的子序列，然后从第2个记录起依次逐个地插人到这个有序的子序列中去。直接插人排序的时间复杂度为0(n)。直接插人排序方法不仅合用于顺序表，并且合用于单链表2.二分法插入排序在直接插人排序｝｝，，若采用二分法查找而不是顺序查找待插入元素的插人位置，则称为二分法插入排序这种插人排序可减少比较次数，使排序速度有所提高，但提高不会太多，由于移动记录的总次数不受改变，其时间复杂度仍为0(n2)。直接插人和二分法插入排序方法都是稳定的，由于它们不会改变原序列中具有相同关键字记录的相对顺序。3.希尔排序希尔排序又称缩小增量排序，它是对直接插人排序的一种改善方法希尔排序的基本思绪：对相隔较大距离的记录进行比较，就能使记录在比较后移动较大的距离这样能使较小的记录尽快往前移，较大的记录尽快往后移，从而提高排序的速度希尔排序是一种不稳定的排序过程考点23选择排序选择排序的基木思想是每次从待排序的记录中选出关键码值最小或最大的记录放在已排好序的记录序列后面，直至排序完毕。1.直接选择排序直接选择排序也是一种简朴的排序方法。选择排序的基本方法是：每次从待排序的区间中选择出具有最小排序码的元素。把该元素与该区间的第一个元素互换位置。第一次待排序区间为A[1]～A[n]，通过选择和互换后，A［1］为最小排序码的元素。第二次待排序区间为A[2]~A[n]，通过选择和互换后，A[2]为仅次于A［1］的具有最小排序码的元素，依次类推，通过n-1次选择和互换后，排序完毕。直接选择排序方法的时间复杂度为O(n2)，此方法是不稳定的。2.堆排序堆的定义如下：n个元素序列{k?1,k2，…，kn}，当且仅当满足下列关系时，称之为堆。Ki≤K2i,Ki≤K2i＋1，i＝1，2，…，n/2堆排序的基本思想：对一组待排序的关键码，一方面把它们按堆的定义排列成一个序列，找到其中最小的关键码．接着将最小的关键码取出，然后将剩下的关键码再建堆排序，依次进行，直到将所有关键码排好为止。建堆的基本方法是将大的元素下沉，小的元素上浮，即所谓的筛选法。在最坏的情况下，堆排序时间复杂度为O(nlog2n)。堆排序仅需一个记录大小的辅助存储空间。堆排序是不稳定的。考点24互换排序互换排序的基本思想：两两比较待排序记录的关键字值，并互换不满足顺序规定的那些记录，直到所有记录满足关键字值排序规定为止。1.起泡排序起泡排序又称为冒泡排序，其基本思想是通过相邻记录之间关键字的比较和互换，使关键字值较小的记录逐渐从底部移向顶部，即从下标较大的单元移向下标较小的单元，关键字较大的记录从顶部移向底部。从起泡排序算法可以看出，若初始序列为“正序”序列，则只需进行一趟排序；反之，若初始序列为“逆序”序列，则需进行。一I趟排序。因此，总的时间复杂度为。(矿)。起泡排序是一种稳定的排序过程。2.快速排序快速排序是口前内部排序中速度最快的一种排序算法，其实质是对起泡排序的改善在快速排序中，记录的比较和互换是从两端向中间进行的，排序码较大的记录一次就可以从前面互换到后面单元，排序码较小的记录一次就可以从后面互换到前面单元，记录每次移动的距离较远，总比较和移动次数较少。快速排序是不稳定的排序。排序速度最快时，其时间复杂度为0(nlog,n)；排序速度最慢时，其时间复杂度为。(n`)快速排序的平均时间复杂度为0(nlog2n)。快速排序除了需要一个记录的辅助空间来存放每次选取的基准记录外，还需要一个栈空间来实现递归。考点25归并排序归并是将两个或者多个有序表合并成一个有序表归井排序规定待排序文献已经部分排序。归并排序的基本思想是将这些已排过序的文献进行合并，得到完全排序的文献。假设初始序列具有n个记录，则可当作是n个有序的子序列，每个子序列的长度为1，然后两两归并，得到n/2个长度为2或I的有序子序列，再两两归并，如此反复，直到得到一个长度为n的有序序列为止。这种排序方法称为二路归并排序。归并排序平均时间复杂度为0(n1092n)，辅助空间为0(n)。第3章操作系统3.1操作系统考点1操作系统概念1.操作系统基本概念操作系统是计算机系统中的一个系统软件，是控制和管理计算机硬件和软件资源，合理组织计算机工作流程及方便用户的程序集合。操作系统有两个重要的作用：一是管理系统中的各种资源；二是给用户提供一个和谐的界面，方便用户操作计算机。2.操作系统的基本特性操作系统涉及以下3个基本特性：(1)并发性。所谓并发性是指在计算机系统中同时存在多个程序，从宏观上看，这些程序是同时向前推生的。(2)共享性。所谓资源共享性是指操作系统程序与多个用户程序共享系统中的各种资源。这种共享是在操作系统控制下实现的。(3)随机性。操作系统运营在一个随机环境中。一个设备也许在任何时候向解决机发出中断请求，系统无法知道运营着的程序会在什么时候做什么事情。考点2操作系统的功能操作系统的重要功能涉及以下几个方面。(1)进程管理。重要是对解决机进行管理。(2)存储管理。重要是对内存的分派、保护和扩充。(3)设备管理。对所有输人、输出设备的管理。(4)文献管理。重要涉及文献的逻辑组织和物理组织，目录的结构和管理。(5)作业管理。为用户提供一个和谐的环境，方便用户组织自己的工作流程。考点3操作系统的类型随着计算机硬件技术的不断发展，出现了多种类型的操作系统：手工操作系统、批解决操作系统、分时系统、实时系统及通用操作系统。随着网络技术的发展，相应地出现了网络操作系统和分布式操作系统。下面将对重要的操作系统进行简朴介绍。1.批解决操作系统批解决操作系统最大的特性就是用户不直接操作计算机，而是将作业交给系统操作员，由操作人员将作业成批地输人计算机，然后按某种调度策略，顺序地执行作业流中的每一个作业，以节省人工操作时间和提高机器的使用效率。批解决操作系统又可分为单道批解决系统和多道批解决系统。2.分时系统分时系统中的分时指多个用户通过终端可同时使用一台计算机。操作系统在接受用户发出的请求后，按照时间片轮转算法轮流分派给每个用户一段CPU时间，进行各自的解决。但对于每个单独的用户都仿佛自己独占了整个计算机系统分时系统重要有以下几个方面的特点：(1)多路性若干个用户同时使用一台计算机，从微观上看是各用户轮流使用计算机；从宏观上看是各用户在并行工作。(2)交互性二用户可根据系统对清求的响应结果，进一步向系统提出新的请求。(3)独立性用户之间可以互相独立、互不十涉；系统保证各用户程序运营的完整性，不会发生互相混淆或破坏等现象。(4)及时性系统对用户的输人及时做出啊应。分时系统性能的重要性能指标之一是响应时间，即从终端发出的命令到系统予以应答听需的时间。3.实时系统实时系统是指可对外部事件做出及时洞应并在一定期间内完毕对事件的解决的操作系统，其特点是及时响应和高可靠性实时系统可分为实时控制系统和实时信息解决系统两大类。4.个人计算机操作系统个人计算机操作系统是指用于个人计算机上的操作系统，提供联机交互功能：这规定系统有和谐的用户接口和操作界面5.网络操作系统网络操作系统可通过通信设备将分散的具有独立功能的多个计算机系统互联起来，用于实现信息互换、资源共享、互操作和协作解决的系统各用户间都要遵守一定的网络协议来共享资源。6.分布式操作系统分布式操作系统可统?管理和调度整个系统上的资源以实现各计算机之间的资源共享和信息传输，对任务实行动态、合理的分派及并行的解决分布式系统各个计算机之间无主次之分，为用户提供一个标准的接口和统一的界面，使用户方便实现听需要的操作。考点4研究操作系统的方法研究操作系统可以从以下几种不同的角度进行1.资源管理观点从资源管理的观点来看，操作系统的管理对象是计算机系统的资源，操作系统则是管理系统资源的程序集合通常，把操作系统分为解决机管理、存储管理、设备管理、作业管理和文献管理等5个重要部分，由这几部分程序的协调、配合来完毕用户的作业规定。2.进程观点这种观点把操作系统看作由若干个可以同时独立进行的程序和一个对这些程序进行协调的核心所组成，这些同时运营的程序称为进程，每个进程都可完毕某一特定的任务。3.虚机器观点从服务用户和机器功能扩充的观点来看，操作系统为用户使用计算机提供了许多服务功能和良好的工作环境。考点5操作系统的硬件环境硬件是构造操作系统的基础，硬件对操作系统的构造提供必要的支持。通常，操作系统所涉及的硬件环境重要涉及以下几个方面。1.特权指今与解决机状态(1)特权指令。只允许操作系统使用，而不允许一般用户使用的指令。(2)非特权指令。特权指令之外的指令称做非特权指令，非特权指令的执行不影响其他用户及系统。(3)CPU状态。CPU交替执行操作系统程序和用户程序。在执行不同程序时，根据运营程序为机器指是，的使用权限而将CPU置为不同的状态CPU的状态属于程序状态字PSW中的一位。2.中断机制中断机制是现代计算机系统中的基本设施之一，它在系统中起着通信联络的作用，以协调系统对各种外部事件的响应和解决。3.定期装置为了实现系统管理和维护，硬件必须提供时钟，即定期装置硬件时钟通常分为两类：即绝对时钟和相讨时钟。3.2进程管理考点6多道程序设计1.程序的顺序执行程序的顺序执行具有以下几个特点：(1)顺序性。程序所规定的动作在机器上严格地按顺序执行，每个动作的执行都以前一个动作的结束为前提条件。(2)封闭性。程序执行得到的最终结果由给定的初始条件决定，不受外界因素的影响，即只有程序自身的动作才干改变程序的运营环境。(3)可再现性。顺序执行的最终结果与程序运营的速度无关。2.多道程序系统中程序执行环境的变化程序执行环境具有以下3个特点：(1)独立性。在多道环境下执行的每道程序都是逻辑上独立的，且执行速度与其他程序无关，执行的起止时间也是独立的。(2)随机性。在多道程序环境下，程序和数据的输入与执行的开始时间都是随机的。(3)资源共享性。一般来说，多道环境下执行程序的道数总是多于计算机系统中CPU的个数，单CPU也是如此。3.程序的并发执行程序的并发执行是指为了充足运用系统资源，提高计算机的解决能力，在计算机系统中有两个或两个以上的程序同时执行的状态。参与并发执行的程序称为并发程序，并发程序执行时的特点如下：(1)各并发程序在执行期间互相制约。(2)程序与计算不是一一相应的关系。(3)不可再现性。4.多道程序系统一般情况下，计算机要同时解决多个具有独立功能的程序来增强系统的解决能力和提高机器的解决效率。常采用并行操作技术来使系统的各种硬件资源做到并行工作，即在计算机中，所运营程序的道数(吞吐量)多。程序在运营时有如下3个特点：独立性、随机性和资源共享性。考点7进程1.进程的概念进程是操作系统中最基本、最重要的概念。通常是指内存区域中的一组指令序列的执行过程，是程序中具有一定独立功能的关于某个数据集合的一次运营活动，是系统进行资源分派和调度的一个独立单位。2.进程的特性(1)并发性可以同其他进程一道向前推动，即一个进程的第一个动作可以在另一个进程的最后一个动作结束之前开始(2)动态性是指进程相应用程序的执行过程，体现在两方面：其一，进程动态产生，动态消亡；其二，在进程的生命周期内，其状态动态变化。(3)独立性。一个进程是一个相对完整的调度单位，它可以获得解决机并参与并发执行。(4)交往性。一个进程在运营过程中也许与其他进程发生直接的或间接的互相作用。(5)异步性。每个进程按照各自独立的、不可预知的速度向前推动。3.进程与程序的区别与联系(1)进程是程序的执行，是动态的；而程序是指令的集合，是静态的。(2)进程的存在是有限的，从运营到结束，是暂时的；而程序则是永久存在的。(3)进程涉及程序、数据和进程控制块(PCB)。(4)一个程序可以有多个进程，一个进程也可以包含多个程序。4.进程的状态进程在其存在过程中，它们的状态在不断发生变化。系统中的不同事件均可以引起进程状态的变化。一般情况下，一个进程可分为以下3种状态：(1)就绪状态。是指一个进程已经具有运营条件，但由于没有获得CPU而不能运营所处的状态。一旦把CPU分派给它，该进程就可运营二处在就绪状态的进程可以是多个。(2)运营状态。是指进程已获得CP1,并且在CPU上执行的状态。(3)等待状态。也称阻塞状态或封锁状态，是指进程由于等待某种事件发生而暂时不能运营的状态。在一定的条件下，进程的状态是可以互相转换的。5.进程控制块进程控制块(ProcessContro1B1ock，简称PCB)是用来记录进程状态及其他相关信息的数据结构,PCB是进程存在的唯一标志，PCB存在则进程存在。系统创建进程时会产生一个PCB，撤消进程时，PCB也自动消失。考点8进程控制进程控制也称进程管理，对进程实行有效的管理，涉及进程的建立、撤消、进程阻塞及进程的唤醒等。进程控制是通过原语来实现的，用于进程控制的原语一般有：创建进程、撤消进程、挂起进程、激活进程、阻塞进程、唤醒进程及改变进程优先级等。1.创建原语创建原语用于建立一个新的进程，其重要操作过程是先向系统申请一个空闲的PCB，然后根据父进程提供的参数，将相关信息填入，最后返回一个进程的内部名。2.撤稍原语撤消原语是用于撤消一个已完毕任务的进程，以释放它所占用的所有的内部和外部资源。实质上是撤消PCB，有两种撤消策略，一种是只撤消1个具有特定标记符的进程，另一种是撤消该进程及其所有子孙进程。3.阻塞原语阻塞原语的作用是将进程由运营状态变回阻塞状态。具体过程是先中断CPU，将CPU的当前状态保存在PCB现场信息中，将进程的当前状态置为等待，插人到等待队列中去。4.唤酸原语唤醒原语的作用是将进程由阻塞状态变为就绪状态，其操作过程是在等待队列中找出某进程，将它的当前状态置为就绪，然后将其从等待队列中撤出并插人到就绪队列中去。考点9进程的同步与互斥1.临界资源和临界区临界资源是指一次只允许一个进程使用的资源：一个进程中访问临界资源的那段程序代码称为临界区。它们不允许两个及以上的进程同时访问或修改。2.进程的同步进程的同步运营是指进程之间的一种直接的协同工作关系，这些进程通过互相合作来完毕一项任务。3.进程的互斤进程间一种间接的互相作用构成进程互斥。进程互斥的目的就是使某一进程可以在某一时间内独占一些资源?考点10进程通信1.信号量和P,V操作解决进程的同步与互斥，既可用硬件实现，也可用软件实现。(1)在系统中信号量(S)是一个整数。当S}--0时，表达可供并发进程使用的资源实体数；当S＜0时，代表等待使用临界区的进程数。(2)只能通过P、V操作原语来改变P,V操作信号量的数值。P操作表达在当前进程申请的各种资源，V操作代表当前进程释放所占用的资源。P操作和V操作都是低档进程通信原语。(3)运用P、V操作可以解决并发进程间的互斥问题。(4)运用P、V操作也可以解决并发进程间的同步问题。2.高级通信机构对进程间大量信息的互换常采用消息通信的方法，高级通信原语不仅可保证互相制约的进程的对的关系，同时还实现了进程之间的信息互换。该方法不仅能实现进程间的通信，并且能实现进程间数据的传送。下面分别介绍3种高级进程通信。(1)消息缓冲通信。消息缓冲通信的基本思想：系统管理一组消息缓冲区，在每一个缓冲区可以存放一个信息。发送进程在发送消息前，在内存中设立一个发送区，装人欲发送的消息，在申请到一个消息缓冲区以后，将发送区里的消息发送到缓冲区中。(2)管道通信。管道通信实质上是运用外存来进行数据通信，传输数据量大，但速度较慢。发送进程从管道的一端写人数据，接受进程在需要的时候从管道的另一端读出数据。(3)信箱通信。信箱通信指进程并不把消息直接发送给对方，而是将通信的消息以信件的方式放在信箱内。考点11进程调度进程调度即解决机调度在多道程序系统中，进程数目往往大于解决机数目，这会使进程互相争夺解决机，必须按照一定的策略将C1't分派给这些进程中的某一进程1.进程调度的功能记录系统中所有进程的状态、优先数及资源使用情况，CPU空闲时按一定算法拟定将CPU分派给哪个进程和分派多长时价。2.进程调度方式进程调度方式是指有优先数更高的进程进人就绪队列时，如何分派CPU，一般涉及剥夺方式和非剥夺方式两种调度方式3.进程调度算法(1)先来先服务算法FCFS。该算法按照进程进入就绪队列的先后顺序来选择二即每当进行进程调度时．总是把就绪队列的队首进程投人运营二(2)时间片轮转算法。这重要是分时系统中使用的一种调度算法。其基本思想是：将CPU的解决时间划提成一个个时间片，就绪队列中的诸进程轮流运营一个时间片。当时间片结束时，就逼迫运营进程让出CPU，该进程进人就绪队列，等待下一次调度。同时，进程调度又去选择就绪队列中的另一个进程，分派给它一个时间片，以投人运营。影响时间片大小设立的重要因素有：系统响应时间、就绪进程数目(终端数目)和一计一算机解决能力。(3)最高优先级算法进程调度每次将解决机分派给具有最高优先级的就绪进程，进程的优先级由进程优先数决定进程优先数的设立可以是静态的，也可以是动态的。最高优先数算法又可与不同的C1'U方式结合起来，形成可剥夺式最高优先数算法和不可剥夺式最高优先数算法。考点12死锁1.死锁的概念死锁是指在多道程序系统中，两个或两个以上的进程无限期地等待永远不会发生的事件，得不到所需资源因而不能运营的状态处在死锁状态的进程称为死锁进程。死锁产生的因素：一是系统资源局限性；二是多道程序运营时，进程的推动顺序不合理。2.产生死锁的必要条件(1)互斥条件。进程互斥使用资源，任一时刻一个资源只为一个进程独占，其他进程若请求一个已被占用的资源，只能等占用者释放后才干使用(2)不可剥夺条件(不可抢rt1-)。进程所获得的资源在未使用完毕之前，不能被其他进程强行剥夺，而只能由获得该资源的进程自己释放(3)部分分派(占有等待)。进程每次申请它所需要的一部分资源，在申请新的资源的同时，继续占用已分派到的资源。(4)循环等待：存在一个进程环路，环路中每一个进程已获得的资源同时被下一个进程所请求。3.资源分派图死锁问题可用一个有向图来表达。资源分派图就是描述进程、资源及它们之间关系的有向图。当进程请求资源时，系统检查并发进程组是否构成资源的请求环路。存在环路，也许存在死锁；不存在环路，一定没有死锁。4.死锁防止只要破坏死锁产生的4个必要条件之一，就可有效避免死锁的产生，重要有以下几种方法：(1)破坏互斥条件(2)破坏不可剥夺条件。(3)破坏部分分派条件二(4)破坏循环等待条件5.死锁解除当发现死锁后，可采用以下两种方法来解除死锁：(1)资源剥夺法。从一些进程那里强行剥夺足够数量的资源分派给死锁进程，以解除死锁状态(2)撤消进程法。按照某种策略逐个地撤消死锁进程，直到获得为解除死锁所需要的足够使用的资源为按照什么原则撤消进程，实用而又简便的方法就是撤消那些代价最小的进程，或者撤消进程的数量最少。考点13线程1.线程的概念线程是进程中的一个实体，是CPU调度和分派的基本单位2.线程的属性(1)每个线程有一个唯一的标记符和一张线程描述表。(2)不同的线程可以执行相同的程序。(3)