级公共基础知识

《级公共基础知识》由会员分享，可在线阅读，更多相关《级公共基础知识（22页珍藏版）》请在金锄头文库上搜索。

1、二级公共基础知识一、 数据结构与算法 考点提示： 1. 算法的基本概念；算法复杂度的概念和意义（时间复杂度与空间复杂度） 。 2. 数据结构的定义；数据的逻辑结构与存储结构；数据结构的图形表示；线性结构与非线 性结构的概念。 3. 线性表的定义；线性表的顺序存储结构及其插入与删除运算。 4. 栈和队列的定义；栈和队列的顺序存储结构及其基本运算。 5. 线性单链表、双向链表与循环链表的结构及其基本运算。 6. 树的基本概念；二叉树的定义及其存储结构；二叉树的前序、中序和后序遍历。 7. 顺序查找与二分法查找算法；基本排序算法（交换类排序，选择类排序，插入类排序） 。1.1 算法 算法：是指解题方

2、案的准确而完整的描述。 算法不等于程序，也不等于计算方法；算法是解题思路，而程序是解题思路的在其 编译环境中的具体描述。 算法的特征：（1）可行性：在具体环境中可执行和正确与否 （2）确定性：每一步必须有明确的定义 （3）有穷性：在有限步骤（时间）内执行完毕 （4）拥有足够的情报：初始数据或初始状态必须要充足且正确。 算法的基本要素：一是对数据对象的运算和操作（四类）二是算法的控制结构（各操作之间的执行顺序） 。 基本运算和操作包括：算术运算、逻辑运算、关系运算、数据传输。 算法的控制结构：顺序、选择、循环。 算法设计的基本方法：列举法、归纳法、递推、递归、减半递推技术、回溯法。 算法复杂度：

3、算法时间复杂度和算法空间复杂度。 算法时间复杂度：是指执行算法所需要的计算工作量（运算的执行次数） 。 衡量算法时间复杂度的主要因素：一方面依赖于问题的规模， （如 NN 矩阵乘法运算，f(n)=O(n3)） 另一方面，某些情况下还和问题的输入数据集有关（如冒泡排序）,此时用两种方法分析：（1）平均性态：用基本运算次数的加权平均值来衡量-A(n)=（2）最坏情况复杂性：最大执行次数-W(n)=算法空间复杂度：是指执行算法所占用的空间，包括算法程序所占用的空间、输入的初始 数据所占用的空间、算法执行过程中所需要的额外空间。 算法设计的要求：（1）正确性 （2）可读性 （3）健壮性（4）效率与低存

4、储量需求 1.2 数据结构的基本概念 数据结构：反映数据元素之间关系的表示。 数据结构研究的三个方面 ：（1）各数据元素之间所固有的逻辑关系，即数据的逻辑结构；)(maxxt Dnx DnxxtxP)()(（2）各数据元素在计算机中的存储关系，即数据的存储结构； （3）对各种数据结构进行的运算。 数据的逻辑结构：（1）表示数据元素的信息； （2）表示各数据元素之间的前后件关系。 数据的逻辑结构是个数据元素之间固有的，是与计算机硬件没有关系的结构 数据逻辑结构的四种形式：集合、线性结构、树形结构、图形结构 数据存储结构：是指数据的逻辑结构在计算机存储空间中的存放形式，也称数据的物理结 构。 数据

5、的物理结构反映的是数据的存储方法，这受到具体的物理存储介质制约。 数据存储结构的三种形式： 顺序、链接、索引。 一个数据结构中的数据元素，其逻辑结构和存储结构不一定相同。 数据结构的表示： 二元关系：图形表示：按前后件（逻辑）关系的复杂程度，将数据结构分为两类：线性结构（线性表）：（1）有且只有一个根结点； （2）每一个结点最多有一个前件，也最多有一个后件。 在一个线性结构中插入或删除任何一个节点后还应该是线性结构。图1.5 线性结构特列非线性结构：不满足线性结构条件的数据结构。 线性结构和非线性结构都可以是空数据结构，对于空数据结构的运算是按线性结构 的规则来处理的，则属于线性结构；否则属于

6、非线性结构。 1.3 线性表及顺序存储结构 线性表：线性表是最常用且最简单的一种线性数据结构。简言之，一个线性表是 n 个数据 元素的有限序列。线性表有两种存储结构（顺序存储和链式存储） 如 26 个英文字母的字母表（A,B,C,D,Z）是一个线性表，表中的数据元素是单个字母 字符。数据元素的定义在不同情况下各不相同 在复杂线性表中，一个数据元素可以由若干个数据项（item）组成。在这种情况下， 常把数据元素称为记录（record） ，含有大量记录的线性表又称文件（file） 非空线性表的结构特征：（1）有且只有一个根结点 a1，它无前件； （2）有且只有一个终端结点 an，它无后件； （3）

7、除根结点与终端结点外，其他所有结点有且只有一个前件，也有且只有一个后件。结 点个数 n 称为线性表的长度，当 n=0 时，称为空表。 线性表的顺序存储结构：指用一组地址连续的存储单元依次存储线性表的数据元素。 线性表的顺序存储结构具有以下两个基本特点： （1）线性表中所有元素的所占的存储空间是连续的； （2）线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。 ai 的存储地址为：ADR(ai)=ADR(a1)+(i-1)k,， ADR(a1)为第一个元素的地址，k 代表每个元素占的字节数。 可以看出，顺序存储是一种随机存取的存储结构。只要知道某元素地址，其他任何元素地 址都可以计算出来顺序

8、表的运算（时间复杂度）： 插入：在平均情况下，要插入一个元素，需要移动表中一半的元素。 删除：在平均情况下，要删除一个元素，需要移动表中一半的元素。 线性表的顺序存储结构对于小线性表或者其中元素不常变动的线性表来说是合适 的，而对于经常需要变动的大线性表就不太合适了，效率比较低。 （线性表的顺序 存储结构，插入和删除元素时需大量移动元素，故不便于插入和删除操作） 1.4 栈和队列（线性结构） 栈：是限定在一端进行插入与删除的线性表，允许插入与删除的一端称为栈顶，不允许插 入与删除的另一端称为栈底。 栈按照“先进后出”（FILO）或“后进先出”（LIFO）组织数据，栈具有记忆作用。用 top 表

9、示栈顶位置，用 bottom 表示栈底。 栈的基本运算：（1）插入元素称为入栈运算；（2）删除元素称为退栈运算；（3）读栈顶 元素是将栈顶元素还有初始化、置空、判断栈是否为空或满队列：是指允许在一端（队尾）进入插入，而在另一端（队头）进行删除的线性表。Rear 指针指向队尾（最后一个元素） ，front 指针指向队头（第一个元素的前面） 。 队列是“先进先出”（FIFO）或“后进后出”（LILO）的线性表。 队列运算：（1）入队运算：从队尾插入一个元素；（2）退队运算：从队头删除一个元素。1.5 线性链表 由于顺序存储有一些缺点，某些情况我们需采用链式存储结构。链式结构中的每一个数据 结点对应

10、于一个存储单元，这种存储单元称为存储结点，简称结点。 结点由两部分组成：（1）用于存储数据元素值，称为数据域； （2）用于存放指针，称为指针域，指向前一个或后一个结点。 线性链表：在定义的链表中，若只含有一个指针域来存放下一个元素的地址，称单链表或 线性链表。查找：在线性链表中，即使知道被访问结点的序号 i，也不能像顺序存储那样直接按序号 i 访问结点，而只能从链表的 head 出发，顺指针域 next 逐个往下搜索，直到找到第 i 个结点 为止。因此，链表不是随机存取结构,而是顺序存取结构。插入： 删除：上述线性链表虽然插入和删除比较方便，但对于空表和非空表的运算不统一，因 此，引入另一种链

11、接方式：循环链表。 循环链表的两个特点：（1）增加一个表头结点，其数据域任意，指针域指向线性表的第一 个元素的结点，循环链表的头指针指向表头结点。 （2）循环链表最后一个结点的指针域不是 NULL，而是指向表头结 点。这样所有结点指针构成了一个环状链。这样，只要给出表中任何一个结点的位置，就可以从他出发访问到表中的其他结点， 这是单链表做不到的；由于在循环链表中设置了一个表头结点，因此，在任何情况 下，循环链表中至少有一个结点存在，从而使空表与非空表的运算统一。 1.6 树与二叉树 树是一种简单的非线性结构，元素之间具有明显的层次特性。 在树结构中，每一个结点只有一个前件，称为父结点，没有前件

12、的结点只有一个，称 为树的根结点，简称树的根。每一个结点可以有多个后件，称为该结点的子结点。没 有后件的结点称为叶子结点。 在树结构中，一个结点所拥有的后件的个数称为该结点的度，所有结点中最大的度称 为树的度。树的最大层次称为树的深度。树的性质： （1）树所有结点的度之和比结点总数小 1 （2）树所有结点的度之和与边的条数之和相等二叉树的特点：（1）非空二叉树只有一个根结点；（2）每一个结点最多有两棵子树，且 分别称为该结点的左子树与右子树。二叉树的五种形态：A空树空树 只有根节点只有根节点 只有左子树只有左子树 只有右子树只有右子树 两棵子树两棵子树二叉树的基本性质：（1）在二叉树的第 k

13、层上，最多有 2k-1(k1)个结点；（求单层最多 节点数） （2）深度为 m 的二叉树最多有 2m-1 个结点；（求树的最多结点总数） （3）度为 0 的结点（即叶子结点）总是比度为 2 的结点多一个；（n0=n2+1 常用于求某个 度的结点数） （4）具有 n 个结点的二叉树，其深度至少为 intlog2n+1（二叉树的最小深度）满二叉树：一颗深度为 k 且有 2k-1 个结点的二叉树称为满二叉树(可见，满二叉树结点总 数一定是奇数) 完全二叉树：深度为 k 的，有 n 个结点的二叉树，当且仅当其每一个结点都与深度为 k 的 满二叉树中编号从 1 至 n 的结点一一对应 （5）具有 n 个

14、结点的完全二叉树的深度为log2n+1 或 log2（n+1） ；（求完全二叉树的深度）（6）设完全二叉树共有 n 个结点。如果从根结点开始，按层序（每一层从左到右）用自然 数 1，2，.n 给结点进行编号（k=1,2.n） ，有以下结论：（用于确定某个点的位置） 若 k=1，则该结点为根结点，它没有父结点；若 k1，则该结点的父结点编号为 INT(k/2)； （常用于确定父节点总数） 若 2kn，则编号为 k 的结点的左子结点编号为 2k；否则该结点无左子结点（也无右子 结点） ； 若 2k+1n，则编号为 k 的结点的右子结点编号为 2k+1；否则该结点无右子结点。 二叉树存储结构 常采用

15、链式存储结构，对于满二叉树与完全二叉树可以按层序进行顺序存储。 二叉树的遍历（按某种次序，访问二叉树中的所有结点，使得每个结点仅被访问一次）： （1）前序（根）遍历（DLR） ，首先访问根结点，然后遍历左子树，最后遍历右子树； （2）中序（根）遍历（LDR） ，首先遍历左子树，然后访问根结点，最后遍历右子树； （3）后序（根）遍历（LRD） ，首先遍历左子树，然后访问遍历右子树，最后访问根结点。注意，遍历时子树也要遵循遍历规则。 前：ABDIJEKCFG中：IDJBKEAFCG后：IJDKEBFGCA 规律：前序遍历第一个节点是树的根， 后续遍历最后一个节点是树的根。 1.7 查找技术 顺序查

16、找：从表的一端开始，顺序扫描线性表 只能使用顺序查找的情况： （1）线性表为无序表（不管是顺序存储还是链式存储） ； （2）表采用链式存储结构（即使是有序存储） 。 最坏情况需要比较 n 次 二分查找：把表不断折半，和中值比较 *只适用于顺序存储的有序表 对于长度为 n 的有序线性表，最坏情况只需比较 log2n 次 1.8 排序技术 交换类排序法：（1）冒泡排序法，最坏需要比较的次数为 n(n-1)/2 。 （2）快速排序法,最坏需要比较的次数为 n2 插入类排序法：（1）简单插入排序法，最坏需要比较的次数为 n(n-1)/2 。 （2）希尔排序法,最坏需要比较的次数为 n1.5 选择类排序法：（1）简单选择排序法，最坏需要比较的次数为 n(n-1)/2 。 （2）堆排序法，最坏情况需要 nlog2n 次比较 。 二、程序设计基础二、程序设计基础 1.形成良好的程序设计风格应注意的因素 2.结构