数组和链表的区别？
从逻辑结构来看：数组的存储长度是固定的，它不能适应数据动态增减的情况。链表能够动态分配存储空间以适应数据动态增减的情况，并且易于进行插入和删除操作。
从访问方式来看：数组在内存中是一片连续的存储空间，可以通过数组下标对数组进行随机访问，访问效率较高。链表是链式存储结构，存储空间不是必须连续的，可以是任意的，访问必须从前往后依次进行，访问效率较数组来说比较低。
如果从第i个位置插入多个元素，对于数组来说每一次插入都需要往后移动元素，每一次的时间复杂度都是O(n)，而单链表来说只需要在第一次寻找i的位置时时间复杂度为O(n)，其余的插入和删除操作时间复杂度均为O(1)，提高了插入和删除的效率。
栈与队列的区别？
队列是允许在一段进行插入另一端进行删除的线性表，对于进入队列的元素按“先进先出”的规则处理，在表头进行删除在表尾进行插入。
栈是只能在表尾进行插入和删除操作的线性表。对于插入到栈的元素按“后进先出”的规则处理，插入和删除操作都在栈顶进行。由于进栈和出栈都是在栈顶进行，所以要有一个size变量来记录当前栈的大小，当进栈时size不能超过数组长度，size+1，出栈时栈不为空，size-1。
括号匹配，表达式的计算
将中缀表达式变为后缀表达式：
①从左往右，运算数输出，运算符号入栈
②栈内：（优先级低，（）内符号依次入栈一起输出
KMP算法：快速从主串找到子串
①上下子串前缀匹配
②找到公共前后缀（取最长且小于比较的上下字串长度）
③将下面的p子串前缀移动到后缀位置
深度优先搜索和广度优先搜索是如何实现的？
深度优先搜索：(1)访问起始点v0(2)若v0的第一个邻接点没有被访问过，则深度遍历该邻接点；(3)若v0的第一个邻接点已经被访问，则访问其第二个邻接点，进行深度遍历；重复以上步骤直到所有节点都被访问过为止
广度优先搜索：(1)访问起始点v0(2)依次遍历v0的所有未访问过得邻接点 (3)再依次访问下一层中未被访问过得邻接点；重复以上步骤，直到所有的顶点都被访问过为止