二级共公基础知识教程
第一章数据结构与算法 1.1 算法
算法：是指解题方案的准确而完整的描述。
算法不等于程序，也不等计算机方法，程序的编制不可能优于算法的设计。
算法的基本特征：是一组严谨地定义运算顺序的规则，每一个规则都是有效的，是明确的，此顺序将在有限的次数下终止。特征包括： （1）可行性；
（2）确定性，算法中每一步骤都必须有明确定义，不充许有模棱两可的解释，不允许有多义性；
（3）有穷性，算法必须能在有限的时间内做完，即能在执行有限个步骤后终止，包括合理的执行时间的含义； （4）拥有足够的情报。
算法的基本要素：一是对数据对象的运算和操作；二是算法的控制结构。 指令系统：一个计算机系统能执行的所有指令的集合。
基本运算和操作包括：算术运算、逻辑运算、关系运算、数据传输。 算法的控制结构：顺序结构、选择结构、循环结构。
算法基本设计方法：列举法、归纳法、递推、递归、减斗递推技术、回溯法。 算法复杂度：算法时间复杂度和算法空间复杂度。 算法时间复杂度是指执行算法所需要的计算工作量。 算法空间复杂度是指执行这个算法所需要的内存空间。 1.2 数据结构的基本基本概念 数据结构研究的三个方面：
（1）数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构；
（2）在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构； （3）对各种数据结构进行的运算。
数据结构是指相互有关联的数据元素的集合。 数据的逻辑结构包含：
（1）表示数据元素的信息；
（2）表示各数据元素之间的前后件关系。 数据的存储结构有顺序、链接、索引等。 线性结构条件：
（1）有且只有一个根结点；
（2）每一个结点最多有一个前件，也最多有一个后件。 非线性结构：不满足线性结构条件的数据结构。 1．3 线性表及其顺序存储结构 线性表由一组数据元素构成，数据元素的位置只取决于自己的序号，元素之间的相对位置是线性的。
在复杂线性表中，由若干项数据元素组成的数据元素称为记录，而由多个记录构成的线性表又称为文件。
非空线性表的结构特征：
（1）且只有一个根结点a1，它无前件； （2）有且只有一个终端结点an，它无后件；
（3）除根结点与终端结点外，其他所有结点有且只有一个前件，也有且只有一个后件。结点个数n称为线性表的长度，当n=0时，称为空表。 线性表的顺序存储结构具有以下两个基本特点：
（1）线性表中所有元素的所占的存储空间是连续的；
（2）线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。
ai的存储地址为：ADR(ai)=ADR(a1)+(i-1)k,，ADR(a1)为第一个元素的地址，k代表每个元素占的字节数。
顺序表的运算：插入、删除。 （详见14--16页） 1．4 栈和队列
栈是限定在一端进行插入与删除的线性表，允许插入与删除的一端称为栈顶，不允许插入与删除的另一端称为栈底。
栈按照“先进后出”（FILO）或“后进先出”（LIFO）组织数据，栈具有记忆作用。用top表示栈顶位置，用bottom表示栈底。 栈的基本运算：（1）插入元素称为入栈运算；（2）删除元素称为退栈运算；（3）读栈顶元素是将栈顶元素赋给一个指定的变量，此时指针无变化。
队列是指允许在一端（队尾）进入插入，而在另一端（队头）进行删除的线性表。Rear指针指向队尾，front指针指向队头。
队列是“先进行出”（FIFO）或“后进后出”（LILO）的线性表。 队列运算包括（1）入队运算：从队尾插入一个元素；（2）退队运算：从队头删除一个元素。 循环队列：s=0表示队列空，s=1且front=rear表示队列满 1．5 线性链表
数据结构中的每一个结点对应于一个存储单元，这种存储单元称为存储结点，简称结点。 结点由两部分组成：（1）用于存储数据元素值，称为数据域；（2）用于存放指针，称为指针域，用于指向前一个或后一个结点。 在链式存储结构中，存储数据结构的存储空间可以不连续，各数据结点的存储顺序与数据元素之间的逻辑关系可以不一致，而数据元素之间的逻辑关系是由指针域来确定的。 链式存储方式即可用于表示线性结构，也可用于表示非线性结构。 线性链表，HEAD称为头指针，HEAD=NULL（或0）称为空表，如果是两指针：左指针（Llink）指向前件结点，右指针（Rlink）指向后件结点。 线性链表的基本运算：查找、插入、删除。 1．6树与二叉树 一、树的基本概念
在树结构中，每一个结点只有一个前件，称为父结点，没有前件的结点只有一个，称为树的根结点，简称为树的根。
在树结构中，每一个结点可以有多个后件，它们都称为该结点的子结点。没有后件的结点称为叶子结点。
在树结构中，一个结点所拥有的后件个数称为该结点的度。 叶子结点的度为0。
树的最大层次称为树的深度。
在一个算术表达式中，有运算符和运算对象。一个运算符可以有若干个运算对象。例职，取正（+）等只有一个运算对象，称为单目运算符；二个运算对象称为双目运算符，三目运算符。
用树来表示算术表达式的原则如下：
表达式中的每一个运算符在树中对应一个结点，称为运算符结点。
运算符的每一个运算对象在树中为该运算符结点的子树（在树中的顺序为从左到右）。 运算对象中的单变量均为叶子结点。 二、二叉树及其基本性质 1、什么是二叉树
二叉树是一种很有用的非线性结构。二就树具有以下两个特点： 非空二叉树只有一个根结点；
每一个结点最多有两棵子树，且分别称为该结点的左子树与右子树。
由以上特点可以看出，在二叉树中，每一个结点的度最大为2，即所有子树（左子树或右子树）也均为二叉树，而树结构中的每一个结点的度可以是任意的。另外，二叉树中的每一个结点的子树被明显地分为左子树与右子树。可以没有其中的一个，也可以全没有。 二叉树的基本性质
性质1：在二叉树的第K层上，最多有（K≥1）个结点。 性质2：浓度为M的二叉树最多有2m-1 个结点。 深度为m 的二叉树是指二叉树共有m层。
性质3：在任意一棵二叉树中度为0的结点（即叶子结点）总是比度为2的结点多一个。 性质4：具有n个结点的二叉树，其深度至少为[ log2n]+1,其中[ log2n]表示取的整数部分。 满二叉树与完全二叉树
满二叉树与完全二叉树是两种特殊形态的二叉树。 满二叉树
所谓满二叉树是指这样的一种二叉树；除最后一层外，每一层上的所有结点都有两个子结点。这就是说，在满二叉树中，每一层上的结点数都达到最大值，即在满二叉树的第K层上有2K-1个结点，且深度为m的满二叉树有2m-1个结点。 完全二叉树
所谓完全二叉树是指这样的二叉树，除最后一层外，每一层上的结点数均达的最大值；在最后一层上只缺少右边的若干结点。 列确切地说，如果从根结点起，对二叉树的结点自上而下、自左至右用自然数进行边疆编号，则深度为m、且有n 个结点的二叉树，当且仅当其每一个结点都与深度为m的满二叉树中编号从1到n的结点一一对应时，称之为完全二叉树。
对于完全二叉树来说，叶子结点只可能在层次最大的两层上出现；对于任何一个结点，若其右分支下的子孙结点的最大层次为p，则其左分支下的子孙结点的最大层次或为p，或为p+1。 由满二叉树与完全二叉树的特点可以看出，满二叉树也是完全二叉树，而完全二叉树一般不是满二叉树。
完全二叉树还具有以下两个性质：
性质5：具有n个结点的完全二叉树的深度为[ log2n]+1。
性质6：设完全二叉树共有n个结点。如果从根结点开始，按层序（每一层从左到右）用自然数1，2，…，n给结点进行编号，则对于编号为k （k=1,2,…n）的结点有以下结论： 若k=1，则该结点为根结点，它没有父结点；若k>1，则该结点的父结点编号为INT(k/2)。 若2k≤n，则编号为k 的结点的左子结点编号为2k ；否则该结点无左子结点（显然也没有右子结点）。
若2k+1≤n，则编号为k 的结点的右子结点编号为2k+1；否则该结点无右子结点。 三、二叉树的存储结构 二叉树的遍历
二叉树的遍历是指不重复地访问二叉树的所有结点。
在遍历二叉树的过程中，一般先遍历左子树，然后再遍历右子树。
1、前序遍历（DLR）
所谓前序遍历是指在访问根结点、遍历左子树与遍历右子树这三者中，首先访问根结点，然后遍历左子树，最后遍历右子树；并且，在遍历左、右子树时，仍然先访问根结点，然后遍历左子树，最后遍历右子树。F，C，A，D，B，E，G，H，P 2、中序遍历（LDR）
所谓中序遍历是指在访问根结点、遍历左子树与遍历右子树这三者中，首先遍历左子树，然后访问根结点，最后遍历右子树；并且，在遍历左、右子树时，仍然先遍历左子树，然后访问根结点，最后遍历右子树。A，C，B，D，F，E，H，G，P 3、后序遍历（LRD）
所谓中序遍历是指在访问根结点、遍历左子树与遍历右子树这三者中，首先遍历左子树，然后遍历右子树，最后访问根结点；并且，在遍历左、右子树时，仍然先遍历左子树，然后遍历右子树，最后访问根结点。A，B，D，C，H，P，G，E，F 1.7查找技术 一、顺序查找
顺序查找又称顺序搜索。顺序查找一般是指在线性表中查找指定的元素，其基本方法如下：从线性表的第一个元素开始，依次将线性表中的元素与被查元素进行比较，若相等则表示找到（即查找成功）；若线性表中所有的元素都与被查元素进行了比较但都不相等，则表示线性表中没有要找的元素（即查找失败）。
顺序查找的效率是很低的。以下两种情况只能采用顺序查找： 如果线性表无序表（即表中元素的排列是无序的），则不管是顺序存储结构还是链式存储结构，都只能用顺序查找。
即使是有序线性表，如果采用链式存储结构，也只能用顺序查找。 二、二分法查找
二分法查找只适用于存储的有序表。在此所说的有序表是指线性表的中元素按值非递减排列（即从小到大，但允许相邻元素值相等）。
设有序线性表的长度为n，被查元素为x，则对分查找的方法如下： 将x与线性表的中间项进行比较：
若中间项的值等于x，则说明查到，查找结束；
若x小于中间项的值，则在线性表的前半部分（即中间项以前的部分）以相同的方法进行查找；
若x大于中间项的值，则在线性表的后半部分（即中间项以后的部分）以相同的方法进行查找。
这个过程一直进行到查找成功或子表长度为0（说明线性表中没有这个元素）为止。
显然，当有序线性表为顺序存储时才能采用二分查找，并且，二分查找的效率要比顺序查找高得多。可以证明，对于长度为n的有序线性表，在最坏情况下，二分查找只需要比较log2n次，而顺序查找需要比较n次。 1.8排序技术
一、交换类排队序法
所谓交换类排序法是指借助数据元素之间的互相交换进行排序的一种方法。冒泡排序法与快速排序法都属于交换类的排序方法。 1、 冒泡排序法 基本过程如下：
首先，从表头开始往后扫描线性表，在扫描过程中逐次比较相邻两个元素的大小。若相邻两个元素中，前面的元素大于后面的元素，则将它们互换，称之为消去了一个逆序。放最大值
然后，从后到前扫描剩下的线性表，同样，在扫描过程中逐次比较相邻两个元素的大小。若相邻两个元素中，后面的元素大于前面的元素，则将它们互换，这样就又消去了一个逆序。放最小值。
重复上述过程，直到剩下的线性有变空为止，此时的线性表已经变为有序。
假设线性表的长为n，则在最坏情况下，冒泡排序需要经过n/2遍的葱馨往后的扫描和n/2遍的从后往前的扫描，需要的比较的次数为n(n-1)/2。 2、 快速排序法
快速排序法也是种互换类的排序法，但由于它比冒泡排序法的速度快，因此称之为快速排序法。
基本思想如下：
从线性表中选取一个元素，设T，将线性表后面小于T的元素移到前，而前大于T的元素移支后面，结果就将线性表分成了两部分（称为两个子表），T插入到其分界线的位置处，这个过程称为线性表的分割。通过对线性表的一次分割，就以T为分界线，将线性表分成了前后两个子表，且前面子表中的所有元素均不大于T，而后面子表中的所有元素均不小于T。
如此反复，则此时的线性表就变成了有序表。
步骤：首先，在表的第一个，中间一个与最后一个元素中选取中项，设为P（K），并将P（K）赋给T，再将表中的第一个元素移到P（K）的位置上。
然后设置两个指针i和j分别指向表的起始与最后的位置。反复操作以下两步：
（4） 将j逐渐减小，并逐次比较P（j）与T，直到发现一个P(j) （5） 将i逐渐减小，并逐次比较P（i）与T，直到发现一个P(i)>T为止，将P(i)移到P(j)位置上。 上述两个操作交替进行，直到指针i与j 指向同一个位置（即i=j）为止，此时将P(i)的位置上。 分割需要记忆，用栈来实现。 二、 插入类排序法 1、 简单插入排序法 所谓插入排序，是指将无序序列中的各元素依次插入到已经有序的线性表中。 一般来说，假设线性中前j-1元素已经有序，现在要将线性表中第j个元素插入到前面的有序子表中，插入过程如下： 道德将第j个元素放到一个变量T中，然后从有序子表的最后一个元素（即线性表中第j-1个元素）开始，往前逐个与T进行比较，将大于T的元素均依次向后移动一个位置，直到发现一个元素不大于T为止，此时就将T（即原线性表中的第j个元素）插入到刚移出的空位置上，有序子表的长度就变为j了。效率与冒泡法相同 在最坏情况下，简单插入排序需要n(n-1)/2次比较。 2、 希尔排序法 基本思想如下： 将整个无序序列分割成若干小的子序列分别进行插入排序。 子序列的分割方法如下： 将相隔某个增量H的元素构成一个子序列。在排序过程中，逐次减小这个增量，最后当H减到1时，进行一次插入排序，排序就完成。增量序列一般取h=n/2k(k=1,2,…[log2n],其中n为待排序序列的长度。 其效率与增量序列有关。在最坏情况下，需要的比较次数为O（Ｎ１.５）。
计算机二级公共基础知识
