什么是哈希表？如何处理冲突？哈希表又名散列表，是根据关键字直接寻找数据的存储位置，不需要进行比较，查找效率较高。
在构建哈希表中，最关键的就是哈希函数的设计，一般有六种方法：● 直接定址法：哈希函数为一次函数；● 数字分析法：如果关键字由多个字符或数字组成，可以考虑抽取其中的若干位作为哈希地址；● 平方取中法：对关键字做平方操作，取中间的若干位作为哈希地址；● 折叠法：将关键字分割为位数相同的几部分，取这几部分的叠加和（舍去进位）作为哈希地址；● 除留余数法：若已知整个哈希表的最大长度m，则可以取一个不大于m的数p，对关键字进行取余运算，将运算结果作为哈希地址；● 随机数法：取关键字的一个随机函数值作为哈希地址；处理冲突的方法：● 开放定址法：包含线性探测法、二次探测法、伪随机数探测法，即H(key)=(H(key) + d) MOD m其中d就是用上面三种方法确定的增量，分别为● 线性探测法：d = 1, 2, 3, ..., m-1，可以理解为一直向右寻找，子弹式；● 二次探测法：d = 12, -12, 22, -22, 32，可以理解为一直向左/右寻找，涟漪式；● 伪随机数探测法；● 再哈希法：使用另一个哈希函数计算，直到冲突不再发生；● 链地址法：将所有发生冲突的关键字所对应的数据全部存储在同一个线性链表中。
常见的树结构有哪些？● 二叉树：对于一棵树，任意节点最多包含两个子树；● 满二叉树：对于一棵二叉树，每一层的节点数目都是最大值；● 深度为$k$的满二叉树必然包含$2^k-1$个节点；● 包含$n$个节点的满二叉树的深度为$log_2(n+1)$；● 完全二叉树：对于一棵二叉树，最后一层的节点从左到右连续且紧密地排列，其他各层的节点数目都是最大值；● 包含$n$个节点的完全二叉树的深度为$floor(log_2n)+1$；● 平衡二叉树：对于一棵二叉树，任意节点的两棵子树的深度差不大于1；● 二叉搜索树：对于一棵二叉树，任意节点的非空左子树的所有结点都小于其根节点的值，任意节点的非空右子树的所有结点都大于其根节点的值，并且其左右子树都是二叉搜索树。
请解释一下数组和链表的区别从逻辑结构来看：（1）数组必须事先定义固定的长度（元素个数），不能适应数据动态地增减的情况。
当数据增加时，可能超出原先定义的元素个数；当数据减少时，造成内存浪费；数组可以根据下标直接存取。
（2）链表动态地进行存储分配，可以适应数据动态地增减的情况，且可以方便地插入、删除数据项。
（数组中插入、删除数据项时，需要移动其它数据项，非常繁琐）链表必须根据next指针找到下一个元素从内存存储来看：（1）(静态)数组从栈中分配空间, 对于程序员方便快速,但是自由度小（2）链表从堆中分配空间, 自由度大但是申请管理比较麻烦从上面的比较可以看出，如果需要快速访问数据，很少或不插入和删除元素，就应该用数组；相反，如果需要经常插入和删除元素就需要用链表数据结构了。
简述快速排序过程（1）选择一个基准元素,通常选择第一个元素或者最后一个元素,（2）通过一趟排序将待排序的记录分割成独立的两部分，其中一部分记录的元素值均比基准元素值小。
另一部分记录的元素值比基准值大。
（3）此时基准元素在其排好序后的正确位置（4）然后分别对这两部分记录用同样的方法继续进行排序，直到整个序列有序。
邻接矩阵与邻接表的区别邻接矩阵表示法：在一个一维数组中存储所有的点，在一个二维数组中存储顶点之间的边的权值邻接表表示法：图中顶点用一个一维数组存储，图中每个顶点vi的所有邻接点构成单链表对比（1）在邻接矩阵表示中，无向图的邻接矩阵是对称的。
矩阵中第i 行或第i 列有效元素个数之和就是顶点的度。
在有向图中第i 行有效元素个数之和是顶点的出度，第i 列有效元素个数之和是顶点的入度。
（2）在邻接表的表示中，无向图的同一条边在邻接表中存储的两次。
如果想要知道顶点的度，只需要求出所对应链表的结点个数即可。
有向图中每条边在邻接表中只出现一次，求顶点的出度只需要遍历所对应链表即可。
求入度则需要遍历其他顶点的链表。
（3）邻接矩阵与邻接表优缺点：邻接矩阵的优点是可以快速判断两个顶点之间是否存在边，可以快速添加边或者删除边。
而其缺点是如果顶点之间的边比较少，会比较浪费空间。
因为是一个n∗n 的矩阵。
而邻接表的优点是节省空间，只存储实际存在的边。
其缺点是关注顶点的度时，就可能需要遍历一个链表。
简单谈一下什么是二叉树，二叉树有哪些特性二叉树是n(n>=0)个结点的有限集合，由一个根结点及两棵互不相交的、分别称作左子树和右子树的二叉树组成。
二叉树也是树的一种，只是在二叉树中，每个结点最多只能有两个孩子结点。
特征：（1）每个结点最多只能有两个孩子结点（不存在度大于2的结点）；（2）二叉树是有序树，左子树和右子树次序不能颠倒，即使树中某个结点只有一棵子树，也要区别是左子树还是右子树。
简单描述一下如何将一个二叉对转换为普通树** 树可以转换为二叉树，自然二叉树也可以还原为原来的树。
并非任意一棵二叉树都能还原成一般树，此时的二叉树必须是由某一棵树（一般树）转换而来的、根结点没有右子树的二叉树。
将二叉树转换为树是树转换为二叉树的逆过程，步骤如下：（1）加线：若某个结点i是其父结点的左孩子，则将结点i的右孩子，右孩子的右孩子……全部与i 的父结点用虚线连接，当且仅当连续地沿着右孩子的右链不断搜索到的所有右孩子，都分别与结点i 的父结点用虚线连接。
（2）去线：把原二叉树中所有父结点与其右孩子的连线抹去。
这些右孩子实质上是其父结点的兄弟。
（3）整理：把虚线改为实线，调整层次结构。
Prim算法求解最小生成树的算法//Prim算法求解最小生成树void Prim_MinTree(MGraph *G){int min, i, j, k;int adjvex[MAX_VERTEX_NUM]; //保存相关顶点下标int lowcost[MAX_VERTEX_NUM];//保存相关顶点间边的权值lowcost[0] = 0; //初始化边(0,0)权值为0，即v0加入生成树//lowcost的值修改为0//就表示该下标的顶点已加入生成树adjvex[0] = 0; //选取顶点v0为起始顶点for (i = 1; i < G->n; i++) //循环遍历除v0外的全部顶点{lowcost[i] = G->edges[0][i]; //将v0顶点与其邻接点边上的权值存入数组adjvex[i] = 0; //adjvex[]初始化为顶点v0的编号0}for (i = 1; i < G->n; i++){min = INF; //初始化最小权值为无穷大j = 1;k = 0;while (j < G->n) //遍历全部顶点{if (lowcost[j] != 0 && lowcost[j] < min){//如果权值w满足0<w<minmin = lowcost[j]; //则让当前权值成为最小值k = j; //若边的权值修改，将对应顶点下标存入k}j++;}printf("(%d,%d)", adjvex[k], k); //打印当前顶点边中权值最小的边lowcost[k] = 0; //将当前边中选中的边权值置为0//表明该下标的顶点已加入生成树for (j = 1; j < G->n; j++){//依附顶点k的边权值小于此前尚未加入生成树的边的权值if (lowcost[j] != 0 && G->edges[k][j] < lowcost[j]){//则用较小的权值替换lowcost[]中的权值lowcost[j] = G->edges[k][j];//并将adjvex[]中对应位置的元素修改为新的依附顶点adjvex[j] = k;}}}}什么是B树B树是为磁盘或其他外存设备而设计的一种多叉平衡查找树，因此它也叫多路平衡查找树，在读取外存文件时许多数据库系统都使用B树或者B树的各种变形结构，如B+树，B*树。
一棵m阶的B树（注意m阶的树并不是简单的有m个叉树）或者是一棵空树，或者在定义中要满足以下要求：（1）树中每个结点最多有m棵子树（m>=2）；（2）根结点至少有两个子结点；唯一的例外是B树是一棵空树，根结点就是叶子结点；（3）除根结点外，结点中关键字的个数取值范围为(m/2) -1到m-1；（m/2向上取整）（4）所有叶子结点都在同一层；（5）除根结点和叶子结点外，如果结点有k-1个关键字，那么这个结点就有k个子结点，关键字按递增次序排列；下图就是一棵B树。
请结合图示描述一下图的深度优先遍历图的深度优先遍历步骤：（1）从图中某个顶点v0出发，首先访问v0;（2）访问结点v0的第一个邻接点，以这个邻接点vt作为一个新节点，访问vt所有邻接点。
直到以vt出发的所有节点都被访问到，回溯到v0的下一个未被访问过的邻接点，以这个邻结点为新节点，重复上述步骤。
直到图中所有与v0相通的所有节点都被访问到。
（3）若此时图中仍有未被访问的结点，则另选图中的一个未被访问的顶点作为起始点。
重复深度优先搜索过程，直到图中的所有节点均被访问过。
什么是红黑树红黑树是一种二叉查找树，但在每个结点上增加了一个存储位表示结点的颜色，可以是RED或者BLACK。
通过对任何一条从根到叶子的路径上各个着色方式的限制，红黑树确保没有一条路径会比其他路径长出两倍，因而是接近平衡的。
当二叉查找树的高度较低时，这些操作执行的比较快，但是当树的高度较高时，这些操作的性能可能不比用链表好。
红黑树（red-black tree）是一种平衡的二叉查找树，它能保证在最坏情况下，基本的动态操作集合运行时间为O(lgn)。
红黑树必须要满足的五条性质：性质1：节点是红色或者是黑色；在树里面的节点不是红色的就是黑色的，没有其他颜色，要不怎么叫红黑树呢，是吧。
性质2：根节点是黑色；根节点总是黑色的。
它不能为红。
性质3：每个叶节点（NIL或空节点）是黑色；性质4：每个红色节点的两个子节点都是黑色的（也就是说不存在两个连续的红色节点）；就是连续的两个节点不能是连续的红色，连续的两个节点的意思就是父节点与子节点不能是连续的红色。
性质5：从任一节点到其每个叶节点的所有路径都包含相同数目的黑色节点。
从根节点到每一个NIL 节点的路径中，都包含了相同数量的黑色节点。
红黑树的应用场景：红黑树是一种不是非常严格的平衡二叉树，没有AVLtree那么严格的平衡要求，所以它的平均查找，增添删除效率都还不错。