文档介绍：有赞2019校招前端笔试
1、给定⼀个有序整数数组以及⼀个整数
，请问在
该数组中查找⽐
⼤的最⼩
元素的最优算法时间复杂度是多少？
选项
A: O(loglogn)
B: O(logn)
C: O(n)
D: O(logn x logn)
正确答案: B
参考解析
- ⼆分法查找
- 找到 k 后，k 右边的就是要找的
- ⼆分法的时间复杂度是 O(log n)
- 最后再加⼀，但是这个会忽略掉
2、以下哪个排序算法对只有⼀两个元素乱序的数组排序性能最好？
A. 快速排序
B. 堆排序
C. 归并排序
D. 插⼊排序
正确答案: D
3、有 8 个完全相同的硬币，其中只有⼀个硬币⽐其他 7 个重,其余七个⼀
样重，给你⼀个没有刻度的天平，请问最少需要称多少次才能找到重的那个
硬币？
A. 2
B. 3
C. 4
D. 5
正确答案: A
⼀共8枚硬币，先分成3，3，⾏称重，如果同等重量，则再秤⼀次就可
以找到；如果重量不等，那么找到重的⼀堆中的3个随机取两个去秤重，3枚硬币那个重就能
分辨出来了。
4、数组的 leader 元素是指⽐它右边所有元素都⼤的元素，请问查找数组
中所有 leader 元素的最优算法时间复杂度是多少？
(logn)
(n)
(nlogn)
(n²)
正确答案: B
只需遍历⼀边数组即可。从右向左遍历，每遍历出来⼀个leader，存下这个数，后续数只需
与这个leader⽐较即可，直到有新的leader产⽣。
5、给定以下哪些遍历结果可以重建出 BST？
A. 先序、中序、后序中的任意⼀个
B. 先序或者后序中的⼀个
C. 先序和中序两个
D. 先序和后序两个
正确答案: C D
由于题⽬说的是重建出来⼆叉搜索树，所以前序遍历（中左右），后续遍历（左右中）都可
唯⼀确定⼀个BST（可通过顺序判断左右⼦树），⽽中序遍历（左右中）排序出来是顺序排
序，⽆法重建树。
关于D选项，如果是⼀般⼆叉树是不能的，因为左右⼦树此时是⽆法区分的。但在BST中，
左⼦树都⼩于右⼦树，则可以区分出左右⼦树，故可建成排序⼆叉树
6、请问下⾯这个函数的时间复杂度是多少（假设 n>0）？
function fn(n)
{
if (n === 1)
return 1;
else
return fn(n-1) + fn(n-1);
}
(n)
(nlogn)
(n²)
(2ⁿ)
正确答案: D
这⾥值得注意的是，⾥⾯有两个递