稻谷2016
50分都没人要？？？这不科学。。我来了1、B说明：计算f(n) 要计算f(n-1)， f(n-2)f(0) 一共n次 每次都只有一个操作 即O(1) n * O(1) = O(n)2、D说明：二维数组 总大小n^2 顺序查找方式下 最好情况O(1) （即1次就找到） 最坏O(n^2) 平均也是O(n^2) （O(n^2 / 2)）3、A说明：此题我比较纠结，不知道A还是D。。首先，尾指针不适合做top，因为出栈时候无法取到前一个元素（单向链表），而头指针可以做top来完成栈的基本操作（后进先出），但是此时top并不指向栈中第一个元素，top->next才是第一个元素，如果要求top必须指向栈中第一个元素，则头尾指针均不适合，而应选取头指针的下一个结点，即head->next（如图所示。）4、D说明：对A：堆是完全二叉树，高度为log2 n，而二叉排序树（并不是平衡的），最高为n（1层一个结点），正确。 B、C分别由二叉排序树和最小堆的概念即可得。D选项，错误。最小堆只要求左右子树大于根，但对于左右子树的大小没有规定，即同一层次中不一定有序。5、B说明：如图：选项A，在我构造的这个图里，最小生成树是红色边，1和3的距离是5，但其实在图里1和3的最小距离是4；选项C，在我构造的这个图里，1、2、3构成一个回路，4是一个孤立节点，4个点，3条边，有回路。B是显然的，所有边都+1没变化。6、C说明：如图，我构造这个图，拓扑排序唯一，即1、2、3、4，但没有一个顶点出度超过1（1、2、3出度为1，4为0），故C错误。 
