数据结构与算法
栈
栈是一种线性表,其限制只能在表尾进行插入或者删除操作。由于该特定又被称为后进先出的线性表。
队列
队列是一种先进先出的线性表,其限制只能在线性表的一端进行插入,在另一端进行删除。
二叉树
二叉树是n个有限元素的集合,该集合为空,或者由一个称为根的元素和两个不相交的,被称为左子树和右子树的二叉树组成。
满二叉树
一个二叉树,如果每一层的结点数都达到最大值,则这个二叉树就是满二叉树。
完全二叉树
一颗深度为k的由n个节点的二叉树,对树中的结点按照从上到下,从左到右的顺序进行编号,如果编号为i(1<=i<=n)的结点与满二叉树编号为i的结点在二叉树中的位置相同,则这颗二叉树称为完全二叉树。
二叉树的遍历算法
- 前序遍历:若二叉树为空树,则执行空逻辑,否则:
- 访问根节点
- 递归前序遍历左子树
- 递归前序遍历右子树
- 中序遍历:若二叉树为空树,则执行空逻辑,否则:
- 递归中遍历左子树
- 访问根节点
- 递归中遍历右子树
- 后续遍历:若二叉树为空树,则执行空逻辑,否则:
- 递归后遍历左子树
- 递归后遍历右子树
- 访问根节点
解决Hash冲突的方法
开放定址法:当发生hash冲突时,如果哈希表没有被填满,那么可以把这这个值存放到冲突位置的下一个空位置中去。
链地址法:对相同的哈希地址,设置一个单链表,单链表内方的都是哈希冲突的元素。
AVL树
AVL树是一种改进版的搜索二叉树,其引入平衡因子(左子支高度与右子之高度只差的绝对值),通过旋转使其尽量保持平衡。
任何一个结点的左子支高度与右子支高度只差的绝对值不超过1。
红黑树
红黑树本身是由2-3树发展而来,红黑树时保持黑平衡的二叉树,其查找会比AVL树慢一点,添加和删除元素会比AVL树快一点。增删改查统计性能上将,红黑树更优。
红黑树主要特征是在每个结点上增加一个属性表示结点颜色,可以红色或者黑丝。红黑树和AVL树类似,都是在进行插入和删除的时候通过旋转自身保持平衡,从而获得较高的查找性能。红黑树保证从根节点到叶尾的最长路径不超过最短路径的2倍,所以最差时间复杂度为O(logn)。红黑树通过重新着色和左右旋转,更加高效地完成了插入和删除之后地自平衡调整。
稳定排序和非稳定排序地区别
稳定排序:排序前后两个相等的数相对位置不变,则算法稳定。
非稳定排序:排序前后两个相等的数相对位置发生了变化,则算法不稳定。
常见的稳定排序
插入排序,冒泡排序,归并排序
常见的非稳定排序
希尔排序,直接选择排序,堆排序,快速排序
简述插入排序
每一趟将一个待排序的记录按照其关键字的大小插入到已经排好序的一组记录的适当位置上,直到所有的排序记录全局插入为止。
排序算法稳定,时间复杂度O(n^2),空间复杂度O(1)。
简述希尔排序
将记录按下标的一定增量进行分组,对每组进行直接插入排序,每次排序后减小增量,当增量少至1时排序完毕。
排序算法不稳定,时间复杂度O(nlogn),空间复杂度O(1)。
简述直接选择排序
每次在未排序序列中找到最小元素,和未排序序列的第一个元素交换位置,再在剩余未排序序列中重复该操作直到所有的元素排序完毕。
排序算法不稳定,时间复杂度O(n^2),空间复杂度O(1)。
简述堆排序
将待排序序列看作一个树状数组,建立一个二叉树堆,通过这种数据结构进行每个元素的插入,完成排序工作。
排序算法不稳定,时间复杂度O(nlogn),空间复杂度O(1)。
简述冒泡排序
比较相邻的元素,如果第一个比第二个大就进行交换,对每一对相邻元素做同样的工作。
排序算法稳定,时间复杂度O(n^2),空间复杂度O(1)。
简述快速排序
随机选择一个基准的元素,通过一趟排序将要排序的数据分割成独立的两个部分,一部分全部小于等于基准元素,一部分全部大于基准元素,再按照此方法递归对这两部分进行快速排序。
排序算法不稳定,时间复杂度O(nlogn),空间复杂度O(logn)。
简述归并排序
将待排序需了分成两部分,然后对两部分进行归并排序,最后进行合并。
排序算法稳定,时间复杂度为O(nlogn),空间复杂度为O(n)。
图
图是由顶点集合和顶点之间的边集合组成的一种数据结构,分为有向图和无向图。
有向图:边具有方向性。
无向图:边不具有方向性。
邻接矩阵
用一个二维数组存放顶点间关系的数据,这个二维数组称为邻接矩阵。
对于无向图,邻接矩阵时对称矩阵。
邻接表
邻接表时通过链表表示图连接关系的一种方法。对于表头结点所对应的顶点存在相邻顶点,则把相邻顶点依次存放于表头结点所指向的单向链表中。
图的深度优先搜索DFS
将每个顶点的访问标志设置为False,之后搜索图中每个顶点,如果没有被访问,则以该顶点V0为起始点出发,访问此顶点,然后以此从V0的各个未被访问的邻接点出发涮肚优先搜索遍历图,直到图中所有和V0由路径相通的顶点都被访问到。
图的广度优先搜索
从图中的某个顶点V0出发,并再访问此顶点之后以此访问V0的所有未被访问过的邻接点,之后按这些顶点被访问的先后次序依次访问它们的邻接点,直至图中所有和V0由路径相通的顶点都被访问到。
简述最小生成树和其对应的算法
对于有n个结点的原图,生成原图的极小连通子图,其包含原图中的所有n个结点,并且有保持图联通的最少的边。
普里姆算法:取图中任意一个顶点v作为生成树的根,之后王生成树上添加新的顶点w。在添加的顶点w和已经在生成树上的顶点v之间指定存在一条边,并且该边的权值在所有的连通顶点v和w之间的边中取值最小。之后继续往生成树上添加顶点,直至生成树上含有n-1个顶点为止。
简述最短路径算法
Dijkstral算法为求解一个点到其余各点最小路径的方法,其算法为:
假设我们求解的顶点v到其余各个点之间的最短路径,n次循环至n个顶点全部遍历:
- 从权值数组中找到权值最小的,标记该边端点k
- 打印该路径及权值
- 如果存在经过顶点k到顶点i的边比v->i的权值小
- 更新权值数组及对应路径
简述堆
堆是一种完全二叉树形式,其可分为最大值堆和最小值堆。
最大值堆:子节点均小于父节点,根节点是树中最大的结点。
最小值堆:子节点均大于父节点,根节点是树种最小的结点。
简述Set
数据结构树是一种由优先结点组成的层次关系的集合,其特点如下:
- 每个结点由零个或多个子节点
- 只有一个结点没有父节点,该节点称为根节点
- 除根节点外,每个节点有且只有一个父节点
简述对树的理解
数据结构树是一种有限节点组成的层次关系的集合。其特点如下:
- 每个结点由零个或者多个子节点
- 只有一个结点没有父节点,该结点为根节点
- 出根节点外,每个节点有且必有一个父节点
二叉查找树
- 二叉查找树的左子树若不为空,则左子树上所有节点的值均小于它根节点的值。
- 二叉查找树的右子树若不为空,则右子树上所有节点的值均发育它根节点的值。
- 二叉查找树的左子树,右子树也分别是二叉查找树。
- 没有键值相等的节点。