2.1 二级公共基础知识选择题高频考点

2.1.1 计算机系统

【考点1】　计算机概述

1.计算机的发展历程

目前公认的第一台电子数字计算机是ENIAC(Electronic Numerical Integrator And Calculator),它于1946年在美国宾夕法尼亚大学研制成功。ENIAC的计算速度是每秒5000次加法或300多次乘法。它的诞生标志着计算机时代的到来,从此以后,计算机以极高的速度发展。

根据计算机本身采用的物理部件不同,将其发展分为4个阶段。

第1阶段是电子管计算机时代,时间为1946年到20世纪50年代后期。

第2阶段是晶体管计算机时代,时间为20世纪50年代后期到20世纪60年代中期。

第3阶段是中小规模集成电路计算机时代,时间为20世纪60年代中期到20世纪70年代初期。

第4阶段是大规模和超大规模集成电路计算机时代,时间是20世纪70年代初期至今。

2.计算机体系结构

虽然ENIAC可以大大提高计算速度,但它本身存在两大缺点:一是没有存储器;二是用布线接板进行控制,电路连接烦琐、耗时,这在很大程度上抵消了ENIAC计算速度高带来的便利。因此,以美籍匈牙利数学家冯·诺依曼为首的研制小组于1946年提出了“存储程序控制”的思想,并开始研制存储程序控制的计算机EDVAC(Electronic Discrete Variable Automatic Computer)。1951年,EDVAC问世。

EDVAC的主要特点如下。

(1)在计算机内部,程序和数据采用二进制数表示。

(2)程序和数据存放在存储器中,即采用程序存储的概念。计算机执行程序时,无须人工干预,能自动、连续地执行程序,并得到预期的结果。

(3)计算机硬件由运算器、控制器、存储器、输入设备及输出设备五大基本部件组成。

直到今天,计算机基本结构的设计仍采用冯·诺依曼提出的思想和原理,人们把符合这种设计的计算机称为冯·诺依曼机。冯·诺依曼也被誉为“现代电子计算机之父”。

3.计算机系统基本组成

计算机系统由硬件系统和软件系统两大部分组成,如图2.1所示。

图2.1 计算机系统的组成

硬件系统是由借助电、磁、光、机械等原理构成的各种物理部件的有机组合,是计算机系统赖以工作的实体。硬件系统也被称为裸机,裸机只能识别由0和1组成的机器代码。

软件系统是为运行、管理和维护计算机而编制的各种程序、数据和文档的总称。软件是计算机的核心,没有软件的计算机毫无实用意义。软件是用户与硬件之间的接口,用户可以通过软件使用计算机硬件上的数据信息资源。

计算机软件按照面向应用对象的不同主要分为系统软件和应用软件。系统软件是控制和协调计算机外部设备、支持应用软件开发和运行的软件,主要负责管理计算机系统中各种独立的硬件,使之可以协调工作。它主要包括操作系统、语言处理系统、数据库管理系统及系统辅助处理程序等。其中最主要的是操作系统,它提供了软件运行的环境。应用软件是指为满足用户不同的应用需求而提供的软件,它可以拓宽计算机系统的应用领域,极大地扩展了硬件的功能。常用的应用软件有信息管理软件、辅助设计软件、文字处理软件、图形图像软件、各种程序包等。

【考点2】　计算机硬件系统

计算机硬件系统主要包含中央处理器、主存储器及其他外部设备,它们之间通过总线连接在一起。

1.中央处理器

中央处理器(Central Processing Unit,CPU)是计算机的运算和控制核心,是计算机的“大脑”,其功能主要是解释计算机指令和处理软件中的数据。CPU主要包括运算器和控制器两个部件,它们都包含寄存器,并通过总线连接起来。

(1)运算器负责对数据进行加工处理(对数据进行算术运算和逻辑运算)。

(2)控制器负责对程序所规定的指令进行分析,控制并协调输入、输出操作或对主存储器的访问。

(3)寄存器是高速存储区域,用来暂时存放参与运算的数据和运算结果。寄存器的类型较多,包括指令寄存器、地址寄存器、存储寄存器及累加寄存器。根据CPU中寄存器的数量和每个寄存器的大小(多少位)可以确定CPU的性能和速度。例如,64位的CPU是指CPU中的寄存器是64位的。所以,每个CPU指令可以处理64位的数据。

(4)CPU的主要技术性能指标有字长、主频、运算速度等。

●字长是指CPU一次能处理的二进制数据的位数。在工作频率不变和CPU体系结构相似的前提下,字长越长,CPU的数据处理速度越快。

●主频是指CPU的时钟频率,计算机的操作在时钟信号的控制下分步执行,每个时钟周期完成一步操作。主频越高,CPU的运算速度就越快。

●运算速度通常是指CPU每秒所能执行的加法指令数目,常用百万次/秒(Million Instructions Per Second,MIPS)来表示。这个指标能更直观地反映计算机的速度。

2.存储器

存储器是存储程序和数据的部件,它可以自动完成程序或数据的存取。

(1)存储器的分类。

●按存储介质分类:半导体存储器、磁表面存储器、磁芯存储器、光盘存储器等。

●按存取方式分类:随机存储器(Random Access Memory,RAM)、只读存储器 (Read Only Memory,ROM)、串行访问存储器、直接存取存储器等。

●按在计算机中的作用分类:主存储器(内存)、高速缓冲存储器(cache)、辅助存储器(外存储器,简称外存)等。

(2)主存储器。

存储器中最重要的是主存储器,它一般采用半导体存储器,包括RAM和ROM两种。

①RAM。

RAM具有可读写性,即信息可读、可写,当写入时,原来存储的数据被擦除;具有易失性,即断电后数据会消失,且无法恢复。RAM又分为静态RAM和动态RAM。

●静态RAM(Static RAM,SRAM)的特点是集成度低、价格高、存储速度快、不需要刷新。

●动态RAM(Dynamic RAM,DRAM)的特点是集成度高、价格低、存储速度慢、需要刷新。

DRAM目前被各类计算机广泛使用,内存条采用的就是DRAM。

②ROM。

ROM中信息只能读出不能写入;ROM具有内容“永久”性,断电后信息不会丢失。根据半导体制造工艺的不同,可将其分为可编程只读存储器(Programmable ROM,PROM)、可擦可编程只读存储器(Erasable PROM,EPROM)、电擦除可编程只读存储器(Electrically EPROM,EEPROM)、掩模型只读存储器(Mask ROM,MROM)。

(3)高速缓冲存储器。

高速缓冲存储器是介于CPU和内存之间的一种小容量、可高速存取信息的芯片,可用于解决它们之间速度不匹配的问题。高速缓冲存储器一般由速度高的SRAM元件组成,其速度与CPU相当,但价格较高。

(4)辅助存储器。

辅助存储器的容量一般都比较大,而且大部分可以移动,便于不同计算机之间进行信息交流。辅助存储器中数据被读入内存后,才能被CPU读取,CPU不能直接访问辅助存储器。

存储器主要有3个性能指标:速度、容量及位(bit)价格。一般来说,速度越快,位价格越高;容量越大,位价格越低,而且容量越大,速度越慢。

3.外部设备

(1)外部设备的分类。

计算机中,CPU和内存构成主机。除主机以外,围绕着主机设置的各种硬件装置称为外部设备(外设)。外设的种类很多,应用比较广泛的有输入/输出(Input/Output,I/O)设备、辅助存储器及终端设备。

①输入/输出设备。

●输入设备。输入设备是指向计算机输入数据和信息的设备,用于向计算机输入原始数据和处理数据的程序。常用的输入设备有键盘、鼠标、摄像头、扫描仪、语音输入设备、传感器等。

●输出设备。输出设备的功能是将各种计算结果数据或信息以数字、字符、图像、声音等形式表示出来。常见的输出设备有显示器、打印机、绘图仪、投影仪、音箱等。

●有一些设备同时集成了输入和输出两种功能,如光盘刻录机。

②辅助存储器。

辅助存储器可存放大量的程序和数据,并且断电后程序和数据不会丢失。目前常见的辅助存储器有硬盘、闪存(U盘、SM卡、SD卡、记忆棒、TF卡)等。

③终端设备。

终端设备是指经由通信设施向计算机输入程序和数据或接收计算机输出的处理结果的设备。终端设备分为通用终端设备和专用终端设备两类。通用终端设备泛指具有通信处理、控制功能的通用计算机输入/输出设备。专用终端设备是指具有特殊性能、适用于特定业务范围的终端设备。

(2)硬盘。

硬盘是计算机主要的外部存储设备,具有容量大、存取速度快等优点。

①硬盘的分类。

根据磁头是否可移动,硬盘可以分为固定磁头硬盘和活动磁头硬盘两类。磁头和磁臂是硬盘的重要组成部分,磁头安装在磁臂上,负责读/写各磁道上的数据。

●固定磁头硬盘中,每条磁道对应一个磁头,当工作时,磁头无径向移动。其特点是存取速度快,省去了磁头寻找磁道的时间,但造价比较高。

●活动磁头硬盘中,每个盘面只有一个磁头,在存取数据时,磁头在盘面上进行径向移动。由于增加了“寻道”时间,其存取速度比固定磁头硬盘要慢。目前常用的硬盘都是活动磁头的。

②硬盘的信息分布。

●记录面。硬盘通常由重叠的一组盘片构成,每个盘片的两面都可用作记录面,每个记录面对应一个磁头,所以记录面号就是磁头号。

●磁道。当盘片旋转时,磁头若保持在一个位置上,则每个磁头都会在记录面上划出一个圆形轨迹,这个圆形轨迹就是磁道。一条条磁道形成一组同心圆,最外圈的磁道为0号,往内则磁道号逐步增加。

●圆柱面。在一个硬盘中,各记录面上相同编号的磁道构成一个圆柱面。例如,某硬盘有8片(16面),则16个0号磁道构成0号圆柱面,16个1号磁道构成1号圆柱面……硬盘的圆柱面数就等于一个记录面上的磁道数,圆柱面号就对应磁道号。

●扇区。通常将一个磁道划分为若干弧段,每个弧段称为一个扇区或扇段,扇区从1开始编号。

因此,硬盘寻址的磁盘地址应该由硬盘号(一台计算机可能有多个硬盘)、记录面(磁头)号、圆柱面(磁道)号、扇区号等字段组成。

磁盘存储器的主要性能指标包括存储密度、存储容量、平均存取时间及数据传输率等。

(3)I/O接口。

I/O接口(I/O控制器)用于主机和外设之间的通信,通过接口可实现主机和外设之间的信息交换。

①I/O接口的功能。

●实现主机和外设的通信联络控制。

●进行地址译码和设备选择。

●实现数据缓冲以匹配速度。

●信号格式的转换(如电平转换、并/串或串/并转换、模/数或数/模转换等)。

●传输控制命令和状态信息。

②I/O方式。

I/O方式包括程序查询方式、程序中断方式、直接存储器存取(Direct Memory Access,DMA)方式和I/O通道控制方式等。

●程序查询方式:一旦某外设被选中并启动,主机将查询这个外设的某些状态位,判断其是否准备就绪,若未准备就绪,主机将再次查询;若已准备就绪,则执行一次I/O操作。这种方式控制简单,但系统效率低。

●程序中断方式:在主机启动外设后,无须等待查询,继续执行原来的程序,外设在做好输入/输出准备时,向主机发送中断请求,主机接到请求后就暂时中止原来执行的程序,转去执行中断服务程序并对外部请求进行处理,在中断处理完毕后返回原来的程序继续执行。

●DMA方式:在内存和外设之间开辟直接的数据通道,可以进行基本上不需要CPU介入的内存和外设之间的信息传递。这样不仅保证了CPU的高效率,也能满足高速外设的需要。

●I/O通道控制方式:是DMA方式的进一步发展,系统中设有通道控制部件,每个通道有若干外设。主机执行I/O指令来启动有关通道,通道执行通道程序,完成输入/输出操作。通道是一种独立于CPU的专门管理I/O的处理机制,它控制设备与内存直接进行数据交换。通道有自己的通道指令,通道指令由CPU启动,并在操作结束时向CPU发出中断信号。

4.总线

总线是一组能被多个部件“分时共享”的公共信息传输线路。分时是指同一时刻总线上只能传输一个部件发送的信息;共享是指总线上可以“挂接”多个部件,各个部件之间相互交换的信息都可以通过这组公共线路传输。

(1)总线的分类。

总线按功能层次可以分为3类。

●片内总线:指芯片内部的总线,如在CPU芯片内部寄存器与寄存器之间、寄存器与算术逻辑单元(Arithmetic and Logic Unit,ALU)之间都由片内总线连接。

●系统总线:指计算机系统内各功能部件(CPU、内存、I/O接口)之间相互连接的总线。系统总线按传输的信息不同,又分为数据总线(双向传输)、地址总线(单向传输)及控制总线(部分出、部分入)。

●通信总线:用于计算机设备之间或计算机设备与其他设备(远程通信设备、测试设备)之间信息传输的总线,也称外部总线。依据不同的传输方式,通信总线又分为串行通信总线和并行通信总线。

(2)总线的基本结构。

从系统总线的角度出发,总线的基本结构如下。

●单总线结构:只有一条系统总线,CPU、内存、I/O设备都挂在该总线上,允许I/O设备之间、I/O设备与CPU之间或I/O设备与内存之间直接交换信息。

●双总线结构:将低速I/O设备从单总线上分离出来,实现内存总线与I/O总线分离。

●三总线结构:各部件之间采用3条各自独立的总线来构成信息通道。内存总线用于在CPU和内存之间传输地址、数据及控制信息;I/O总线用于在CPU和外设之间通信;直接内存访问总线用于在内存和高速外设之间直接传输数据。

(3)总线的性能指标。

●总线周期:一次总线操作(包括申请阶段、寻址阶段、传输阶段及结束阶段)所需的时间简称总线周期。总线周期通常由若干总线时钟周期构成。

●总线时钟周期:即计算机的时钟周期。

●总线的工作频率:总线上各种操作的频率,为总线周期的倒数。若总线周期=N×时钟周期,则总线的工作频率=时钟频率/N。

●总线宽度:通常指数据总线的根数,用位表示,如数据总线有32根则称该总线为32位总线。

●总线带宽:可理解为总线的数据传输率,即单位时间总线上传输数据的位数,通常用每秒传输信息的字节数来衡量,单位可用MB/s(兆字节每秒)表示。例如,总线工作频率为33MHz,总线宽度为32位(4B),则总线带宽为33×(32÷8)=132(MB/s)。

●时钟同步/异步:数据与时钟同步工作的总线称为同步总线,数据与时钟不同步工作的总线称为异步总线。

●总线复用:一种总线在不同的时间传输不同的信息。

●信号线数:地址总线、数据总线及控制总线3种总线数的总和。

(4)总线仲裁。

为了保证同一时刻只有一个申请者使用总线,总线控制机构中设有总线判优和仲裁控制逻辑,即按照一定的优先次序来决定哪个部件首先使用总线,只有获得总线使用权的部件才能开始数据传输。总线判优按照仲裁控制机构的设置可分为两种。

●集中式控制:仲裁控制逻辑基本上集中于一个设备(如CPU)中。将所有的总线请求集中起来,利用一个特定的裁决算法进行裁决。

●分布式控制:不需要中央仲裁器,仲裁控制逻辑分散在连接于总线上的各个部件或设备中。

(5)总线操作。

在总线上的操作主要有读和写、块传输、写后读或读后写、广播和广集等。

(6)总线标准。

总线标准是国际上公布或推荐的连接各个模块的标准,是把各种不同的模块组成计算机系统时必须遵守的规范。

常见的系统总线标准有工业标准结构(Industry Standard Architecture,ISA)、扩展的ISA(Extended Industry Standard Architecture,EISA)、视频电子标准协会(Video Electronics Standards Association,VESA)、外设部件互连(Peripheral Component Interconnect,PCI)及加速图形接口(Accelerated Graphics Port,AGP)等。

常见的外部总线标准有集成设备电路(Integrated Drive Electronics,IDE)、小型计算机系统接口(Small Computer System Interface,SCSI)、美国电子工业协会推行的串行通信总线标准(Recommended Standard-232C,RS-232C)和通用串行总线(Universal Serial Bus,USB)等。

5.计算机的工作原理

计算机在执行程序前须将要执行的相关程序和数据先放入内存中,在执行时CPU根据当前程序指针寄存器的内容取出指令并执行,然后取出下一条指令并执行,如此循环直到程序结束时才停止执行。其工作过程就是不断地取指令和执行指令,最后将计算的结果放入指令指定的存储器地址中。

(1)计算机指令格式。

指令是指计算机完成某个基本操作的命令。指令能被计算机硬件理解并执行。一条计算机指令是用一串二进制代码表示的,它通常包括两方面的信息:操作码和操作数(地址码),如图2.2所示。

图2.2 计算机指令

操作码指明指令所要完成操作的性质和功能,即指出进行什么操作。操作码也是二进制代码。对同一种类型的计算机来说,各种指令的操作码互不相同,分别表示不同的操作。因此,指令中操作码的二进制位数决定了该类型计算机最多能具有的指令条数。

操作数指明操作码执行的操作对象。操作数可以是数据本身,也可以是存放数据的内存单元地址或寄存器名称。根据指令中操作数的性质,操作数又可以分为源操作数和目的操作数两类。例如,减法指令中减数和被减数为源操作数,它们的差为目的操作数。

如果指令中的操作码和操作数共占n字节,则称该指令为n字节指令。

(2)计算机指令的寻址方式

寻址方式是指找到当前正在执行指令的数据地址和下一条将要执行指令的地址的方法。

寻址方式被分为两大类:找到下一条将要执行指令的地址,称为指令寻址;找到当前正在执行指令的数据地址,称为数据寻址。

指令寻址分为顺序寻址和跳跃寻址两种。常见的数据寻址有立即寻址、直接寻址、隐含寻址、间接寻址、寄存器寻址、寄存器间接寻址、基址寻址、变址寻址、相对寻址及堆栈寻址等。

(3)计算机指令系统。

一台计算机所能执行的全部指令的集合,称为该计算机的指令系统。不同类型的计算机的指令系统的指令数目与格式也不同。但无论哪种类型的计算机,指令系统都应该具有以下功能指令。

●数据传输类指令:用来实现数据在内存和CPU之间的传输。

●运算类指令:用来进行数据的运算。

●程序控制类指令:用来控制程序中指令的执行顺序。

●输入/输出指令:用来实现外设与主机之间的数据传输。

●处理器控制和调试指令:用来实现计算机的硬件管理等。

(4)指令的执行过程。

指令的执行过程可分为取指令、分析指令和执行指令3个步骤。

●取指令:按照程序规定的次序,从内存取出当前执行的指令,并送到控制器的指令寄存器中。

●分析指令:对所取的指令进行分析,即根据指令中的操作码确定计算机应进行什么操作。由指令中的地址码确定操作码存放的地址。

●执行指令:根据指令分析结果,由控制器发出完成操作所需的一系列控制电位,以便指挥计算机有关部件完成这一操作。同时,为取下一条指令做好准备。

一般把计算机完成一条指令所花费的时间称为一个指令周期。指令周期越短,指令执行就越快。

【考点3】　数据的内部表示

1.计算机中的数据及其存储单位

(1)计算机中的数据。

计算机内部均使用二进制数表示各种信息,但计算机在与外部沟通中会采用人们比较熟悉和方便阅读的形式,如十进制数。其间的转换,主要由计算机系统的硬件和软件来实现。

二进制只有“0”和“1”两个数。相对十进制而言,二进制不但运算简单、易于物理实现、通用性强,而且所占的空间和所消耗的资源也少得多,可靠性较高。

(2)计算机中数据的存储单位。

位(bit)是计算机中数据的最小单位,二进制的数码只有0和1,计算机中采用多个数码表示一个数,每一个数码称为1位。

字节(Byte,B)是存储容量的基本单位,一个字节由8位二进制位组成。在计算机内部,一个字节可以表示一个数字,也可以表示一个英文的字母或其他特殊字符,两个字节可以表示一个汉字。为了便于衡量存储器的大小,统一以字节为单位。表2.1所示为常用的存储单位。

表2.1 常用的存储单位

随着电子技术的发展,计算机的并行处理能力越来越强,人们通常将计算机一次能够并行处理的二进制位的个数称为字长,也称为计算机的一个“字”。字长是计算机的一个重要指标,直接反映一台计算机的计算能力和精度,即字长越长,计算机的数据处理速度越快。计算机的字长通常是字节的整数倍,如8位、16位、32位。发展到今天,微型机的字长已达到64位,大型机的字长已达到128位。

2.进位记数制及其转换

(1)进位记数制。

数的表示规则称为数制。如果用R表示任意整数,进位记数制为“逢R进一”。处于不同位置的数码代表的值不同,与它所在位置的权值有关。任意一个R进制数D均可展开为

(D)R=ki×Ri

此时,R为记数的基数,数制中固定的基本符号称为“数码”。i称为位数,ki是第i位的数码,为0~R-1中的任意整数,Ri称为第i位的权,m、n为最低位和最高位的位序号。例如,十进制数“5820”,基数R为10,数码“8”的位数i=2(位数从0开始计),权值为Ri=102,此时“8”的值代表:ki×Ri=8×102=800。

常用数制包括二进制、八进制、十进制、十六进制,其中的各个要素如表2.2所示。

表2.2 常用数制的各个要素

通常用圆括号加数制基数作为下标的方式来表示不同的进制数,如二进制数(1100)B、八进制数(3567)O、十进制数(5820)D,也可直接表示为(1100)2、(3567)8、(5820)10。

十六进制数除了数码0~9之外,还使用了6个英文字母A、B、C、D、E、F,相当于十进制的10、11、12、13、14、15。十进制数、二进制数、八进制数、十六进制数的对照如表2.3所示。

表2.3 不同进制数的对照

(2)R进制数转换为十进制数。

R进制数转换为十进制数的方法是“按权展开”。如下。

二进制数转换为十进制数:(11010)2=1×24+1×23+0×22+1×21+0×20=(26)10。

八进制数转换为十进制数:(140)8=1×82+4×81+0×80=(96)10。

十六进制数转换为十进制数:(A2B)16=10×162+2×161+11×160=(2603)10。

(3)十进制数转换为R进制数。

将十进制数转换为R进制数时,可将此数分成整数与小数两部分分别转换,然后拼接起来。下面以十进制数转换为二进制数为例进行介绍。

十进制整数转换为二进制整数的方法是“除以2取余法”,具体步骤如下。

步骤1:把十进制数除以2得到商和余数,商再除以2又得到商和余数……依次除下去直到商是0为止。

步骤2:以最先除得的余数为最低位,最后除得的余数为最高位,从最高位到最低位依次排列。

将十进制整数13转换为二进制整数,步骤如表2.4所示。

表2.4 将十进制整数转换为二进制整数步骤

十进制小数转换为二进制小数采用“乘2取整法”,具体步骤如下。

步骤1:把小数部分乘以2得到一个新数,然后取整数部分,剩下的小数部分继续乘以2,然后取整数部分,剩下的小数部分再乘以2,一直取到小数部分为0为止。

步骤2:以最先乘得的乘积整数部分为最高位,最后乘得的乘积整数部分为最低位,从高位向低位依次排列。

将十进制小数0.125转换为二进制小数,步骤如表2.5所示。

表2.5 将十进制小数转换为二进制小数步骤

将十进制数转换为八进制数、十六进制数,均可以采用类似的“除以8取余”“除以16取余”“乘8取整”“乘16取整”的方法来实现转换。

(4)二进制数、十六进制数、八进制数之间的转换。

①二进制数转换为十六进制数。

将二进制数转换为十六进制数的步骤如下。

步骤1:二进制数从小数点开始,整数部分向左、小数部分向右,每4位分成1节。

步骤2:整数部分最高位不足4位或小数部分最低位不足4位时补“0”。

步骤3:将每节4位二进制数依次转换成1位十六进制数,再把这些十六进制数连接起来即可。

将二进制数(10111100101.00011001101)2转换为十六进制数,如表2.6所示。

表2.6 将二进制数转换为十六进制数

同理,将二进制数转换为八进制数,只要将二进制数按每3位为1节划分,并分别转换为1位八进制数即可。

②十六进制数转换为二进制数。

将十六进制数转换为二进制数,就是对每1位十六进制数,用与其等值的4位二进制数代替。将十六进制数(1AC0.6D)16转换为二进制数,如表2.7所示。

表2.7 将十六进制数转换为二进制数

同理,将八进制数转换为二进制数,只需分别将每1位八进制数转换为3位二进制数即可。

3.无符号数和带符号数

在计算机中,采用数字化方式来表示数据,数据有无符号数和带符号数之分。

(1)无符号数。

无符号数是指整个计算机字长的全部二进制位均表示数值位(没有符号位),相当于数的绝对值。字长为n的无符号数的表示范围为0~2n-1。若计算机字长为8位,则无符号数的表示范围为0~28-1,即0~255。

(2)带符号数。

日常生活中,把带有“+”或“-”符号的数称为真值。在计算机中,数的“+”“-”是无法识别的,因此需要把符号数字化。通常,约定二进制数的最高位为符号位,0表示正号,1表示负号。这种把符号数字化的数称为机器数。常见的机器数有原码、反码、补码及移码等不同的表示形式。

●原码。原码是机器数中最简单的一种表示形式,符号位为0表示正数,符号位为1表示负数,数值位即真值的绝对值。用原码实现乘除运算的规则很简单,但实现加减运算的规则很复杂。

●反码。正数的反码与原码相同;负数的反码是对该数的原码除符号位外的各位取反(将0变为1,将1变为0)。

●补码。正数的补码与原码相同;负数的补码是在该数的反码的最低位(最右边一位)加1。

●移码。一个真值的移码和补码只差一个符号位,若将补码的符号位由0改为1,或由1改为0,即可得该真值的移码。

4.机器数的定点表示和浮点表示

根据小数点的位置是否固定,在计算机中有两种方法表示小数点,即定点表示和浮点表示。定点表示的机器数称为定点数,浮点表示的机器数称为浮点数。

(1)定点表示。

定点表示,即约定机器数中的小数点位置是固定不变的,小数点不再使用“.”表示,而是约定它的位置。在计算机中通常采用两种简单的约定:将小数点的位置固定在最高位之前、符号位之后,或固定在最低位之后。一般常称前者为定点小数(纯小数),后者为定点整数(纯整数)。

除了加、减、乘、除外,定点数的运算还有移位运算。根据操作对象的不同,移位运算分为算术移位(带符号数的移位)和逻辑移位(无符号数的移位)。

(2)浮点表示。

计算机中处理的数不一定是纯小数或纯整数(如圆周率约为3.1416),而且在运算中常常会遇到非常大(如太阳的质量约2×1033g)或非常小(如电子的质量9×10-28g)的数值,用定点表示它们非常不方便,但可以用浮点表示。

浮点数是指小数点位置可浮动的数据。例如,679.32=6.7932×102=6793.2×10-1=0.67932×103。

通常,浮点数被表示成

N=S×Rj

其中,N为浮点数,S为其尾数,j为其阶码,R为其阶码的底(隐含,在机器数中不出现)。通常R=2,j和S都是带符号的定点数。可见,浮点数由阶码和尾数两部分组成,如图2.3所示。

图2.3 浮点数的表示形式

阶码是整数,阶符jf和阶码的位数m共同反映浮点数的表示范围和小数点的实际位置;数符Sf反映浮点数的正/负;尾数的位数n反映浮点数的精度。

为了提高运算的精度,浮点数的尾数必须为规格化数(即尾数的最高位必须是一个有效值)。如果不是规格化数,需要修改阶码并左/右移尾数,使其变成规格化数。将非规格化数转化成规格化数的过程称为规格化操作。例如,二进制数0.0001101可以表示为0.001101×2-01、0.01101×2-10、0.1101×2-11……而其中只有0.1101×2-11是规格化数。

现代计算机中,浮点数一般采用IEEE 754标准。IEEE 754标准浮点数的格式如图2.4所示。

图2.4 IEEE 754标准浮点数的格式

这种标准规定常用的浮点数格式有短浮点数(单精度、float型)、长浮点数(双精度、double型)、临时浮点数,如表2.8所示。除临时浮点数外,短浮点数和长浮点数的尾数用隐藏位的原码表示,阶码用移码表示。

表2.8 IEEE 754标准规定常用的浮点数格式

以短浮点数为例,最高位为数符位;其后是8位阶码,以2为底,用移码表示,阶码的偏置值为28-1-1=127;其后23位是原码表示的尾数数值位。对于规格化的二进制浮点数,数值的最高位总是“1”,为了能使尾数多表示一位有效位,将这个“1”隐藏,因此尾数数值实际是24位。隐藏的“1”是一位整数。在浮点数格式中表示的23位尾数是纯小数。例如,(12)10=(1100)2,将它规格化后结果为1.1×23,其中整数部分的1将不存储在23位尾数内。

【考点4】　操作系统

1.操作系统概述

(1)操作系统的功能与任务。

操作系统是现代计算机中最基本和最核心的系统软件之一,所有其他的软件都依赖于操作系统的支持。

操作系统是配置在计算机硬件上的第1层软件,是对硬件系统的首次扩充。其主要作用是管理好硬件设备,提高它们的利用率和系统的吞吐量,并为用户和应用程序提供一个简单的接口,便于用户使用。

如果把操作系统看成计算机系统资源的管理者,则操作系统的任务及其功能主要有以下5个方面。

●处理器(CPU)管理:对进程进行管理。其主要功能有创建和撤销进程,对多个进程的运行进行协调,实现进程之间的信息交换,以及按照一定的算法把处理器分配给进程。

●存储器管理:为多道程序的运行提供良好的环境,提高存储器的利用率,方便用户使用,并能从逻辑上扩充内存。因此,存储器管理应具有内存分配和回收、内存保护、地址映射和内存扩充等功能。

●设备管理:完成用户进程提出的I/O请求,为用户进程分配所需的I/O设备,并完成指定的I/O操作;提高CPU和I/O设备的利用率,提高I/O速度,方便用户使用I/O设备。因此,设备管理应具有缓冲管理、设备分配、设备处理以及虚拟设备等功能。

●文件管理:对用户文件和系统文件进行管理以方便用户使用,并保证文件的安全性。因此,文件管理应具有对文件存储空间的管理、目录管理、文件的读/写管理以及文件的共享与保护等功能。

●提供用户接口:为了方便用户使用计算机和操作系统,操作系统向用户提供了“用户和操作系统的接口”。

(2)操作系统的发展。

操作系统经历了如下的发展过程:手工操作(无操作系统)、批处理系统、多道程序系统、分时系统、实时操作系统、个人计算机操作系统。

(3)操作系统的分类。

根据使用环境和对作业处理方式的不同,操作系统分为多道批处理操作系统、分时操作系统、实时操作系统、网络操作系统、分布式操作系统、嵌入式操作系统等。

2.进程管理

(1)程序的并发执行。

程序只有经过执行才能得到结果。程序的执行又分为顺序执行和并发执行。

一个具有独立功能的程序独占处理器直至执行结束的过程称为程序的顺序执行。顺序执行具有顺序性、封闭性及可再现性等特点。

程序顺序执行时,虽然可以给程序员带来方便,但系统资源的利用率很低。为此,在系统中引入了多道程序技术,使程序或程序段间能并发执行。程序的并发执行是指一组在逻辑上互相独立的程序或程序段在执行过程中,其执行时间在客观上互相重叠,即一个程序段的执行尚未结束,另一个程序段的执行已经开始的执行方式。

并发程序在执行过程中有以下几个特点。

●失去了封闭性。

●不可再现性。

●间断性,即程序之间可以互相制约。

并发程序具有并行性和共享性,而顺序程序则以顺序性和封闭性为基本特征。

(2)进程的基本概念。

进程是指一个具有一定独立功能的程序关于某个数据集合的一次运行活动。简单地说,进程是指可以并发执行的程序的执行过程。

进程与程序有关,但它与程序又有本质的区别,主要反映在以下几个方面。

●进程是程序在处理器上的一次执行过程,它是动态的概念。程序只是一组指令的有序集合,其本身没有任何运行的含义,它是一个静态的概念。

●进程具有一定的生命周期,它能够动态地产生和消亡。程序可以作为一种软件资源长期保存,它的存在是“永久”的。

●进程包括程序和数据。进程还包括记录进程相关信息的“进程控制块”。

●一个程序可能对应多个进程。

●一个进程可以包含多个程序。

(3)进程的状态及其转换。

进程从创建、产生、撤销至消亡的整个生命周期,有时占有处理器并运行,有时虽可运行但不占有处理器,有时虽有空闲处理器但因等待某个事件发生而无法运行,这说明进程是活动的且有状态变化。一般来说,一个进程的活动情况至少可以划分为以下5种基本状态。

●创建状态:进程正在创建过程中、尚不能运行的状态。

●就绪状态:进程具备运行条件、等待系统分配处理器以便运行的状态。

●运行状态:进程占有处理器、正在运行的状态。

●等待状态:又称阻塞状态或睡眠状态,指进程不具备运行条件,正在等待某个事件完成的状态。

●终止状态:进程运行结束的状态。

处于运行状态的进程个数不能大于处理器个数,处于就绪和等待状态的进程可以有多个。进程的几种基本状态之间在一定的条件下是可以互相转换的。图2.5表示了进程的5种基本状态之间在一定条件下的转换。

图2.5 进程的5种基本状态及转换

(4)进程控制块。

每个进程有且仅有一个进程控制块(Process Control Block,PCB)。它是进程存在的唯一标识,是操作系统用来记录和刻画进程状态和环境信息的数据结构,是进程动态特征的汇集,也是操作系统掌握进程的唯一资料结构和管理进程的主要依据。PCB包括进程运行时的状态,以及进程让出处理器之后所处的状态、断点等信息。

PCB中通常应包括以下基本内容。

●进程名:唯一标识,对应进程的一个标识符或数字,系统根据该标识符来识别一个进程。

●特征信息:反映该进程是不是系统进程等信息。

●执行状态信息:反映对应进程当前的状态。

●通信信息:反映该进程与其他进程之间的通信关系。

●调度优先数:用于分配处理器时参考的一种信息。它决定在所有就绪的进程中哪一个进程先得到处理器。

●现场信息:在对应进程放弃处理器时,将处理器的一些现场信息(如指令计数器值、各寄存器值等)保留在该进程的PCB中,当下次恢复运行时,只要按保存值重新装配即可继续运行。

●系统栈:主要反映对应进程在运行时的一条嵌套调用路径上的历史。

●进程映像信息:用于说明该进程的程序和数据存储情况。

●资源占有信息:指明对应进程所占有的外设种类、设备号等。

●族关系:反映该进程与其他进程间的隶属关系。

除此之外,PCB中还包含文件信息、工作单元等内容。

(5)进程的组织。

进程的物理组织方式通常有线性方式、链接方式及索引方式。

●线性方式:先将系统中所有的PCB都组织在一张线性表中,再将该表的首地址存放在内存的一个专用区域中。该方式实现简单、开销小,但每次查找时都需要扫描整张表,因此适合进程数目不多的系统。

●链接方式:把具有相同状态进程的PCB分别通过PCB中的链接字链接成一个队列,这样可以形成一个就绪队列、若干个阻塞队列及空白队列等。在就绪队列中,往往按进程的优先级将PCB从高到低进行排列,将优先级高的进程的PCB排在队列的前面。

●索引方式:系统根据所有进程不同的状态,建立几张索引表等,如就绪索引表、阻塞索引表等,并把各索引表在内存的首地址记录在内存的一些专用单元中。在每张索引表的表目中,记录具有相应状态的某个PCB在表中的地址。

(6)进程调度。

进程调度是指按一定策略动态地把CPU分配给处于就绪队列中的某一进程并使之运行的过程。进程调度亦可称为处理器调度或低级调度,相应的进程调度程序可称为分配程序或低级调度程序。进程调度仅负责对CPU进行分配。

进程调度方式有抢占方式和非抢占方式。抢占方式指就绪队列中一旦有优先级高于当前正在运行的进程出现时,系统便立即把CPU分配给高优先级的进程,并保存被抢占了CPU的进程的有关状态信息,以便以后恢复。而对于非抢占方式,一旦CPU分给了某进程,即使就绪队列中出现了优先级比它高的进程,高优先级进程也不能抢占当前正在运行进程的CPU。

基本的进程调度算法有先来先服务调度算法、时间片轮转调度算法、优先级调度算法等。

(7)其他概念。

●线程。线程是比进程更小的能独立运行的基本单位,用它来提高程序的并行程度,减少系统开销,从而可进一步提高系统的吞吐量。

●死锁。由于各进程互相独立地动态获得,并不断申请和释放系统中的软硬件资源,这就有可能使系统中若干个进程均因互相“无知地”等待对方所占有的资源而无限地等待,这种状态称为死锁。

3.存储管理

存储管理是操作系统的重要组成部分,管理的主要对象是内存。操作系统的主要任务之一是尽可能方便用户使用和提高内存利用率。此外,有效的存储管理也是多道程序设计技术的关键支撑。

(1)存储管理的功能。

●地址变换。

●内存分配。

●存储共享与保护。

●存储器扩充。

(2)地址重定位。

地址变换:当用户程序进入内存执行时,必须把用户程序中的所有相对地址(逻辑地址)转换成内存中的实际地址(物理地址)。

地址重定位:在进行地址转换时,必须修改程序中所有与地址有关的项,也就是要对程序中的指令地址和指令中有关地址的部分(有效地址)进行调整。

地址重定位建立用户程序的逻辑地址与物理地址之间的对应关系,实现方式包括静态地址重定位和动态地址重定位。

●静态地址重定位是在程序执行之前由操作系统的重定位将其装入内存来完成的,程序必须占用连续的内存空间,且一旦装入内存后,程序不便于移动。

●动态地址重定位则在程序执行期间进行,由专门的硬件机构来完成,通常采用一个重定位寄存器,在每次进行存储访问时,将取出的逻辑地址加上重定位寄存器的内容形成物理地址。

动态地址重定位的优点是不要求程序装入固定的内存空间,在内存中允许程序再次移动位置,而且可以部分地装入程序运行,同时也便于多个作业共享同一程序的副本。动态地址重定位技术被广泛采用。

(3)存储管理技术。

①连续存储管理。

基本特点:内存空间被划分成一个个分区,一个作业占一个分区,即系统和用户作业都以分区为单位享用内存。

在连续存储管理中,地址重定位采用静态地址重定位,分区的存储保护可采用上、下界寄存器保护方式。

分区分配方式分为固定分区和可变分区。固定分区存储管理的优点是简单,要求的硬件支持少;缺点是容易产生内部碎片。可变分区避免了固定分区中每个分区都可能有剩余空间的情况,但由于它的空闲区域仍是离散的,因此会出现外部碎片。

②分页式存储管理。

在分页式存储管理中,当作业提出存储分配请求时,系统首先根据存储块大小把作业分成若干页,每一页可存储在内存的任意一个空白块内。这样,只要建立程序的逻辑页和内存的存储块之间的对应关系,借助动态地址重定位技术,分散在不连续物理存储块中的用户作业就能够正常运行。

分页式存储管理的优点是能有效解决碎片问题,内存利用率高,内存分配与回收算法也比较简单;缺点是采用动态地址变换机构增加了硬件成本,也降低了处理器的运行速度。

③分段式存储管理。

在分段式存储管理中,作业的逻辑地址空间由若干个逻辑段组成,每一段是一组逻辑意义完整的信息集合,并有自己的名字(段名)。每一段都是以0开始的、连续的一维地址空间,整个作业则构成了二维地址空间。

分段式存储管理是以段为基本单位来分配内存的,且每一段必须分配连续的内存空间,但各段之间不要求连续。由于各段的长度不一样,因此分配的内存空间大小也不一样。

分段式存储管理较好地解决了程序和数据的共享以及程序动态链接等问题。与分页式存储管理一样,分段式存储管理采用动态地址重定位技术来进行地址转换。分页式存储管理的优点体现在内存空间的管理上,而分段式存储管理的优点体现在地址空间的管理上。

④段页式存储管理。

段页式存储管理是分页和分段两种存储管理方式的结合,它同时具备两者的优点。

段页式存储管理是目前使用较多的一种存储管理方式,它有如下特点。

●将作业的逻辑地址空间分成若干个逻辑段,每段都有自己的段名。

●每段再分成若干大小固定的页,每段都从0开始为自己的各页依次编写连续的页号。

●对内存空间的管理仍然和分页式存储管理一样,将其分成若干个与页面大小相同的物理块,对内存空间的分配是以物理块为单位的。

●作业的逻辑地址包括3个部分:段号、段内页号及页内位移。

⑤虚拟存储器管理。

连续存储管理和分页/分段式存储管理技术必须为作业分配足够的内存空间,可装入其全部信息,否则作业将无法运行。把作业的全部信息装入内存后,实际上并非同时使用这些信息,有些部分运行一次,有些部分暂时不用或在某种条件下才使用。让作业全部信息驻留于内存是对内存资源的极大浪费,会降低内存利用率。

虚拟存储器管理技术的基本思路是把内存扩大到大容量外存上,把外存空间当作内存的一部分,作业运行过程中可以只让当前用到的信息进入内存,其他当前未用的信息留在外存;而当作业进一步运行,需要用到外存中的信息时,再把已经用过但暂时还不会用到的信息换到外存,把当前要用的信息换到已空出的内存中,从而给用户提供一个比实际内存空间大得多的地址空间。这种大容量的地址空间并不是真实的存储空间,而是虚拟的,因此,这样的存储器称为虚拟存储器。

虚拟存储器管理主要采用请求分页式存储管理、请求分段式存储管理及请求段页式存储管理技术实现。

4.文件管理

在操作系统中,无论是用户数据,还是计算机系统程序和应用程序,甚至各种外设,都是以文件形式提供给用户的。文件管理就是对用户文件和系统文件进行管理,以方便用户使用,并保证文件的安全性,提高外存空间的利用率。

(1)文件与文件系统的概念。

文件是指一组带标识(文件名)的、具有完整逻辑意义的相关信息的集合。用户作业、源程序、目标程序、初始数据、输出结果、汇编程序、编译程序、连接装配程序、编辑程序、调试程序和诊断程序等,都是以文件的形式存在的。

各种操作系统的文件命名规则略有不同,文件名的格式和长度也因系统而异。一般来说,文件名由文件名和扩展名两部分组成,前者用于识别文件,后者用于区分文件类型,中间用“.”分隔开。

操作系统中与管理文件有关的软件和数据的集合称为文件系统。它负责为用户建立、撤销、读/写、修改及复制文件,还负责完成对文件的按名存取和存取控制。常用的、具有代表性的文件系统有EXT2/4、NFS、HPFS、FAT、NTFS等。

(2)文件类型。

文件依据不同标准可以有多种类型,具体如表2.9所示。

表2.9 文件类型

(3)文件系统模型。

文件系统的传统模型为层次模型,该模型由许多不同的层组成。每一层都会使用下一层的功能特性来创建新的功能,为上一层服务。层次模型比较适合支持单个文件系统。

(4)文件的组织结构。

①文件的逻辑结构。

文件的逻辑结构是用户可见的结构。根据有无逻辑结构,文件可分为记录式文件和流式文件。

在记录式文件中,每个记录都用于描述实体集中的一个实体,各个记录有着相同或不同数目的数据项。记录的长度可分为定长和不定长两类。

流式文件内的数据不再组成记录,只是一串有顺序的信息集合(有序字符流)。这种文件的长度以字节为单位。可以把流式文件看作记录式文件的一个特例:一个记录仅有一个字节。

②文件的物理结构。

文件按不同的组织方式在外部存储介质上存放,就会得到不同的物理结构。文件的物理结构有时也称为文件的“存储结构”。

文件在外存上有连续存放、链接块存放及索引表存放这3种不同的存放方式,其对应的存储结构分别为顺序结构、链接结构及索引结构。

(5)文件目录管理。

①文件目录的概念。

为了能对一个文件进行正确的存取,必须为文件设置用于描述和控制文件的数据结构,称为文件控制块(File Control Block,FCB)。FCB一般应包括以下内容。

●有关文件存取控制的信息:文件名、用户名、文件主存取权限、授权者存取权限、文件类型及文件属性等。

●有关文件结构的信息:记录类型、记录个数、记录长度、文件所在设备名及文件的物理结构类型等。

●有关文件使用的信息:已打开文件的进程数、文件被修改的情况、文件最大长度及文件当前大小等。

●有关文件管理的信息:文件建立日期、最近修改日期及最后访问日期等。

文件与FCB一一对应,而人们把多个FCB的有序集合称为文件目录,即一个FCB就是一个文件目录项。通常,一个文件目录也被看作一个文件,可称为目录文件。

对文件目录的管理就是对FCB的管理。除了要解决存储空间的有效利用问题外,对文件目录的管理还要解决快速搜索、文件命名冲突以及文件共享等问题。

②文件目录的结构。

文件目录根据不同结构可分为单级目录、二级目录、多层级目录、无环图结构目录及图状结构目录等。

●单级目录的优点是简单,缺点是查找速度慢,不允许重名,不便于实现文件共享。

●二级目录提高了检索目录的速度;在不同的用户目录中,可以使用相同的文件名;不同用户还可以使用不同的文件名访问系统中的同一个共享文件。但对同一用户目录,也不能有两个同名的文件存在。

●多层级目录也叫树结构目录,既可以方便用户查找文件,又可以把不同类型和不同用途的文件分类;允许文件重名,不但不同用户目录可以使用相同名称的文件,同一用户目录也可以使用相同名称的文件;利用多级层次结构关系,可以更方便地设置文件的存取权限,有利于文件的保护。其缺点为不能直接支持文件或目录的共享等。

●为了使文件或目录可以被不同的目录所共享,出现了结构更复杂的无环图结构目录和图状结构目录等。

③存取权限。

存取权限可以通过建立访问控制表和存取权限表来实现。

大型文件系统主要采用两个措施来进行安全性保护:一是对文件和目录进行权限设置,二是对文件和目录进行加密。

(6)文件存储空间管理。

文件存储空间管理是文件系统的重要任务之一。文件存储空间管理实质上是空闲块管理问题,它包括空闲块的组织、空闲块的分配及空闲块的回收等问题。

空闲块管理方法主要有空闲文件项、空闲区表、空闲块链、位示图、空闲块成组链接法(UNIX操作系统中)等。

5.I/O设备管理

I/O设备类型繁多,差异又非常大,因此I/O设备管理是操作系统中最庞杂和琐碎的部分之一。

(1)I/O软件的层次结构。

I/O软件的设计目标是将I/O软件组织成一种层次结构,每一次都是利用其下层提供的服务,完成输入/输出功能中的某些子功能,并屏蔽这些功能实现的细节,向上层提供服务。

通常把I/O软件组织成4个层次,如图2.6所示,图中的箭头表示I/O的控制流。各层次功能如下。

图2.6 I/O软件的层次结构

●用户层软件:用于实现与用户交互的接口,用户可直接调用该层提供的、与I/O操作有关的库函数对设备进行操作。

●设备独立性软件:用于实现用户程序与设备驱动器的统一接口、设备命名、设备的保护以及设备的分配与释放等,同时为设备管理和数据传送提供必要的存储空间。

●设备驱动程序:与硬件直接相关,用于具体实现系统对设备发出的操作指令,是驱动I/O设备工作。

●中断处理程序。用于保持被中断进程的CPU环境,转入相应的中断处理程序进行处理,处理完毕再恢复被中断进程的现场,并返回到被中断进程。

(2)中断处理程序。

当一个进程请求I/O操作时,该进程将被“挂起”,直到I/O设备完成I/O操作后,设备控制器便向CPU发送一个中断请求,CPU响应后便转向中断处理程序。中断处理过程如下。

●CPU检查响应中断的条件是否满足。

●如果条件满足,CPU响应中断,则CPU关中断,使其进入不可再次响应中断的状态。

●保存被中断进程的CPU环境。

●分析中断原因,调用中断处理子程序。

●执行中断处理子程序。

●退出中断,恢复被中断进程的CPU现场或调度新进程占用CPU。

●开中断,CPU继续执行。

I/O操作完成后,驱动程序必须检查本次I/O操作中是否发生了错误,并向上层软件报告,最终向调用者报告本次I/O的执行情况。

(3)设备驱动程序。

设备驱动程序是驱动物理设备和DMA控制器或I/O控制器等直接进行I/O操作的子程序的集合。它负责启动I/O设备进行I/O操作,指定操作的类型和数据流向等。设备驱动程序有如下功能。

●接收由设备独立性软件发来的命令和参数,并将命令中的抽象要求转换为与设备相关的低层次操作序列。

●检查用户I/O请求的合法性,了解I/O设备的工作状态,传递与I/O设备操作有关的参数,设置设备的工作方式。

●发出I/O命令,如果设备空闲,便立即启动I/O设备,完成指定的I/O操作;如果设备忙碌,则将请求者的请求块挂在设备队列上等待。

●及时响应由设备控制器发来的中断请求,并根据其中断类型,调用相应的中断处理程序进行处理。

(4)设备独立性软件。

为了实现设备独立性,必须在设备驱动程序上设置一层软件,该软件称为与设备无关的I/O软件,或设备独立性软件。其主要功能:①向用户层软件提供统一接口;②设备命名;③设备保护;④提供一个独立于设备的块尺寸;⑤缓冲技术;⑥设备分配和状态跟踪;⑦错误处理和报告等。

(5)用户层软件。

用户层软件在层次结构的最上层,它面向用户,负责与用户和设备无关的I/O软件通信。当接收到用户的I/O指令后,该层会把具体的请求发送到与设备无关的I/O软件进一步处理。它主要包含用于I/O操作的库函数和Spooling系统。此外,用户层软件还会用到缓冲技术。

(6)设备的分配与回收。

由于设备、控制器及通道资源的有限性,因此不是每一个进程都能随时随地得到这些资源。进程必须首先向设备管理程序提出资源申请,然后由设备分配程序根据相应的分配算法为进程分配资源。如果进程得不到它所申请的资源,将被放入资源等待队列中等待,直到所需要的资源被释放。如果进程得到了它所需要的资源,就可以使用该资源完成相关的操作,使用完之后通知系统,系统将及时回收这些资源,以便其他进程使用。

2.1.2 数据结构与算法

【考点1】　什么是算法

1.算法及其基本特征

算法是指对解题方案准确而完整的描述。简单地说,算法就是解决问题的操作步骤。

算法不等于数学上的计算方法,也不等于程序。程序可以描述算法。

算法的基本特征如下。

(1)可行性:步骤可以实现,执行结果达到预期目的。

(2)确定性:步骤明确,不模棱两可,不准有多义性。

(3)有穷性:有限的时间内完成。

(4)拥有足够的情报:当拥有足够的输入信息和初始化信息时,算法才是有效的;当提供的情报不够时,算法可能无效。

2.算法复杂度

算法复杂度用来衡量算法的优劣,它包括算法的时间复杂度和算法的空间复杂度。

(1)算法的时间复杂度。

算法的时间复杂度是指执行算法所需要的计算工作量。

算法的时间复杂度不等于算法程序执行的具体时间。算法程序执行的具体时间受到所使用的计算机、程序设计语言,以及算法实现过程中的许多细节的影响,而算法的时间复杂度与这些因素无关。

算法所需要的计算工作量是用算法所执行的基本运算次数来度量的。算法所执行的基本运算次数与问题的规模有关。

当具体分析一个算法的工作量时,在同一个问题规模下,算法所执行的基本运算次数还可能与特定的输入有关。也就是说,输入不同时,算法所执行的基本运算次数也不同。

(2)算法的空间复杂度。

算法的空间复杂度是指执行这个算法所需要的存储空间。

执行算法所需要的存储空间包括3个部分:输入数据所占的存储空间;程序本身所占的存储空间;算法执行过程中所需要的额外空间。其中,额外空间包括算法执行过程中的工作单元,以及某种数据结构所需要的附加存储空间。如果额外空间量相对问题规模(输入数据所占的存储空间)来说是常数,即额外空间量不随问题规模的变化而变化,则称该算法是原地(in place)工作的。

为了降低算法的空间复杂度,主要应减少输入数据所占的存储空间和算法执行过程中所需要的额外空间,通常采用压缩存储技术来实现。

【考点2】　数据结构的基本概念

1.什么是数据结构

数据结构是指相互有关联的数据元素的集合。它包含两个要素,即“数据”和“结构”。

数据是需要处理的数据元素的集合。一般来说,这些数据元素具有某个共同的特征。如早餐、午餐、晚餐这3个数据元素有一个共同的特征,即它们都是一日三餐的名称,从而构成了“一日三餐”的集合。

所谓“结构”,就是关系,是集合中各个数据元素之间存在的某种关系(或联系)。在数据处理领域中,通常把数据元素两两之间的关系用前件/后件关系(或直接前驱/直接后继关系)来描述。如当考虑一日三餐的时间顺序关系时,“早餐”是“午餐”的前件(或直接前驱),而“午餐”是“早餐”的后件(或直接后继);同样,“午餐”是“晚餐”的前件,“晚餐”是“午餐”的后件。

数据结构分为数据的逻辑结构和存储结构。数据的逻辑结构指反映数据元素之间逻辑关系(前件/后件关系)的数据结构。数据的存储结构又称为数据的物理结构,是数据的逻辑结构在计算机存储空间中的存放方式。

2.数据结构的表示

数据的逻辑结构的数学形式定义——数据结构是一个二元组:

B=(D,R)

其中,B表示数据结构;D是数据元素的集合;R是D上关系的集合,它反映了D中各数据元素之间的前件/后件关系。前件/后件关系也可以用一个二元组来表示。

如果把一日三餐看作数据结构,则可表示成

B=(D,R)

D={早餐,午餐,晚餐}

R={(早餐,午餐),(午餐,晚餐)}

如果把部队军职看作数据结构,则可表示成

B=(D,R)

D={连长,排长,班长,士兵}

R={(连长,排长),(排长,班长),(班长,士兵)}

除了用二元关系表示外,一个数据结构还可以用图形来表示。用中间标有元素值的方框表示的数据元素,一般称为数据节点,简称节点。对于每一个二元组,用一条有向线段从前件指向后件。

一日三餐的数据结构如图2.7(a)所示。而部队军职的数据结构如图2.7(b)所示。

图2.7 数据结构的图形表示

由前件/后件关系还可引出3个节点基本概念,如表2.10所示。

表2.10 节点基本概念

3.线性结构与非线性结构

根据数据结构中各数据元素之间前件/后件关系的复杂程度,一般将数据结构划分为两大类型,即线性结构和非线性结构,如表2.11所示。

表2.11 线性结构和非线性结构

如果一个数据结构中没有数据元素,则称该数据结构为空的数据结构。在只有一个数据元素的数据结构中,删除该数据元素,就得到一个空的数据结构。

【考点3】　线性表及其顺序存储结构

1.线性表的基本概念

数据结构中,线性结构习惯称为线性表。线性表是最简单、也是最常用的一种数据结构。

线性表是由n(n≥0)个数据元素构成的有限序列。表中除第1个元素外的每一个元素,有且只有一个前件;除最后一个元素外,有且只有一个后件。

线性表要么是空表,要么可以表示为

(a1,a2,…,ai,…,an)

其中,ai(i=1,2,…,n)是线性表的数据元素,也称为线性表的一个节点。同一线性表中的数据元素必定具有相同的特性,即属于同一数据对象。数组、矩阵、向量等都是线性表。

非空线性表具有以下结构特征。

●只有一个根节点,即节点a1,它无前件。

●有且只有一个终端节点,即节点an,它无后件。

●除根节点与终端节点外,其他所有节点有且只有一个前件,并有且只有一个后件。

节点个数n称为线性表的长度,当n=0时,称为空表。

2.线性表的顺序存储结构

通常,线性表可以采用顺序存储和链式存储两种存储结构。

顺序存储结构是存储线性表最简单的存储结构之一,具体做法:将线性表中的元素一个接一个地存储在一片相邻的存储区域中。这种顺序存储的线性表也被称为顺序表。

顺序表具有以下两个基本特征。

●线性表中所有数据元素所占的存储空间是连续的。

●线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。

在顺序表中,其前件、后件两个元素在存储空间中是紧邻的,且前件元素一定存储在后件元素的前面。

【考点4】　栈和队列

1.栈及其基本运算

(1)栈的定义。

栈(stack)是一种特殊的线性表,它所有的插入与删除都限定在表的同一端进行,允许插入与删除的一端称为栈顶,不允许插入与删除的一端称为栈底。当栈中没有元素时,称为空栈。

(2)栈的运算。

栈的修改原则是“后进先出”或“先进后出”。

通常用指针top来指示栈顶的位置,用指针bottom来指示栈底的位置。栈顶指针top反映了栈不断变化的状态。

假设栈S=(a1,a2,…,an),则称a1为栈底元素,an为栈顶元素。栈中元素按a1,a2,…,an的次序进栈,退栈的第1个元素应为栈顶元素an。图2.8所示为栈结构和入栈、退栈示意。

图2.8 栈结构和入栈、退栈示意

栈的基本运算有3种:入栈、退栈及读栈顶元素。

栈和一般线性表的存储方法类似,通常也可以采用顺序存储和链式存储。

2.队列及其基本运算

(1)队列的定义。

队列(queue)是指允许在一端进行插入,而在另一端进行删除的线性表。允许进行删除运算的一端称为队头(排头),允许进行插入运算的一端称为队尾。若有队列:

Q=(q1,q2,…,qn)

那么,q1为队头元素(排头元素),qn为队尾元素。队列中的元素是按照q1,q2,…,qn的顺序进入的,退出队列也只能按照这个次序依次退出。与栈相反,队列又称为“先进先出”或“后进后出”的线性表。

(2)队列的运算。

可以用顺序存储的线性表来表示队列。为了指示当前执行退队运算的队头位置,需要一个队头指针(排头指针)front;为了指示当前执行入队运算的队尾位置,需要一个队尾指针rear。队头指针front总是指向队头元素的前一个位置,而队尾指针rear总是指向队尾元素。队尾指针rear和队头指针front共同反映了队列中元素动态变化的情况。图2.9所示为队列的入队、退队示意。

图2.9 队列的入队、退队示意

(3)循环队列及其运算。

在实际应用中,队列的顺序存储结构一般采用循环队列的形式。

所谓循环队列,就是将队列存储空间的最后1个位置绕到第1个位置,形成逻辑上的环状空间,供队列循环使用。

在循环队列中,用队尾指针rear指向队列中的队尾元素,用队头指针front指向队头元素的前一个位置。因此,从队头指针front指向的后一个位置直到队尾指针rear指向的位置之间所有的元素均为队列中的元素。

循环队列的初始状态为空,即front=rear=m,如图2.10所示。

图2.10 循环队列初始状态示意

在循环队列中,当front=rear时,不能确定队列是满还是空。在实际使用循环队列时,通常会增加一个标志s来区分队列是满还是空。当s=0时表示队列空;当s=1且front=rear时表示队列满。

【考点5】　线性链表

1.线性链表的基本概念

(1)线性链表。

线性链表指线性表的链式存储结构,简称链表。这种链表每个节点只有一个指针域,又称为单链表。

在线性链表中,第1个元素没有前件,因此指向链表中的第1个节点的指针,是一个特殊的指针,称为这个链表的头指针(HEAD)。最后一个元素没有后件,因此,线性链表最后一个节点的指针域为空,用NULL或0表示。

线性链表的存储单元是任意的,即各数据节点的存储序号可以是连续的,也可以是不连续的;各数据节点在存储空间中的位置关系与逻辑关系不一致,前件/后件关系由存储节点的指针来表示。当线性链表指向第1个数据元素的头指针等于NULL或者0时,该表称为空表。

在某些应用中,对线性链表中的每个节点设置两个指针,一个指针域存放前件的地址,称为左指针(Llink);一个指针域存放后件的地址,称为右指针(Rlink)。这样的线性链表称为双向链表。图2.11所示为双向链表示意。在双向链表中,由于为每个节点设置了两个指针,因此从某一个节点出发,可以很方便地找到其他任意一个节点。

图2.11 双向链表示意

(2)带链的栈。

栈也可以采用链式存储结构表示,可以把栈组织成一个单链表。这种数据结构称为带链的栈。图2.12(a)所示为带链的栈示意。

(3)带链的队列。

与栈类似,队列也可以采用链式存储结构表示。带链的队列就是用一个单链表来表示队列,队列中的每一个元素对应链表中的一个节点。图2.12(b)所示为带链的队列示意。

图2.12 带链的栈和带链的队列示意

(4)顺序表和链表的优缺点比较。

顺序表和链表的优缺点比较如表2.12所示。

表2.12 顺序表和链表的优缺点比较

2.循环链表的基本概念

在单链表的第1个节点前增加一个表头节点,队头指针指向表头节点,最后一个节点的指针域的值由NULL改为指向表头节点,这样的链表称为循环链表。在循环链表中,所有节点的指针构成了一个环状链。

在循环链表中,只要指出表中任何一个节点的位置,就可以从它出发访问表中其他所有的节点。并且,由于表头节点是循环链表固有的节点,因此,即使在表中没有数据元素的情况下,表中也至少有一个节点存在,从而使空表和非空表的运算统一。

循环链表的逻辑状态如图2.13所示。

图2.13 循环链表的逻辑状态

【考点6】　树与二叉树

1.树的基本概念

树(tree)是一种简单的非线性结构。如一个家族中的族谱关系为A有后代B、C;B有后代D、E、F;C有后代G;E有后代H、I,则这个家族的成员和血统关系可用图2.14所示的“一棵倒置的树”来描述。树的相关术语如表2.13所示。

图2.14 树的示例

表2.13 树的相关术语

树中的节点数等于树中所有节点的度之和再加1。

2.二叉树及其基本性质

(1)二叉树的定义。

二叉树与树不同,但它与树的结构很相似。图2.15所示为二叉树。

图2.15 二叉树

二叉树的特点如下。

①二叉树可以为空。空的二叉树没有节点,非空二叉树有且只有一个根节点。

②每个节点最多有两棵子树,即二叉树中不存在度大于2的节点。

③二叉树的子树有左右之分,其次序不能任意颠倒。

(2)二叉树的性质。

二叉树具有以下几个性质。

性质1:在二叉树的第k层上,最多有2k-1(k≥1)个节点。

性质2:深度为m的二叉树中,最多有2m-1个节点。

性质3:对任何一棵二叉树,度为0的节点(叶子节点)总是比度为2的节点多1个。

性质4:具有n个节点的二叉树,其深度至少为[log2n]+1,其中[log2n]表示取log2n的整数部分。

(3)满二叉树和完全二叉树。

满二叉树是指除最后一层外,每一层上的所有节点都有两个子节点的二叉树。即满二叉树在其第k层上有2k-1个节点,且深度为m的满二叉树共有2m-1个节点。

图2.16所示为深度是4的满二叉树。

图2.16 满二叉树

完全二叉树是指除最后一层外,每一层上的节点数均达到最大值,在最后一层上只缺少右边的若干节点的二叉树。图2.17所示为深度是4的完全二叉树。

图2.17 完全二叉树

由完全二叉树可知,满二叉树一定是完全二叉树,完全二叉树一般不是满二叉树。完全二叉树具有如下特点。

①叶子节点只可能在最后两层出现。

②对于任一节点,若其右子树的深度为m,则该节点左子树的深度为m或m+1。

性质5:具有n个节点的完全二叉树的深度为[log2n]+1。

3.二叉树的存储结构

在计算机中,二叉树通常采用链式存储结构。用于存储二叉树中元素的存储节点由数据域和指针域两部分构成。由于每一个元素可以有两个后件,因此用于存储二叉树中元素的存储节点的指针域有两个:一个用于指向该节点的左子节点,即左指针域;另一个用于指向该节点的右子节点,即右指针域。二叉树的存储节点如图2.18所示。

图2.18 二叉树的存储节点

由于二叉树的存储结构中每一个存储节点有两个指针域,因此二叉树的链式存储结构也称为二叉链表。

满二叉树与完全二叉树可以按层次进行顺序存储。

4.二叉树的遍历

二叉树的遍历是指不重复地访问二叉树中的所有节点。

在遍历二叉树的过程中,一般先遍历左子树,再遍历右子树。在先左后右的原则下,根据访问根节点的不同次序,二叉树的遍历可以分为3种:前序遍历(DLR)、中序遍历(LDR)、后序遍历(LRD)。

(1)前序遍历。

首先访问根节点,然后遍历左子树,最后遍历右子树;并且在遍历左子树和右子树时,仍然先访问根节点,然后遍历左子树,最后遍历右子树。对图2.19中的二叉树进行前序遍历的结果(或称为该二叉树的前序遍历序列)为A,B,D,H,E,I,C,F,G。

图2.19 一棵二叉树

(2)中序遍历。

首先遍历左子树,然后访问根节点,最后遍历右子树;并且在遍历左子树和右子树时,仍然首先遍历左子树,然后访问根节点,最后遍历右子树。对图2.19中的二叉树进行中序遍历的结果(或称为该二叉树的中序遍历序列)为H,D,B,E,I,A,C,G,F。

(3)后序遍历。

首先遍历左子树,然后遍历右子树,最后访问根节点;并且在遍历左子树和右子树时,仍然首先遍历左子树,然后遍历右子树,最后访问根节点。对图2.19中的二叉树进行后序遍历的结果(或称为该二叉树的后序遍历序列)为H,D,I,E,B,G,F,C,A。

如果已知一棵二叉树的前序遍历序列和中序遍历序列,可以唯一确定这棵二叉树;已知一棵二叉树的后序遍历序列和中序遍历序列,也可以唯一确定这棵二叉树。但是,已知一棵二叉树的前序遍历序列和后序遍历序列,不能唯一确定这棵二叉树。

【考点7】　查找

1.顺序查找

基本思想:从线性表的第1个元素开始,逐个将线性表中的元素与被查元素进行比较,若相等,则查找成功,停止查找;若整个线性表扫描完毕,仍未找到与被查元素相等的元素,则表示线性表中没有要查找的元素,查找失败。

●最好的情况下,第1个元素就是要查找的元素,则比较次数为1。

●最坏的情况下,最后一个元素才是要找的元素,或者在线性表中,没有要查找的元素,则需要与线性表中所有的元素比较,比较次数为n。

●平均情况下,大约需要比较n/2次。

在以下两种情况中,顺序查找是唯一的选择。

(1)线性表为无序表(表中的元素是无序的),则不管采用的是顺序存储结构,还是链式存储结构,都只能用顺序查找。

(2)即使线性表是有序的,如果采用的是链式存储结构,也只能用顺序查找。

2.二分法查找

能使用二分法查找的线性表必须满足两个条件:用顺序存储结构,线性表是有序表。此处的“有序”特指元素按非递减顺序排列,即从小到大排列,但允许相邻元素相等。

对于长度为n的有序线性表,利用二分法查找元素X的过程如下。

将X与线性表的中间项比较的过程如下。

●如果X的值与中间项的值相等,则查找成功,结束查找。

●如果X的值小于中间项的值,则在线性表的前半部分以二分法继续查找。

●如果X的值大于中间项的值,则在线性表的后半部分以二分法继续查找。

顺序查找每比较一次,只将查找范围缩小1,而二分法查找每比较一次,可将查找范围缩小为原来的一半,效率大大提高。对于长度为n的有序线性表,在最坏情况下,二分法查找只需比较log2n次。

【考点8】　排序

排序是指将一个无序序列整理成按值非递减顺序排列的有序序列。

1.交换类排序

交换类排序是借助数据元素的“交换”来进行排序的一种方法。

(1)冒泡排序。

在数据元素的序列中,对于某个元素,如果其后存在一个元素小于它,则称存在一个逆序。冒泡排序的基本思想就是通过两两相邻数据元素之间的比较和交换,不断地消去逆序,直到所有数据元素有序为止。

在最坏情况下,对长度为n的线性表排序,冒泡排序需要比较的次数为n(n-1)/2。

(2)快速排序。

基本思想:在待排序的n个元素中取一个元素K(通常取第1个元素),以元素K作为分割标准,把所有小于元素K的数据元素都移到K前面,把所有大于元素K的数据元素都移到K后面。这样,以K为分界线,把线性表分割为两个子表,这称为一趟排序。然后,对K前后的两个子表分别重复上述过程,直到分割的子表的长度为1为止。这时线性表已经排好序。

快速排序在最坏情况下需要进行n(n-1)/2次比较,但实际的排序效率要比冒泡排序高得多。

2.插入类排序

插入类排序是每次将一个待排序元素,按其元素值的大小插入前面已经排好序的子表中的适当位置,直到全部元素插入完成为止。

(1)简单插入排序。

简单插入排序是把n个待排序的元素看成一个有序表和一个无序表。开始时,有序表只包含一个元素,而无序表包含另外n-1个元素。每次取无序表中的第1个元素插入有序表中的正确位置,使之成为增加一个元素的新的有序表。插入元素时,插入位置及其后的记录依次向后移动。最后有序表的长度为n,而无序表为空,此时排序完成。

在最坏情况下,简单插入排序需要进行n(n-1)/2次比较。

(2)希尔排序。

希尔排序的基本思想是,先取一个整数d1(称为增量,d1<n),把全部数据元素分成d1个组,所有距离为d1倍数的元素放在一组中,组成了一个子序列,对每个子序列分别进行简单插入排序。然后取d2(d2<d1)重复上述分组和排序工作,直到di=1,即所有记录在一组中为止。

希尔排序的效率与所选取的增量序列有关。在最坏情况下,希尔排序需要比较的次数是nr(1<r<2)。

3.选择类排序

选择类排序的基本思想是通过每一次从待排序序列中选出值最小的元素,然后将其顺序放在已排好序的有序子表的后面,直到全部序列满足排序要求为止。

(1)简单选择排序。

基本思想:先从所有n个待排序的数据元素中选择最小的元素,将该元素与第1个元素交换,再从剩下的n-1个元素中选出最小的元素与第2个元素交换。重复这样的操作直到所有的元素有序为止。

简单选择排序在最坏的情况下需要比较n(n-1)/2次。

(2)堆排序。

若有n个元素的序列(h1,h2,…,hn),将元素按顺序组成一棵完全二叉树,该树当且仅当满足下列条件时称为堆。

或者　　　

其中,i=1,2,3,…,n/2。

第1种情况称为大根堆,所有节点的值大于或等于左右子节点的值。第2种情况称为小根堆,所有节点的值小于或等于左右子节点的值。

堆排序在最坏情况下需要比较nlog2n次。

2.1.3 程序设计基础

【考点1】　程序设计风格

程序的质量主要受到程序设计的方法、技术及风格等因素的影响。“清晰第一、效率第二”是当今主导的程序设计风格,即首先要保证程序的清晰、易读,其次考虑提高程序的执行速度、节省系统资源。

要形成良好的程序设计风格,主要应注重和考虑下述因素。

①源程序文档化。

②数据说明风格:次序应规范化;变量安排有序化;使用注释来说明复杂数据的结构等。

③语句的结构:不要在同一行内写多个语句;首先保证程序正确,然后要求提高速度;尽可能使用库函数;避免不必要的转移等。

④输入和输出:对所有的输入数据都要进行检验,确保输入数据的合法性;在采用交互式输入/输出方式进行输入时,在屏幕上使用提示符明确提示输入的请求,同时在数据输入过程中和输入结束时,应在屏幕上给出状态信息;给所有的输出加注释,并设计良好的输出报表格式等。

【考点2】　结构化程序设计

就程序设计方法的发展而言,主要经历了结构化程序设计和面向对象的程序设计这两个阶段。

1.结构化程序设计的原则

结构化程序设计方法的重要原则是自顶向下、逐步求精、模块化及限制使用goto语句。

2.结构化程序设计的基本结构

结构化程序设计方法是使用“顺序结构”“选择结构”及“循环结构”3种基本结构就足以表达其他各种结构的程序设计方法。它们的共同特征是:严格地只有一个入口和一个出口。

遵循结构化程序的设计原则,按此原则设计出的程序具有以下优点。

●程序易于理解、使用及维护。

●提高了编程工作的效率,降低了软件开发成本。

【考点3】　面向对象的程序设计

1.面向对象方法的优点

●与人类习惯的思维方法一致。

●稳定性好。

●可重用性好。

●便于开发大型软件产品。

●可维护性好。

2.面向对象方法的基本概念

(1)对象。

面向对象方法中的对象由两部分组成。

①数据,也称为属性,即对象所包含的信息,表示对象的状态。

②方法,也称为操作,即对象能执行的功能、所具有的行为。

对象的基本特点如表2.14所示。

表2.14 对象的基本特点

(2)类和实例。

类(class)是具有共同属性、共同方法的对象的集合,是关于对象的抽象描述,反映属于该对象类型的所有对象的性质。一个具体对象则是其对应类的一个实例(instance)。

例如,“大学生”是一个大学生类,它描述了所有大学生的性质。因此,任何大学生都是类“大学生”的一个对象(这里的“对象”不可以用“实例”来代替),而一个具体的大学生“张三”是类“大学生”的一个实例。

类是关于对象性质的描述,它同对象一样,包括一组数据属性和在数据上的一组合法操作。

(3)消息。

消息(message)传递是对象间通信的手段,一个对象通过向另一个对象发送消息来请求其服务。

(4)继承。

在面向对象的程序设计中,类与类之间可以继承,一个子类可以直接继承其父类的全部描述(数据和操作)。这些属性和操作在子类中不必定义,此外,子类还可以定义它自己的属性和操作。

例如,“四边形”类是“矩形”类的父类,“四边形”类可以有“顶点坐标”等属性,有“移动”“旋转”“求周长”等操作。“矩形”类除了继承“四边形”类的属性和操作外,还可定义自己的属性和操作,如“长”“宽”等属性和“求面积”等操作。

继承具有传递性,如果类Z继承类Y,类Y继承类X,则类Z继承类X。

需要注意的是,类与类之间的继承应根据需要来做,并不是任何类都要继承。

(5)多态性。

在面向对象的软件技术中,多态性是指子类对象可以像父类对象那样使用,同样的消息(如方法)既可以发送给父类对象,也可以发送给子类对象。

例如,在一般类polygon(多边形)中定义了一个方法Show来显示自身,但并不确定执行时到底画一个什么图形。特殊类square和类rectangle都继承了polygon类的显示操作,但其实现的结果却不同。把方法Show的消息发送给一个rectangle类的对象是在屏幕上画一个矩形,而将同样消息名的消息发送给一个square类的对象则是在屏幕上画一个正方形。

2.1.4 软件工程基础

【考点1】　软件工程的基本概念

1.软件定义与软件特点

计算机软件是由程序、数据及相关文档构成的完整集合,它与计算机硬件一起组成计算机系统。其中,程序和数据是机器可执行的,文档是机器不可执行的。

软件具有以下特点。

(1)软件是一种逻辑实体,具有抽象性。

(2)软件没有明显的制作过程。

(3)软件在使用期间不存在磨损、老化问题。

(4)软件对硬件和环境具有依赖性。

(5)软件复杂性高,成本高。

(6)软件开发涉及诸多的社会因素。

2.软件的分类

计算机软件按功能分为系统软件、应用软件、支撑软件(或工具软件)。

(1)系统软件是管理计算机的资源、提高计算机的使用效率、为用户提供各种服务的软件,如操作系统(Operating System, OS)、数据库管理系统(DataBase Management System, DBMS)、编译程序、汇编程序及网络软件等。

(2)应用软件是为了应用于特定的领域而开发的软件。我们熟悉的办公软件、即时通信、杀毒软件、财务管理系统软件等属于应用软件。

(3)支撑软件是介于系统软件和应用软件之间,协助用户开发软件的工具软件,其中包括帮助程序人员开发和维护软件产品的工具软件,也包括帮助管理人员控制开发进程和项目管理的工具软件。

3.软件工程

软件工程是试图用工程、科学及数学的原理与方法研制、维护计算机软件的有关技术和管理方法,是应用于计算机软件的定义、开发及维护的一整套方法、工具、文档、实践标准及工序。软件工程包含3个要素:方法、工具及过程。

抽象、信息隐蔽、模块化、局部化、确定性、一致性、完备性及可验证性是软件工程的原则。

4.软件过程

软件过程是把输入转换为输出的一组彼此相关的资源和活动。软件过程是指为了获得高质量软件所需要完成的一系列任务的框架,它规定了完成各项任务的工作步骤。软件过程所进行的基本活动主要有软件规格说明、软件开发或软件设计与实现、软件确认、软件演进。

5.软件生命周期

软件开发应遵循软件生命周期。通常把软件产品从问题定义、可行性研究、需求分析、概要设计、详细设计、实现、测试到使用、维护和退役的过程称为软件生命周期。软件生命周期分为3个时期,共8个阶段,如图2.20所示。

图2.20 软件生命周期

软件生命周期各阶段的主要任务介绍如下。

(1)问题定义:确定要解决的问题是什么。

(2)可行性研究:决定该问题是否存在一个可行的解决办法,确定完成开发任务的实施计划。

(3)需求分析:对待开发软件提出的需求进行分析并给出详细定义。编写软件的需求规格说明书和初步的用户手册,提交评审。

(4)软件设计:通常又分为概要设计和详细设计两个阶段,其目的是给出软件的结构、模块的划分、功能的分配以及处理流程等。软件设计阶段提交评审的文档有概要设计说明书、详细设计说明书及测试计划初稿。

(5)实现:在软件设计的基础上编写程序。该阶段完成的文档有用户手册、操作手册等面向用户的文档,以及为下一阶段编写的单元测试计划。

(6)测试:在设计测试用例的基础上,检验软件的各个组成部分。编写测试分析报告。

(7)使用和维护:将已交付的软件投入运行,同时不断地维护,进行必要而且可行的扩充和删改。

【考点2】　需求分析及其方法

1.需求分析

(1)需求分析相关概念。

需求分析是发现需求、求精、建模及定义需求的过程。需求分析将创建所需的数据模型、功能模型及控制模型。

需求分析阶段的工作可以分为4个方面:需求获取、需求分析、编写需求规格说明书及需求评审。

(2)需求规格说明书。

需求规格说明书是需求分析阶段的最后成果。需求规格说明书应重点描述软件的目标,如软件的功能需求、性能需求、外部接口、属性及约束条件等。

需求规格说明书的特点:正确性、无歧义性、完整性、可验证性、一致性、可理解性、可修改性、可追踪性。

(3)需求分析方法。

需求分析方法可以分为结构化分析方法和面向对象分析方法两大类。

①结构化分析方法。结构化分析方法主要包括面向数据流的结构化分析方法、面向数据结构的Jackson系统开发方法及面向数据结构的结构化数据系统开发方法。

②面向对象分析方法。面向对象分析是面向对象软件工程方法的第1个环节,包括概念原则、过程步骤、表示方法、提交文档等规范要求。

另外,从需求分析建模的特性来划分,需求分析方法还可以分为静态分析方法和动态分析方法。

2.结构化分析方法的常用工具

结构化分析方法是使用数据流图、数据字典、结构化英语、判定表及判定树等工具建立一种新的、被称为结构化规格说明的目标文档。

需求分析的结构化分析方法中常用的工具是数据流图(Data Flow Diagram,DFD)。数据流图的主要图形元素与说明如表2.15所示。

表2.15 数据流图的主要图形元素与说明

为使构造的数据流图表达完整、准确、规范,应遵循如下的构造规则和注意事项。

(1)数据流图上的每个元素都必须被命名。

(2)对加工处理建立唯一、层次性的编号,并且每个加工处理通常要求既有输入,又有输出。

(3)数据存储之间不应有数据流。

(4)数据流图的一致性,即输入/输出、读/写的对应。

(5)父图、子图关系与平衡规则:子图个数不大于父图中的处理个数。所有子图的输入/输出数据流和父图中相应处理的输入/输出数据流必须一致。

【考点3】　软件设计及其方法

1.软件设计的基本概念

软件设计的基本目标是用比较抽象、概括的方式确定目标系统如何完成预定的任务。也就是说,软件设计是确定系统的物理模型。

软件设计是开发阶段最重要的步骤之一。从工程管理的角度来看,软件设计可分为两步:概要设计和详细设计。从技术方面来看,软件设计包括结构设计、数据设计、接口设计、过程设计4个步骤。

将软件按功能分解为组成模块,是概要设计的主要任务。划分模块要本着提高独立性的原则。模块独立性的高低决定设计的好坏,而设计又是决定软件质量的关键环节。模块的独立性可以由两个定性标准度量:耦合性和内聚性。

(1)耦合性衡量不同模块彼此间互相依赖(连接)的紧密程度。

(2)内聚性衡量一个模块内部各个元素彼此结合的紧密程度。

模块的内聚性越高,模块的耦合性就越低,可见模块的耦合性和内聚性是相互关联的。因此,好的软件设计,应尽量做到高内聚、低耦合。

2.概要设计

(1)概要设计的任务。

概要设计又称总体设计,软件概要设计的基本任务如下。

①设计软件系统结构。

②设计数据结构和数据库。

③编写概要设计文档:概要设计阶段的文档有概要设计说明书、数据库设计说明书及集成测试计划等。

④评审概要设计文档。

(2)结构图。

在概要设计中,常用的软件结构设计工具是结构图(Structure Chart,SC),也称为程序结构图。它反映了整个系统的功能实现以及模块之间的联系。

结构图的基本图符及其含义如表2.16所示。

表2.16 结构图的基本图符及其含义

软件结构图是一种层次化的表示,它指出了软件各个模块之间的关系,如图2.21所示。

图2.21 软件结构图

软件结构图术语及其含义如表2.17所示。

表2.17 软件结构图术语及其含义

好的软件设计结构通常顶层扇出多,中间较低扇出,底层扇入多。

3.详细设计

详细设计的任务是为软件结构图中的每一个模块确定实现算法和局部数据结构,用某种选定的表达工具表示算法和数据结构的细节。

常用的设计工具有程序流程图(Program Flow Diagram,PFD)、N-S图(Nassi-Shneiderman Diagram,N-S)、问题分析图(Problem Analysis Diagram,PAD)、HIPO(Hierarchy plus Input-Process-Output,HIPO)图、判定表、过程设计语言(Procedure Design Language,PDL)。

【考点4】　软件测试

1.软件测试的目的和准则

软件测试的目的是在软件投入运行之前,尽可能多地发现软件中的错误。软件测试是保证软件质量、可靠性的关键步骤。它是对软件规格说明、设计和编码的最后复审。

软件测试应遵循如下准则。

(1)所有测试都应追溯到用户需求。

(2)在测试之前制定测试计划,并严格执行。

(3)充分注意测试中的群集现象。

(4)避免由程序的编写者测试自己的程序。

(5)不可能进行穷举测试。

(6)妥善保存测试计划、测试用例、出错统计和最终分析报告,为维护提供方便。

2.软件测试方法

软件测试方法较多,如果根据软件是否需要被执行,可以分为静态测试和动态测试;如果根据功能划分,可以分为白盒测试和黑盒测试。

(1)静态测试和动态测试。

①静态测试。静态测试包括代码检查、静态结构分析、代码质量度量等。其中代码检查分为代码审查、代码走查、桌面检查、静态分析等具体形式。静态测试不实际运行软件,主要通过人工进行分析。

②动态测试。动态测试就是通常所说的上机测试,通过运行软件来检验软件中的动态行为和运行结果的正确性。

动态测试的关键是设计高效、合理的测试用例。测试用例就是为测试设计的数据,由测试输入数据和预期的输出结果两部分组成。

(2)白盒测试和黑盒测试。

①白盒测试。白盒测试假设程序装在一只透明的白盒子里,测试者完全了解程序的结构和处理过程。它根据程序的内部逻辑来设计测试用例,检查程序中的逻辑通路是否都按预定的要求正确地工作。

白盒测试的主要技术有逻辑覆盖测试、基本路径测试等。其中逻辑覆盖测试又分为语句覆盖、路径覆盖、判定覆盖、条件覆盖及判断-条件覆盖。

②黑盒测试。黑盒测试又称功能测试或数据驱动测试,着重测试软件功能,假设程序装在一只黑盒子里,测试者完全不了解或不考虑程序的结构和处理过程。它根据规格说明书的功能来设计测试用例,检查程序的功能是否符合规格说明书的要求。

常用的黑盒测试方法和技术有等价类划分法、边界值分析法、错误推测法及因果图等。

3.软件测试的实施

软件测试的实施过程主要有4个步骤:单元测试、集成测试、确认测试及系统测试。

(1)单元测试。

单元测试也称模块测试,模块是软件设计的最小单位,单元测试是对模块的正确性进行检验,以尽早发现各模块内部可能存在的各种错误。

单元测试通常在编码阶段进行,单元测试的依据除了源程序以外,还有详细设计说明书。

单元测试可以采用静态测试或者动态测试。动态测试通常以白盒测试为主,测试程序的结构;以黑盒测试为辅,测试程序的功能。

(2)集成测试。

集成测试也称组装测试,它是对各模块按照设计要求组装成的程序进行测试,主要目的是发现与接口有关的错误(系统测试与此类似)。

集成测试主要发现设计阶段产生的错误。集成测试的依据是概要设计说明书,通常采用黑盒测试。

集成可以分为非增量方式(一次性组装方式)集成和增量方式集成两种。增量方式包括自顶向下、自底向上,以及自顶向下和自底向上相结合的混合增量方式。

(3)确认测试。

确认测试也称验收测试,其任务是检查软件的功能、性能及其他特征是否与用户的需求一致,它是以需求规格说明书作为依据的测试。确认测试通常采用黑盒测试。

(4)系统测试。

在确认测试完成后,把软件系统整体作为一个元素,与计算机硬件、支持的软件、数据、人员及其他计算机系统的元素组合在一起,在实际运行环境下对计算机系统进行一系列的集成测试和确认测试,这样的测试称为系统测试。

【考点5】　程序调试

1.程序调试的基本概念

调试(debug),也称为排错,是在成功测试之后出现的步骤。也就是说,调试是在测试发现错误之后排除错误的过程。程序调试的任务是诊断和改正程序中的错误。

程序调试由两部分组成。

(1)根据错误的迹象确定程序中错误的确切性质、原因和位置。

(2)对程序进行修改,改正这个错误。

2.调试方法

从是否跟踪和执行程序的角度,调试分为静态调试和动态调试。静态调试是主要的调试手段,是指通过人的思维来分析源程序的代码和排错。而动态调试是静态测试的辅助手段,主要调试方法有强行排错法、回溯法、原因排除法(二分法、归纳法及演绎法)等。

2.1.5 数据库设计基础

【考点1】　数据库的基本概念

1.基本概念

(1)数据。

描述事物的符号记录称为数据。数据库系统中的数据具有长期保存的特点,它们通常被称为持久性数据,而把一般存放在计算机内存中的数据称为临时性数据。

(2)数据库。

数据库(database,DB)是指长期存储在计算机内的、有组织的、可共享的数据集合。

通俗理解,数据库就是存放数据的仓库,只不过数据库存放数据是按数据所提供的数据模式存放的。数据库中的数据具有两大特点:“集成”与“共享”。

(3)数据库管理系统。

数据库管理系统是数据库的机构,它是一个系统软件,负责数据库中的数据组织,数据操纵,数据维护、控制及保护,数据服务等。

数据库管理系统是数据库系统的核心,它位于用户与操作系统之间。从软件分类的角度来看,它属于系统软件。

数据库管理系统的主要功能包括:数据模式定义;数据存取的物理构建;数据操纵;数据完整性、安全性的定义与检查;数据库的并发控制与故障恢复;数据的服务等。

为了完成以上6个功能,数据库管理系统提供了相应的数据语言。

①数据定义语言。该语言负责数据的模式定义与数据的物理存取构建。

②数据操纵语言。该语言负责数据的操纵,包括查、增、删、改等操作。

③数据控制语言。该语言负责数据完整性、安全性的定义与检查,以及并发控制、故障恢复等功能。

(4)数据库管理员。

由于数据库的共享性,数据库的规划、设计、维护、监视等需要有专人(数据库管理员)管理。其主要工作是设计数据库、维护数据库、改善系统性能,及提高系统效率等。

(5)数据库系统。

数据库系统由如下几部分组成:数据库、数据库管理系统、数据库管理员、系统平台之一——硬件平台、系统平台之二——软件平台。数据库系统是一个以数据库管理系统为核心的、完整的运行实体。

(6)数据库应用系统。

在数据库系统的基础上,如果使用数据库管理系统软件和数据库开发工具编写出应用程序,用相关的可视化工具开发出应用界面,则构成了数据库应用系统(Database Application System,DBAS)。数据库应用系统包括数据库、数据库管理系统、人员(数据库管理员和用户)、硬件平台、软件平台、应用软件、应用界面7个部分。

2.数据管理技术的发展

数据管理技术的发展经历了3个阶段:人工管理阶段、文件系统阶段及数据库系统阶段。3个发展阶段的背景和特点如表2.18所示。

表2.18 数据管理技术的3个发展阶段的背景和特点

3.数据库系统的基本特点

与人工管理和文件系统相比,数据库系统具有图2.22所示的基本特点。

图2.22 数据库系统的基本特点

数据库系统的数据独立性,是指数据库中数据独立于应用程序且不依赖于应用程序,即数据的逻辑结构、存储结构与存取方式的改变不会影响应用程序。数据独立性一般分为物理独立性和逻辑独立性两级。

4.数据库系统的内部结构体系

数据库系统在其内部分为三级模式和两级映射,如图2.23所示。

图2.23 三级模式和两级映射关系

(1)数据库系统的三级模式。

数据库系统在其内部分为三级模式,即概念模式、外模式及内模式。

①概念模式。概念模式也称模式,是对数据库系统中全局数据逻辑结构的描述,是全体用户的公共数据视图。对它的描述可用数据库管理系统中的数据定义语言定义。

②外模式。外模式也称子模式或者用户模式,是用户的数据视图,也就是用户所能够看见和使用的局部数据的逻辑结构和特征的描述,是与某一应用有关的数据的逻辑表示。外模式通常是概念模式的子集。

③内模式。内模式也称物理模式,是数据库物理结构和存储方式的描述,是数据在数据库内部的表示方式。

三级模式反映了模式的3个不同环境和它们的不同要求。其中内模式处于最内层,它反映了数据在计算机物理结构中的实际存储形式;概念模式处于中层,它反映了设计者的数据全局逻辑要求;而外模式处于最外层,它反映了用户对数据的要求。

一个数据库只有一个概念模式和一个内模式,有多个外模式。

(2)数据库系统的两级映射。

数据库系统在三级模式之间提供了两级映射:外模式/概念模式的映射和概念模式/内模式的映射。两级映射保证了数据库中的数据具有较高的逻辑独立性和物理独立性。

【考点2】　数据模型

1.数据模型的基本概念

(1)数据模型的概念。

数据模型(data model)是对数据特征的抽象。通俗来讲,数据模型就是对现实世界的模拟、描述或表示,建立数据模型的目的是建立数据库来处理数据。

(2)数据模型的3个部分。

数据模型通常由数据结构、数据操作及数据约束3个部分组成。

①数据结构:主要描述数据的类型、内容、性质以及数据间的联系等。

②数据操作:主要描述在相应数据结构上的操作类型与操作方式。

③数据约束:主要描述数据结构内数据间的语法、语义联系,它们之间的制约与依存关系,以及数据动态变化的规则,以保证数据的正确、有效及相容。

(3)数据模型的类型。

数据模型按照不同的应用层次分为以下3种类型。

①概念模型:着重于对现实世界复杂事物的描述及对它们内在联系的刻画。目前,著名的概念模型有实体联系模型(E-R模型)、面向对象模型、谓词模型。

②逻辑模型:又称数据模型,是面向数据库系统的模型,着重于在数据库系统一级的实现。成熟并大量使用的数据模型有层次模型、网状模型、关系模型及面向对象模型等。

③物理模型:是面向计算机物理实现的模型。此模型给出了数据模型在计算机上物理结构的表示。

2.E-R模型

E-R模型是广泛使用的概念模型。它采用了3个基本概念:实体、属性及联系。

(1)E-R模型的基本概念。

①实体。客观存在并且可以相互区别的事物称为实体。实体可以是一个实际的事物,如一本书、一间教室等;也可以是一个抽象的事件,如一场演出、一场比赛等。

②属性。描述实体的特性称为属性。如一个学生可以用学号、姓名、出生年月等来描述。

③联系。实体之间的对应关系称为联系,它反映现实世界事物之间的相互关联。

根据一个实体型中可能出现的每一个实体和另一个实体型中有多少个具体实体存在联系,实体间联系可归纳为3种类型,如表2.19所示。

表2.19 实体间联系的类型

(2)E-R模型的3个基本概念之间的连接关系。

E-R模型的3个基本概念是实体、属性及联系,但现实世界是有机联系的整体,为了表示现实世界,必须把这三者连接起来。

①实体(集)与联系的连接关系。一般来说,实体集之间必须通过联系来建立连接关系。如教师与学生之间无法直接建立连接关系,他们只能通过“教与学”的联系才能在相互之间建立连接关系。

②属性与实体(集/联系)的连接关系。实体和联系是概念世界的基本元素,而属性是附属于实体和联系的,它本身并不是独立的单位。

联系也可以附有属性,如供应商和零件两个实体之间有“供应”的联系,该联系具有“供应量”的属性。联系和它的属性构成了联系的完整描述。

(3)E-R图。

E-R模型可以用图形来表示,该图形称为E-R图。E-R图可以直观地表达E-R模型。在E-R图中,我们分别用下面不同的几何图形(见图2.24)表示E-R模型中的3个基本概念(见表2.20)。

表2.20 几何图形表示E-R模型中的3个基本概念

图2.24 E-R模型3个基本概念的示意

3个基本概念分别用3种几何图形表示,它们之间的连接关系也可用图形表示。如实体集student有属性S#(学号)、Sn(姓名)及Sa(年龄);实体集course有属性C#(课程号)、Cn(课程名)及P#(预修课号);联系SC有属性G(成绩),其E-R图如图2.25所示(线段上注明联系的类型,如1∶1、1∶n、n∶m等)。

图2.25 E-R图

3.关系模型

(1)关系模型的数据结构。

关系模型是目前最常用的数据模型之一。关系模型的数据结构非常单一。在关系模型中,现实世界的实体和实体间的各种联系均用关系来表示。关系模型中常用的术语如表2.21所示。

表2.21 关系模型中常用的术语

表2.22 学生登记表

表2.23 系信息表

关系具有以下7个性质。

①元组个数的有限性:二维表中元组的个数是有限的。

②元组的唯一性:二维表中任意两个元组不能完全相同。

③元组的次序无关性:二维表中元组的次序,即行的次序可以任意交换。

④元组分量的原子性:二维表中元组的分量是不可分割的基本数据项。

⑤属性名的唯一性:二维表中不同的属性要有不同的属性名。

⑥属性的次序无关性:二维表中属性的次序可以任意交换。

⑦分量值域的同一性:二维表属性的分量具有与该属性相同的值域,或者说列是同质的。

满足以上7个性质的二维表称为关系,以二维表为基本结构所建立的模型称为关系模型。

(2)关系模型的完整性约束。

关系模型有3种完整性约束:实体完整性约束、参照完整性约束及用户定义的完整性约束。在这3种完整性约束中,前两种约束是任何一个关系数据库都必须满足的,由关系数据库管理系统自动支持。

①实体完整性约束。若属性M是关系的主键,则属性M中的属性值不能为空。如在“学生登记表”中,主键为“学号”,则“学号”不能取空值。

②参照完整性约束。若属性(或属性组)A是关系M的外键,它与关系N的主键相对应,则关系M中的每个元组在A上的值:要么为空(A的每个属性值均为空);要么等于关系N中某个元组的主键值。

如对于“学生登记表”和“系信息表”,“学生登记表”中每个元组的“系号”属性只能取两类值:空值,表示尚未给该学生分配系;非空值,这时该值必须是系信息表中某个元组的“系号”值,表示该学生不可能分配到一个不存在的系。

③用户定义的完整性约束。用户定义的完整性约束反映了某一具体应用所涉及的数据必须满足的语义要求。如某个属性的取值范围为1~200,某个属性必须取唯一值等。

【考点3】　关系代数

关系代数就是关系与关系之间的运算。在关系代数中,进行运算的对象都是关系,运算的结果也是关系(表)。

1.差运算

关系R和关系S经过差运算后得到的关系由属于关系R但不属于关系S的元组构成,记为R-S。图2.26所示为对关系R和关系S做差运算的示例。

图2.26 差运算示例

2.交运算

假设有n元关系R和n元关系S,它们经过交运算得到的关系仍然是一个n元关系,该关系由属于关系R且属于关系S的元组组成,并记为R∩S。R∩S=R-(R-S)。图2.27所示为对关系R和关系S做交运算的示例。

图2.27 交运算示例

3.并运算

关系R与关系S经过并运算后得到的关系由属于关系R或属于关系S的元组构成,记为R∪S。图2.28所示为对关系R和关系S做并运算的示例。

图2.28 并运算示例

4.笛卡儿积运算

设有n元关系R和m元关系S,它们分别有p和q个元组,则关系R与关系S的笛卡儿积记为R×S。它是一个m+n元关系,元组个数是p×q。图2.29所示为对关系R和关系S做笛卡儿积运算的示例。

图2.29 笛卡儿积运算示例

5.投影运算

从关系模式中指定若干个属性组成新的关系称为投影。

对关系R进行投影运算的结果记为πA(R),其形式定义如下:

πA(R)={t[A]|t∈R}

其中,A为R中的属性列。

如对关系R中的“系”属性进行投影运算,记为π系(R),得到无重复元组的新关系S,如图2.30所示。

图2.30 投影运算示例

6.选择运算

从关系中找出满足给定条件的元组的操作称为选择。选择的条件以逻辑表达式给出,使逻辑表达式为真的元组将被选取。

选择是在二维表中选出符合条件的行,并形成新的关系的过程。选择运算用公式表示为

σF(R)={t|t∈R且F(t)为真}

其中,F表示选择条件,它是一个逻辑表达式,取逻辑值“真”或“假”。逻辑表达式F由逻辑运算符 ┐、∧、∨连接各算术表达式组成。算术表达式的基本形式为

XθY

其中,θ表示比较运算符>、<、≤、≥、=或≠。X、Y等为属性名、常量或简单函数。属性名也可以用它的序号来代替。

如在关系R中选择出“系”为“建筑”的学生,表示为σ系=建筑(R),得到新的关系S,如图2.31所示。

图2.31 选择运算示例

7.除运算

除运算可以近似地看作笛卡儿积的逆运算。当S×T=R时,则必有R÷S=T,T称为R除以S的商。

设关系R有属性M1,M2,…,Mn,关系S有属性Mn-s+1,Mn-s+2,…,Mn,此时有

关系R、S,如图2.32(a)、(b)所示,求T(T=R÷S),结果如图2.32(c)所示。

图2.32 除运算示例

8.连接运算

连接运算也称θ连接,是对两个关系进行的运算,其意义是从两个关系的笛卡儿积中选择满足给定属性间一定条件的元组。

设m元关系R和n元关系S,则R和S两个关系的连接运算用公式表示为

它的含义可用公式定义

其中,A和B分别为关系R和关系S上度数相等且可比的属性组。连接运算从关系R和关系S的笛卡儿积R×S中,找出关系R在属性组A上的值与关系S在属性组B上的值满足θ关系的所有元组。

当θ为“=”时,该运算称为等值连接;当θ为“<”时,该运算称为小于连接;当θ为“>”时,该运算称为大于连接。

设关系R和关系S如图2.33(a)、(b)所示,对图中的关系R和关系S做连接运算的结果如图2.33(c)、(d)所示。

图2.33 连接运算示例

在实际应用中,最常用的连接是自然连接。自然连接要求两个关系中进行比较的是相同的属性,并且进行等值连接,相当于θ恒为“=”,在结果中还要把重复的属性列去掉。自然连接可记为

R▷◁S

设有关系R和关系S,如图2.34(a)、(b)所示,则R▷◁S的结果如图2.34(c)所示。

图2.34 自然连接运算示例

【考点4】　数据库设计

1.数据库设计概述

基本思想:过程迭代和逐步求精。

方法:面向数据的方法和面向过程的方法。

设计过程:需求分析→概念设计→逻辑设计→物理设计→编码→测试→运行→进一步修改。

2.数据库设计的需求分析

需求收集和分析是数据库设计的第一阶段,常采用结构化分析方法(自顶向下、逐层分解)和面向对象方法,主要工作有绘制数据流程图、分析数据和功能、确定功能处理模块和数据间关系等。

数据字典包括数据项、数据结构、数据流、数据存储和处理过程,是对系统中数据的详尽描述。

3.数据库的设计

(1)数据库的概念设计:分析数据间内在的语义关联,以建立数据的抽象模型。

(2)数据库的逻辑设计:从E-R图向关系模型转换,使逻辑模式规范化,关系视图可以根据用户需求随时创建。实体转换为元组,属性转换为关系的属性,联系转换为关系。

(3)数据库的物理设计:对数据在物理设备上的存储结构与存取方法进行设计,目的是对数据库内部物理结构进行调整并选择合理的存取路径,以提高速度和存储空间。

4.范式

关系数据库中的关系需要满足一定要求,满足不同程度要求的关系为不同的范式。满足最低要求的关系叫第一范式,简称1NF。在满足第一范式的基础上,进一步满足更多要求的关系是第二范式。然后在满足第二范式的基础上,还可以再满足第三范式,以此类推。

对于关系,若其中的每个属性都已不能再分为简单项,则它属于第一范式。

例如,关系SC(学号,姓名,所在系,系主任,年龄,课程号,课程名,成绩),其中的每个属性不能再分,属于第一范式。

若某个关系R为第一范式,并且R中每一个非主属性完全依赖于R的某个候选键,则称其为第二范式。第二范式消除了非主属性对主键的部分依赖。

例如,关系SC的主键为复合键(学号,课程号),但明显有学号→姓名,课程号→课程名等,存在非主属性对主属性的部分依赖。对关系SC进行如下的分解,就可以消除对非主属性的部分依赖,满足第二范式:

S1(学号,姓名,所在系,系主任,年龄)

C(课程号,课程名)

SC1(学号,课程号,成绩)

如果关系R是第二范式,并且每个非主属性都不传递依赖于R的候选键,则称R为第三范式。(传递依赖:在关系模式中,如果Y→X,X→A,且X不决定Y,A不属于X,那么Y→A是传递依赖。)

如在关系S1中,学号→所在系,所在系→系主任,所以“系主任”传递依赖于主属性“学号”。对关系S1进行如下分解,即可消除传递依赖,满足第三范式:

S2(学号,姓名,所在系,年龄)

D(所在系,系主任)

C(课程号,课程名)

SC1(学号,课程号,成绩)

比第三范式更高级的是BC范式,它要求所有属性都不传递依赖于关系的任何候选键。

关系模式进行规范化的目的是使关系结构更加合理,消除存储异常,使数据冗余尽量小,便于进行插入、删除和更新等操作。