全国计算机等级考试四级详细复习纲要

第一章考试要点

一、计算机的发展

自从1946年2月现代电子计算机的鼻祖ENIAC(electronic numerical integrator and computer)在美国宾夕法尼亚大学问世以后，短短50年里，计算机技术经历了巨大的变革。

学术界经常使用器件(硬件)划分计算机的发展史，如第一代电子管计算机(1947～1957)，第二代晶体管计算机(1958～1964)，第三代集成电路计算机(1964～1972)，第四代大规模集成电路计算机(1972～)，目前提出了所谓的第五代(或新一代)计算机。

从1946年到50年代后期(1946～1957)为电子管计算机时期。计算机的元器件主要由电子管(vacuum tube)组成。其特点是体积庞大、功耗高、运算速度较低。如ENIAC占地170m 2 ，重达30t，功耗为140kW，有18000多个电子管，每秒钟能进行5000次加法计算。这一阶段，计算机主要用于军事、国防等尖端技术领域。除了ENIAC以外，1945年左右，冯?诺依曼等人在研制EDVAC(electronic discrete variable computer)时，提出了存储程序(stored-program)概念，奠定了以后计算机发展的基石。IBM公司1954年12月推出的IBM650是第一代计算机的代表。从20世纪50年代后期到60年代中期(1958～1964)为晶体管计算机时期。自从1947年晶体管(transistor)在贝尔实验室诞生后，引发了一场影响深远的电子革命。体积小、功耗低、价格便宜的晶体管取代了电子管，不仅提高了计算机的性能，也使计算机在科研、商业等领域内广泛地被应用。第二代计算机不仅采用了晶体管器件，而且存储器改用速度更快的磁芯存储器;与此同时高级编程语言和系统软件的出现，也大大提高了计算机的性能和拓宽了其应用领域。这一时期计算机的代表主要有DEC公司1957年推出的PDP-I、IBM公司于1962年推出的7094以及CDC公司1964年研制成功的CDC6600。1969年CDC公司研制的DCD7600平均速度达到每秒千万次浮点运算。

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

从20世纪70年代初期到70年代后期(1972～1978)为大规模集成电路(LSI)计算机时代。20世纪70年代初半导体存储器的出现，迅速取代了磁芯存储器，计算机的存储器向大容量、高速度的方向飞速发展。存储器芯片从1kbit，4kbit，16kbit，64kbit，256kbit，1Mbit，4Mbit发展到16Mbit(1992年)。

接着就进入了超大规模集成电路(VLSI)计算机时代。随着技术的日新月异，软件和通信的重要性也逐步上升，成为和硬件一样举足轻重的因素。同时系统结构的特点对计算机的性能也有巨大的影响(中断系统、Cache存储器、流水线技术等等)。实际上在第三代计算机以后，就很难找到一个统一的标准进行划分。

也可以从应用的观点来划分计算机的发展史。最早的应用是军事上的需要，如炮弹弹道计算，核武器的设计等;其次是广泛地用于科学计算，工程设计计算;第三阶段是大量用于管理，现在计算机的80%以上用于管理;再接着是计算机辅助设计(CAD)和辅助制造(CAM);进入90年代，计算机的应用已趋向于综合化和智能化，例如在一个企业里，计算机不仅用于科学计算、辅助设计和辅助制造，还用于辅助管理和辅助决策(MIS与DSS)，以及办公自动化(OA)等等，使设计、生产自动化和管理自动化融为一体，形成所谓计算机集成制造系统(CIMS-Computer Integrated Manufacturing System)，再发展下去就是工厂自动化(Factory Automation)或称无人工厂。DSS(Decision Support System)/ES(Expert System)利用人工智能(AI———Artifcation Inˉtelligence)技术，让计算机代替人判断、推理，寻找最优方案，以辅助决策者决策。目前更

流行的是认为计算机的发展经过了三次浪潮(wave)。

计算机的发展第一个浪潮是单个主机(Mainframe)的时期，以IBM360、370为代表的大型机的出现，其特点是以批处理为主，主要用于大规模科学计算。

第二次浪潮为客户机/服务器(Client/Server)的时期，这时期出现了小型机、微型机和局域网。其特点是多用户分时处理。

第三个浪潮是70～80年代的微型计算机PC(Personal Computer)的出现。现在正处于第三次浪潮，网络计算机的时期，即以网络为中心或以网络为基础的计算机时期。

目前计算机向综合的方向发展，将各种计算机的特点和优点综合起来，并结合了多媒体技术、通信技术等，把人类带入了网络社会。

二、计算机的分类及其应用

计算机分类的方法大致可分如下几种:

1.按信息的形式和处理方式分类

计算机按信息的形式和处理方式可分为数字计算机、模拟计算机以及数字混合计算机。

2.按计算机的用途分类

计算机按用途可分为通用计算机和专用计算机。

3.按计算机规模分类

计算机按规模可划分为巨型机、大型机、中型机、小型机、微型机等。计算机的应用如下:

(1)在科学计算中的应用

(2)在实时控制中的应用

(3)在数据处理中的应用

(4)计算机在辅助设计和辅助制造(CAD/CAM)中的应用

(5)办公自动化系统中的应用

三、计算机硬件结构

实际应用的计算机系统是由计算机硬件系统、软件系统以及通信网络系统组成的一个整体系统。计算机硬件系统是指构成计算机的所有实体部件的集合，通常这些部件由电路(电子元件)、机械等物理部件组成，它们都是看得见摸得着的，故通常称为“硬件”。计算机硬件结构也可以称为冯?诺伊曼结构，它由五大部件组成:主机部分由运算器、控制器、存储器组成，外设部分由输入设备和输出设备组成，其中核心部

分部件是运算器。

计算机硬件之间的连接线路分为网状结构与总线结构，这里主要介绍总线(BUS)结构。总线结构有如下几种形式:

1.以CPU为中心的双总线结构

所谓总线实际上是一组并行的导线，导线的数目和计算机字长相同，数据和指令通过总线传送。

2.以存储器为中心的双总线结构

3.单总线结构

主要部件功能:

1.运算器

运算器是完成二进制编码的算术或逻辑运算的部件。运算器由累加器(用符号L A )、通用寄存器(用符号L B )和算术逻辑单元(用符号ALU)组成，核心是算术逻辑单元。

2.存储器

在计算机中的存储器包括内存储器(又叫主存储器或随机存储器，简称内存或主存)、外存储器、只读存储器和高速缓冲存储器以及寄存器等。随机存储器是按地址存取数据的，若地址总线共有20条地址线(A 0 ～A 19 )，即有20个二进制位，可形成2 20 =1048576个地址(1兆地址)。

3.控制器

控制器由三大部件组成，它们是指令部件、时序部件和操作控制部件。

(1)指令部件

指令部件包括程序计数器PC，指令寄存器IR和指令译码器ID。

(2)时序部件

时序部件产生定时节拍，一般由时钟信号源、节拍发生器及微操作电路组成。

4.输出寄存器

输出寄存器用于存放输出结果，以便由它通过必要的接口(输出通道)，在输出设备上输出运算结果。

5.输入设备

目前主要通过CRT终端和键盘实现人机对话。磁性设备阅读机、光学阅读机等可作为输入设备

四、计算机软件的功能及分类

所谓软件是指为运行、维护、管理、应用计算机所编制的所有程序的总和。软件分为系统软件和应用软件。

系统软件包括计算机操作系统(Operation System)、计算机的各种管理程序、监控程序、调试程序、编辑程序以及各种语言的编译或解释程序等。应用软件是为解决各种实际问题而设计的程序。

1.操作系统

操作系统具有三大功能:管理计算机硬、软件资源，使之有效使用;组织协调计算机的运行，以增强系统的处理能力;提供人机接口，为用户提供方便。

操作系统具有的功能:

(1)作业操作。

(2)资源管理。

(3)中断处理。

(4)I/O处理。

(5)调度。

(6)错误处理。

(7)保护和保密处理。

(8)记帐。

操作系统的基本类型:

(1)批处理操作系统。

(2)分时系统。

(3)实时系统。

操作系统的管理功能主要内容:

(1)处理机管理。

(2)存储管理。

(3)文件管理。

(4)设备管理。

2.数据库管理系统

数据库管理系统既可以认为是一个系统软件也可以认为是一个通用的应用软件。目前有三种类型的数据库管理系统，故可存放三种模型的数据，这三种数据库管理系统分别为层次数据库、网状数据库和关系数据库。

3.计算机网络软件

计算机网络系统是通过通信线路连接的硬件、软件与数据集合的一个计算机系统。从硬件来说，除计算机作为网络的结点以外，还有如服务器(也可用一台计算机)，网络适配器，终端控制器以及网络连接器等硬件设备;从软件来说，有网络操作系统，网络通信及协议软件，网络数据库管理系统等。

4.高级语言及语言处理器

用户用高级语言编写的程序称源程序，源程序不能由计算机直接执行，必须翻译成机器能执行的语言———机器语言，这种翻译是由机器自动翻译的，“译员”称编译程序或编译器，当源程序输入计算机后，调用编译程序编译成机器语言(称目标程序)，然后执行。还有一种语言处理程序叫解释程序，输入一条语句，翻译一条。现在已出现了第4代语言(4GL)和计算机辅助软件工具CASE。

5.常用的通用软件

在数据处理、事务处理、报表处理中有许多通用软件，如字处理软件WPS、WORD，报表处理软件LOTUS1-2-3等。

五、计算机数据表示

1.二进位计数制

引入二进制数字系统的计算机结构和性能具有如下的优点:

(1)技术实现容易。

(2)二进制运算规则简单。

(3)计算机中二进制数的0、1数码与逻辑代数变量值0与1吻合，所以二进制同时可以使计算机方便地进行逻辑运算。

(4)二进制数和十进制数之间的关系亦不复杂。

2.进位计数制相互转换

十进制数转换成二进制数:

十进制数据转换为二进制数时，因整数部分与小数部分转换算法不同，需要分别进行。

全国计算机等级考试四级复习纲要一[2]

(1)整数转换方法———除基取余法

十进制整数除以2取余数作最低位系数k0 再取商的整数部分继续除以2取余数作高一位的系数，如此继续直到商为0时停止除法，最后一次的余数就是整数部分最高有效位的二进制系数，依次所得到的余数序列就是转换成的二进制数。因为除数2是二进制的基数，所以这种算法称作“除基取余”法。

(2)小数转换方法———乘基取整法

把十进制小数乘以2，取其积的整数部分作对应二进制小数的最高位系数k -1 再取积的纯小数部分乘以2，新得积的整数部分又作下一位的系数k -2 ，再取其积的纯小数部分继续乘2，?，直到乘积小数部分为0时停止，这时乘积的整数部分是二进制数最低位系数，每次乘积得到的整数序列就是所求的二进制小数。这种方法每次乘以基数取其整数作系数。所以叫乘基取整法。需要指出的是并不是所有十进制小数都能转换成有限位的二进制小数并出现乘积的小数部分0的情况，有时整个换算过程无限进行下去。此时可以根据要求并考虑计算机字长，取定长度的位数后四舍五入，这时得到的二进制数是原十进制数的近似值。

一个既有整数又有小数部分的数送入计算机后，由机器把整数部分按“除基取余”法，小数部分按“乘基取整”法分别进行转换，然后合并。任意进制数转换成十进制数:

任意一种进位计数制的数转换成十进制数的方法都是一样的。把任意进制数按权展开成多项式和的形式，把各位的权与该位上的数码相乘，乘积逐项相加，其和便是相应的十进制数。十进制数转换成任意进制数:

十进制数转换成任意进制数与十进制数转换成二进制数的方法完全相同，即整数部分用除基取余的算法，小数部分用乘基取整的方法，然后将整数与小数拼接成一个数作为转换的最后结果。

3.数的机器码表示

符号数的机器码表示:

(1)机器数和真值

数在计算机中的表示形式统称为机器数。机器数有两个基本特点，其一，数的符号数值化。实用的数据有正数和负数，因为计算机只能表示0、1两种状态，数据的正号“+”或负号“-”，在机器里就用一位二进制的0或1来区别。通常这个符号放在二进制数的最高位，称符号位，以0代表符号“+”，以1代表符号“-”，这样正负符号就被数值化了。因为有符号占据一位，数的形式值就不等于真正的数值，带符号位的机器数对应的数值称为机器数的真值。

机器数的另一个特点是二进制的位数受机器设备的限制。机器内部设备一次能表示的二进制位数叫机器的字长，一台机器的字长是固定的。字长8位叫一个字节(Byte)，现在机器字长一般都是字节的整数倍，如字长8位、16位、32位、64位。

符号位数值化之后，为能方便的对机器数进行算术运算、提高运算速度，计算机设计了多种符号位与数值一起编码的方法，最常用的机器数表示方法有三种:原码、反码和补码。

(2)原码表示法和反码表示法

一个机器数X由符号位和有数数值两部分组成。

(3)补码表示法(complement)

设计补码表示法的目的是:①使符号位能和有效数值部分一起参加数值运算从而简化运算规则，节省运算时间。②使减法运算转化成加法运算，从而进一步简化计算机中运算器的线路设计。计算机是一种有限字长的数字系统，因此都是有模运算，超过模的运算结果都将溢出。n位二进制整数的模是2 n 。

对于二进制数还有一种更加简单的方法由原码求得补码。①正数的补码表示与原码一样，[X]补 =[X]原②负数的补码是将原码符号位保持“1”之后其余各位取相反的码，末位加1便得到补码，即取其原码的反码再加1∶[X]补 =[X]反 +1。

真值+0和-0的补码表示是一致的，但在原码和反码表示中具有不同的形式。8位补码机器数可以表示-128，但不存在+128的补码与之对应，由此可知8位二进制补码能表示数的范围是-128～+127。应该注意，不存在-128的8位原码和反码形式。

根据互补的概念，一个补码机器数再求一次补就得到机器数的原码了。

定点数与浮点数:

(1)定点数(fixed-point number)

计算机处理的数据不仅有符号，而且大量的数带有小数，小数点不占有二进制一位而是隐含有机器数里某固定位置上。通常采用两种简单的约定:一种是约定所有机器数的小数点位置隐含在机器数的最低位之后，叫定点纯整数机器数，简称定点整数。

另一种约定所有机器数的小数点位置隐含有符号位之后、有效数值部分最高位之前，叫定点纯小数机器数，简称定点小数。

计算机采用定点数表示时，对于既有整数又有小数的原始数据，需要设定一个比例因子，数据按比例因子缩小成定点小数或扩大成定点整数再参加运算，结果输出时再按比例折算成实际值。n位原码定点整数的表示范围是-(2 n-1 -1)≤X≤2 n-1 -1，n位原码定点小数的表示范围是-(1-2 -(n-1) )≤X≤1-2 -(n-1) 。当机器数小于定点数的最小值时，被当作0处理，超出定点数的最大值时，机器无法表达，称作“溢出”，此时机器将停止运算，屏幕显示溢出警告。

定点数表示方法简单直观，不过定点数表示数的范围小，不易选择合适的比例因子，运算过程容易产生溢出。

(2)浮点数(floating-point number)

计算机采用浮点数来表示数值，它与科学计算法相似，把任意一个二进制数通过移动小数点位置表示

成阶码和尾数两部分:N=2 E ×S

其中:E———N的阶码(exponent)，是有符号的整数;

S———N的尾数(mantissa)，是数值的有效数字部分，一般规定取二进制定点纯小数正式。浮点数运算必须化成规格化形式。所谓规格化，对于原码尾数应使最高数字位S1 =1，如果不是1，且尾数不是全为0时就要移动尾数直到S1 =1，阶码相应变化，保证N值不变。如果尾数是补码，当N是正数时，S1 必须是1，而N是负数时，S1 必须是0，才称为规格化的形式。

4.数字编码

十进制数在机内转换成二进制数时，有时也以一种中间数字编码形式存在，它把每一位十进制数用四位二进制编码表达，每一组只表达0～9的数值运算时，有专门的线路在每四位二进制间按“十”进位处理，故称为二进制编码的十进制数———BCD码(Binary Coded Decimal(或称二—十进制数。其编码种类很多，如格雷码、余3码等，最常用的叫8421BCD码，4个二进制位自左向右每位的权分别是8、4、2、1。0～9的8421码与通常的二进制一样进位，十分简单，当计数超过9时，需要采取办法自动向十进制高位进一，即要进行“十进制调整”才能得到正确结果。

5.校验码

由于器件质量不可靠、线路工艺不过关、远距离传送带来的干扰或受来自电源、空间磁场影响等因素，使得信息在存取、传送和计算过程中难免会发生诸如“1”误变为“0”的错误，计算机一旦出错，要能及时检测并纠正错误，其中一种方法是对数据信息扩充，加入新的代码，它与原数据信息一起按某种规律编码后具有发现错误的能力，有的甚至能指出错误所在的准确位置使机器自动纠正，能起这种作用的编码叫“校验码”(check code)。

奇偶校验码:

将每个数据代码扩展一个二进位作校验位(parity bit)，这个校验取0还是取1的原则是:若是奇校验(odd parity)，编码是含“1”的个数连同校验位的取值共有奇数个“1”;若是偶校验(even parity)，连同校验位在内编码里含“1”的个数是偶数个。

交叉校验:

计算机进行大量字节传送时一次传送几百甚至更多字节组成的数据块，如果不仅每一个字节有一个奇偶校验位———称横向校验，而且全部字节的同一位也设置了一个奇偶校验位———称纵向校验，对数据块代码的横向纵向同时校验，这种情况叫交叉校验。

循环冗余校验码———CRC码(Cyclic Redundancy Check):

计算机信息传向远方终端或传到另一个计算中心时，信息沿一条通信线路一位位传送，这种通信方式叫串行通信。循环冗余码(简称CRC码)就是一种检验能力很强，在串行通信中广泛采用的校验编码。

(1)CRC码

串行传送的信息M(X)是一串k位二进制序列，在它被发送的同时，被一个事先选择的“生成多项式”

相除，“生成多项式”长r+1位，相除后得到r位余数就是校验位，它拼接到原k位有效信息后面即形成CRC码。CRC码到达接收方时，接收方的设备一方面接收CRC码，一方面用同样的生成多项式相除，如果正好除尽，表示无信息差错，接收方去掉CRC码后面r位校验，收下k位有效信息;当不能除尽时，说明有信息的状态位发生了转变，即出错了。一般要求重新传送一次或立即纠错。

(2)CRC码计算

传送信息时生成CRC码以及接收时对CRC码校验都要与“生成多项式”相除，这里除法是“模2运算”，即二进位运算时不考虑进位和借位。作模2除法时，取商的原则是当部分余数首位为1时商取1，反之商取0，然后按模2减，求部分余数。这个余数不计高位。当被除数逐位除完时，最后余数的位数比除数少一位。该余数就是校验位。它拼接在有效信息后面组成CRC码。因为校验位扩充了传送部分的代码，所以这是一种基于“冗余校验”的思想的校验办法。

(3)生成多项式

CRC码是M(X)除以某一个预先选定的多项式后产生的，所以这个多项式叫生成多项式。并不是任何一个r+1位的编码都可以作生成多项式用，它应能满足当任何一位发生传送错误时都能使余数不为0，并且不同位发生错误时应当使余数也不同，这样不但能检错而且能推断是哪一位出错，从而有利准确的纠错。有两个生成多项式，其检错率很高。

X 16 +X 15 +X 2 +1

X 16 +X 12 +X 6 +1

6.非数值数据的表示方法

计算机中数据的概念是广义的，机内除有数值数据之外，还有文字、符号、图象、语言和逻辑信息等等，因为它们也都是0、1形式存在，所以称为非数值数据。

(1)字符数据

字符数据主要指数字、字母、通用符号、控制符号等，在机内它们都被变换成计算机能够识别的二进制编码形式。国际上被普遍采用的一种编码是美国国家信息交换标准代码(American Standard Code for Information Interchange)，简称ASCII码。ASCII码选择了四类共128种常用的字符:①数字0～9。②字母。③通用符号。④动作控制符。

(2)逻辑数据

逻辑数据是指计算机不带符号位的一位二进制数。

逻辑数据在计算机中虽然也是“0”或“1”的形式，但是与数值有很大区别:

①逻辑数据的取值只有“0”和“1”两个值，不可能再有其他值，而数值数据与1的不同组合可以反映很多不同数值。

②逻辑数据的“0”和“1”代表两种成对出现的逻辑概念，与一般数学中代表“0”和“1”的数值概

念截然不同。

③逻辑数据和逻辑数据运算可以表达事物内部的逻辑关系，而数值数据表达的是事物的数量关系。汉字:

(1)汉字字音编码

(2)汉字字形编码

(3)汉字音形编码

(4)电报码

(5)整字编码为了能在不同的汉字系统之间交换信息、高效率高质量共享汉字信息，近年来国家推出了一系列有关中文信息处理的标准。比如1981年我国制定推行的GB2312-80国家标准信息交换用流字编码字符集(基本集)———简称国标码，以及若干辅助集。国标码收集、制定的基本图形字符有7千余个，其中常用汉字3755个，次常用汉字3008个，共6763个汉字，还有俄文字母、日语假名、拉丁字母、希腊字母、汉语拼音，每字节内占用7bit信息，最高位补0，例如汉字“啊”的国际码，前一字节是01100000，后一字节是00100001，编码为3021H。

汉字内部码是汉字在计算机内部存储、运算的信息代码，内部码的设计要求与西文信息处理有较好的兼容性，当一个汉字以某种汉字输入方案送入计算机后，管理模块立刻将它转换成两字节长的GB2312-80国标码，如果给国标码的每字节最高位加“1”，作为汉字标识符，就成为一种机器内部表示汉字的代码———汉字内部码。汉字内部码的特点十分明显:

①汉字内部码结构简短，一个汉字内部码只占两个字节，两字节足以表达数千个汉字和各种符号图形，且又节省计算机存储空间。

②便于和西文字符兼容。西文字符的ASCII码占一个字节，两字节的汉字内码可以看成是它扩展的字符代码，在同一个计算机系统中，只要从最高位标识符就能区分这两种代码。标识符是“0”，即是ASCII码;标识符是“1”，则是汉字内部码。

7.语音识别及语言表示原理

语音产生机理的研究表明，每一种语言的语音都有自己特定的音素特征，语音是不同频率振动的结果。分析语音的音素特点，找出音素的基频和高次频率优分，就能在计算机中建立发音系统的模型，在实施中对语音采样，通过滤波器分解提取频率信息，由模/数转换设备转换成数字输入计算机，与机内的语言模型比较，由此达到识别语音的目的。与此相反，如果选择已知音素的参数，应用语音系统模型，就能得到指定的音素，进一步按照一定的规则合成语言。

六、运算器

1.运算器的组成

多功能算术/逻辑运算单元(ALU):

(1)基本思想

(2)逻辑表达式

对一片ALU来说，可有三个进位输出。其中G称为进位发生输出，P称为进位传送输出。在电路中，多加这两个进位输出的目的是为了便于实现多片(组)ALU之间的先行进位，为此，还需一个配合电路，它称为先行进位发生器(CLA)。

内部总线:

根据总线所处位置，总线分为内部总线和外部总线两类。内部总线是指CPU内各部件的连线，而外部总线是指系统总线，即CPU与存储器、I/O系统之间的连线。

按总线的逻辑结构来说，总线可分为单向传送总线和双向传送总线。所谓单向总线，就是信息只能向一个方向传送。所谓双向总线，就是信息可以向两个方向传送。换句话说，总线既可以用来发送数据，也可以用来接收数据。

总线的逻辑电路往往是三态的，即输出电平有三种状态:逻辑“1”、逻辑“0”和“浮空”状态。

2.运算器的基本结构

运算器包括ALU、阵列乘除器件、寄存器、多路开关或三态缓冲器、数据总线等逻辑部件。现代计算机的运算器大体有如下三种结构形式。①单总线结构的运算器②双总线结构的运算器③三总线结构的运算器

七、控制器

1.控制器在CPU中的位置

中央处理器(CPU)由两个主要部分———控制器及运算器组成。其中程序计数器、指令寄存器、指令译码器、时序产生器和操作控制器等组成了控制器。它是对计算机发布命令的“决策机构”，协调和指挥整个计算机系统的操作，因此，它处于CPU中极其重要的位置。在CPU中，除算术逻辑单元(ALU)及累加器外，尚有下列逻辑部件:

(1)缓冲寄存器(DR)

缓冲寄存器用来暂时存放由内存储器读出的一条指令或一个数据字;反之，当向内存存入一条指令或一个数据字时，也暂时将它们存放在这里。缓冲寄存器的作用是:①作为CPU和内存、外部设备之间信息传送的中转站;②补偿CPU和内存、外部设备之间在操作速度上的差别;

③在单累加器结构的运算器中，缓冲寄存器还可兼作为操作数寄存器。

(2)指令寄存器(IR)指令寄存器用来保存当前正在执行的一条指令。指令划分为操作码和地址码字段，它们由二进制数字组成。为执行任何给定的指令，必须对操作码进行译码，以便指出所要求的操作。指令寄存器中操作码字段的输出就是指令译码器的输入。操作码一经译码后，即可向操作控制器发生具体操作的特定信号。

(3)程序计数器(PC)

为了保证程序能够连续地执行下去，CPU必须具有某些手段来确定下一条指令的地址。而程序计数器(PC)正是起到这种作用，所以通常又称其为指令计数器。

(4)地址寄存器(AR)

地址寄存器用来保存当前CPU所要访问的内存单元的地址。由于在内存和CPU之间存在着操作速度上的差别，所以必须使用地址寄存器来保持地址信息，直到内存读/写操作完成为止。

(5)累加寄存器(AC)

累加寄存器AC通常简称为累加器。它的功能是:当运算器的算术/逻辑单元(ALU)执行全部算术和逻辑运算时，为ALU提供一个工作区。例如，在执行一个加法前，先将一个操作数暂时存放在AC中，再从存放中取出另一个操作数，然后同AC的内容相加，所得结果送回AC中，而AC中原有的内容随即被破坏。顾名思义，累加寄存器用来暂时存放ALU运算的结果信息。显然，运算器中至少要有一个累加器寄存器。

由于运算器的结构不同，可采用多个累加寄存器。

(6)状态寄存器(SR)

状态寄存器保存由算术指令和逻辑指令运行或测试结果建立的各种状态码内容。

(7)操作控制器

操作控制器的功能，就是根据指令操作码和时序信号，产生各种操作控制信号，以便正确地建立数据通路，从而完成取指令和执行指令的控制。

全国计算机等级考试四级复习纲要一[3]

根据设计方法不同，操作控制器可分为组合逻辑型、存储逻辑型、组合逻辑与存储逻辑结合型三种。第一种称为常规控制器，它是采用组合逻辑技术来实现的;第二种称为微程序控制器，它是采用存储逻辑来实现的;第三种称为PLA控制器，它是吸收前两种的设计思想来实现的。

(8)时序产生器

CPU中除了操作控制器外，还必须有时序产生器，因为计算机高速地进行工作，每一动作的时间是非常严格的，不能有任何差错。时序产生器的作用，就是对各种操作实施时间上的控制。

2.控制器的组成

运算器包括ALU、累加器、数据缓冲寄存器和状态寄存器，而控制器的核心是操作控制器，围绕它的有程序计数器(PC)、指令寄存器(IR)、指令译码器(ID)和时序产生器。

八、存储器

1.存储器的基本组成及其读写操作

(1)存储器的基本组成部分

主存储器由存储体、地址译码电路、驱动电路、读写电路和控制电路等组成。主存储器的主要功能是:①存储体:是信息存储的集合体，由某种存储介质按一定结构组成的存储单元的集合。通常是二维阵列组织，是可供CPU和计算机其他部件访问的地址空间。

②地址寄存器、译码电路与驱动器:即寻址系统，将CPU确定的地址先送至地址寄存器中，然后根据译码电路找到应访问的存储单元。在存储与译码器之间的驱动器的功能是减轻译码线驱动负载能力。由于一条译码线需要与它控制的所有存储单元相联，其负载很大。需要增加驱动器，以译码线连接驱动器的输入端，由驱动器的输出端控制连接在译码线上的所有存储单元。

③读写电路与数据寄存器:根据CPU的命令，将数据从数据寄存器中写入存储体中特定的存储单元或将存储体中指定单元的内容读到数据寄存器中。

④控制电路:接收CPU传来的控制命令，经过控制电路一系列的处理，产生一组时序信号控制存储器的操作。

在存储器的组成中，存储体是核心，其余部分是存储的外围线路。不同的存储器都是由这几部分组成，只是在选用不同的存储介质和不同的存取方式时，各部分的结构与工作方式略有变化。

(2)存储体阵列

计算机存储器中存储的是“0”和“1”的信息，每一个能存取一位二进制并能保持两种状态的元件称为记忆元件。若干记忆元件组成存储单元，一个存储单元能够存取一个或几个字节的二进制信息。每个存储单元都有一个地址编号，用以唯一标识存储单元的位置。信息按地址存入指定的存储单元中，按地址从指定的存储单元中取出。存储单元的集合称为存储体。由于存储体中存储单元的每个二进制位必须并行工作，因此将存储单元按其地址的顺序组成存储阵列。

(3)存储器的地址译码系统

CPU要访问存储单元的地址由地址总线输入到地址寄存器中。地址译码器将地址转换为对应地址线(字线)上的控制信号，以表示选中某一单元，并驱动相应的读写电路，完成对存储单元的读写操作。

地址译码为两种方式:一种是单译码方式，仅有一个译码器。译码器输出的每条译码线对应一个存储单元。如地址位数N=10，即译码器可以有2 10 =1024种状态，对应有1024条译码线(字线)即1024个存储单元。另外一种是双译码方式，将译码器分成X向和Y向两个译码器，通过双译码器的相互作用确定存储单元的地址。

设地址长度n仍为10，将其中的前5位输入到X地址译码器中，译出X0 到X31 译码线，分别选择0～31行。将后5位输入到Y地址译码器中译出Y0 到Y31 译码线，分别选择0～31列。X向译码器和Y向译码器引出的地址线都是2 5 =32条。若采用X向和Y向交叉选择，可以选择从存储单元(0，0)至(31，31)共2 5 ×2 5 =1024个存储单元地址。即同样可以提供1024种状态，而地址线只需要64条，比单译码

器节省93.75%的地址线。

(4)存储器的读写操作

在CPU向存储体发生读操作命令时，首先由CPU将相应存储单元的地址码送至地址寄存器中;地址译码器将地址寄存器中的地址编码译成相应地址线(字线)的高电位，标志指定的存储单元;然后在CPU的统一控制下，由控制电路将读命令转换成读写电路的操作，执行将指定存储单元的内容传送到数据寄存器的操作，完成了整个存储器读的操作。存储器写的操作与读的操作相类似。

不同类型的存储器根据其特点有不同的读写操作控制电路、控制机构、读写电路及地址译码器，但它们的基本操作原理大同小异。

2.RAM的结构、组织及其应用

半导体存储器有体积小、存取速度快、生产制造易于自动化等特点，其性能价格比远远高于磁芯存储器，因而得到广泛的应用。

半导体存储器的种类很多，就其制造工艺可以分成双极型半导体存储器和金属-氧化物-半导体存储器(简称MOS型存储器)。MOS型存储器按其工作状态又可以分为静态和动态两种。动态存储器必须增设恢复信息的电路，外部线路复杂。但其内部线路简单，集成度高，价格较静态存储器便宜。因此经常用做大容量的RAM。

静态存储器和动态存储器的主要差别在于:静态存储器存储的信息不会自动消失，而动态存储器存储的信息需要在再生过程的帮助下才能保持。但无论双极型或MOS型存储器，其保持的信息将随电源的撤消而消失。

(1)RAM的组织

半导体RAM芯片是在半导体技术和集成电路工艺支持下的产物。一般计算机中使用的RAM芯片均是有自己的存储体阵列、译码电路、读写控制电路和I/O电路。

①RAM的并联

为扩展存储器的字长，可以采用并联存储器芯片的方式实现。

②RAM的串联

为扩展存储器的存储单元数量，可以采用多个芯片地址串联的方式解决。

③地址复用的RAM组织

随着大规模集成电路技术的发展，使得一块存储器芯片能够容纳更多的内容。其所需地址线随之增加，为了保持芯片的外部封装不变，一般采用地址复用的技术，采用地址分批送入的结构保证不增加芯片的地址引脚。

(2)RAM的实际应用

由于一个存储器的芯片一般不能满足使用的要求，所以通常将若干个存储器芯片按串联和并联的两种方式相结合连接，组成一定容量和位数的存储器。

如果设计的存储器容量有x字，字长为y，而采用的芯片为N×M位。要组成满足字长要求的存储器所需芯片数为:y/M。根据容量要求，组成要求容量的RAM所需芯片数为:(x/N)×(y/M)。

3.ROM的工作原理及其应用

使用时只读出不写入的存储器称为只读存储器(ROM)。ROM中的信息一旦写入就不能进行修改，其信息断电之后也仍然保留。一般用于存放微程序、固定子程序、字母符号阵列等信息。ROM和RAM相比，使用时不需写入、再生和刷新等操作，所以其电路比较简单，但同样有地址译码器、数据读出电路等。制作ROM的半导体材料有二极管、MOS电路和双极型晶体管等。因制造工艺和功能不同，一般分为普通ROM、可编程ROM(PROM)、可擦写可编程ROM(EPROM)和电可擦写可编程ROM(EEPROM)等。

(1)ROM的工作原理

一般的ROM使用掩模式ROM。这类ROM由生产厂家做成，用户不能加以修改。

掩模ROM的特点是其存储内容出厂时由生产厂家一次制成，用户不能对其内容进行修改，而依赖于生产厂家，这种RAM适用于定型批量制作。在实际使用过程中，部分用户希望自己根据需要填写ROM的内容，因此产生可编程ROM(PROM)。PROM与掩模ROM的主要区别是PROM在出厂时其内容均为“0”或“1”，用户在使用前按照自己的需要利用工具将编码写入PROM中，一次写入不可修改。PROM的使用相当于由用户RAM生产中的最后一道工序———向RAM中写入编码，其余同掩模RAM的使用完全相同。

(2)EPROM和EEPROM的工作原理

为了适应程序调试的要求，针对一般PROM的不可修改特性，设计出可以多次擦写的可编程ROM(EPROM)。其特点是可以根据用户的要求用工具擦去RAM中原有的存储内容，重新写入新的编码。擦除和写入可以根据用户的要求用工具擦去RAM中原有的存储内容，重新写入新的编码。擦除和写入可以多次进行，其信息的内容同样不会因断电而丢失。最常见的EˉPROM是UVEPROM，其存储元件常用浮置栅型MOS管组成。出厂时全部置“0”或“1”，由用户通过高压脉冲写入信息。擦写时通过其外部的一个石英玻璃窗，利用紫外线的照射，使浮栅上的电荷获得高能而泄漏，恢复原有的全“0”或“1”状态，允许用户重新写入信息。平时窗口上必须贴有不透明胶纸，以防光线进入而造成信息流失。

另有一种EPROM是通过电气方法擦除其中的已有内容，也称为电可擦写编程ROM(EEPROM)。

4.外存储器的工作原理

外存储器是指那些不能被CPU直接访问的，读取速度较内存慢，容量比内存大，通常用来存放不常用的程序和数据的存储器。磁带、磁盘存储器是现今最常用的外存，因其利用磁表面介质存储数据，通常也称为磁表面存储器。而光盘是外存发展的方向，有必要了解它们的原理和应用。

(1)磁盘存储器

磁盘存储器具有容量大，存取速度高(相对其他种类外存储器)的特点，因而在各种类型的计算机中普遍被用做主要的外存储器。磁盘存储器避免了磁带存储的缺点。磁盘存储器将磁性材料涂粘在以某种材料为主的盘形圆片上，用若干封闭的圆形磁道代替了磁带的长形磁道。使用时，通过磁盘面的高速旋转代替磁带的直线运动，减少寻找特定位置的时间。

磁盘存储器由磁盘、磁头、定位系统和传动系统等部分组成，一般也将这些部件统称为磁盘驱动器。根据盘片的基本组成材料将磁盘分为硬盘和软盘两种。所谓硬盘是指由金属材料制成一定厚度的盘片基体，这些盘片一般组合成盘片组构成硬盘驱动器的存储主体。

软盘和硬盘盘片记录信息的方式相同，都是将每个盘面由外向内分成若干个磁道，每个磁道也划分为多个扇区，信息以扇区为单位存储。

扇区是磁盘存放信息的最小物理单位。扇区包括头空、序标、数据区、检验字段和尾空等几个部分。通常对磁盘进行的所谓格式化操作就是在磁盘上划分磁道、扇区及扇区内各特定区域，刚出厂的磁盘上没有这些划分，所以必须在格式化后才能使用。磁盘区域的划分随计算机系统而不同，其存储容量也有较大的差别。但可以通过查阅计算机系统相应的说明掌握磁盘容量的数据。计算一个磁盘容量的公式是:

磁盘存储容量=盘面数×每盘面磁道数×每磁道扇区数×每扇区存储容量

(2)光盘存储器

所谓光盘(CD)是利用光学原理读写信息的存储器。由于光盘的容量大、速度较快、不易受干扰等特点，光盘的应用愈来愈广泛。

光盘系统一般是由光学、电气和机械部件组成。

从结构上看光盘存储器同磁盘存储基本相同，两者均有存储信息的盘片、机械驱动部件、定位部件和读写机构。不同的是后者利用磁性原理存储信息，利用磁头存取信息;而前者是利用光学原理存储信息并用光学读写头来存取这些信息。

光盘本身是靠盘面上一些能够影响光线反射的表面特征存储信息，例如现在常用的只读光盘(CD-ROM)上利用光盘表面的凹凸不平表示“0”和“1”。以CD-ROM为例，读取数据时，由机械驱动部件和定位部件负责确定读取的位置。激光器发出激光经光学线路至聚焦透镜射向光盘表面，表面的凹凸不平造成反射光的变化，利用数据光检测器将这些变化转换为数据“0”和“1”的电信号传输到数据输出端，整个读取工作完成。其他类型光盘的写入过程大体与此相同，唯一的差别是数据自数据输入端传来。

一般将光盘存储器分为只读式(readonly)、一次写入式(writeonce)和可擦式(erasable)或可逆式(reversible)三种。只读式光盘利用材料表面的凹凸不平的特征记录信息，在出厂前由生产厂家将有关信息存放到光盘上。对于一次写入式光盘，用户可以利用会聚的激光束在光盘表面照射使材料发生永久性变化而记录信息。这种光盘现已普遍用于多媒体系统。可擦式光盘利用激光在磁性材料上或相变材料上实现信息的存储和擦除。

光盘存储器的记录密度高，存储容量大，一片5.25英寸大小的一次写入式光盘可以存储680MB的信息，其容量远远大于外形同样大小的软磁盘。光盘信息的保存时间也比磁盘的长。目前影响光盘普遍应用的主要原因是光盘存储器的读写速度慢和光盘驱动器的成本高。随着技术的进步，以上问题是可以解决的。因此光盘存储器有广泛的应用前景。

5.虚拟存储的概念、作用和工作过程

(1)虚拟存储的概念、作用

一般将由主存和部分辅存组成的存储结构称为虚拟存储器，其对应的存储地址称为虚拟地址(逻辑地址)，其对应的存储容量称为虚拟容量。将实际主存地址称为物理地址或实地址，主存的容量称为实存容量。

当用虚拟地址访问主存时，系统首先查看所用虚拟地址对应的单元内容是否已装入主存。如果在主存中，可以通过辅助软、硬件自动把虚拟地址变成主存的物理地址后，对主存相应单元进行访问。如果不在主存中，通过辅助的软、硬件将虚拟地址对应的内容调入主存中，然后再进行访问。因此，对虚拟存储器的每次访问都必须进行虚实地址的变换。

全国计算机等级考试四级复习纲要一[4]

虚拟存储器的作用是扩大整个主存的容量，允许在程序中使用比主存容量大得多的虚拟存储器。同时可以减轻人们编程中对程度进行分块的苦恼，从而提高软件开发的效率。虚拟存储器是实现利用小容量的主存运行大规模的程序的一种有效的办法。尽管实现虚拟存储要增加一些额外的投资和软件开销，虚拟存储技术在各种计算机系统中仍得到了广泛的应用。虚拟存储器必须建立在主存-辅存结构上，但一般的主存-辅存系统并不一定是虚拟存储器，虚拟存储器与一般的主存-辅存系统的本质区别是:

①虚拟存储器允许人们使用比主存容量大得多的地址空间来访问主存，非虚拟存储器最多只允许人们使用主存的整个空间，一般只允许使用操作系统分配的主存中的某一部分空间。

②虚拟存储器每次访问主存时必须进行虚、实地址的变换，而非虚拟存储系统则不必变换。

(2)虚拟存储的工作原理

虚拟存储技术，实际上是将编写程序时所用的虚拟地址(逻辑地址)转换成较小的物理地址。在程序运行时随时进行这种变换。为了便于主存与辅存之间信息的交换，虚拟存储器一般采用二维或三维的复合地址格式。采用二维地址格式时，将整个存储器划分为若干页(或段)，每个页(或段)又包括若干存储单元。采用三维地址格式时将整个存储空间分为若干段，每段分为若干页，每页又包括若干存储单元。根据地址格式不同，虚拟存储器分为:页式虚拟存储器、段式虚拟存储器和段页式虚拟存储器。

在虚拟存储器中逻辑地址与物理地址之间的对应称为地址映象。通常有三种地址映象的方式:全相联映象、直接映象和组相联映象。

①全相联映象

任一逻辑页能映象到实际主存的任意页面位置称为全相联映象，通常利用页表法进行地址间的变换。

②直接映象

每个逻辑页只能映象到一个特定页面的方式称为直接映象。如主存实际有2 P 页，虚拟存储器的逻辑空间有2 P 页，则将逻辑空间按物理空间大小分为2 P -P块，块内各页只能映象到主存的相应页中。即所有各块的第0页对应主存的第0页，各块的第n页对应主存的第n页。若程序需要轮流使用第i块和第j

块的第m页，只能将两页交替在主存和辅存之间调入调出，形成存储页面的“抖动”。

③组相联映象 组相联映象方法是先按直接映象方法将虚拟存储空间(逻辑空间)分成若干块，在主存和逻辑空间中的各块内划分为若干组，每个组间按直接映象方法控制。可以这样理解，如果将组相联映象方法中的组按直接映象方法的页来看待，组相联方法与直接映象方法相同，逻辑空间各组内的页只能与对应的物理空间组相联。但在组内各页与物理空间的页面之间采用全相联映象方法处理。因此，可以认为组相联映象是全相联映象和直接映象方法的结合。6.缓冲技术使用

缓冲技术就是为缓解慢速设备对整个计算机系统速度的影响，在计算机的某些部件中划定一块区域，模拟慢速设备的操作，将对慢速设备的操作先存放在此区域中，其他部件完成这一操作后可以继续其他工作，而慢速设备可以用自己的速度逐渐完成相应的操作。做为中间缓冲的区域称为缓冲区，相应的技术称为缓冲技术。

在整个存储体系的组织中，缓冲技术成为解决容量与速度之间矛盾的主要方法。实际上在计算机系统中缓冲技术解决了许多难题，促进了计算机系统的发展。在存储体系中，缓冲技术主要体现在Cache的应用和磁盘缓冲的使用。

(1)Cache的原理和作用Cache的工作原理基于对大量典型程序运行实例的分析。分析结果表明，在较短的时间间隔内，由程序产生的地址往往集中在存储器逻辑地址空间很小的范围内。指令地址的分布又是连续的，加上循环程序和子程序段的重复执行，对这些地址的访问自然具有时间上集中分布的倾向。这种对局部范围的存储器地址频繁访问，对此范围外的地址访问甚少的现象称为程序访问的局部性。程序访问的局部性为Cache的引入提供了理论依据。

Cache是缓冲技术在存储体系中的一个具体应用。Cache处于主存与CPU之间，负责解决主存与CPU之间速度的协调问题。Cache中存放着主存的一部分副本(主存中的部分内容)，当存储器接到有关读取指令时，先在Cache中查找此信息是否存在，若有则不经主存直接从Cache中取出;否则直接从主存中取出，同时写入Cache，以备再次使用。当向存储器写入内容时，由辅助硬件采用各种方法保证主存中的内容同Cache中的内容保持一致。

为保证写入时两者内容一致的方法有:①将内容同时写入主存和Cache;②数据仅写入主存，若Cache中有此内容则将其释放;③数据只写入Cache，在规定的时候将修改过的Cache的内容写入主存。

Cache的主要特点是:①存取速度快，一般Cache的速度完全可以跟上CPU的运算速度;②存储量小，由于Cache的速度快，其价格也相当昂贵，因此为保证整个存储器的性能价格比，一般采用适当容量的Cache，其容量小于主存。

(2)磁盘缓冲技术

磁盘缓冲技术的目的是减少由于主、辅存之间的速度差异对计算机总体性能的影响。磁盘是存储系统中的辅助部分，其主要作用是用来存储不常用的数据和程序等信息，减轻对主存容量的需求压力。由于磁盘中的信息不能被计算机的其他部件直接调用，因此在信息的输入/输出过程中必须在主存中开辟一定的空单位和为与磁盘上信息交换的中间过渡区域称为磁盘缓冲区。如从键盘(输入设备)向磁盘中输入一个信息，此信息必须通过总线先输入到主存中的特定区域中，通过程序控制将信息存放到主存中对应于磁盘输入/输出的一个特定区域内，然后将此信息转存到磁盘上。一般将主存中对应于磁盘的特定区域称为磁盘缓冲区。

为了提高磁盘的读写速度，操作系统一般根据程序运行的需要设置磁盘缓冲区的大小及输入/输出操作。同Cache技术相类似，不立即覆盖磁盘缓冲区的内容，当系统需要继续读入磁盘中的信息时，首先检查磁盘缓冲区中是否有所需要的信息，若有则直接使用，否则根据信息的位置将磁盘上特定扇区的内容调入磁盘缓冲区后再加以使用。这样可以提高磁盘的信息读取速度，减少因磁盘存取速度慢对系统整体性能的影响。

九、输入与输出系统

1.输入输出系统的发展

输入输出系统的发展大致分为五种方式，即程序控制的输入输出方式、中断方式，DMA方式、输入/输出通道方式和I/O处理机等五种方式。

程序查询方式和程序中断方式适用于数据传输率比较低的外部设备。而DMA方式、通道方式和I/O处理机方式适用于数据传输率比较高的设备。目前，小型机和微型机大都采用程序查询方式、程序中断方式和DMA方式。通道方式I/O处理机方式大都用在中、大型计算机中。为了介绍方便，我们把通道方式和I/O处理机方式视为一种方式。

2.程序查询方式

程序查询方式又叫程序控制I/O方式。在这种方式中，数据在CPU和外部设备之间的传送完全靠计算机程序控制，是在CPU主动控制下进行的，当输入/输出时，CPU暂停执行主程序，转去执行输入/输出的服务程序，根据服务程序中的I/O指令进行数据传送。

这是一种最简单、最经济的输入/输出方式。它只需很少的硬件，因此几乎所有的机器都具有程序查询方式。特别是在微、小型机中，常用程序查询方式来实现低速设备的输入输出管理。

3.程序中断方式

“中断”概念的提出，是计算机系统结构设计中的一个重大变革。在程序中断方式中，某一外设的数据准备就绪后，它“主动”向CPU发请求中断的信号，请求CPU暂时中断目前的工作而进行数据交换。当CPU响应这个中断时，便暂停运行主程序，并自动转移到该设备的中断服务程序。当中断服务程序结束以后，CPU又回到原来的主程序。其原理和调用子程序相仿，不过，这里要求转移到中断服务子程序的请求是由外部设备发出的。中断方式特别适合于随机出现的服务。

4.DMA方式

(1)DMA方式的基本概念

直接访问内存DMA方式，是一种完全由硬件执行I/O交换的工作方式。在这种方式中，DMA控制器从CPU中完全接管对总线的控制，数据交换不经过CPU，而直接在内存储器和I/O设备之间进行。DMA方式一般用于高速地传送成组的数据。DMA控制器将向内存发出地址和控制信号、修改地址、对传送的字的个数计数，并且以中断方式向CPU报告传送操作的结束。DMA方式的主要优点是速度快。由于CPU根本不参加传送操作，因此就省去了CPU取指令、取数、送数等操作。在数据传送过程中，也不象中断方式那样，要进行保存现场、恢复现场之类的工作。内存地址修改、传送字个数的计数等，也不是由软件实现，而是用硬件线路直接实现的。DMA的种类很多，但各种DMA至少能执行以下一些基本操作:①从

外部设备发出DMA请求;

②CPU响应请求，把CPU工作改成DMA操作方式，DMA控制器从CPU接管总线的控制;③由DMA控制器对内存寻址，即决定数据传送的内存单元首地址及数据传送个数的计数，并执行数据传送的操作;

④向CPU报告DMA操作的结束。

(2)DMA技术的出现，使得外部设备可以通过DMA控制器直接访问内存，与此同时，CPU可以继续执行程序。那么DMA控制器与CPU怎样分时使用内存呢?通常采用以下三种方法:①停止CPU访问;②周期挪用;

③DMA与CPU交替访问。

(3)基本的DMA控制器

一个DMA控制器实际上是采用DMA方式的外部设备与系统总线之间的接口电路。这个接口电路是在中断接口的基础上再加DMA机构组成。习惯上将DMA方式的接口电路称为DMA控制器。

①内存地址计数器

用于存放内存中要交换的数据地址。在DMA传送前，需通过程序将数据在内存中的起始位置(首地址)送到内存地址计数器。而当DMA传送时，每交换一次数据，将地址计数器加“1”，从而以增量方式给出内存中要交换的一批数据的地址。

②字计数器

用于记录传送数据块的长度(多少字数)。其内容也是在数据传送之间由程序预置，交换的字数通常以补码形式表示。在DMA传送时，每传送一个字，字计数器就加“1”，当计数器溢出即最高位产生进位时，表示这批数据传送完毕，于是引起DMA控制器向CPU发出中断信号。

③数据缓冲寄存器

用于暂存每次传送的数据(一个字)。当输入时，由设备(如磁盘)送往数据缓冲寄存器，再由缓冲寄存器通过数据总线送到内存。反之，输出时，由内存通过数据总线送到数据缓冲寄存器，然后再送到设备。

④“DMA请求”标志

每当设备准备好一个数据字后给出一个控制信号，使“DMA”请求标志置“1”。该标志置位后向“控制/状态”逻辑发出DMA请求，后者又向CPU发出总线使用权的请求(HOLD)，CPU响应此请求后发回响应信号HLDA，“控制/状态”逻辑接收此信号后发出DMA响应信号，使“DMA请求”标志复位，为交换下一个字做好准备。

⑤“控制/状态”逻辑它由控制和时序电路，以及状态标志等组成，用于修改内存地址计数器和字计数器，指定传送类型(输入输出)，并对“DMA请求”信号和CPU响应信号进行协调和同步。⑥中断机构

当字计数器溢出时(全0)，意味着一组数据交换完毕，由溢出信号触发中断机构，向CPU提出中断报

告。这里的中断与前面介绍的I/O中断所采用的技术相同，但中断的目的不同，前面是为了数据的输入或输出，而这里是为了报告一组数据传送结束。因此它们是I/O系统中不同的中断事件。

5.通道方式

(1)通道的功能

DMA控制器的出现已经减轻了CPU对数据输入输出的控制，使得CPU的效率有显著的提高。而通道的出现则进一步提高了CPU的效率。这是因为通道是一个特殊功能的处理器，它有自己的指令和程序专门负责数据输入输出的传输控制，而CPU将“传输控制”的功能下放给通道后只负责“数据处理”功能。这样，通道与CPU分时使用内存，实现了CPU内部运算与I/O设备的并行工作。

通道的基本功能是执行通道指令、组织外部设备和内存进行数据传输，按I/O指令要求启动外部设备，向CPU报告中断等，具体有以下五项任务:

①接受CPU的I/O指令，按指令要求与指定的外部设备进行通信;

②从内存选取属于该通道程序的通道指令，经译码后向设备控制器和设备发送各种命令;

③组织外部设备和内存之间进行数据传送，并根据需要提供数据中间缓存的空间，以及提供数据存入内存的地址和传送的数据量;

④从外部设备得到设备的状态信息，形成并保存通道本身的状态信息，根据要求将这些状态信息送到内存的指定单元，供CPU使用;

⑤将外部设备的中断请求和通道本身的中断请求，按次序及时报告CPU。

(2)通道类型

根据通道的工作方式，通道可分为:①选择通道。②数组多路通道。③字节多路通道。④通道适配器。

6.外部设备

外部设备分为输入设备、输出设备、输入输出兼用设备、外存设备、数据通信设备和过程控制设备等。

①输入设备②输出设备③汉字设备

④数据通信设备

⑤过程控制设备

全国计算机等级考试四级复习纲要二[1]

第二章考试要点

本章内容主要是:数据结构、算法的基本概念;线性表逻辑结构，链表、数组的存储和运算;队列与栈的

定义，存储及应用;树和二叉树的定义，互相转换，二叉树的存储，二叉树的周游;图的基本概念，图的存储的周游;排序的基本概念与排序算法(选择排序，插入排序，交换排序，归并排序);检索的基本概念与检索算法(顺序检索，二分检索，散列技术检索，二叉排序树)。

以下介绍一些常用的数据结构，阐明各种数据结构内在的逻辑关系，讨论它们在计算机中的存储表示，以及在这些数据结构上进行的各种运算和实际的执行算法，并对算法的效率进行简单的分析。

一、基本概念

1.什么是数据结构

数据是描述客观事物的数字、字符以及所有能直接输入到计算机中并被计算机程序处理的符号的集合。

数据对象是具有相同性质的数据元素的集合。通常，一个数据对象中的数据元素不是孤立的，而是彼此之间存在着一定的联系，这种联系就是数据结构。数据对象中数据元素之间的联系需要在对数据进行存储和加工中反映出来，因此，数据结构概念一般包括三方面的内容:数据之间的逻辑关系、数据在计算机中的存储方式、以及在这些数据上定义的运算的集合。

(1)数据的逻辑结构

数据的逻辑结构只抽象地反映数据元素之间的逻辑关系，它与数据的存储无关，是独立于计算机的。

数据的逻辑结构分为线性结构和非线性结构两大类，线性结构的逻辑特征是:有且仅有一个开始结点和一个终端结点，并且所有的结点都最多有一个直接前驱和一个直接后继。线性表就是一个典型的线性结构。非线性结构的逻辑特征是:一个结点可能有多个直接前驱和直接后继。树、图等都是非线性结构。

(2)数据的存储结构

数据的存储结构是数据的逻辑结构在计算机存储器里的实现(亦称为映象)。它是依赖于计算机的，并有四种基本的存储映象方法。它们是:

①顺序存储方法 该方法是把逻辑上相邻的结点存储在物理位置上相邻的存储单元内，结点间的逻辑关系由存储单元的邻接关系来体现。顺序存储方法主要用于线性的数据结构，非线性的数据结构也可以通过某种线性化方法来实现顺序存储。

②链接存储方法 在链接存储方法中，逻辑上相邻的结点在物理位置上未必相邻，结点间的逻辑关系是由附加的指针字段表示的。

③索引存储方法 该方法通常是在存储结点信息的同时，还建立一个附加的索引表，索引表中的每一项称为索引项，索引项的一般形式是:(关键字，地址)。关键字是能唯一标识一个结点的那些数据项。

④散列存储方法 在散列存储方法中，结点的存储地址是根据结点的关键字值直接计算出来的。上述四种基本的存储方法也可以组合起来对数据结构进行存储映象。

(3)数据的运算

数据的运算定义在数据的逻辑结构之上，每种逻辑结构都有一个运算的集合。常用的运算有:查找、插入、删除、更新、排序等。显然，对数据运算的具体实现方法只有在确定了存储结构之后才能加以考虑。

2.算法

(1)算法及其特征

简单地说，一个算法就是一种解题方法，更严格地说，算法是由若干条指令组成的有穷序列，它必须具有以下特征:

①有穷性 一个算法必须在执行有穷步后结束。

②确定性 算法的每一步必须是确切地定义的，无二义性。

③可行性 算法中的所有待实现的运算必须在原则上能够由人使用笔和纸在做有穷次运算后完成。

④输入 一个算法具有0个或多个输入的外界量，它们是算法开始前对算法最初给出的量。

⑤输出 一个算法至少产生一个输出，它们是与输入有某种关系的量。

算法的含义与程序十分相似，但二者又有区别。一个程序不一定满足有穷性，操作系统就是如此，只要整个系统不被破坏，操作系统就永远不会停止，所以操作系统程序不是一个算法。另外，程序中的指令必须是机器可以执行的，而算法中的指令则无此限制。但是，一个算法如果用机器可执行的语言书写，则它就是一个程序。

对一个算法的描述可以采用自然语言、数学语言、约定的符号语言、以及图解等方式。

(2)算法的分析

求解同一个问题可以有多种不同的算法，评价一个算法的优劣除了正确性和简明性外，主要考虑两点:一是执行算法所耗费的时间，二是执行算法所耗费的存储空间，特别是辅助存储空间的耗费。就这两者而言，前者显得比后者更为重要，在数据结构中往往更注重对算法执行时间的分析。

一个算法所耗费的时间是该算法中每条语句的执行时间之和，而每条语句的执行时间是该语句执行次数(频度)与该语句一次执行所需时间的乘积。如果假定每条语句一次执行所需的时间均为单位时间，则一个算法的时间耗费就是该算法中所有语句的频度之和。

二、线性表

(1)线性表及其基本操作

线性表是n≥0个元素的一个有限序列:(a 1 ，a 2 ，a 3 ，?，a n- 1 ，a n ，)表中元素的个数n称为表的长度，长度n=0的表称为空表。表元素又称为结点，线性表的一个重要特性是可以按照诸元素在表中的位置确定它们在表中的先后次序。若n≥1，则a 1 ，为第一个元素，a n 为最后一个元素。元素a i-1 先于a i ，我们称a i-1 为a i 的前驱;a i 在a i-1 之后，a 1 为a i-1 的后继。除第一个元素外，每个元素都

有一个且仅有一个直接前驱;除最后一个元素外，每个元素都有一个且仅有一个直接后继，下面所列的是其中一些常用的运算。

①查找运算

查找线性表的第i(0≤i≤n-1)个表元;

在线性表中查找具有给定键值的表元;

②插入运算

把新表元插在线性表的第i(0≤i≤n)个位置上;

把新表元插在具有给定键值的表元的前面或后面;

③删除运算

删除线性表的第i(0≤i≤n-1)个表元;

删除线性表中具有给定键值的表元;

④其他运算

统计线性表元的个数;

输出线性表各表元的值;

复制线性表;

线性表分析;

线性表合并;

线性表排序;

按某种规则整理线性表。

(2)线性表的存储

有多种存储方式能将线性表存储在计算机内，其中最常用的是顺序存储和链接存储。

①线性表的顺序存储

线性表的顺序存储是最简单的存储方式。程序通常用一个足够大的数组，从数组的第一个元素开始，将线性表的结点依次存储在数组中。即线性表的第i个结点存储在数组的第i(0≤i≤n-1)个元素中，用数组元素的顺序存储来体现线性表中结点的先后次序关系。用数组存储线性表的最大优点是能直接访问线性表

中的任一结点。

用数组存储线性表的缺点主要有两个:一是程序中的数组通常大小是固定的，可能会与线性表的结点可以任意增加和减少的要求相矛盾;二是执行线性表的结点插、删操作时要移动存于数组中的其他元素，使插和删操作不够简便。

②线性表的链接存储

线性表链接存储是用链表存储线性表，最简单的用单链表。如从链表的第一个表元开始，将线性表的结点依次存储在链表的各表元中。即线性表的第i个结点存储在链表的第i(0≤i≤n-1)个表元中。链表的每个表元除要存储线性结点的信息外，还要有一个成分用来存储其后继结点的指针。单链表就是通过链接指针来体现线性表中结点的先后次序关系。每个链表还要有一个指向链表的第一个表元，链表的最末一个表元的后继指针值为空。用链表存储线性表的优点是线性表的每个表元的后继指针就能完成插或删的操作，不需移动任何表元。

其缺点也主要有两条:一是每个表元增加了一个后继指针成分，要花费更多的存储空间;二是不便随机地直接访问线性表的任一结点。

(3)线性表上的查找

线性表上的查找运算是指在线性表中找某个链值的结点。根据线性表的存储形式和线性表本身的性质差异，有多种查找算法，如:顺序查找、二分法查找、分块查找、散列查找等。

(4)线性表的新结点插入顺序存储线性表的插入:

设线性表结点的类型为整型，插入之前有n个结点，把值为x的新结点插在线性表的第i(0≤i≤n)个位置上。完成插入主要有以下几个步骤:

检查插入要求的有关参数的合理性;

把原来第n-1个结点至第i个结点依次往后移一个数组元素位置;

把新结点放在第i个位置上;

修正线性表的结点个数。

(5)栈

堆栈的工作原理是采用后进先出(LIFO)技术，栈顶由中央处理器中的堆栈指示器(SP)指出。在执行PUSH操作中SP减量，而在POP操作中SP增量。

下面从数据结构的角度，进一步说明堆栈的基本概念与操作。需要说明的是，其工作原理与前面所介绍的是一致的，不同的是脱离了硬件背景，例如，栈顶指针不是中央处理器的某个寄存器的内容，而是一个抽象的数据结构。

栈是一种特殊的线性表，这种线性表只能在固定的一端进行插入和删除操作。允许插入和删除的一端称为栈顶，另一端称为栈底。一个新元素只能从栈顶一端进入，删除时，只能删除栈顶的元素，即刚刚被

插入的元素。由于元素是按后进先出的次序入栈和出栈的，所以栈又称后进先出表(Last In First Out)，简称LIFO表。栈的基本操作有:

①create(s) 建立一个空栈s。

②empty(s) 测试栈是否为空栈。

③full(s) 测试栈是否满。

④push(x，s) 将元素x插入栈s的栈顶。

⑤top(s) 取栈顶元素。

⑥pop(s) 删除栈顶元素。

由于栈是一种特殊的线性表，栈的各种操

作实际上是线性表的操作的特殊情形，所以表示线性表的方法同样可以用来表示栈。

(6)队列

队列可看作是插入在一端进行，删除在另一端进行的线性表，允许插入的一端称为队尾，允许删除的一端称为队头。在队列中，只能删除队头元素。队列的最后一个元素一定是最新入队的元素。因此队列又称先进先出表(First-In-First-Out)。

日常生活中排队购物就是队列应用的例子:新来的顾客排在队尾等待，排在队头的顾客购物后离开队伍。队列的基本操作有:

①create(Q)建立一个空队列。

②empty(Q)测试队列是否为空队列。③full(Q)测试队列是否为满。④front(Q)取队头元素。

⑤enq(X，Q)向队列中插入一个元素X。⑥enq(Q)删除队头元素。

三、数组

线性表(包括栈和队列)都是线性结构，结构中的每个元素只是无结构的数据元素。我们对线性表作进一步的推广，使结构中的元素本身也可以是具有某种结构(如向量)的数据，从而引出了数组这一种新的数据结构。

(1)数组的定义和运算

类似于线性表，一个二维数组(或称矩阵)可以看成是由m个行向量所组成的向量，也可以看成是由n个列向量所组成的向量。

对于数组的运算，主要有检索或存取数组中某个元素。

(2)数组的顺序存储结构

由于对数组一般不作插入或删除运算，因此，一旦数组被建立，则结构中的元素个数和元素之间的关系就不再发生变动。对这种情况采用顺序存储结构表示数组是比较恰当的。

由于计算机存储单元是一维的结构，而数组是多维的结构，因此就必须把多维结构映射为一维的结构，即把多维结构按一定次序排列成一维的。

四、树型结构

线性表、栈和队列等数据结构所表达和处理的数据以线性结构为组织形式。然而，在计算机科学和计算机应用的各个领域中，存在着大量需要用更复杂的逻辑结构加以表示的问题。因此必须研究更复杂的逻辑结构及相应的数据结构。树形结构就是这些更复杂的结构中最重要的一类。

1.树的基本概念

树是一类重要的树形结构，其定义如下:树是n(n>0)个结点的有穷集合，满足:

(1)有且仅有一个称为根的结点;

(2)其余结点分为m(m≥0)个互不相交的非空集合，T 1 ，T 2 ，?，T m ，这些集合中的每一个都是一棵树，称为根的子树。

在树上，根结点没有直接前趋。对树上任一结点X来说，X是它的任一子树的根结点惟一的直接前趋。为了讨论方便，我们引入树的若干习惯术语。树上任一结点所拥有的子树的数目称为该结点的度。度为0的结点称为叶子或终端结点。度大于0的结点称为非终端结点或分支点。一棵树中所有结点的度的最大值称为该树的度。若树中结点A是结点B的直接前趋，则称A为B的双亲或父结点，称B为A的孩子(即“子女”)或子结点。易知任何结点A的孩子B也就是A的一棵子树的根结点，父结点相同的结点互称为兄弟。一棵树上的任何结点(不包括根本身)称为根的子孙。反之若B是A的子孙，则称A是B的祖先，结点的层数(或深度)从根开始算起:根的层数为1，其余结点的层数为其双亲的层数加1。一棵树中所有结点层数的最大值称为该树的高度或深度。

树(及一切树形结构)是一种“分支层次”结构。所谓“分支”是指树中任一结点的子孙可以按它们所在的子树的不同而划分成不同的“分支”;所谓“层次”是指树上所有结点可以按它们的层数划分不同的“层次”。在实际应用中，树中的一个结点可用来存储实际问题中的一个数据元素，而结点间的逻辑关系(即父结点与子结点之间的邻接关系)往往用来表示数据元素之间的某种重要的、必须加以表达的关系。

用图示法表示任何树形结构时，箭头的方向总是从上到下，即从父结点指向子结点，因此，可以简单地用连线代替箭头。

2.树的基本运算包括:

①求根ROOT(T)，引用型运算，其结果是结点X在树T的根结点。

②求双亲PARENT(T，X)，引用型运算，其结果是结点X在树T上的双亲结点;若X是树T的根或X

不在T上，则结果为一特殊标志。

③求孩子CHILD(T，X，i)，引用型运算，其结果是树T上的结点X的第i个孩子;若X不在T上或X没有第i个孩子，则结果为一特殊标志。

④建树CREATE(X，T 1 ，?，T k )k≥1，加工型运算，其作用是建立一棵以X为根，以T 1 ，?，T k 为第1，?k棵子树的树。

⑤剪枝DELETE(T，X，i)，加工型运算，其作用是删除树T上结点X的第i棵子树;若T无第i棵子树，则为空操作。

3.二叉树

(1)二叉树的基本概念

二叉树是结点的有穷集合，它或者是空集，或者同时满足下述两个条件:(1)有且仅有一个称为根的结点:

(2)其余结点分为两个互不相交的集合T 1 、T 2 ，T 1 与T 2 都是二叉树，并且T 1 与T 2 有顺序关系(T 1 在T 2 之前)，它们分别称为根的左子树和右子树。

二叉树是一类与树不同的树形结构。它们的区别是:第一，二叉树可以是空集，这种二叉树称为空二叉树。第二，二叉树的任一结点都有两棵子树(当然，它们中的任何一个可以是空子树)，并且这两棵子树之间有次序关系，也就是说，它们的位置不能交换。相应地，二叉树上任一结点左、右子树的根分别称为该结点的左孩子和右孩子。另外，二叉树上任一结点的度定义为该结点的孩子数(即非空子树数)。除这个几个术语之外，树的其它术语也适用于二叉树。

特别值得注意的是，由于二叉树上任一结点的子树有左、右之分，因此即使一结点只有一棵非空子树，仍须区别它是该结点的左子树还是右子树，这是与树不同的。

(2)二叉树的性质

在某些情况下，了解二叉树的下列性质是有帮助的。

4.二叉树的存储结构

二叉树通常有两类存储结构，顺序存储结构和链式存储结构。

(1)二叉树的链式存储结构

二叉树有不同的链式存储结构，其中最常用的是二叉树链表与三叉链表。

其中，data域称为数据域，用于存储二叉树结点中的数据元素;lchild域称为左孩子指针域，用于存放指向本结点左孩子的指针(这个指针及指针域有时简称为左指针)。类似地，rchild域称为右孩子指针域，用于存放指向本结点右孩子的指针(简称右指针)。二叉链表中的所有存储结点通过它们的左、右指针的链接而形成一个整体。此外，每个二叉链表还必须有一个指向根结点的指针，该指针称为根指针。根指针具有

标识二叉链表的作用，对二叉链表的访问只能从根指针开始。值得注意的是，二叉链表中每个存储结点的每个指针域必须有一个值，这个值或者是指向该结点的一个孩子的指针，或者是空指针NULL。

若二叉树为空，则root=NULL。若某结点的某个孩子不存在，则相应的指针为空。具有n个结点的二叉树中，一共有2n个指针域，其中只有n-1个用来指向结点的左右孩子，其余的n+1个指针域为NULL。

二叉树的链式存储结构操作方便，表达简明(二叉树的逻辑关系———结点间的父子关系———在二叉链表和三叉链表中被直接表达成对应存储结点之间的指针)，因而成为二叉树最常用的存储结构。然而在某些情况下，二叉树的顺序存储结构也很有用。

(2)二叉树的顺序存储结构

二叉树的顺序存储结构由一个一维数组构成，二叉树上的结点按某种次序分别存入该数组的各个单元。显然，这里的关键在于结点的存储次序，这种次序应能反映结点之间的逻辑关系(父子关系)，否则二叉树的基本运算就难以实现。

由二叉树的性质5可知，若对任一完全二叉树上的所有结点按层编号，则结点编号之间的数值关系可以准确地反映结点之间的逻辑关系。因此，对于任何完全二叉树来说，可以采用“以编号为地址”的策略将结点存入作为顺序存储结构的一维数组。具体地说就是:将编号为i的结点存入一维数组的第i个单元。

在这一存储结构中，由于一结点的存储位置(即下标)也就是它的编号，故结点间的逻辑关系可通过它们下标间的数值关系确定。

5.二叉树的遍历

由于二叉树的基本运算在链式存储结构上的实现比较简单，无需详加讨论。下面研究二叉树的一种较为复杂的重要运算———遍历及其在二叉链表上的实现。

遍历一棵二叉树就是按某种次序系统地“访问”二叉树上的所有结点，使每个结点恰好被“访问”一次。所谓“访问”一个结点，是指对该结点的数据域进行某种处理，处理的内容依具体问题而定，通常比较简单。遍历运算的关键在于访问结点的“次序”，这种次序应保证二叉树上的每个结点均被访问一次且仅一次。

由定义可知，一棵二叉树由三部分组成:根、左子树和右子树。因此对二叉树的遍历也可相应地分解成三项“子任务”:

①访问根根点;

②遍历左子树(即依次访问左子树上的全部结点);③遍历右子树(即依次访问右子树上的全部结点)。

因为左、右子树都是二叉树(可以是空二叉树)，对它们的遍历可以按上述方法继续分解，直到每棵子树均为空二叉树为止。由此可见，上述三项子任务之间的次序决定了遍历的次序。若以D、L、R分别表示这三项子任务，则人有六种可能的次序:DLR、LDR、LRD、DRL、RDL和RLD。通常限定“先左后右”，即子任务②在子任务③之前完成，这样就只剩下前三种次序，按这三种次序进行的遍历分别称为先根遍历(或前序遍历)、中根(或中序)遍历、后根(或后序)遍历。三种遍历方法的定义如下:

先根遍历 若需遍历的二叉树为空，执行空操作;否则，依次执行下列操作:

①访问根结点;

②先根遍历左子树;

③先根遍历右子树。

中根遍历 若需遍历的二叉树为空，执行空操作，否则，依次执行下列操作:

①中根遍历左子树;②访问根结点;③中根遍右子树。

后根遍历 若需遍历的二叉树为空，执行空操作，否则，依次执行下列操作:

①后根遍历左子树。②后根遍历右子树。③访问根结点。

显然，上述三种遍历方法的区别在于执行子任务“访问根结点”的“时机”不同;最先(最后、在中间)执行此子任务，则为先根(后根、中根)遍历。

按某种遍历方法遍历一棵二叉树，将得到该二叉树上所有结点的访问序列。

6.树

树是一种常用的数据结构。为了适应各种应用问题的需要，多种不同的存储结构也相应地建立起来。下面介绍树的三种常用存储结构。

(1)孩子链表表示法

孩子链表表示法是树的一种链式存储结构。与二叉树的二叉链表存储方法类似，孩子链表表示法的基本思想是:树上的一个结点的内容(数据元素)以及指向该结点所有孩子的指针存储在一起以便于运算的实现。由于树上的结点的度(孩子数)没有限制，而且各个结点的度可能相差很大，一种自然的表示方法是为树上的每个结点X建立一个“孩子链表”，以便存储X中的数据元素和指向X的所有孩子的指针。一个孩子链表是一个带头结点的单链表，单链表的头结点含两个域:数据域和指针域。其中，数据域用于存储结点X中的数据元素;指针域用于存储指向该单链表中第一个表结点(首结点)的指针。为了检索方便，所有头结点组织成一个数组，称为表头数组。对每个结点X的孩子链表来说，其中的所有表结点也含两个域，孩子域(即数据域)和指针域。第i个表结点的孩子域存储X的第i个孩子在头结点数组中的下标值。

(2)孩子兄弟链表表示法

孩子兄弟链表中所有存储结点的形式相同，均含三个域:数据域———用于存储树上的结点中的数据元素;孩子域———用于存储指向本结点第一个孩子的指针;兄弟域———用于存放指向本结点下一个兄弟的指针。

值得注意的是，孩子兄弟链表的结构形式与二叉链表完全相同;但存储结点中指针的含义不同。二叉链表中存储结点的左、右指针分别指向左、右孩子;而孩子兄弟链表中存储结点的两个指针分别指向“长子”和“大弟”。

在孩子兄弟链表表示法中，结点形式统一，结点间的联系比较简捷。同时，在这种存储结构上容易实现树数据结构的大多数运算。

(3)双亲表示法

树上每个结点的孩子可以有任意多个，但双亲只有一个。因此，通过指向双亲的指针而将树中所有结点组织在一起形成一种存储结构是十分简法的。树的这种存储表示方法称为双亲表示法。在双亲表示法下，每个存储结点由两个域组成:数据域———用于存储树上结点中的数据元素;“指针”域———用于指示本结点之双亲所在的存储结点。值得注意的是，“指针”域的类型定义可以有两种选择。第一种是将其定义为高级语言(如C语句)中的指针类型。通过将存储结点中的指针域定义为高级语言中的指针类型，就得到各种链式存储结构，如单链表、二叉链表、孩子链表等等。第二种选择是将“指针”域定义为整型、子界型等型。严格地说，无论选择上述哪种定义，得到的都是链式存储结构，因为在这两种定义之下，各存储结点之间的联结是通过“指针”完成的，而且这些指针反映了结点之间的逻辑关系。

为了区别这两种链式结构，通常将指针域定义为高级语言中的指针类型的各种链式存储结构(如单链表、二叉链表等等)称为“动态链表”，相应的指针称为“动态指针”;将指针域定义为整型、子界型等类型的各种键式存储结构称为“静态链表”，相应的“指针”称为:“静态指针”。动态链表中的结点是通过高级语言中的标准过程例如C语言的库函数malloc(size)动态(即运行期间)生成的(动态链表由此得名)，无需事先规定链表的容量，因此动态链表的大小是动态变化的。相反，静态链有的容量必须事先说明，因而其大小是固定的。然而，在某些情况下，特别是当结点数固定不变且可事先确定时，采用静态链表往往更加方便、直观。

静态双亲链表由一个一维数组树成。数组的每个分量包含两个域:数据域和双亲域。数据域用于存储树上一个结点中的数据元素;双亲域用于存放本结点的双亲结点在数组中的序号(下标值)。

7.树的遍历

与二叉树类似，遍历是树的一种重要运算。树的主要遍历方法有以下三种。

(1)先根遍历若树非空，则

①访问根结点;

②依次先根遍历根的各个子树T 1 ，?，T m 。

(2)后根遍历若树非空，则

①依次先根遍历根的各个子树T 1 ，?，T m 。②访问根结点;

(3)层次遍历

①若树非空，访问根结点;

②若第1，?，i(i≥1)层结点已被访问，且第i+1层结点未访问，则从左到右依次访问第i+1层结点。

显然，按层次遍历所得的结点访问序列中，各结点的序号与按层编号所得的编号一致。

8.树与二叉树之间的转换

一般树转换为二叉树的基本思想是:将树中每个结点用两个链接表示就可以了，一个指向它最左边的孩子，另一个指向它右边的一个兄弟，从图形上看，具体步骤是:

①加线:在兄弟结点直接加一虚线;

②抹线:对每个结点，除了其最左的一个孩子外，抹去该结点原来与其余孩子之间的边线;

③旋转:将新加上的虚线改为实线，并将虚线以及有关的实线顺时钟旋转45度。

二叉树还原为一般树的步骤是:

①加线:若某结点是一父结点的左孩子，则将该结点的右孩子以及沿着右链搜索到的所有右孩子结点都用线与那个父结点连接起来;

②抹线:抹去原二叉树中所有结点与其右孩子的连线;

③旋转:将虚线及有关实线逆时钟旋转约45度，并将几个结点按层次排列。

9.二叉树与森林之间的转换

森林转换为二叉树的步骤是:

①将森林中的每棵树转换为二叉树;

②森林中第一棵树的根结点就是转换后二叉树的根结点，依次将后一棵树作为前一棵树根结点的右子树。

二叉树转换为森林的步骤是:

①森林第一棵树的根就是二叉树的根;

②二叉树的左子树转换为森林的第一棵树，二叉树的右子树对应于森林中其余的树;③二叉树右子树的根结点作为余下树中第一棵树的根结点??，以此类推。

五、图

图的概念

图是一种较线性表和树形结构更为复杂的数据结构。在线性表中每个数据元素只有一个(直接)前驱和后继，即各数据元素之间仅有线性关系。在树形结构中，数据元素之间有明显的层次关系，每一层中的数据元素只和上一层中的一个元素(即双亲结点)相关。而在图中，任意两个数据元素之间均有可能相关。

图(graph)是图型结构的简称。它是一种复杂的非线性数据结构。图在各个领域都有着广泛的应用。图的二元组定义为:

G=(V，E)

其中，V是非空的顶点集合，即

V={v i |1≤i≤n，n≥1，v i ∈elemtype，n为顶点数｝

E是V上二元关系的集合，一般只讨论仅含一个二元关系的情况，且直接用E表示这个关系。这样，E就是V上顶点的序偶或无序对(每个无序对(x，y)是两个对称序偶和的简写形式)的集合。对于V上的每个顶点，在E中都允许有任意多个前驱和任意多个后继，即对每个顶点的前驱和后继个数均不加限制。回顾一下线性表和树的二元组定义，都是在其二元关系上规定了限制条件，线性表的限制条件是只允许每个结点有一个前驱和一个后继，树的限制条件是只允许每个结点有一个前驱。因此，图比线性表和树更具有广泛性，它包含线性表和树在内，线性表和树可以认为是图的简单情况。

对于一个图G，若E是序偶的集合，则每个序偶对应图形中的一条有向边，若E是无序对的集合，则每个无序对对应图形中的一条无向边，所以可把E看作为边的集合。这样，图的二元组定义可叙述为:图的非空顶点集(vertexset)和边集(edgeset)所组成。针对图G，顶点集和边集可分别记为V(G)和E(G)。边集E(G)允许是空集，若是空集，图G中的顶点均为孤立顶点。对于一个图G，若边集E(G)为有向边的集合，则称此图为有向图(digraph)，若边集E(G)为无向边的集合，则称此图为无向图(undigraph)。

六、排序

1.直接插入排序

直接插入排序的基本思想是把表中元素依次插入一个已排好序的表中，就像人们打扑克摸牌时把牌插入手中的若干张牌里一样。表中n个元素依次插入的比较次数为1+2+3+?+(n-1)=n(n-1)/2。在插入时，元素的移动次数最多为1+2+3+?+(n-1)=n(n-1)/2。如果表中元素已排好序，则只需比较n-1次，而移动次数为0。

2.直接选择排序

直接选择排序的基本思想是在表的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次扫描后，就完成了整个表的排序。第一趟扫描的比较次数是n-1，第二趟扫描的比较次数是n-2??，总的比较次数是(n-1)+(n-2)+??+1=n(n-1)/2。如果恰好表中元素按反序排列，则需要移动的次数为3×n(n-1)/2。如果表中元素已排好序，并采用交换标志来表示并未发生过交换，则只需一趟扫描，只比较n-1次，就够了;当然，移动次数也是0。

4.归并排序

归并排序的基本思想是表中元素两两比较排序，使表中的n个元素变成n/2个已排序的组，再两两组比较，而变成n/4个已排序的组??，直到表中只含有一个已排序的组，即完成排序。所需要的比较次数为nlog 2 n，移动次数为n。若表已排好序，则比较次数仍为nlog 2 n，但移动次数为0。

5.快速排序

快速排序的基本思想是把表中某元素作为基准，将表划分为大于该值和小于该值的两部分，然后用递归的方法处理这两个子表，直到完成整个表的排序。快速排序的比较次数为(n-1)+(n-2)+?+1=n(n-1)/2，移动次数最多也是n(n-1)/2。如果每次的基准元素刚好是表的中值，使表分为大小相等的两个子表，则比较次数为nlog 2 n;如果表已排好序，则移动次数为0。

6.常用排序方法的性能比较如下表所示:

常用排序方法的性能比较

排序方法 平均时间 最坏情况的时间 辅助存储

冒泡法、直接选择法、直接插入法 O(n2 ) O(n2 ) O(1)

快速排序 O(nlog2 n) O(n2 ) O(log2 n)

堆排序 O(nlog2n) O(nlog2 n) O(1)

归并排序 O(nlog2 n) O(nlog2 n) O(n)

注:在上表中，我们将n(n-1)/2也记为O(n2 )。如果在待排序的表中含有多个码值相同的记录，经过排序后，这些记录的相对次序不变，则称这种排序方法是稳定的，否则是不稳定的。根据上述说法，可以看出直接插入法、归并法是稳定的;而直接选择法、冒泡法、快速排序法、堆排序法是不稳定的。

七、检索

1.顺序检索

检索又称为查找。顺序检索是将待查找的关键码值与线性表中个结点的关键码值逐一比较，直到找到所需的记录，检索成功;或者在表中找不到所需记录而检索失败。顺序检索不要求线性表事先排序。设线性表有n个元素，则最多检索次数为n，最少检索次数为1。

2.二分法检索

二分法检索要求线性表结点按关键排序且以顺序方式存储。在查找时，首先与表的中间位置上结点的关键值比较，若相等则检索成功;否则根据比较结果确定下一步在表的前半部或后半部中继续进行。二分法检索的效率较主动，设线性表有n个元素，则最多的检索次数为大于log 2 n的最小整数，最少的检索次数为1。

3.分块检索

分块检索把线性表分成若干块，块内结点不必有序，但块与块之间必须有序，即每一块中各结点的关键值必须大于(或小于，与此类推)前一块最大关键值。为加快查找，还要建立一个索引表，表中给出每一块的最大关键值和指向块内第一个结点位置的指针。分块检索分两步进行，先查索引表，确定要找的记录在哪一块;然后再在相应的块中检索。分块检索适合于线性表很大，数据又是动态变化的情况。在查索引表时，可采用顺序法或二分法;在块内查找所求记录时，采用顺序法。由于分块而缩小了查找范围，从而加快检索速。

4.散列表检索

根据关键值，就可以迅速找到该记录所对应的存储位置，这就是建立在散列函数基础上的散列检索。设记录的关键值为k，则该记录的存储位置可用散列函数H来计算H=H(k)。常用来产生的散列函数的方法是除余法，即取H(k)=k mod p设散列表长度为n，取p为小于n的最大素数。一般说来，关键码值的集合比散列表存储位的数目大得多，这正是体现散列表的优势所在，但同时带来了冲突问题，即不同的关键值经散列函数计算，可能得到相同的存储位置。一个好的散列函数应该使冲突的可能性尽量小。最常用的解决冲突的方法是线性探测法，就是在发生冲突时，从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的方法在此不做讨论。

本文来源：https://www.bwwdw.com/article/jwbg.html