本文主要整理了一些python二级要考到的知识点，希望对各位有帮助。
数据结构和算法是计算机科学的两个重要的支柱。他们是不可分割的整体。
一、算法
算法是指解题方案的准确而完整的描述。但算法不等于程序，也不等于计算方法。当然程序也可以作为算法的一种描述，但程序通常还需要考虑很多与方法和分析无关的细节问题，这是因为在编程时要收到计算机系统运行环境的限制。通常，程序的编制不可能优于算法的设计。
作为一个算法，一般应具有可行性、确定性、有穷性、拥有足够情报四个基本特征。也因此设计算法时不仅仅需要考虑结果的可靠性，即不仅考虑算法结果的可行性，还要考虑不知的确定性，时间和步骤的有穷性等。因此算法是一组严谨地定义运算顺序的规则，并且每一个规则都是有效的，明确的，此顺序将在有限的次数下终止。
一个算法通常有两种基本要素组成：一是对数据对象的运算和操作，二是算法的控制结构。因此设计算法时不仅需要考虑树结构的设计，还要考虑数据的操作和运算及各操作之间的执行顺序。
算法的设计可以撇开具体的计算机程序设计语言，但算法的实现必须借助程序设计语言中提供的数据类型及其算法。
计算机算法是指解题方案的准确而完整的描述
二、存储结构
数据的逻辑结构在计算机存储空间中存放形式称为数据的存储结构也称数据的物理结构
三、算法复杂度
算法的复杂度主要包括时间复杂度和空间复杂度：算法在运行过程中需要辅助存储空间的大小成为算法的空间复杂度：算法的时间复杂度是指执行算法所需要的计算工作量，计算法执行过程中所需要的基本运算次数。
为了能够比较客观的反映出一个算法的效率，在度量一个算法的工作量时，不仅应该与所使用的计算器、程序设计语言以及程序编制者无关，而且还应该与算法实现过程中的许多细节无关。因此，可以用算法在执行过程中所需基本运算的执行次数来度量算法的工作量
四、算法的时间复杂度
是指执行算法所需要的计算工作量。不仅应该与所使用的计算机、程序设计语言以及程序编制者无关，而且还应该与算法实现过程中的许多细节无关。为此，可以用算法在执行过程中所需基本运算的执行次数来度量算法的工作量。
五、算法的空间复杂度
一般是指执行这个算法所需要的内存空间。一个算法所占用的存储空间包括算法程序所占的空间，输入的初始数据所占的存储空间以及算法执行过程中所需要的额外空间。在许多实际问题中，通常采用压缩存储技术，以便尽量减少不必要的额外空间。
六、算法效率
我们通常用时间复杂度和空间复杂度来衡量算法效率。算法的时间复杂度是指执行算法所需要的计算工作量；算法所执行的基本运算次数与问题的规模有关。算法的空间复杂度是指执行这个算法所需要的内存空间；一般来说，一种数据的逻辑结构根据需要可以表示成多种存储结构。
七、算法的基本特征
可行性、确定性、有穷性、拥有足够的情报
八、算法分析的目的
算法分析是指对一个算法的运行时间和占用空间做定量的分析，一般计算出相应的数量级，常用时间复杂度和空间复杂度表示。分析算法的目的就是要降低算法的时间复杂度和空间复杂度，提高算法的执行效率
九、原地工作
一个算法的空间复杂度，一般是指执行这个算法所需要的内存空间。一个算法所占用的存储空间包括程序所占的空间、输入的初始数据所占的存储空间以及算法执行过程中所需要的额外空间。其中额外空间包括算法程序执行过程中的工作单元以及某种数据结构所需要的附加存储空间。如果额外空间相对于问题规模来说是常数，则称该算法是原地(inplace)工作的。
十、线型结构与非线性结构
根据数据结构中数据元素之间前后件关系的复杂程序，一般将数据结构分为两大类：线性结构与非线性结构。一个空的数据结构究竟是属于线性结构还是属于非线性结构，这要根据具体情况来确定。并且线性结构与非线性结构都可以是空的数据结构。
如果一个非空对的数据结构满足下列两个条件：（1）有且只有一个根节点。（2）每个节点最多有一个前件也最多有一个后件。则称该数据结构为线型结构，又称线型表，不是线性结构的就是非线性结构。
十一、栈
图
用top表示栈顶位置，用bottom表示栈底。
11.1
栈是限定在一端进行插入与删除的线性表，允许插入与删除的一端称为栈顶，不允许插入与删除的另一端称为栈底。栈按照“先进后出”（FILO）或“后进先出”（LIFO）组织数据，栈具有记忆作用。
在主程序调用子程序先是要首先保存主程序当前的状态，然后去执行子程序，最终把子程序的执行结果返回到主程序调用子程序的位置，继续向下执行。这种调用符合栈“先进后出”的功能
11.2
链式结构则把每一个存储结点分两部分：一部分用于存储数据元素的值，称为数据域；另一部分用于存放下一个元素的序号，称指针域。带链的栈则可以通过指针域的变化改变原有的栈的组织数据原则,带链栈的栈底指针是随栈的操作而动态变化的；而顺序栈的栈底指针不变，栈顶指针改变。
11.3栈中元素个数
1.栈中的元素个数=bottom-top+1
2.栈的存储空间S（1：m），如果初始状态为0，则栈中元素个数为top，如果初始状态top=m+1，则栈中元素个数为m-top+1,top改变为x后，栈中有m+1-x个
11.4栈的基本运算：
（1）插入元素称为入栈运算；
（2）删除元素称为退栈运算；
（3）读栈顶元素是将栈顶元素赋给一个指定的变量，此时指针无变化。
11.5
带链的栈与顺序存储的栈相比，入栈操作时不会受到栈存储空间的抑制而发生溢出
11.6
栈有向上生长堆栈和向下生长的堆栈之分，当栈是倒着压的话，当你存放一个元素之后，那么top=m+1-1=m，存两个元素top=m+1-2=m-1，因此当top=1时，栈中有m+1-1=m个元素，此时栈已满，如果再存放元素则发生"溢出"。
十二、队列
图
12.1
队列是指允许在一端（队尾）进入插入，而在另一端（队头）进行删除的线性表。Rear指针指向队尾，front指针指向队头。
12.2
队列是“先进先出”（FIFO）或“后进后出”（LILO）的线性表。
十三、特殊队列—循环队列
图
循环队列：就是将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上环状空间，供队列循环使用。循环队列是队列的顺序存储结构。
13.1
循环队列的头指针front指向队列的第一个元素的前一位置，队尾指针rear指向队列的最后一个元素。循环队列的动态变动需要头尾指针共同反映。
13.2循环队列长度
循环队列列的长度是：（sq.rear-sq.font+maxsize）%maxsize,所以循环队列的长度是由队头和队尾指针共同决定的。
13.3基本运算
循环队列主要有两种基本运算：入队运算与退队运算。
每进行一次入队运算，队尾指针（rear）就进1。
每进行一次退队运算，排头指针（front）就进1。
当rear或front的值等于队列长度+1时，就将rear或front的值置为1。
一般情况下rear大于front，因为入队的元素肯定比出队的元素多。特殊的情况是rear达到数组的上线之后又从数组的低端开始，此时是rear小于front的
当循环队列满或空时front=rear
rear大于front的情况下，队列里的个数为：rear-front
rear小于front的情况下，队列里的个数为：m-front+rear
十四、栈和队列的区别
栈和队列都是一种特殊的操作受限的线性表，只允许在端点处进行插入和删除。二者的区别是：栈只允许在表的一段进行插入或者删除操作，是一种“后进先出”的线性表，队列只允许在表的一端进行插入，在另一端进行删除操作，是一种“先进先出”的线性表
十五、线性链表
15.1
线性表的链式存储结构称为线性链表，为了适应线性表的链式存储结构，计算机存储空间被划分为一个一个小块，每个小块占若干字节，通常这些小块为存储结点，简称结点。
15.2
每个存储节点分为两部分：一部分用于存储数据元素的值，称为数据域；另一部分用于存放下数据元素的存储序号，即指向后件的结点，称为指针域。
15.3链式存储结构
链式存储结构：存储数据结构的存储空间可以不连续，各数据结点的存储顺序与数据元素之间的逻辑关系可以不一致，而数据元素之间的逻辑关系是由指针域来确定的。
链式存储结构，要对某个节点进行存取，都得从链的头指针指向的结点开始，这是一种顺序存储的存储结构
15.4顺序存储结构
顺序存储结构：数据元素存放在一组地址连续的存储单元中，每个数据元素地址可以通过LOC（ai）=LOC（a1）+（i-1）L计算得到，从而实现随机存取。
15.5
链式存储结构与顺序存储结构即可用于表示线性结构，也可用于表示非线性结构-链式结构。在表示非线性结构时，其指针域的个数要多一些。
15.6基本运算
线性链表的基本运算：查找、插入、删除。
15.7增加头结点的目的
在单链表中，增加头节点的目的是方便实现运算。头结点不仅标识了表中首节点的位置，而且根据单链表（包含头结点）的结构，只要掌握了表头，就能访问整个链表，因此增加头结点的目的是为了方便运算的实现。
15.8
顺序结构使用的是连续物理空间，链式结构可以使用零散的物理空间存储，链式结构更灵活，不存在谁节约空间的说法
15.9
线性表的顺序存储结构的存储空间只用于存放节点数据，而链式存储结构的存储空间不仅要存放节点数据，还要存放数据指针，所以线性表的链式存储结构所需要的存储空间一般要多于顺序存储结构，并且存储空间通常是不连续的
15.10
进行插入和删除时，不需要移动表中的元素：为了要在线性链表中插入一个新元素，首先要给该元素分配一个新结点，以便用于存储该元素的值，然后将存放新元素值的结点连接到线性表中的指定位置。在线型链表的插入过程中不发生数据移动的现象，只需要改变有关节点的指针即可，从而提高插入的效率。为了在线性链表中删除包含指定元素的结点，首先要在线性链表中找到这个结点，然后将要删除结点放回到可利用栈。在线性链表中删除一个元素后，不需要异动表的数据元素，只需要改变被删除元素所在结点的前一个结点的指针域即可。
15.11
遍历是指不重复的访问所有节点。线型单表链每个节点只有一个指针域，由这个指针只能找到后件接地点，但不能找到前件的结点。双向表链中的每个节点设置两个指针，左指针指向前件结点，右指针指向后件结点。循环链表中增加了一个表头结点，循环链表中的所有节点的指针构成了一个环状。二叉链表即二叉树的链式结构，每个存储结点有两个指针域，左指针域指向该节点的左子节点的存储地址，右指针域指向该节点的右子节点的存储地址
15.12
在初始状态为front=rear=NULL的带链队列入队时，在带链队列中入队时，如果插入的结点即是队首结点又是队尾结点，则rear和front同时指向这个结点，否则在循环队列的队尾介入一个新元素，rear指向新增节点的数据域，rear+1，front不变。退队时，若退队后队列不为空，则在循环队列的排头位置推出一个元素并赋给指定的变量，front指向第二个结点的数据域，front+1，rear不变；若退队队列中只有一个结点，退队后队列为空，则front=rear=null。当front=rear不为空时，front和rear同时指向这个唯一元素，所以该队列中的元素个数为1.当front=rear=null时，队列中的元素个数为0.
15.13
在链式存储结构中，每个结点指针域中的指针用于指向该结点的前件或后件。在用链式结构表示非线性结构时，其指针域的个数要多一些。并不能确定有多个指针域的链表是线性结构还是非线性结构。
十六、树与二叉树
树是一种简单的非线性结构，所有元素之间具有明显的层次特性。
16.1二叉树的特点
（1）非空二叉树只有一个根结点；
（2）每一个结点最多有两棵子树，且分别称为该结点的左子树与右子树。
16.2二叉树的基本性质
性质很多主要靠理解，这里只说最重要的：
度为0的结点（即叶子结点）总是比度为2的结点多一个；
满二叉树：是指除最后一层外，每一层上的所有结点有两个子结点
深度为n的满二叉树的总结点为2n-1个，叶子结点个数为2（n-1）
完全二叉树：是指除最后一层外，每一层上的结点数均达到最大值;在最后一层上只缺少右边若干结点。
完全二叉树的总结点为奇数时，叶子结点数是总结点加以再除以2
16.3
结构图的深度表示控制的层数
16.4二叉树的遍历：
（1）前序遍历（DLR），首先访问根结点，然后遍历左子树，最后遍历右子树；
中左右
（2）中序遍历（LDR），首先遍历左子树，然后访问根结点，最后遍历右子树；并且在遍历左、右子树时，仍然先遍历左子树，然后访问根节点，最后遍历右子树
左中右
（3）后序遍历（LRD）首先遍历左子树，然后访问遍历右子树，最后访问根结点。
左右中
16.5二叉树计算公式总结：
1.n层二叉树的第n层最多为2^（n-1）个
2.二叉树结点计算公式N=n0+n1+n2+n3，度为0的结点比度为2的结点多一个。N=1xn1=2xn2+3xn3+1
3.具有n个结点的完全二叉树的深度为log2(n)+1
4.深度为k的二叉树最多有2^k-1个结点
5.如果二叉树共有m个结点，度为1的结点有n个如果m-n为偶数，则不存在这样的二叉树。
十七、排序
快速排序：通过一趟排序将待排序记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，再分别对这两部分记录继续进行排序，以达到整个序列的有序；
插入排序：将无序列表中各元素一次插入到已经有序的线性表中，从而得到一个新的序列
选择排序：扫描整个线性表，从中选出最小的元素，将它交给表的最前面（这是他应有的位置），然后对剩下的子表采用统一的方法，直到表空为止
归并排序：将两个或两个以上的有序表组合成一个新的有序表
冒泡排序：是一种最简单的交换类排序方法，它是通过相邻数据元素的交换逐步将现行表变成有序。假设线性表的长度为n，则在最坏的情况下，冒牌排序需要经过n/2遍的从前往后的扫描和n/2的从后往前的扫描需要比较的次数为n(n-1)/2次,
简单插入排序：在简单cherub排序法中，每一次比较后最多移调一个逆序，因此这种排序方法的效率与冒泡排序法相同
简单选择排序：对于长度为n的序列，选择排序需要扫描n-1遍，每一遍扫描均从剩下的子表中选出最小的元素，然后将该最小的元素与子表中第一个元素进行交换。简单选择排序法在最坏的情况下需要比较n(n-1)/2次
堆排序法：首先将一个无序序列简称堆，然后将堆顶元素（序列中最大项）与堆中最后一个元素交换（最大项应该在序列的最后）满足父节点必须大于其子节点。在最坏的情况下，堆排序需要比较的次数为O（nlog2n）
希尔排序和快速排序后，都能消除多个逆序
十八、强连通图
在有向图中，若任意两个顶点都连通，则称该图是强连通图，这样的有向图的形状是环状的，因此n个顶点的强连通图至少有n条边。
十九、用链表表示线性表的优点
链式存储结结构服了顺序存储结构的缺点：它的结点空间可以动态申请和释放；它的数据元素的逻辑次序靠结点的指针来指示，不需要移动数据元素，因此链式存储结构下的线型表便于插入和删除操作
二十、最多次数
对分查找：O(log2n)[只适用于顺序存储的有序列表，有序列表因为会存在值相等的情况，因此不适用]
快速排序：n(n-1)/2
冒泡排序：n(n-1)/2
直接插入排序：n(n-1)/2
简单插入排序：n(n-1)/2
堆排序：nlog2n
希尔排序：n1.5
寻找最大项和最小项：n-1
二十一、时间复杂度
冒泡排序：O(n2)
直接插入排序：O(n2)
快速排序：O（n2）
希尔排序：O(n1.5)
顺序查找：O（n）
寻找最大项和最小项：O(n-1)
堆排序：O（nlog2n）
对分查找：O（log2n）
周安
