- 1 二叉树遍历
- 2 如何单链表和双链表的进行插入删除操作，有什么注意细节。如何从无头单链表中删除当前节点
- 3 栈和队列分别有什么特点。如何用两个栈实现一个队列？
- 4 如何构造二叉搜索树（即二叉排序树)。以下序列是否与参考序列对应相同的二叉搜索树。
- 5 如何翻转二叉树。即交换所有结点的左右子树
- 6 常用的排序算法有哪些。时间复杂度如何。
- 7 平衡二叉树有什么优点。怎么进行插入，删除，查找操作
- 8 hash表如何构造。如何解决冲突问题。
- 9 怎么用堆栈模拟四则运算
- 10 设计一个最优算法来查找n个元素数组中的最大值和最小值。注意常数优化
- 11 迷宫问题。迷宫有墙，求当前点到出口是否有可行路径。
- 12 寻找最大的k个数
- 13 最小生成树有几种算法。时间复杂度分别是多少。
- 14 单源最短路径。
- 15 如何判断链表是否有环。
- 16 如何判断两个链表是否相交
- 17 快速查找某些字符串是否在字典中
- 18 最长上升子序列。
- 19 图匹配问题
- 20 字符串匹配
给公司技术评级准备的数据结构考题。考察都是基础内容，没敢出太难。虽然这样，大部分人只能回答上部分题目。现在感觉再提起以前搞ACM做各种状态题目，有点装逼的感觉。。。
基本能答上欢迎加入我们。
1 二叉树遍历
- 二叉树遍历有哪几种方式。
- 如何根据遍历结果重构二叉树。例如: 前序:abdcef 中序: dbaecf.
2 如何单链表和双链表的进行插入删除操作，有什么注意细节。如何从无头单链表中删除当前节点
解答: 把下一节点拷贝到当前节点，再删掉下一节点
3 栈和队列分别有什么特点。如何用两个栈实现一个队列？
解答: 栈先进后出，队列先进先出
- 进队列: push到A栈
- 出队列: 如果B栈非空，则直接从B栈pop栈顶元素。否则，则A栈依次pop出来，再push到B栈。再从B栈pop
4 如何构造二叉搜索树（即二叉排序树)。以下序列是否与参考序列对应相同的二叉搜索树。
- 参考序列: 5 6 7 4 3 2
- A: 5 4 3 2 6 7
- B：5 7 6 3 4 2
解答: A是，Ｂ不是。
5 如何翻转二叉树。即交换所有结点的左右子树
解答: 递归
TreeNode invertTree(TreeNode root) {
if (root == null) {
return null;
}
root.left = invertTree(root.left);
root.right = invertTree(root.right);
TreeNode tmp = root.left;
root.left = root.right;
root.right = tmp;
return root;
}
扩展题: 如果不用递归怎么做。（考察二叉树的遍历)
6 常用的排序算法有哪些。时间复杂度如何。
7 平衡二叉树有什么优点。怎么进行插入，删除，查找操作
8 hash表如何构造。如何解决冲突问题。
解答:
- 构造:直接定址，除留余数等
- 解决冲突: 开放地址，再哈希，链地址
9 怎么用堆栈模拟四则运算
解答: 波兰，逆波兰
10 设计一个最优算法来查找n个元素数组中的最大值和最小值。注意常数优化
解答: 每个元素都与当前最大值最小值比较，复杂度为O(2n)。优化算法是每两个数字比较一下获取较大的数和较小的数。再将较大的和当前最大的对比，较小的和当前最小的对比。这样复杂度为O(1.5n)
11 迷宫问题。迷宫有墙，求当前点到出口是否有可行路径。
解答: 图搜索算法。bfs, dfs
扩展题目:
- 双层迷宫，在某些位置可以传送到二层对应位置。
- 连连看怎么实现。(最多只能有两个转折)
- dfs,bfs算法在实际应用中可能导致什么问题。(dfs超时，bfs内存爆炸)。两者是否可以结合。问题hdu1044: 求解是否能够到达出口，如果能，求解到达时的最大携带价值 解决方案: 首先使用广搜搜出包括起点和终点在内，所有特殊点之间的最短距离，建立一个隐式图，然后使用DFS枚举各个组合，然后求出最大值，注意DFS的强剪
12 寻找最大的k个数
解答: 用最小堆保存数字。
扩展问题: 堆的插入和删除。
13 最小生成树有几种算法。时间复杂度分别是多少。
解答:
- prim 邻接矩阵:O(v^2) 邻接表:O(elog2v)
- Kruskal O(elog2e)
prim
1).输入：一个加权连通图，其中顶点集合为V，边集合为E；
2).初始化：Vnew = {x}，其中x为集合V中的任一节点（起始点），Enew = {},为空；
3).重复下列操作，直到Vnew = V：
a.在集合E中选取权值最小的边<u, v>，其中u为集合Vnew中的元素，而v不在Vnew集合当中，并且v∈V（如果存在有多条满足前述条件即具有相同权值的边，则可任意选取其中之一）；
b.将v加入集合Vnew中，将<u, v>边加入集合Enew中；
4).输出：使用集合Vnew和Enew来描述所得到的最小生成树。
Kruskal
1).记Graph中有v个顶点，e个边
2).新建图Graphnew，Graphnew中拥有原图中相同的e个顶点，但没有边
3).将原图Graph中所有e个边按权值从小到大排序
4).循环：从权值最小的边开始遍历每条边 直至图Graph中所有的节点都在同一个连通分量中
if 这条边连接的两个节点于图Graphnew中不在同一个连通分量中
添加这条边到图Graphnew中
扩展题:
- Kruskal算法如何快速判断是否处于同一个联通分量。
- 如果现在要求添加最少的边，使得任意两点相通，可以用什么算法。并查集算法。
- 怎么求一个图的联通分量数目。
14 单源最短路径。
解答: 找到一个点到其余所有节点的最短路径
a.初始时，S只包含源点，即S＝{v}，v的距离为0。U包含除v外的其他顶点，即:U={其余顶点}，若v与U中顶点u有边，则<u,v>正常有权值，若u不是v的出边邻接点，则<u,v>权值为无穷
b.从U中选取一个距离v最小的顶点k，把k，加入S中（该选定的距离就是v到k的最短路径长度）。
c.以k为新考虑的中间点，修改U中各顶点的距离；若从源点v到顶点u的距离（经过顶点k）比原来距离（不经过顶点k）短，则修改顶点u的距离值，修改后的距离值的顶点k的距离加上边上的权。
d.重复步骤b和c直到所有顶点都包含在S中。
扩展问题: 所有两个节点之间的最短距离？
15 如何判断链表是否有环。
解答: 用p,q两个指针定位与链表开头。p每次前进一格，ｑ前进两格。如果ｑ赶上ｐ则表明链表有环。
16 如何判断两个链表是否相交
解答:
- 可以用将每个地址hash，再统计总的节点数目。如果数目小于两者之和，则说明相交。
- 可以分别记录两个链表的最后节点。如果节点相同则说明相交。（如果链表有环，则这种方法不可行)
17 快速查找某些字符串是否在字典中
解答: trie树。
扩展:
- trie树可以用什么数据结构实现。
- 如何判断一个单词是否两个单词的连接。（加上结束标记)
18 最长上升子序列。
例子: 在序列1, -1, 2, -3, 4, -5, 6, -7中，最长上升子序列是4
解答: 动态规划。dp[i]表示以i结尾的子序列中LIS的长度。dp[i]=max(dpj)+(a[i]>a[j]?1:0).复杂度O(n^2).维护每个长度的最大元素的最小值，再使用二分法可以进一步减少到O(nlogn)
扩展题: 编辑距离。即如何比较两个Ａ字符串通过最小的操作数可以变成Ｂ字符串。删除一个字符，增加一个字符，修改一个字符均表示一次操作。可以继续考察01背包，完全背包。
19 图匹配问题
团队去游乐场玩过山车。过山车的每一排只有两个座位，但是A只愿意和B或D做搭档，B只愿意和F或C做搭档…。请问最多有多少对组合可以坐上过山车？
解答: 二分图匹配问题。
扩展问题: 最大流最小割。网络流
20 字符串匹配
举例来说，有一个字符串”BBC ABCDAB ABCDABCDABDE”，想知道里面是否包含另一个字符串”ABCDABD”？
解答: kmp算法。关键在于部分匹配表的构造