关于数据结构的几道题目！！！

Question

一 下列函数的时间复杂度是:
int f(int n)
{
if(n<=0) return 1;
else return n+f(n-1);
}
A O(log2 n) B O(n) C O(nlog2 n) D O(n^2)

二 设某二维数组 A[1..n, 1..n], 则在该数组中用顺序查找 查找一个元素的时间复杂度是:

A O(log2 n) B O(n) CO(nlog2 n) D O(n^2)

三若采用带头，尾指针的单向链表表示一个推栈,那么该推栈的栈顶指针top应该如何设置
A 将表头项设置为top B 将链表尾设置为top

C 随便那端作为top都可以 D 链表头,尾都不适合作为top

四 对相同的n个整数构成的二叉排序树和最小堆,下面那个说法是 不正确的

A 二叉排序树高度大于等于最小堆高度
B 对该二叉树排序树进行中序遍历可得到从小到大的序列
C 从最小根节点到其任何叶节点的路径上的节点值构成从小到大的序列
D 对该最小堆进行按层次遍历可以得到从小到大的序列

五 给定一个无向有权图G,下列哪些说法是 正确的？
A 设T为G的最小生成树,那么T中任何两个顶点之间的路径就是图G中这两个顶点的最短路径
B 设P是V到U的最短路径,如果将图G中的每条边长度均加1后,那么P仍然是从V到U的最短路径
C 如果该图有n个顶点且正好有n-1条边,那么该图一定没有回路.
D 以上说法都不对

六 对于一个n个顶点的有向无环图,如果他的拓扑排序是唯一的,那么下面那句话是 不正确的？
A 该图的最长路径是n-1;
B 该图不是一个双连通图
C 至少存在一个顶点它的出度大于1
D 当从入度为0的顶点开始分别进行深度和宽度遍历时,遍历结果是一样的

PS:如果能说明下选择原因最好了！～～～～

Answer 1

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错误。