[公共基础知识电子书百度云盘]公共基础知识备考教材电子版 公共基础教材.docx

公共基础知识备考教材电子版 公共基础教材.docx 公共基本知识备考教材电子版 公共基本教材

　　第一章数据构造和算法
　　算法
　　★算法：是指解题方案的对的而完整的描述。
　　算法不等于程序，也不等计算机措施，程序的编制不也许优于算法的设计。
　　算法的基本特性：是一组严数为0或容量个数，表达队空或队满。
　　队列运算涉及入队运算：从队尾插入一种元素；退队运算：从队头删除一种元素。
　　线性链表
　　数据构造中的每一种结点相应于一种寄存单元，这种寄存单元称为寄存结点，简称结点。
　　★线性链表的结点由两部分构成：
　　用于寄存数据元素值，称为数据域；
　　用于寄存指针，称为指针域，用于指向前一种或后一种结点。
　　★在链式寄存构造中，寄存数据构造的寄存空间可以不持续，各数据结点的寄存顺序和数据元素之间的逻辑关系可以不一致，而数据元素之间的逻辑关系是由指针域来拟定的。根据指针域指向方向的不同样，线性链表有单向链表，双向链表，循环链表等。
　　链式寄存措施即可用于表达线性构造，也可用于表达非线性构造。
　　线性链表，HEAD 称为头指针，HEAD=NULL称为空表，如果是两指针：左指针指向前件结点，右指针指向后件结点。
　　线性链表的基本运算：查找、插入、删除。
　　树和二叉树
　　树是一种简朴的非线性构造，所有元素之间具有明显的层次特性。
　　在树构造中，每一种结点只有一种前件，称为父结点，没有前件的结点只有一种，称为树的根结点，简称树的根。每一种结点可以有多种后件，称为该结点的子结点。没有后件的结点称为叶子结点。
　　★在树构造中，一种结点所拥有的后件的个数称为该结点的度，所有结点中最大的度称为树的度。树的最大层次称为树的深度。
　　二叉树的特点：非空二叉树只有一种根结点；每一种结点最多有两棵子树，且分别称为该结点的左子树和右子树。二叉树中结点的度只也许有度为0、1、2三种状态。
　　★二叉树的基本性质：
　　在二叉树的第k 层上，最多有2k-1 个结点；
　　深度为m 的二叉树最多有2m -1个结点；
　　度为0的结点总是比度为2的结点多一种；
　　具有n 个结点的二叉树，其深度至少为[log2n]+1,其中[log2n]表达取log 2n 的整数部分；
　　具有n 个结点的完全二叉树的深度为[log2n]+1；
　　设完全二叉树共有n 个结点。如果从根结点开始，按层序用自然数1，2，?.n 给结点进行编号，有如下结论：
　　①若k=1，则该结点为根结点，它没有父结点；若k>1，则该结点的父结点编号为INT； ②若2k ≤n ，则编号为k 的结点的左子结点编号为2k ；否则该结点无左子结点；
　　③若2k+1≤n ，则编号为k 的结点的右子结点编号为2k+1；否则该结点无右子结点。
　　★满二叉树是指除最后一层外，每一层上的所有结点有两个子结点，则k 层上有2k-1个结点深度为m 的满二叉树有2m -1个结点。
　　★完全二叉树是指除最后一层外，每一层上的结点数均达到最大值，在最后一层上从右边开始依次缺少若干结点。在完全二叉树中，总结点数是偶数时度为1的结点只有1个，并且叶子结点数占一半；总结点数是奇数时度为1的结点没有，并且叶子结点数是总结点数加1的一半。
　　二叉树寄存构造采用链式寄存构造，对于满二叉树和完全二叉树可以按层序进行顺序寄存。
　　★二叉树的遍历：
　　前序遍历，一方面访问根结点，然后遍历左子树，最后遍历右子树；
　　中序遍历，一方面遍历左子树，然后访问根结点，最后遍历右子树；
　　后序遍历一方面遍历左子树，然后访问遍历右子树，最后访问根结点。
　　例如下图：根据遍历规则，前序遍历的成果为FCADBEGHP ，中序遍历为ACBDFEHGP ，后序遍历为ABDCHPGEF 。
　　1．7查找技术
　　★顺序查找的使用状况：
　　线性表为无序表；
　　表采用链式寄存构造。
　　★二分法查找只合用于顺序寄存的有序表，对于长度为n 的有序线性表，采用二分法查找，最坏状况只需比较log 2n 次。
　　1．8排序技术
　　排序是指将一种无序序列整顿成按值非递减顺序排列的有序序列。
　　★互换类排序法：冒泡排序法，最坏状况下需要比较的次数为n/2；迅速排序法，最坏状况下需要比较的次数为n/2。
　　★插入类排序法：简朴插入排序法，最坏状况需要n/2次比较；希尔排序法，最坏状况需要O 次比较。
　　★选择类排序法：简朴选择排序法, 最坏状况需要n/2次比较；堆排序法，最坏状况需
　　要O 次比较。
　　本章****题
　　1、算法的空间复杂度是指。
　　A. 算法在实行过程中所需要的计算机寄存空间
　　B. 算法所解决的数据量
　　C. 算法程序中的语句