判断题
1.It is always possible to represent a tree by a one-dimensional integer array.（T）
想一下不相交集的表示方法，下标表示某一个顶点，数组内储存的数字表示该顶点的父节点，由于每一个顶点都只有一个父节点，所以这样的表示是没有问题的
2.During the sorting, processing every element which is not yet at its final position is called a "run". To sort a list of integers using quick sort, it may reduce the total number of recursions by processing the small partion first in each run.(F)
这个题考察的是什么是影响快速排序的因素，应该是每一次pivot的选择，只有当pivot每次都选择最居中的元素时，递归的深度最浅，如果每一次都选择最大或最小的pivot,那么递归地深度最深
3.For binary heaps with N elements, the *BuildHeap* function (which adjust an array of elements into a heap in linear time) does at most N−log(N+1) comparisons between elements.(F)
线性时间建堆，最多的比较次数是2N-2
4.Given that the pushing sequence of a stack is { 1, 2, ⋯, n } and popping sequence is { x1,x2,⋯,xn }. If x2=n, we can obtain 2 different possible popping sequences.(F)
我们只需要满足：n是第二个出堆就可以了，也就是说前N-1个元素我们可以任意弹出一个元素
5.The best "worst-case time complexity" for any algorithm that sorts by comparisons only must be O(NlogN).(T)
基于比较的排序算法，最佳的上界是$O(N\log{N})$
选择题tips
- 无向图中去掉一条边会减少两个顶点的度，有向图中去掉一条边会减少一个顶点的入度和一个顶点的出度
- 利用循环来进行树的中序遍历时，空间复杂度为$O(H)$,因为我们需要用到的栈的大小至少为树的最大高度
- 最大流问题中，Gf是从互不连接的顶点加上增广路径得到的，Gr是原图减去增广路径并且加上反向边得到的
- 给定一个图的顶点数量和边的数量，求至少有多少个连通分量时，将边环连接，这样求得的连通分量数最少，求最多有多少连通分量，将边连成完全图，这样求得的连通分量最多
- 树中节点的度表示这个节点有几个孩子，度的和等于边的和，等于节点数加1（根节点）
- 对二叉搜索树的节点的删除，我们将删除的节点用该节点的左子树最大值或者右子树最小值进行替代，其他的替代方法是不行的
- 文件夹目录的打印用到的方法是前序遍历
- 哈希的二次探测法，每一次是在第一次得到的结果上加上$i^2$，而不是加上$i^2$如果还是冲突，再加上$(i+1)^2$.
- 堆排序是原地排序，不需要占用额外的空间
- 判断一个排序算法是否是稳定的，我们看在这个算法里相等的元素在算法前后是否次序发生了改变，如果次序改变了，那么就不是稳定的，如果次序不变，那么就是稳定的，稳定的排序算法有：冒泡排序，归并排序，插入排序，基数排序，桶排序，不稳定的排序算法有：选择排序，快速排序，堆排序，希尔排序、
- Unoin by size得到的树的高度最高为$\log{N}+1$,最高的情况是，每一次都是大小相同的树合并，从两个孤立的根两两配对直到所有顶点结合成为一颗树
- 审题要注意，堆的问题往往重建后还会有删除的要求，不要只读一半的条件就选答案
- 堆排序建立的堆是最大堆，然后进行N次删除最大值的操作，这就是堆排序的过程
- 在遇到和pivot相等的元素时停下的条件下，所有元素都相等的数组的快速排序的时间复杂度为$N\log{N}$
- 在利用栈将中序表达式转化为后续表达式的过程中，优先级较小的操作符入栈前，要将栈内所有优先级大于等于它的操作符出栈，右括号不入栈，当选到右括号操作符时，将栈内所有在左括号上的元素出栈。
- rehash要取大于原来的TableSize两倍的最小质数