告。这里的中断与前面介绍的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增量。
下面从数据结构的角度，进一步说明堆栈的基本概念与操作。需要说明的是，其工作原理与前面所介绍的是一致的，不同的是脱离了硬件背景，例如，栈顶指针不是中央处理器的某个寄存器的内容，而是一个抽象的数据结构。
栈是一种特殊的线性表，这种线性表只能在固定的一端进行插入和删除操作。允许插入和删除的一端称为栈顶，另一端称为栈底。一个新元素只能从栈顶一端进入，删除时，只能删除栈顶的元素，即刚刚被