计算机一级编号什么数带头,全国计算机等级考试四级复习纲要汇总(2)-蒲公英云

①全相联映象

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

②直接映象

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

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

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

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

第二章考试要点

本章内容主要是:数据结构、算法的基本概念;线性表逻辑结构，链表、数组的存储和运算;队列与栈的定义，存储及应用;树和二叉树的定义，互相转换，二叉树的存储，二叉树的周游;图的基本概念，图的存储的周游;排序的基本概念与排序算法(选择排序，插入排序，交换排序，归并排序);检索的基本概念与检索算法(顺序检索，二分检索，散列技术检索，二叉排序树)。

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

一、基本概念

1.什么是数据结构

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

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

(1)数据的逻辑结构

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

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

(2)数据的存储结构

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

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

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

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

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

(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) 删除栈顶元素。

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

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

其中，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)孩子兄弟链表表示法

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

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

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

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

③旋转:将虚线及有关实线逆时钟旋转约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.快速排序

第三章考试要点

一、数理逻辑

(一) 命题逻辑基本概念数理逻辑是用数学方法研究抽象思维规律的数学学科，它研究的中心问题是推理，而推理的基本要素是命题。

在数理逻辑中，将命题用符号表示，称为命题符号值。可用p，q，r…或pi ，qi ，ri …表示命题。将真值也用符号表示，用“1”表示“真”，用“0”表示“假”。

(二) 命题公式及其分类

简单命题又称为命题常项或命题常元。命题常项有确定的真值。在数理逻辑中，不仅要研究具体的逻辑关系，还要研究抽象的逻辑关系，因而不仅要有命题常项，还要有命题变项。称真值可以变化的简单陈述句为命题变项或命题变元，仍然用p，q，r，…表示命题变项。

二、集合论

集合的基本概念

用朴素的语言描述，一些事物汇集在一起，称作一个集合。集合的每一个成员称作它的元素。往往用大写英文字母A，B，C，…表示集合。设A为一个集合。用x∈A表示x是A的元素，x∈A表示x不是A的元素。