分享些有意思的面试题

最近为了面试，每天都会做些牛客网上的题目。

其中有些题目个人觉得出的比较有意思，分享一下_(:з」∠)_

1.图

设有6个结点的无向图，该图至少应有（）条边，才能确保是一个连通图？

答案：11

解析：注意题目中的“至少”和“确保”，题目的意思是6个顶点不管怎么连（平行边除外），任意两个顶点都可以连通，根据C(n, n-1) = n*（n-1）/2，首先5个顶点的全连通图需要的边为n*（n-1）/2=10，再加一条边与另一个顶点相连接，总共11条边，不管你怎么连，都可以确保这个图是连通的（不存在平行边）。如图：

假如只有10条边的情况，这个图肯定不是连通图。同理少于10条边也有可能不是。而11条边时无论你怎么画都是连通图。

这个题目真的是不好理解，反正我跟同学各种解释了十几分钟他都没明白（摊手）

2.智力题

A.1

B.2

C.50

D.99

E.100

答案：D

解析：选择题，代入选项试一下

3.时间复杂度

int func(int n){
 int i=0, sum=0;
 while(sum < n) sum += ++i;
 return i;
}

答案：O(n^(1/2))

解析：分析一下 while(sum < n) sum += ++i;  实际上是求等差数列的和，而等差数列的和的计算式为n(n+1)/2。

假设此题中循环了k次之后sum近似等于n，可列方程 k(k+1)/2 = n，得k = (2n – k)^(1/2)，即n^(1/2)。

4.排序

答案：AD

解析：

5.二叉搜索树

A.待删除节点有左子树和右子树时，只能使用左子树的最大值节点替换待删除节点。

B.给定一棵二叉搜索树的前序和后序遍率历结果，无法确定这棵二叉搜索树。

C.给定一棵二叉搜索树，根据节点值大小排序所需时间复杂度是线性的。

D.给定一棵二叉搜索树，可以在线性时间复杂度内转化为平衡二叉搜索树。

答案：C

解析：

A可以用右子树最小结点来替代 错误

B 对于搜索树来说，只要知道前序遍历就能还原了，第一个是根结点，之后的连续K个小于根节点的为左子树，后面的都是右子树，然后递归； 错误

C 正确， 中序遍历就可以了

D 如果允许额外的存储空间，可以先按照C生成一个排好序的数组，然后不断的找mid节点作为根来构造平衡树就是线性的，如果不允许额外空间只能靠旋转的话无法用线性时间。因为题目是单选，只能理解为不允许额外的存储空间了，所以只能选C

6.折半查找判定树

[infobox title=”下列二叉树中，可能成为折半查找判定树（不含外部结点）的是 。”]

[/infobox]

答案：A

解析（某个大佬的回答）：

折半查找判定树实际上是一棵二叉排序树，它的中序序列是一个有序序列。可以在树结点上依次填上相应的元素，符合折半查找规则的树即是所求。

B选项4、5相加除二向上取整，7、8相加除二向下取整，矛盾。C选项，3、4相加除二向上取整，6、7相加除二向下取整，矛盾。D选项，1、10相加除二向下取整，6、7相加除二向上取整，矛盾。A符合折半查找规则，正确。

这里的矛盾是指折半查找既可以向上取整，也可以向下取整，但是一个折半查找判定树中只能用一种取整方式

7.

[info]7*7 的方格，从左下角走到右上角，最短路径前提下一共有 ()  种不同路径。[/info]

答案：C(12,6)

解析：这个应该是按方格为单位的，从下到上应该是6步。也就是最短路径总共为12步——总要向上6步向右6步，就看怎么排列了。所以答案是C（12，6）