公共基础章节总结

《公共基础章节总结》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、公共基础章节总结　　第一章数据结构与算法　　1.1算法　　算法:指解题方案的准确而完整的描述(算法不等于程序也不等于计算方法)。算法的基本特征：（1）可行性（2）确定性:是指算法中的每一个步骤都必须是有明确定义的，不允许有模棱两可的解释，也不允许有多义性。（3）有穷性:是指算法必须能在有限的时间内做完，即算法必须能在执行有限个步骤以后终止。（4）拥有足够的情报　　算法的控制结构:是指算法中各操作之间的执行顺序,一般都可以用顺序、选择、循环三种基本控制结构组合而成。算法的复杂度:主要包括时间复杂度和空间复杂度。时间复杂度：是指执行算法所需要的

2、计算工作量(度量方式：基本运算次数)。算法的空间复杂度:是指执行算法所需要的内存空间。数据的逻辑结构:数据集合中各数据元素之间所固有的逻辑关系,实际上就是指数据元素之间的前后件关系。。数据的物理结构:也称为数据的存储结构,是在对数据进行处理时，各数据元素在计算机中的存储关系。　　（2）数据的存储结构　　一个数据结构中的各数据元素在计算机存储空间中的位置关系与逻辑关系是有可能不同的(没有直接的相关性)。　　一般说来，一种数据的逻辑结构根据需要可以表示成多种存储结构，常用的存储结构有顺序、链接、索引等存储结构，而采用不同的存储结构，其数据处理的

3、效率是不同的。　　依据数据结构中各数据元素之间前后件关系的复杂程度，一般将数据结构分为两大类型：线性结构与非线性结构。　　如果一个非空的数据结构满足下列两个条件：　　a）有且只有一个根结点　　b）每一个结点最多有一个前件，也最多有一个后件，则称该数据结构为线性结构。线性结构又称线性表。　　说明：线性结构插入或删除任何一个结点后还是线性结构。　　如果一个数据结构不是线性结构。则称之为非线性结构。　　线性表是一种线性结构。数据元素在线性表中的位置只取决于它们自己的符号，即数据元素之间的相对位置是线性的。　　非空线性表有如下的一些结构特征：　　a

4、）有且只有一个根结点，它无前件　　b）有且只有一个终端结点，它无后件　　c）除根结点与终端结点外，其他所有结点有且只有一个前件，也有且只有一个后件。　　线性表中结点的个数n称为线性表的长度。当n=0时，称为空表。　　1.4栈和队列栈是限定在一端进行插入与删除的线性表　　允许插入与删除的一端称为栈顶，而不允许插入与删除的另一端称为栈底。栈是按照“先进后出”或者“后进先出”的原则组织数据的。因此，栈也被称为“先进后出”表或“后进先出”表。栈底指针一般不变，变动的是栈顶指针。　　栈元素个数的计算公式：栈顶指针-栈底指针+1　　队列:是指允许在一端

5、进行插入,而在另一端进行删除的线性表。　　允许插入的一端称为队尾，通常用一个称为尾指针的指针指向队尾元素；允许删除的一端称为排头（队头），通常也用一个排头指针指向排头元素的前一个位置。因此，队列又称为“先进先出”或“后进后出”的线性表。　　循环队列，就是将队列在存储空间的最后一个位置绕到第一个位置，形成逻辑上的形状空间，供队列循环使用。循环队列是队列的顺序存储结构。（1）链式存储方式既可以用于表示线性结构，也可用于表示非线性结构。1.6树与二叉树　　树（Tree）:是一种简单的非线性结构。　　基本特征及基本术语:　　在树的结构中，每一个结点

6、只有一个前件，称为父结点，没有前件的结点只有一个，称为树的根结点，简称为树的根。　　在树结构中，一个结点所拥有的后件，他们都称为该结点的子结点。没有后件的结点称为叶子结点。　　在树结构中，一个结点所拥有的后件个数称为该结点的度。　　树的最大层次称为树的深度。在树结构中，所有结点中的最大的度(后件个数)称为树的度。　　二叉树及其基本性质　　二叉树（binarytree）:是结点度最大为2的树。　　二叉树具有以下两个特点：　　（1）非空二叉树只有一个根结点；　　（2）每一个结点最多有两棵子树，且分别称为该结点的左子树与右子树。　　2.2二叉树的

7、基本性质(重点掌握)　　性质1：在二叉树的第K层上，最多有2k-1（k>=1）个结点。　　性质2：深度为m的二叉树最多有2m-1个结点。　　深度为m的二叉树是指二叉树共有m层。　　性质3：在任意一棵二叉树中，度为0的结点（即叶子结点）总是比度为2的结点多一个。　　满二叉树与完全二叉树是两种特殊形态的二叉树。　　满二叉树:是指除最后一层外，每一层上的所有结点都有两个子结点的二叉树。　　前面的公式完全适合于满二叉树。　　完全二叉树:除最后一层外，每一层上的结点数均达到最大值；在最后一层上只缺少右边的若干结点。一般情况下，满二叉树是完全二叉树，但

8、完全二叉树并不一定是满二叉树。　　二叉树的遍历(重要考点):是指不重复地访问二叉树中的所有结点。　　二叉树的遍历可分为三种：　　前序遍历（根左右）前序遍历结果：ABDECF　　中