全国计算机等级考试四级考试要点(3)
九、输入与输出系统
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)数据的逻辑结构
数据的逻辑结构只抽象地反映数据元素之间的逻辑关系，它与数据的存储无关，是独立于计算机的。
数据的逻辑结构分为线性结构和非线性结构两大类，线性结构的逻辑特征是:有且仅有一个开始结点和一个终端结点，并且所有的结点都最多有一个直接前驱和一个直接后继。线性表就是一个典型的线性结构。非线性结构的逻辑特征是:一个结点可能有多个直接前驱和直接后继。树、图等都是非线性结构。
(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)有且仅有一个称为根的结点:
