二级公共基础知识

二级公共基础知识一、数据结构与算法考点提示：1.算法的基本概念；算法复杂度的概念和意义（时间复杂度与空间复杂度）。2.数据结构的定义；数据的逻辑结构与存储结构；数据结构的图形表示；线性结构与非线性结构的概念。3.线性表的定义；线性表的顺序存储结构及其插入与删除运算。4.栈和队列的定义；栈和队列的顺序存储结构及其基本运算。5.线性单链表、双向链表与循环链表的结构及其基本运算。6.树的基本概念；二叉树的定义及其存储结构；二叉树的前序、中序和后序遍历。7.顺序查找与二分法查找算法；基本排序算法（交换类排序，选择类排序，插入类排序）。1.1算法算法：是指解题方案的准确而完整的描述。算法不等于程序，也不等于计算方法；算法是解题思路，而程序是解题思路的在其编译环境中的具体描述。算法的特征：（1）可行性：在具体环境中可执行和正确与否（2）确定性：每一步必须有明确的定义（3）有穷性：在有限步骤（时间）内执行完毕（4）拥有足够的情报：初始数据或初始状态必须要充足且正确。算法的基本要素：一是对数据对象的运算和操作（四类）二是算法的控制结构（各操作之间的执行顺序）。基本运算和操作包括：算术运算、逻辑运算、关系运算、数据传输。算法的控制结构：顺序、选择、循环。算法设计的基本方法：列举法、归纳法、递推、递归、减半递推技术、回溯法。算法复杂度：算法时间复杂度和算法空间复杂度。算法时间复杂度：是指执行算法所需要的计算工作量（运算的执行次数）。衡量算法时间复杂度的主要因素：一方面依赖于问题的规模，（如N×N矩阵乘法运算，f(n)=O(n3)）另一方面，某些情况下还和问题的输入数据集有关（如冒泡排序）,此时用两种方法分析：（1）平均性态：用基本运算次数的加权平均值来衡量----A(n)=（2）最坏情况复杂性：最大执行次数----W(n)=算法空间复杂度：是指执行算法所占用的空间，包括算法程序所占用的空间、输入的初始数据所占用的空间、算法执行过程中所需要的额外空间。算法设计的要求：（1）正确性（2）可读性（3）健壮性（4）效率与低存储量需求1.2数据结构的基本概念数据结构：反映数据元素之间关系的表示。数据结构研究的三个方面：（1）各数据元素之间所固有的逻辑关系，即数据的逻辑结构；（2）各数据元素在计算机中的存储关系，即数据的存储结构；（3）对各种数据结构进行的运算。)}({maxxtDnxDnxxtxP)()(数据的逻辑结构：（1）表示数据元素的信息；（2）表示各数据元素之间的前后件关系。数据的逻辑结构是个数据元素之间固有的，是与计算机硬件没有关系的结构数据逻辑结构的四种形式：集合、线性结构、树形结构、图形结构数据存储结构：是指数据的逻辑结构在计算机存储空间中的存放形式，也称数据的物理结构。数据的物理结构反映的是数据的存储方法，这受到具体的物理存储介质制约。数据存储结构的三种形式：顺序、链接、索引。一个数据结构中的数据元素，其逻辑结构和存储结构不一定相同。数据结构的表示：二元关系：图形表示：按前后件（逻辑）关系的复杂程度，将数据结构分为两类：线性结构（线性表）：（1）有且只有一个根结点；（2）每一个结点最多有一个前件，也最多有一个后件。在一个线性结构中插入或删除任何一个节点后还应该是线性结构。非线性结构：不满足线性结构条件的数据结构。线性结构和非线性结构都可以是空数据结构，对于空数据结构的运算是按线性结构的规则来处理的，则属于线性结构；否则属于非线性结构。1.3线性表及顺序存储结构线性表：线性表是最常用且最简单的一种线性数据结构。简言之，一个线性表是n个数据元素的有限序列。线性表有两种存储结构（顺序存储和链式存储）如26个英文字母的字母表（A,B,C,D……,Z）是一个线性表，表中的数据元素是单个字母字符。数据元素的定义在不同情况下各不相同在复杂线性表中，一个数据元素可以由若干个数据项（item）组成。在这种情况下，常把数据元素称为记录（record），含有大量记录的线性表又称文件（file）非空线性表的结构特征：（1）有且只有一个根结点a1，它无前件；（2）有且只有一个终端结点an，它无后件；（3）除根结点与终端结点外，其他所有结点有且只有一个前件，也有且只有一个后件。结点个数n称为线性表的长度，当n=0时，称为空表。线性表的顺序存储结构：指用一组地址连续的存储单元依次存储线性表的数据元素。线性表的顺序存储结构具有以下两个基本特点：（1）线性表中所有元素的所占的存储空间是连续的；（2）线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。ai的存储地址为：ADR(ai)=ADR(a1)+(i-1)k,，ADR(a1)为第一个元素的地址，k代表每个元素占的字节数。可以看出，顺序存储是一种随机存取的存储结构。只要知道某元素地址，其他任何元素地址都可以计算出来顺序表的运算（时间复杂度）：图1.5线性结构特列插入：在平均情况下，要插入一个元素，需要移动表中一半的元素。删除：在平均情况下，要删除一个元素，需要移动表中一半的元素。线性表的顺序存储结构对于小线性表或者其中元素不常变动的线性表来说是合适的，而对于经常需要变动的大线性表就不太合适了，效率比较低。（线性表的顺序存储结构，插入和删除元素时需大量移动元素，故不便于插入和删除操作）1.4栈和队列（线性结构）栈：是限定在一端进行插入与删除的线性表，允许插入与删除的一端称为栈顶，不允许插入与删除的另一端称为栈底。栈按照“先进后出”（FILO）或“后进先出”（LIFO）组织数据，栈具有记忆作用。用top表示栈顶位置，用bottom表示栈底。栈的基本运算：（1）插入元素称为入栈运算；（2）删除元素称为退栈运算；（3）读栈顶元素是将栈顶元素还有初始化、置空、判断栈是否为空或满队列：是指允许在一端（队尾）进入插入，而在另一端（队头）进行删除的线性表。Rear指针指向队尾（最后一个元素），front指针指向队头（第一个元素的前面）。队列是“先进先出”（FIFO）或“后进后出”（LILO）的线性表。队列运算：（1）入队运算：从队尾插入一个元素；（2）退队运算：从队头删除一个元素。1.5线性链表由于顺序存储有一些缺点，某些情况我们需采用链式存储结构。链式结构中的每一个数据结点对应于一个存储单元，这种存储单元称为存储结点，简称结点。结点由两部分组成：（1）用于存储数据元素值，称为数据域；（2）用于存放指针，称为指针域，指向前一个或后一个结点。线性链表：在定义的链表中，若只含有一个指针域来存放下一个元素的地址，称单链表或线性链表。查找：在线性链表中，即使知道被访问结点的序号i，也不能像顺序存储那样直接按序号i访问结点，而只能从链表的head出发，顺指针域next逐个往下搜索，直到找到第i个结点为止。因此，链表不是随机存取结构,而是顺序存取结构。插入：删除：上述线性链表虽然插入和删除比较方便，但对于空表和非空表的运算不统一，因此，引入另一种链接方式：循环链表。循环链表的两个特点：（1）增加一个表头结点，其数据域任意，指针域指向线性表的第一个元素的结点，循环链表的头指针指向表头结点。（2）循环链表最后一个结点的指针域不是NULL，而是指向表头结点。这样所有结点指针构成了一个环状链。这样，只要给出表中任何一个结点的位置，就可以从他出发访问到表中的其他结点，这是单链表做不到的；由于在循环链表中设置了一个表头结点，因此，在任何情况下，循环链表中至少有一个结点存在，从而使空表与非空表的运算统一。1.6树与二叉树树是一种简单的非线性结构，元素之间具有明显的层次特性。在树结构中，每一个结点只有一个前件，称为父结点，没有前件的结点只有一个，称为树的根结点，简称树的根。每一个结点可以有多个后件，称为该结点的子结点。没有后件的结点称为叶子结点。在树结构中，一个结点所拥有的后件的个数称为该结点的度，所有结点中最大的度称为树的度。树的最大层次称为树的深度。树的性质：（1）树所有结点的度之和比结点总数小1（2）树所有结点的度之和与边的条数之和相等二叉树的特点：（1）非空二叉树只有一个根结点；（2）每一个结点最多有两棵子树，且分别称为该结点的左子树与右子树。二叉树的五种形态：二叉树的基本性质：（1）在二叉树的第k层上，最多有2k-1(k≥1)个结点；（求单层最多节点数）（2）深度为m的二叉树最多有2m-1个结点；（求树的最多结点总数）（3）度为0的结点（即叶子结点）总是比度为2的结点多一个；（n0=n2+1常用于求某个度的结点数）（4）具有n个结点的二叉树，其深度至少为int[log2n]+1（二叉树的最小深度）AΦ空树只有根节点只有左子树只有右子树两棵子树满二叉树：一颗深度为k且有2k-1个结点的二叉树称为满二叉树(可见，满二叉树结点总数一定是奇数)完全二叉树：深度为k的，有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应（5）具有n个结点的完全二叉树的深度为[log2n]+1或[log2（n+1）]；（求完全二叉树的深度）（6）设完全二叉树共有n个结点。如果从根结点开始，按层序（每一层从左到右）用自然数1，2，….n给结点进行编号（k=1,2….n），有以下结论：（用于确定某个点的位置）①若k=1，则该结点为根结点，它没有父结点；若k1，则该结点的父结点编号为INT(k/2)；（常用于确定父节点总数）②若2k≤n，则编号为k的结点的左子结点编号为2k；否则该结点无左子结点（也无右子结点）；③若2k+1≤n，则编号为k的结点的右子结点编号为2k+1；否则该结点无右子结点。二叉树存储结构常采用链式存储结构，对于满二叉树与完全二叉树可以按层序进行顺序存储。二叉树的遍历（按某种次序，访问二叉树中的所有结点，使得每个结点仅被访问一次）：（1）前序（根）遍历（DLR），首先访问根结点，然后遍历左子树，最后遍历右子树；（2）中序（根）遍历（LDR），首先遍历左子树，然后访问根结点，最后遍历右子树；（3）后序（根）遍历（LRD），首先遍历左子树，然后访问遍历右子树，最后访问根结点。注意，遍历时子树也要遵循遍历规则。前：ABDIJEKCFG中：IDJBKEAFCG后：IJDKEBFGCA规律：前序遍历第一个节点是树的根，后续遍历最后一个节点是树的根。1.7查找技术顺序查找：从表的一端开始，顺序扫描线性表只能使用顺序查找的情况：（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.结构化程序设计的主要原则3.结构化程序的基本结构与特点4.结构化程序设计的原则和方法的应用5.面向对象程序设计的主要优点6.面向对象方法的基本概念（对象、类和实例、消息、继承和多态性）注意区分：结构化程序设计和面向对象程序设计本章学习方法：这两章以概述的形式简介了规范化开发软件的方法。与数据结构不同，这两章内容主要是记忆性的知识点。程序设计基础的内容与大纲改革前添加了面向对象程序设计的内容，大家可以对本章进行几次细读后了解即可；软件工程基础这章主要考核内容为结构化分析及结构化设计方法（即SA及SD，约占50%），信息量较大，其次是软件测试（约占20%），考生需要将相关的概念及规则背诵，在以后有机会进行程序开发时这些知识可以得到深刻理解。2.1程序设计方法与风格当今主导程序设计风格：“清晰第一，效率第二”良好的程序设计风格