公共基础知识01.pptVIP

公共 基础知识 笔试部分 第一章 数据结构与算法 一、算法：是对题求解步骤的一种描述，它是指令的有限序列。 1、算法的基本特征： （1）可行性：针对实际问题而设计的算法，执行后能够得到满意的结果。 （2）确定性：每一个步骤必须有明确的定义，不允许有模棱两可的解释和多义性。 （3）有穷性：必须在有限时间内做完，即必须在执行有限个步骤之后停止。 （4）拥有足够的情报。 2、算法的基本要素 （1）对数据的运算和操作：算术运算 逻辑运算 关系运算 数据传输 （2）算法的控制结构：顺序 选择 循环 3、算法设计的基本方法：列举法、归纳法、递推法、递归法、减半递推、回溯法 4、算法的复杂度 （1）算法的时间复杂度：指执行算法所需要的计算工作量 （2）算法的空间复杂度：执行这个算法所需要的内存空间 二、数据结构： 1、数据结构：相互之间存在一种或多种特定关系和数据元素的集合，即数据的组织形式，它主要研究三个方面： 逻辑结构：数据集合中各数据元素之间固有的逻辑关系 数据结构主要分为线性结构与非线性结构 存储结构：各数据元素在计算机中的存储关系 对各种数据结构进行运算 2、线性结构：非空数据结构满足有且只有一个根结点，每个结点至少有一个前件，也最多有一个后件 3、线性表的顺序存储 线性表是最简单、最常用的一种数据结构。 （1）线性表的所有元素所占的存储空间是连续的。 （2）各数据元素在存储空间是按逻辑顺序存放的。 它是一种随机存取的存储结构 4、栈：只能在表的一端进行插入和删除运算的线性表，能进行插入和删除操作的为栈顶，另一端为栈底，表中没有元素为空栈。 特点：先进后出 栈的操作：入栈、退栈、读取栈的元素 -入栈运算是指在栈顶位置插入一个新的元素 -退栈运算是指取出栈顶元素并赋给一个指定变量 -读栈顶元素是指将栈顶元素赋给一个指定的变量。 当栈顶指针为0时，说明栈空，不可能进行退栈操作。称为“下溢”错误。 例1：ABCD依次入栈又依次出栈，出栈顺序是___ 例2：若进栈序列为1、2、3、4，进栈过程可以出栈，则（ ）不可能是一个出栈序列。 A、1、4、3、2 B、2、3、4、1 C、3、1、4、2 D、3、4、2、1 21 5、队列：只允许在一端删除，另一端插入的顺序表，允许删除的一端叫队头(front头指针)，允许插入的一端叫队尾(rear尾指针)，队中没有元素叫空队。 特点：先进先出 操作：进队，退队 循环队列及其计算 队列的顺序存储结构一般采用循环队列的形式。 所谓循环队列，就是将队列存储空间的最后一个位置绕道第一个位置，形成逻辑上的环状空间，供队列循环使用。 -入队运算（rear=rear+1） -退队运算（front=front+1） 当循环队列为空（s=0）时，不能进行退队运算，称为“下溢” *计算公式：* （非循环队列）元素的个数＝尾指针－头指针 （循环队列）元素的个数＝[（尾指针－头指针 + 容量）除以 容量 ]所得的余数 6、线性链表：线性表的链式存储结构称为线性链表。在存储时，每个结点有两部分组成，一部分用于存放数据元素值，称为数据域，另一部分用来存放指针，称为指针域，其中指针用来指向该结点的前一个或后一个结点。（即前件或后件） 分为线性单链表与线性双向链表 操作：插入、删除 7、循环链表：最后一个结点的指针域不是空而是指向表头结点，即在循环链表中，所有结点的指针构成了一个环状链。 8、树与二叉树 （1）树：是一种简单的非线性结构 根结点，只有直接后件没有直接前件 除根结点以外的其它结点可以划分为M（M=0）个互不相交的有限集合，每个集合又是一棵树，称为根的子树。 度：一个结点所拥有的后件个数称为该结点的度，所有结点中的最大度称为树的度。 树的深度：指最大层次数。 （2）二叉树：树的每个结点最多只能有两棵子树，并且分别称为该结点的左子树与右子树 满二叉树：除最后一层外，每一层所有结点都有两个子结点 完全二叉树：除最后一层外，每一层的结点都达到最大值，在最后的一层上只缺少右边的若干个结点。 (图36页) 二叉树的性质： 1、在二叉树的第k层上，最多有2k-1（k≥1）个结点。 2、深度为m的二叉树最多有2m-1个结点。 3、在任意一棵二叉树中，度为0的结点（即叶子结点）总是比度为2的结点多一个。 4、具有n个结点的二叉树，其深度至少为[log2n]+1,其中[log2n]表示取log2n的整数部分。 （3）二叉树的遍历： 前序：根左右 中序：左根右 后序：左右根 二叉树的存储： 二叉树通常采用链式存储结构 ABDEGCF DBGEACF DGEBFCA 例 前序遍历：abdgcefh 中序遍历：dgbaecfh 后序