全国计算机等级考试
公共基础知识
1
第1章 数据结构与算法
1.1算法
1.1.1算法的基本概念
1、算法：是指解题方案的准确而完整的描述。
2、算法的基本特征：可行性、确定性、有穷性、拥有足够的情报 。
3、算法的基本要素：
一是对数据对象的运算和操作；
二是算法的控制结构。一个算法一般都可以用顺序、选择、循环三种基本控制结 构组合而成。
4、算法设计基本方法：列举法、归纳法、递推、递归、减半递推技术、回溯法。
1.1.2算法复杂度
1、算法的复杂度主要包括时间复杂度和空间复杂度 。
（1）时间复杂度：执行算法所需要的计算工作量。用算法在执行过程中所需基本运算 的执行次数来度量算法的工作量。
（2）空间复杂度：一般是指执行这个算法做需要的内存空间。
1.2数据结构的基本概念
数据结构作为计算机的一门学科，主要研究和讨论一下三个方面的问题： （1）数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构
（2）在对数据进行处理时，各数据元素在计算机中的储存关系，即数据的存储结构 （3）对数据结构进行的运算
1.2.1什么是数据结构
1、数据结构是指反应数据元素之间关系的数据元素集合的表示。更通俗的说，数据结 构是指带有结构的数据元素的集合。在此，所谓的结构实际上是指数据元素之间的前后件 关系。
所以，一个数据结构应包含以下两方面的信息：
（1）表示数据元素的信息； （2）表示 各数据元素之间的前后件关系 。 2、所谓数据的逻辑结构，是指反应数据元素之间逻辑关系的数据结构。
数据的逻辑结构有两个要素：一是数据元素的集合，通常记为D；二是D上的关系，它反映了D中数据元素之间的前后件关系，通常记为R。即一个数据节后可以表示成B=（D，R），其中B表示数据结构。
3、数据的逻辑结构在计算机存储空间中的存放形式称为数据的存储结构。
2
1.2.2数据结构的图形表示
1、一个数据的结构除了用二元关系表示外，还可以直观的用图形表示。在数据结构的图形表示中，对于数据集合D中的每一个数据元素用中间标有元素值的方框表示，一般称之为数据结点，并简称为结点；为了进一步表示各数据元素之间的前后件关系，对于关系R中的每一个二元组，用一条有向线段从前件结点指向后件结点。
2、在数据结构中，没有前件的结点称为根结点；没有后件的结点称为终端结点（也称 为叶子结点）。
1.2.3线性结构与非线性结构
1、根据数据结构中各数据元素之间前后件关系的复杂程度一般将数据结构分为两大类型： 线性结构与非线性结构。
2、如果一个非空的数据结构满足下列两个条件： （1）有且只有一个根结点；
（2）每一个结点最多有一个前件，也最多有一个后件，则称该数据结构为线性结构， 又称线性表。
3、特别说明：在一个线性结构中插入或删除任何一个结点后还应是线性结构。如果一个数据结构满足上述两个条件，但当在此数据结构中插入或删除任何一个节点后就不满足这两个条件了，则该数据结构不能称为线性结构。
1.3线性表及其顺序存储结构 1.3.1线性表的基本概念
1、线性表是最简单、最常用的一种数据结构。 2、非空线性表有以下结构特征：
（1）有且只有一个根结点a，它无前件；
1 （2）有且只有一个终结点an，它无后件；
（3）除根结点与终结端外，其他所有结点有且只有一个前件，也有且只有一个后件， 线性表中结点的个数n称为为线性表长度，当n=0时，称为空表。
3
1.3.2线性表的顺序存储结构
1、在计算机中存放线性表，一种最简单的方法是顺序存储，也称为顺序分配。 2、线性表的顺序存储结构具有两个基本特点： （1）线性表中所有元素所占的存储空间是连续的；
（2）线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。
3、顺序表的插入、删除运算
1.4栈和队列 1.4.1栈及其基本运算
1、栈：是限定在一端进行插入与删除的线性表.
2、 在栈中，允许插入与删除的一端称为栈顶，而不允许插入 删除的一端称为栈底。栈顶元素总是最后被插入的元素，从而也是 最先被删除的元素；栈底元素总是最想被插入的元素，从而也是最 后才能被删除的元素。即栈是按照“先进后出”或“后进先出”的 原则组织数据的。因此，栈也被称为“先进后出” 表或“后进先出” 表。
3、栈中元素的个数=bottom-top+1 (用值大的减值小的再加一) 。 Top=0表示栈空 top=m表示栈满。
4、栈的基本运算有三种：入栈、退栈、与读栈顶元素。
1.4.2队列及其基本运算
1、队列：是指允许在一端进行插入、而在另一端进行删除的线性表。
2、在队列中，允许插入的一端称为队尾，通常用一个称为尾指针（Rear）的指针指向队尾元素，即尾指针总是指向最后被插入的元素；允许删除的一端称为排头（也称为对头），通常也用一个排头指针（Front）指向排头元素的前一个位置。显然，在队列这种数据结构中，最先插入的元素将最先能够被删除，反之最后插入的元素将最后才能被删除。因此，队列称为“先进先出”或“后进后出”的线性表。
3、对列空与对列满的条件：队列空的条件为s=0，队列满的条件为s=1且ftont=rear 。
4
4、入队运算：是指在循环队列的队尾加入一个新元素
退队运算：是指在循环队列的排头位置退出一个元素并赋给指定的变量
1.5线性链表
1、线性表的链式存储式结构称为线性链表。 2、线性链表的基本运算： （1）在线性链表中查找指定元素；
（2）线性链表的插入：是指在链式存储结构下的线性表中插入一个新元素；
（3）线性链表的删除：是指在链式存储结构下的线性表中删除包含指定元素的结点。
1.6树与二叉树 1.6.1树的基本概念
1、树是一种简单的非线性结构。
2、树这种数据结构的基本特征：
（1）在树结构中每一个结点只有一个前件，称为父结点；没有前件的结点只有一个，称为树的根结点，简称为树的根。
（2）在树结构中，每一个结点可以有多个后件，它们都称为该结点的子结点。没有后件的结点称为叶子结点。
（3）在树结构中，一个结点所拥有的后件个数称为该结点的度。叶子结点的度为0；在树中，所有结点中的最大的度称为树的度。 3、树的最大层次称为树的深度。
4、在树中，以某结点的一个子结点为根构成的树称为该结点的一颗子树，叶子结点没有子树。
5