2025年全国计算机等级考试四级通关宝典与实战演练_第1页
2025年全国计算机等级考试四级通关宝典与实战演练_第2页
2025年全国计算机等级考试四级通关宝典与实战演练_第3页
2025年全国计算机等级考试四级通关宝典与实战演练_第4页
2025年全国计算机等级考试四级通关宝典与实战演练_第5页
已阅读5页,还剩27页未读, 继续免费阅读

付费下载

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

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

第一章考试要点

一、计算机的发展

自从1946年2月现代电子计算机的鼻祖ENIAC(electronicnumericalintegratorandcomputer)在美国宾夕

法尼亚大学问世后来,短短50年里,计算机技术经历了巨大的变革。

学术界常常使用器件(硬件)划分计算机的发展史,如第一代电子管计耳机(1947〜1957),第二代晶体管

计算机(1958〜1964),第三代集成电路计算机(1964〜1972),第四代大规棉集成电路计算机(1972〜),目前

提出了所谓的第五代(或新一代)计算机。

从1946年到50年代后期(1946〜1957)为电子管计算机时期。计算机的元器件重要由电子管(vacuumtube)

构成,其特点是体积庞大、功耗高、运算速度较低。如ENIAC占地170m2,重达30t,功耗为140kW,

有18000多种电子管,每秒钟能进行5000次加法计算。这一阶段,计算机重要用于军事、国防等尖端技术

领域。除「ENIAC以外,1945年左右,冯?诺依曼等人在研制EDVAC(dcclronicdiscrclcvariablecomputer)

时,提出了存储程序(stored-program)概念,奠定了后来计算机发展的基石。IBM企业1954年12月推出的

IBM650是第一代计算机的代表。从20世纪50年代后期到60年代中期(1958〜1964)为晶体管计算机时期。

自从1947年晶体管(transistor)在贝尔试验室诞生后,引起了一场影响深远的电子革命。体积小、功耗低、

价格廉价的晶体管取代了电子管,不仅提高了计算机的性能,也使计算机在科研、商业等领域内广泛地被

应用。第二代计算机不仅采用了晶体管器件,并且存储器改用速度更快的磁芯存储器;与此同步高级编程语

言和系统软件的出现,也大大提高J'计算机的性能和拓宽J'其应用领域。这一时期计算机的代表重要有DEC

企业1957年推出的PDP-LIBM企业于1962年推出的7094以及CDC企业1964年研制成功的CDC6600.

1969年CDC企业研制的DCD760C平均速度到达每秒千万次浮点运算。

从2()世纪60年代中期到70年代初期(1965〜1972)为集成电路计算:机时代。第一代和第二代计算机均

采用分离器件(discretecomponent)构成。集成电路(integratedcircuit)的出现,宣布了第::代计匏机的来临。

由于采用了集成电路,使得计宜机为制导致本迅速下降:同步由于逻辑和存储器件集成化的封装,大大提高

了运行速度,功耗也随之下降;集成电路的使用,使得计算机内各部分的互联愈加简朴和可靠,计算机的体

积也深入缩小。这一时期的代表为IBM的system/360和DEC的PDP-8。

从20世纪70年代初期到70年代后期(1972〜1978)为大规模集成电路(LSI)计算机时代。20世纪70年

代初半导体存储器的出现,迅速取代了磁芯存储器,计算机的存储器向大容珏、高速度的方向飞速发展。

存储器芯片从Ikbit,4kbit.16kbit.64kbit,256kbit,IMbit,4Mbil发展到16Mbit(1992年)。

接着就进入了超大规模集成电路(VLSI)计算机时代。伴随技术的日新月异,软件和通信的重要性也逐

渐上升,成为和硬件同样举足轻重的原因。同步系统构造的特点对•计算机的性能也有巨大的影响(中断系统、

Cache存储器、流水线技术等等)“实际上在第三代计算机后来,就很奉找到一种统一的原则进行划分.

也可以从应用的观点来划分计算机的发展史。最早的应用是军事上的需要,如炮弹弹道计算,核武器

的设计等;另一方面是广泛地用于科学计算,工程设计计算;第三阶段是大量用于管理,目前计算机的80%

以上用于管理;再接着是计算机辅助设计(CAD)和辅助制造(CAM);进入90年代,计算机的应用已趋向于综

合化和智能化,例如在•种企业里,计算机不仅用于科学计克、辅助设计和辅助制造,还用于辅助管理和

辅助决策(MIS与DSS),以及办公自动化(0A)等等,使设计、生产自动化和管理自动化融为一体,形成所

调计算机集成制造系统(CIMS-CompulerIntegratedManufaciuringSystem)»再发展下去就是工厂白动化

(FactoryAulomalion)或称无人工厂,DSS(DccisionSupportSys〔cm)/ES(ExpcnSyslcm)运用人工智能

(AI----------ArtifbationhTtelligence)技术,让计算机替代人判断、推理,寻找最优方案,以辅助决策者决策。

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

计算机的发展第一种浪潮是单个主机(Mainframe)的时期,以IBM360,370为代表的大型机的出现,其

特点是以批处理为主,重要用于大规模科学计算。

第二次浪潮为客户机/服务髭(QieWServer)的时期,这时期出现了小型机'微型机和局域网。其特点是

多顾客分时处理。

第三个浪潮是70〜80年代的微型计算机PC(PersonalComputer)的出现。目前正处在第三次浪潮,网络

计算机的时期,即以网络为中心或以网络为基础的计算机时期。

目前计算机向综合的方向发展,将多种计算机的特点和长处综合起来,并结合了多媒体技术、通信技

术等,把人类带入了网络社会。

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

计算机分类的措施大体可分如下几种:

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

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

2.按计算机的用途分类

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

3.按计算机规模分类

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

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

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

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

(4)计灯机在辅助设计和辅助制造(CADAZAM)中的应用

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

三、计算机硬件构造

实际应用的计律机系统是由计算机硬件系统、软件系统以及通信网络系统构成的一种整体系统,计算

机硬件系统是指构成计算机的所有实体部件的集合,一般这些部件由电路(电子元件)、机械等物理部件构

成,它们都是看得见摸得者的,故一般称为“硬件计算机硬件构造也可以称为冯?诺伊曼构造,它由五大

部件构成:主机部分由运算器、控制器、存储器构成,外设部分由输入设备和输出设备构成,其中关键部分

部件是运算器。

计算机硬件之间的连接线路分为网状构造与总线构造,这里重要简介总线(BUS)构造。总线构造有如下

几种形式:

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

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

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

3.单总线构造

重要部件功能:

I.运算器

运算器是完毕二进制编码的算术或逻辑运算的部件。运算器由累加带(用符号LA)、通用寄存器(用符

号LB)和算术逻辑单元(用符号ALU)构成,关键是算术逻辑单元。

2.存储器

在计算机中的存储器包括内存储器(又叫主存储器或陋机存储器,简称内存或主存)、外存储器、只读

存储器和高速缓冲存储器以及寄存器等。随机存储器是按地址存取数据的,若地址总线共有20条地址线(A

0〜A19),即有20个二进制位,可形成220=1048576个地址(1兆地址)。

3.控制器

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

(1)指令部件

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

(2)时序部件

时序部件产生定期节拍,•般由时钟信号源、节拍发生器及微操作电路构成。

4.输出寄存器

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

5.输入设备

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

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

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

软件。

系统软件包括计算机操作系统(OperationSysiem)、计算机的多种管理程序、监控程序、调试程序、编

辑程序以及多种语言的编洋或解样程序等。应用软件是为处理多种实际问题而设计的程序。

I.操作系统

操作系统具有三大功能:管理计算机硬、软件资源,使之有效使用:组织协调计算机的运行,以增强系统

的处理能力;提供人机接口,为顾客提供以便。

操作系统具有的功能:

(1)作业操作。

(2)资源管理。

(3)中断处理。

(4)1/0处理。

(5)调度。

(6)错误处理。

(7)保护和保密处理。

(8)记帐。

操作系统的基本类型:

(I)批处理操作系统。

(2)分时系统。

⑶实时系统。

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

⑴处理机管理。

(2)存储管理。

(3)文献管理。

(4)设备管理。

2.数据库管理系统

数据库管理系统既可以认为是一种系统软件也可以认为是一种通用的应用软件。目前有三种类型的数

据库管理系统,故可寄存三种模型的数据,这三种数据库管理系统分别为层次数据库、网状数据库和关系

数据库。

3.计算机网络软件

计算机网络系统是通过通信线路连接的硬件、软件与数据集合的一种计算.机系统。从硬件来说,除计

算机作为网络的结点以外,尚有如服务器(也可用一台计算机),网络适配器,终端控制器以及网络连接器

等硬件设备;从软件来说,有网络操作系统,网络通信及协议软件,网络数据库管理系统等。

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

顾客用品级语言编写的程序称源程序,源程序不能由计算机直接执仃,必须翻译成机器能执仃的语言

—机器语言,这种翻译是由机器自动翻译的,“译员”称编译程序或编译器,当源程序输入计算机后,

调用编译程序编译成机怒语言(称E的程序),然后执行。尚有•种语言处理程序叫解释程序,输入•条语

句,翻译一条。目前已出现了第4代语言(4GL)和计算机辅助软件工具CASE。

5.常用的通用软件

在数据处理、事务处理、报表处理中有许多通用软件,如字处理软件WPS、WORD,报表处理软件

LOTUS123等。

五、计算机数据表达

I.二进位计数制

引入二进制数字系统的计算机构造和性能具有如下的长处:

(1)技术实现轻易。

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

(3)计算机中二进制数的0、1数码与逻辑代数变鼠值。与1吻合,囚此二进制同步可以使计算机以使

地进行逻辑运算。

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

2.进位计数制互相转换

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

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

(1)整数转换措施-----除基取余法

十进制整数除以2取余数作最低位系数kO再取商的整数部分继续除以2取余数作高一位的系数,如

此继续直到商为0时停止除法,最终•次的余数就是整数部分最高有效位的二进制系数,依次所得到的余

数序列就是转换成的二进制数。由于除数2是二进制的基数,因此这种算法称作“除基取余”法。

(2)小数转换措施-----乘基取整法

把十进制小数乘以2,取其积的整数部分作对应二进制小数的最高位系数k-1再取积的纯小数部分乘

以2,新得积的整数部分又作下一位的系数k-2,再取其积的纯小数部分继续乘2,…,直到乘积小数部

分为()时停止.这时乘积的整数部分是二进制数最低位系数,每次乘积在到的整数序列就是所求的二进制

小数.这种措施每次乘以基数取其整数作系数。因此叫乘基取整法。需要指山的是并不是所有十进制小数

都能转换成有限位的二进制小数并出现乘积的小数部分0的状况,有时整个换算过程无限进行下去。此时

可以根据规定并考虑计算机字长,取定长度的位数后四舍五入,这时得到的二进制数是原十进制数的近似

值。

一种既有整数又有小数部分的数送入计算机后,由机器把整数部分按“除基取余”法,小数部分按“乘基

取整''法分别进行转换,然后合并。任意进制数转换成十进制数:

任意一种进位计数制的数转换成十进制数的措施都是同样的。把任盍进制数按权展开成多项式和的形

式,把各位的权与该位上的数码相乘,乘积逐项相加I,其和便是对应的十进制数。十进制数转换成任意进

制数:

十进制数转换成任意进制数与十进制数转换成二进制数的措施完全相似,即整数部分用除基取余的算

法,小数部分用乘基取整的措施,然后将整数与小数拼接成一种数作为转换的最终成果。

3•数的机器码表达

符号数的机器码表达:

(1)机器数和其值

数在计算机中的表达形式统称为机器数。机器数有两个基本特点,其一,数的符号数值化。实用的数

据有正数和负数,由于计算机只能表达0、I两种状态,数据的正号“+”或负号“•”,在机器里就用一位二进

制的。或I来区别。一般这个符号放在二进制数的最高位,称符号位,以。代表符号“+”,以1代表符号

这样正负符号就被数值化了。由于有符号占据一位,数的形式值就不等于真正的数值,带符号位的机器数

对应的数值称为机器数的真值。

机器数的另一种特点是二进制的位数受机器设备的限制。机器内部设备一次能表达的二进制位数叫机

器的字长,一台机器的字长是固定的。字长8位叫•种字节(Byte),目前利器字长一般都是字节的整数倍,

如字长8位、16位、32位、64位,

符号位数值化之后,为能以便的对机器数进行算术运算、提高运算速度,计算机设计了多种符号位与

数值一起编码的措施,最常用的机器数表达措施有三种:原码、反码和补码。

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

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

⑶补码表达法(complement

设计补码表达法的目的是:①使符号位能和有效数值部分一起参与数值运算从而简化运算规则,行省运

算时间。②使减法运算转化成加法运算,从而深入简化计算机中运算器的线路设计。计算机是一种有限字

长的数字系统,因此都是有模运算,超过模的运算成果都将溢出。n位二进制整数的模是2n0

对于二进制数尚有一种愈加简朴的措施由原码求得补码。①正数的补码表达与原码同样,[X[补=[X)

原②负数的补码是将原码符号位保持力”之后其他各位取相反的码,末位加I便得到补码,即取其原码的反

码再加1:凶补=凶反+lo

真值M)和-0的补码表达是一致的,但在原码和反码表达中具有不一样的形式。8位补码机器数可以表

达“28,但不存在+128的补码与之对应,由此可知8位二进制补码能表达数的范围是-128〜+127。应当注

意,不存在-128的8位原码和反码形式。

根据互补的概念,•种补码机器数再求•次补就得到机器数的原码了。

定点数与浮点数:

(I)定点数(fixed-pointnumber)

计算机处理的数据不仅布•符号,并且大量的数带有小数,小数点不占rr二进制一位而是隙具有机器数

里某固定位置上。一般采用两种简朴的约定:一种是约定所有机器数的小数点位置隐含在机器数的最低位之

后,叫定点纯整数机器数,简称定点整数。

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

器数,简称定点小数。

计算机采用定点数表达时,对于既有整数又有小数的原始数据,需要设定一种比例因子,数据按比例

因子缩小成定点小数或扩大成定点整数再参与运算,成果输出时再按比例折算成实际值。n位原码定点整

数的表达范围是-(2n-l-lHXS2n-l-l,n位原码定点小数的表达范围是<l-2-(n-l)HXSl-2-(n-D0当机器

数不不小于定点数的最小值时,被当作0处理,超过定点数的最大值时,机器无法体现,称作“溢出“,此

时机器将停止运算,屏幕显示溢出警告。

定点数表达措施简朴直观,不过定点数表达数的范围小,不易选择合适的比例因子,运算过程轻易产

生溢出。

(2)浮点数(floating-pointnumbe)

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

达阶码和尾数两部分:N=2ExS

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

S------N的尾数(mantissa),是数值的有效数字部分,一般规定取二进制定点纯小数正式。浮点数运

算必须化成规格化形式。所谓规格化,对于原码尾数应使最高数字位Sl=1,假如不是1,且尾数不是全为

0时就要移动尾数亢到S1=I,阶码对应变化,保证N值不变。假如尾数是补码,当N是正数时,SI必须

是I,而N是负数时,SI必须是0,才称为规格化的形式。

4.数字编码

十进制数在机内转换成二进制数时,有时也以一种中间数字编码形式存在,它把每一位十进制数用四

位二进制编码体现,每一组只体现0―9的数值运算时,有专门的线路在每四位二进制间按“卜”进位处理,

故称为二进制编码的十进制数BCD码(BinaryCodedDecimal或称二一十进制数.其编码种类诸多,

如格雷码、余3码等,附常用的叫842IBCD码,4个二进制位自左向右每位的权分别是8、4、2、1。0-9

的8421码与一般的二进制同样进位,十分简朴,当计数超过9时,需要采用措施自动向十进制高位进一,

即要进行“十进制调整”才能得到对的成果。

5.校验码

由于器件质量不可靠、线路工艺不过关、远距离传送带来的干扰或受来自电源、空间磁场影响等原因,

使得信息在存取、传送和计算过程中难免会发生诸如“「误变为“0”的错误,计算机一旦出错,要能及时检

测并纠正错误,其中一种措施是对数据信息扩充,加入新的代码,它与原数据信息一起按某种规律编码后

具有发现错误的能力,有的甚至能指出错误所在的精确位置使机器自动纠正,能起这种作用的编码叫“校验

码”(checkcode)。

奇偶校验码:

将每个数据代码扩展一种二进位作校验位(paritybil),这个校验取0还是取1的原则是:若是奇校验(odd

parity),编码是含T的个数连同校验位的取值共有奇数个T;若是偶校验(evenparity),连同校验位在内编

码里含“1”的个数是偶数个。

交叉校验:

计算机进行大量字节传送时一次传送几百共至更多字节构成的数据块,假如不仅每一种字节有一种奇

偶校验位-----称横向校验,并且所有字节的同一位也设置了一种奇偶校验位------称纵向校验,对数据

块代码的横向纵向同步校验,这种状况叫交叉校验。

循环冗余校验码-----CRC码(CyclicRedundancyCheck):

计算机信息传向远方终端或传到另一种计算中心时,信息沿一条通信线路-位位传送,这种通信方式

叫串行通信。循环冗余码(简称CRC码)就是一种检查能力很强,在串行通信中广泛采用的校验编码。

⑴CRC码

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

相除,''生成多项式“长r+1位,相除后得到r位余数就是校验位,它拼接到原k位有效信息背面即形成CRC

码。CRC码抵达接受方时,接受方的设备首先接受CRC码,首先用同样的生成多项式相除,假如恰好除

尽,表达无信息差错,接受方去掉CRC码背面1■位校验,收下k位有效信息;当不能除尽时,阐明有信息的

状态位发生了转变,即出错了。一般规定重新传送一次或立即纠错。

(2)CRC码计算

传送信息时生成CRC码以及接受时对CRC码校验都要与“生成多项北,相除,这里除法是“模2运算

即二进位运兑时不考虑进位和借位。作模2除法时,取商的原则是当部分余数首位为1时商取1,反之商

取0,然后按模2减,求部分余数,这个余数不计高位。当被除数逐位除完时,最终余数的位数比除数少

一位。该余数就是校验位。它拼接在有效信息背面构成CRC码。由于校验位扩充了传送部分的代码,因此

这是一种基于“冗余校聆''的思想的校验措施。

(3)生成多项式

CRC码是M(X)除以某一种预先选定的多项式后产生的,因此这个多项式叫生成多项式。并不是任何

一种r+1位的编码都可以作生成多项式用,它应能满足当任何一位发生传送错误时都能使余数不为0,并

且不一样位发生错误时应当使余数也不一样,这样不仅能检错并且能推断是哪一位出错,从而有利精确的

纠错。有两个生成多项式,其检错率很高。

X16+XI5+X2+I

X16+X12+X6+1

6.非数值数据的表达措施

计算机中数据的概念是广义的,机内除有数值数据之外,尚有文字、符号、图望、语言和逻辑信息等

等,由于它们也都是0、I形式存在,因此称为非数值数据。

(1)字符数据

字符数据重要指数字、字母、通用符号、控制符号等,在机内它们都被变换成计算机可以识别的一进

制编码形式。国际上被普遍采用的一种编码是美国国家信息互换原则代g(AmericanStandardCodefor

InfonnationInterchange),简称ASCII码。ASCII码选择了四类共128种常用的字符:①数字0-9。②字母。

③通用符号。④动作控制符。

(2)逻辑数据

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

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

①逻辑数据的取值只有“0”和“广两个值,不也许再有其他值,而数值数据与I的不一样组合可以反应

诸多不一样数值。

②逻辑数据的“0”和T代表两种成对出现的逻辑概念,与一般数学中代表“0”和T的数值概念故然不一

样。

③逻辑数据和逻辑数据运算可以体现事物内部的逻辑关系,而数值数据体现的是事物的数量关系。中

文:

(1)中文字音编码

(2)中文字形编码

(3)中文音形编码

(4)电报码

(5)整字编码为了能在不一样的中文系统之间互换信息、高效率高质量共享中文信息,近年来国家推出

了一系列有关中文信息处理的原则。例如1981年我国制定推行的GB2312-8O国标信息互换用流字编码字

符集(基本集)------简称国标码,以及若干辅助集。国标码搜集、制定的基本图形字符有7千余个,其中

常用中文3755个,次常用中文3008个,共6763个中文,尚有俄文字母、口语假名、拉丁字母、希腊字母、

汉语拼音,每字节内占用7bii侑息,最高位补0,例如中文“啊”的国际码,前一字节是01100000,后一字

节是00100001,编码为3021H。

中文内部码是中文在计兑机内部存储、运兑的信息代秒,内部码的设计规定与西文信息处理有很好的

兼容性,当一种中文以某种中文输入方案送入计算机后,管理模块立即将它转换成两字节长的GB2312-80

国标码,假如绐国标码的每字节最岛位加“I”,作为中文标识符,就成为一种机器内部表达中文的代码一

中文内部码。中文内部码的特点十分明显:

①中文内部码构造简短,一种中文内部码只占两个字节,两字节足以体现数千个中文和多种符号图形,

且又节省计算机存储空间。

②便于和西文字符兼容。西文字符的ASCII码占•种字节,两字节的中文内因可以当作是它扩展的字

符代码,在同一种计算机系统中,只要从最高位标识符就能辨别这两种代码。标识符是“0”,即是ASCII

码;标识符是'T',则是中文内部码。

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

语音产生机理的研窕表明,每一种语言的语音均有白己特定的音素特性,语音是不一样频率振动的成

果。分析语音的音素特点,找出音素的基频和高次频率优分,就能在计算机中建立发音系统的模型,在实

行中对语音采样,通过滤波器分解提取频率信息,由模,数转换设备转换成数字输入计算机,与机内的语言

模型比较,由此到达识别语音的目的。与此相反,假如选择己知音素的参数,应用语音系统模型,就能得

到指定的音素,深入按照一定的规则合成语言。

六、运算器

1.运算器的构成

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

(1)基本思想

(2)逻辑体现式

对一片ALU来说,可有三个进位输出。其中G称为进位发生输出,P称为进位传送输出。在电路中,

多加这两个进位输出的目的是为了便于实现多片(组)ALU之间的先行进位,为此,还需一种配合电路,它

称为先行进位发生疑(CLA)。

内部总线:

根据息线所处位直,总线分为内部总线和外部总线两类。内部总线是指CPU内件部件的连线,而外部

总线是指系统总线,即CPU与存储器、I/O系统之间的连线。

按总线的逻辑构造来说,总线可分为单向传送总线和双向传送总线。所谓单向总线,就是信息只能向

一种方向传送。所谓双向总线,就是信息可以向两个方向传送。换句话说,总线既可以用来发送数据,也

可以用来接受数据。

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

2.运算器的基本构造

运算器包括ALU、阵列乘除卷件、寄存器、多路开关或三态缓冲器、数据总线等逻辑部件。现代计和

机的运算器大体有如卜三种构造形式。①单总线构造的运算器②双总线构造的运算器③三总线构造的运算

器

七、控制器

1.控制器在CPU中的位置

中央处理器(CPU)由两个重要部分-----控制器及运算器构成。其中程序计数器、指令寄存器、指令译

码器、时序产生器和操作控制器等构成r控制器。它是对计算机公布命令的“决策机构”,协调和指挥整个

计算机系统的操作,因此,它处在CPU中极其重要的位置.,在CPU中,除算术逻辑单元(ALU)及累加器外,

尚有下列逻辑部件:

⑴缓冲寄存器(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)操作控制匿

操作控制器的功能,就是根据指令操作码和时序佶号,产生多种操作控制佶号,以便对的地建立数据

通路,从而完毕取指令和执行指令的控制。

根据设计措施不一样,操作控制器可分为组合逻辑型、存储逻辑型、组合逻辑与存储逻辑结合型三种。

第一种称为常规控制器,它是采用狙合逻辑技术来实现的;第二种称为微程序控制器,它是采用存储逻辑来

实现的;第三种称为PLA控制器,它是吸取前两种的设计思想来实现的。

(8)时序产生器

CPU中除了操作控制器外,还必须有时序产生器,由于计算机高速地进行工作,每动作的时间是非

常严格的,不能有任何差错。时序产生器的作用,就是对多种操作实行时间上的控制。

2.控制器的构成

运算器包括ALU、累加器、数据缓冲寄存器和状态寄存器,而控制器的关键是操作控制器,围绕它的

有程序计数滞(PC)、指令奇存希(IR)、指令译码2§(ID)和时序产生器。

八、存储器

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

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

主存储器由存储体、地址译码电路、驱动电路、读写电路和控制电路等构成。主存储器的重要功能是:

①存储体:是信息存储的集合体,由某种存储介质按一定构造构成的存储单元的集合。一般是二维阵列组.织,

是可供CPU和计算机其他部件访问的地址空间。

②地址寄存器、译内电路与驱动器:即寻址系统,将CPU确定的地址先送至地址寄存器中,然后根据

译码电路找到应访问的存储单元。在存储与译码器之间的卵动器的功能是减轻译码线驱动负载能力。由于

一条译码线需要与它控制的所有存储单元相联,其负载很大.需要增长驱动器,以译码线连接驱动器的输

入端,由驱动错的输出端控制连接在译码线上的所有存储单元。

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

将存储体中指定单元的内容读到数据寄存器中。

④控制电路:接受CPU传来的控制命令,通过控制电路一系列的处理,产生一组时序信号控制存储器

的操作。

在存储器的构成中,存储体是关健,其他部分是存储的外围线路。不一样的存储器都是由这几部分构

成,只是在选用不一样的存储介质和不一样的存取方式时,各部分的构造与工作方式略有.变化。

(2)存储体阵列

计算机存储器中存储的是“0"和T'的信息,每一种能存取一位二进制并能保持两种状态的元件称为记

忆元件。若干记忆元件构成存储单元,一种存储单元可以存取一种或几种字节的二进制信息。每个存储第

元均有•种地址编号,用以唯•标识存储单元的位置。信息按地址存入指定的存储单元中,按地址从指定

的存储单元中取出。存储单元的集合称为存储体。由于存储体中存储单元的每个二进制位必须并行工作,

因此将存储单元按其地址的次序构成存储阵列。

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

CPU要访问存储单元的地址由地址总线输入到地址寄存器中。地址译码器将地址转换为对应地址线(字

线)上的控制信号,以表达选中某一单元,并驱动对应的读写电路,完毕对存储单元的读写操作。

地址译码为两种方式:•种是单译码方式,仅1T-种译码器。译码器输出的每条译码线对应一种存储单

元。如地址位数N=10,即译码器可以有210=1024种状态,对应有1024条译码线(字线)即1024个存储单

元。此外一种是双译码方式,将译码器提成X向和Y向两个译码器,通过双译码器的互相作用确定存储聃

元的地址。

设地址长度n仍为10,将其中的前5位输入到X地址译码器中,译出X0到X31译码线,分别选择

0~31行。将后5位输入到Y地址译码器中译出Y0到Y31译码线,分别选择0〜31歹hX向译码器和Y

向译码器引出的地址线都是25=32条。若采用X向和Y向交叉选择,可以选择从存储单元(0,0)至(31,

31洪25x25=1024个存储单元地址。即同样可以提供1024种状态,而地址线只需要64条,比单译码器

节省93.75%的地址线。

(4)存储器的读写操作

在CPU向存储体发生读操作命令时,首先由CPU将对应存储单元的地址码送至地址寄存器中;地址译

码器籽地址寄存器中的地址编码译成对应地址线(字线)的高电位,标志指定的存储单元;然后在CPU的统一

控制下,由控制电路将读命令转换成读写电路的操作,执行将指定存储单元的内容传送到数据寄存器的操

作,完毕了整个存储器读的操作。存储器写的操作与读的操作相类似。

不•样类型的存储器根据其特点有•不•样的读写操作控制电路、控制机构、读写电路及地址译码器,

但它们的基本操作原理大同小异。

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

半导体存储器有体积小、存取速度快、生产制造易于自动化等特点,其性能价格比远远高于磁芯存储

器,因而得到广泛的应用。

半导体存储器的种类诸多,就其制造工艺可以提成双极型半导体存储器和金属-氧化物-半导体存储器

(简称MOS型存储釜)。MOS型存储器按其工作状态又可以分为静态和动态两种。动态存储器必须增设恢

复信息的电路,外部线路复杂。但其内部线路简朴,集成度高,价格较静态存储器廉价。因此常常用做大

容殳的RAM。

静态存储器和动态存储器的重要差异在于:静态存储器存储的信息不会自动消失,而动态存储器存储的

信息需要在再生过程的协助下才能保持。但无论双极型或MOS型存储器,其保持的信息将随电源的撤销

而消失。

(DRAM的组织

半导体RAM芯片是在半导体技术和集成电路工艺支持卜的产物”•段计算机中使用的RAM芯片均是

有自己的存储体阵列、译码电路、读写控制电路和I/O电路。

①RAM的并联

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

②RAM的串联

为扩展存储器的存储单.元数量,可以采用多种芯片地址串联的方式处理。

③地址友用的RAM组织

伴随大规模集成电路技术的发展,使得块存储器芯片可以容纳更多的内容。其所需地址线随之增长,

为了保持芯片的外部封装不变,一般采用地址且用的技术,采用地址分批送入的构造保证不增长芯片的地

址引脚.

(2)RAM的实际应用

由「一种存储器的芯片一般不能满足使用的规定,因此一般将若干个存储器芯片按串联和并联的两种

方式相结合连接,构成一定容量和位数的存储器。

假如设计的存储器容量有x字,字长为y,而采用的芯片为NXM位。要构成满足字氏规定的存储器所

需芯片数为:y/M。根据容量规定,陶成规定容量的RAM所需芯片数为:(x/N)x(y/M)。

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

使用时只读出不写入的存储器称为只读存储器(ROM)。ROM中的信息一旦写入就不能进行修改,其信

息断电之后也仍然保留。•般用于寄存微程序、固定子程序、字母符号阵列等信息。ROM和RAM相比,

使用时不需写入、再生和刷新等操作,因此其电路比较简朴,但同样有地址译码器、数据读出电路等。制

作ROM的半导体材料有二极管、MOS电路和双极型晶体管等。因制造工艺和功能不一样,一般分为一股

ROM、可编程ROM(PROM)、可擦写可编程ROM(EPROM)和电可擦写可编程ROM(EEPROM)等。

(DROM的工作原理

一般的ROM使用掩模式ROM。此类ROM由生产厂家做成,顾客不能加以修改。

掩模ROM的特点是其存储内容出厂时由生产厂家一次制成,顾客不能对其内容进行修改,而依赖于

生产厂家,这种RAM合用于定型批量制作。在实际使用过程中,部分顾客但愿自己根据需要填写ROM的

内容,因此产生可编程ROM(PROM)..PROM与掩模ROM的重要区别是PROM在出厂时其内容均为“0”

或力”,顾客在使用前按照自己的需要运用工具将编码写入PROM中,一次写入不可修改。PROM的使用

相称「由顾客RAM生产中的最终一道工序-----向RAM中写入编码,其他同掩模RAM的使用完全相似。

(2JEPROM和EEPROM的工作原理

为了适应程序调试的规定,针对一•般PROM的不可修改特性,设计出可以多次擦写的可编程

ROM(EPROM)。其特点是可以根据顾客的规定用工具擦去RAM中原有的存储内容,重新写入新的编科。

擦除和写入可以根据顾客的规定用工具擦去RAM中原有的存储内容,重新写入新的编码。擦除和写入可

以多次进行,其信息的内容同样不会因断电而丢失。最常见的ETROM是UVEPROM,其存储元件常用浮

省栅型MOS管构成。出厂时所有置“0”或“1”,由顾客通过高压脉冲写入信息。擦写时通过其外部的•种石

英玻璃窗,运用紫外线的照射,使浮栅上的电荷获得高能而泄漏,恢熨原有的全“0”或T”状态,容许顾客

重新写入信息。平时窗口上必须贴有不透明胶纸,以防光线进入而导致信息流失。

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

4.外存储器的工作原理

外存:储器是指那些不能被CPL直接访问的,读取速度较内存慢,容量比内存大,一般用来寄存不常用

的程序和数据的存储器。磁带、磁盘存储器是现今最常用的外存,因其运用磁表面介质存储数据,一般也

称为磁表面存储器。而光盘是外存发展的方向,有必要理解它们的原理和应用。

(I)磁盘存储器

磁盘存储器具有容战大,存取速度高(相对其他种类外存储器)的特点,因而在多种类型的计算机中普

遍被用做重要的外存储器。磁盘存储器防止了磁带存储的缺陷。瞄盘存储器将磁性材料涂粘在以某种材料

为主的盘形圆片匕用若干封闭的圆形磁道替代了磁带的长形磁道。使用时,通过磁盘面的高速旋转替代

磁带的直线运动,减少寻找特定位置的时间。

磁盘存储器由磁盘、磁头、定位系统和传动系统等部分构成,一般也将这些部件统称为磁盘驱动器.

根据盘片的基本构成材料将磁盘分为硬盘和软盘两种。所谓硬盘是指由金国材料制成一定厚度的盘片基体,

这些盘片i股组合成盘片组构成硬盘驱动器的存储主体。

软盘和硬盘盘片记录信息的方式相似,都是将每个盘而由外向内提成若干个融道,每个磁道也划分为

多种扇区,信息以园区为单位存储。

扇区是磁盘寄存信息的最小物理单位。扇区包括头空、序标、数据区、检查字段和尾空等几种部分。

一股对磁盘进行的所谓格式化操作就是在磁盘上划分磁道、扇区及扇区内各特定区域,刚出厂的磁盘上没

有这些划分,因此必须在格式化后才能使用。磁盘区域的划分随计律机系统而不•样,其存储容量也有较

大的差异。但可以通过查阅计算机系统对应的阐明掌握磁盘容埴的数据。计算一种磁盘容量的公式是:

磁盘存储容量=盘面数X每盘面磁道数X每肱道扇区数X每扇区存饰容坦

(2)光盘存储器

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

光盘的应用愈来愈广泛。

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

从构造上看光盘存储器同磁盘存储基本相似,两者均有存储信息的盘片、机械驱动部件、定位部件和

读写机构。不一样的是后者运用磁性原理存储信息,运用磁头存取信息;而前者是运用光学原理存储信息并

用光学读写头来存取这些信息。

光盘自身是鸵盘面上某些可以影响此线反射的表面特性存储信息,例如目前常用的只读光盘(CD-ROM)

上运用光盘表面的凹凸不平表达"0.'和"1”。以CD-ROM为例,读取数据时,由机械驱动部件和定位部件负

责确定读取的位置。激光器发出激光经光学线路至聚焦透镜射向光盘表面,表面的凹凸不平导致反射光的

变化,运用数据光检测髭将这些变化转换为数据“0'、和"l'、的电信号传播到数据输出端,整个读取工作完毕。

其他类型光盘的写入过程大体与此相似,唯一的差异是数据自数据输入端传来。

一般将光盘存储器分为只读式(readonly)、一次写入式(writconce)和可然式(erasable)或可逆式(reversible)

三种.只读式光盘运用材料表面的凹凸不平的特性记录信息,在出厂前由生产厂家将有关信息寄存到光盘

上。对丁•一次写入式光盘,顾客可以运用会聚的激光束在光盘表面照射使材料发牛.永久性变化而记录信息。

这种光盘现已普遍用于多媒体系统。可擦式光盘运用激光在磁性材料上或相变材料上实现信息的存储和擦

除。

光盘存储器的记录密度高,存储容量大,一片5.25英寸大小的一次写入式光盘可以存储680MB的信

息,其容量远远不小于外形同样大小的软磁盘。光盘信息的保留时间也比磁盘的长。目前影响光盘普遍应

用的重要原因是光盘存储器的读写速度慢和光盘驱动器的成本高。伴随技术的进步,以上问题是可以处理

的。因此光盘存储器有广泛的应用前景。

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

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

一般将由主存和部分辅存构成的存储构造称为虚拟存储器,其对应的存储地址称为虚拟地址(逻辑地

址),其对应的存储容量称为虚拟容量。将实际主存地址称为物理地址或实地址,主存的容量称为实存容量。

当用虚拟地址访问主存时,系统首先查看所用虚拟地址对应的单元内容与否已装入主存。假如在主存

中,可以通过辅助软、硬件自动把虚拟地址变成主存的物理地址后,对主存对应单元进行访问。假如不在

主存中,通过辅助的软、硬件将虚拟地址对应的内容调入主存中,然后再进行访问。因此,对虚拟存储器

的每次访问都必须进行虚实地址的变换。

虚拟存储器的作用是扩大整个主存的容量,容许在程序中使用比主存容量大得多的虚拟存储器。同步

可以减轻人们编程中对程度进行分块的苦恼,从而提高软件开发的效率。虚拟存储器是实现运用小容最的

主存运行大规模的程序的一种有效的措施。尽管实现虚拟存储要增长某些额外的投资和软件开销,虚拟存

储技术在多种计算机系统中仍得到了广泛的应用。虚拟存储器必须建立在主存-辅存构造上,但一股的主存

-辅存系统并不一定是虚拟存储器,虚拟存储器与一般的主存-辅存系统的本质区别是:

①虚拟存储器容许人们使用比主存容量大得多的地址空间来访问主存,非虚拟存储器最多只容许人们

使用主存的整个空间,一般只容许使用操作系统分派的主存中的某一部分空间。

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

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

虚拟存储技术,实际上是将编写程序时所用的虚拟地址(逻辑地址)转换成较小的物理地址。在程序运

行时随时进行这种变换。为了便于主存与辅存之间信息的互换,虚拟存储器一般采用二维或三维的豆合地

址格式。采用二维地址格式时,将塾个存储器划分为若干页(或段),每个页(或段)又包括若干存储单元。采

用三维地址格式时将整个存储空间分为若干段,每段分为若干贞,每页又包括若干存储单元。根据地址格

式不一样,虚拟存储器分为:页式虚拟存储器、段式虚拟存储器和段页式虚拟存储器。

在虚拟存储器中逻辑地址与物理地址之间的对应称为地址映象。•般有三种地址映象的方式:金相联映

象、直接映象和组相联映象。

①全相联映象

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

②直接映象

每个逻辑贞只能映象到一种特定页面的方式称为直接映象。如主存实际有2P页,虚拟存储器的逻辑

空间有2P页,则将逻辑空间按物理空间大小分为2P-P块,块内各页只能映象到主存的对应页中。即所

有各块的第0页对应主存的第。页,各块的第n页对应主存的第n页。若程序需要轮番使用第i块和第j

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

③组相联映象组相联映象措施是先按直接映象措施将虚拟存储空间(逻辑空间)提成若干块,在主存和

逻辑空间中的各块内划分为若干组,每个组间按直接映象措施控制。可以这样理解,假如将组相联映象措

施中的组按直接映象措施的页来看待,组相联措施与直接映象措施相似,逻辑空间各组内的页只能与对应

的物理空间组相联。但在组内各页与物理空间的页面之间采用全相联映象措施处理。因此,可以认为组相

联映象是全相联映象和巴接映象措施的结合。6.缓冲技术使用

缓冲技术就是为缓和慢速设备对整个计算机系统速度的影响,在计算机的某些部件中划定一块区域,

模拟慢速设备的操作,将对慢速设备的操作先寄存在此区域中,其他部件完毕这一操作后可以继续其他工

作,而慢速设备可以用自己的速度逐渐完毕对应的操作。做为中间缓冲的区域称为缓冲区,对应的技术称

为缓冲技术。

在整个存储体系的组织中,缓冲技术成为处理容法与速度之间矛盾的重要措施。实际上在计算机系统

中缓冲技术处理了许多难题,增进了计算机系统的发展。在存储体系中,缓冲技术重要体目前Cache的应

用和磁盘缓冲的使用。

(l)Cache的原理和作用Cache为工作原理基于对大庆经典程序运行实例的分析。分析成果表明,在较

短的时间间隔内,由程序产生的地址往往集中在存储器逻辑地址空间很小的范围内。指令地址的分布乂是

持续的,加上循环程序和子程序段的反更执行,对这些地址的访问自然具有时间上集中分布的倾向。这种

对局部范围的存储器地址频繁访问,对此范围外的地址访问甚少的现象称为程序访问的局部性。程序访问

的局部性为Cache的引入提供了理论根据。

Cache是缓冲技术在存储体系中的一种详细应用。Cache处在主存与CPU之间,负责处理主存与CPU

之间速度的协调问题,Cache中寄存着主存的•部分副本(主存中的部分内容),当存储器接到有关读取指令

时,先在Cache中查找此信息与否存在,若有则不经主存直接从Cache中取出;否则直接从主存中取出,同

步写入Cache,以备再次使用。当向存储器写入内容时,由辅助硬件采用多种措施保证主存中的内容同Cache

中的内容保持一致。

为保证写入时两者内容一致的措施有:①将内容同步写入《存和Cache:②数据仅写入I■:存,若Cache中

有此内容则将其释放;③数据只写入Cache,在规定的时候将修改正的Cache的内容写入主存。

Cache的重要特点是:①存取速度快,一般Cache的速度完全可以跟上CPU的运算速度;②存储量小,

由「Cache的速度快,其价格也相称昂贵,因此为保证整个存储器的性能价格比,一般采用合适容量的

Cache,其容量不不小于主存。

(2)磁盘缓冲技术

磁盘缓冲技术的R的是减少由于主、辅存之间的速度差异对计算机总体性能的影响。磁盘是存储系统

中的辅助部分,其重要作用是用来存储不常用的数据和程序等信息,减轻对主存容显的需求压力。由于磁

盘中的信息不能被计算机的其他部件直接调用,因此在信息的输入/输出过程中必须在主存中开辟一定的空

单位和为与磁盘上信息互换的中间过渡区域称为磁盘缓冲区。如从键盘(输入设备)向磁盘中输入一种信息,

此信息必须通过总线先输入到主存中的特定区域中,通过程序控制将信息寄存到主存中对应于磁盘输入/输

出的一种特定区域内,然后将此信息转存到磁盘上。一般将主存中时应于就盘的特定区域称为磁盘辍冲区。

为了提高磁盘的读写速度,操作系统一般根据程序运行的需要设置磁盘缓冲区的大小及输入/输出操

作。同Cache技术相类似,不立即澄盅磁盘缓冲区的内容,当系统需要继续读入磁盘中的信息时,首先检

行磁盘缓冲区中与否有所需要的信息,若有则直接使用.否则根据信息的位置将磁盘上特定扇区的内容调

入磁盘缓冲区后再加以使用。这样可以提高磁盘的信息读取速度,减少因磁盘存取速度慢对系统整体性能

的影响。

第二章考试要点

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

定义,存储及应用;树和二叉树的定义,互相转换,二叉树的存储,二叉树的环游;图的基本概念,图的存储

的环游;排序的基本概念与排序算法(选择排序,插入排序,互换排序,归并排序);检索的基本概念与检索算

法(次序检索,二分检索,数列技术检索,二叉揖序树)。

如卜.简介某些常用的数据构造,阐明多种数据构造内在的逻辑关系,讨论它们在计算机中的存储表达,

以及在这些数据构造上进行的多种运算和实际的执行算法,并对算法的效率进行简朴的分析。

一、基本概念

1.什么是数据构造

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

数据对象是具有相似性质的数据元素的集合。一股,一种数据对象中的数据元素不是孤立的,而是彼

此之间存在若一定的联络,这种联络就是数据构造。数据对象中数据元素之间的联络需要在对数据进行存

储和加工中反应出来,因此,数据构造概念一般包括三方面的内容:数据之间的逻辑关系、数据在计算机中

的存储方式、以及在这些数据上定义的运算的集合。

(1)数据的逻辑构造

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

数据的逻辑构造分为线性构造和非线性构造两大类,线性构造的逻辑特性是:有且仅有i种开始结点和

一种终端结点,并且所有的结点都最多有一种直接前驱和i种直接后继。线性表就是一种经典的线性构造。

非线性构造的逻辑特性是:一种结点也许有多种直接前驱和直接后继。树、图等都是非线性构造。

(2)数据的存储构造

数据的存储构造是数据的逻辑构造在计算机存储器里的实现(亦称为映象)。它是依赖于计算机的,并

有四种基本的存储映象措施。它们是:

①次序存储措施该措施是把逻辑上相邻的结点存储在物理位置上相邻的存储单元内,结点间的逻辑关

系由存储单元的邻接关系来体现。次序存储措施重要用于线性的数据构造,非线性的数据构造也可以通过

某种线性化措施来实现次序存储。

②锌接存储措施在链接存储措施中,逻辑上相邻的结点在物理位置二未必相邻,结点间的逻辑关系是

由附加的指针字段表达的。

③索引存储措施该措施一般是在存储结点信息的同步,还建立一种附加的索引表,索引表中的每一项

称为索引项,索引项的一般形式是:(关键字,地址)。关键字是能唯一标诙一种结点的那些数据项。

④散列存储措施在散列存储措施中,结点的存储地址是根据结点的关键字值直接计算出来的。上述四

种基本的存储措施也可以组合起来对数据构造进行存储映象。

(3)数据的运算

数据的运算定义在数据的逻辑构造之上,仔种逻辑构造均有一种运算的集合。常用的运算有:查找、插

入、删除、更新、排序等。显然,对数据运算的详细实现措施只有在确定了存储构造之后才能加以考虑。

2.算法

(I)算法及其特性

简朴地说,•种算法就是•种解题措施,更严格地说,算法是由若干条指令构成的存穷序列,它必须

具有如下特性:

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

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

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

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

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

算法的含义与程序十分相似,但两相又rx区别。

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论