ndzj081221130 · March 30, 2014 13:15
diff --git a/阿里笔试 b/阿里笔试

 记人生的第一次笔试

 确实挺难的，好多题目都没来得及仔细思考，估计挂的很惨。。。

 跳跃链表的概念。
 参考数据结构，平均搜索、插入、删除的复杂度都是O(logp(n))
 maxLevel= (logp(n)上取整) -1 
 对于有n个元素的跳表，搜索、插入、删除的时间复杂度O(n+maxLevel)
 最坏情况下，只有个1个maxLevel元素，其余都在0层上。
 i>0时，在i级花费时间为O(maxLevel),在0层花费O(n)


 求叶节点的个数？有公式的吧、
 n4 = 20 , n3 =10 , n2 = 1 , 求n0？
 树是没有回路的连通图，且，边数=节点数-1
 边数=所有节点的度数

 ----------


 三个包，A（白白）、B（黑黑），C（黑白），随机选择一个包，随机拿一个球出来，发现是白球。
 问再次从这个包中拿出白球的概率？ p = 2/3


 ----------

 生男孩、生女孩的概率相等。但生一个女孩后，会接着生第二个小孩，直到生出男孩为止。
 问每家平均有几个小孩？

 0个女孩：1/2
 1个女孩:1/4
 2个女孩: 1/8
 ...
 k个女孩:(1/2)^ (k+1)
 Ex = 1 * (1/2)^2 + 2 * (1/2)^3 + ... + k * (1/2)^(k+1)
   = 1

 ----------
 N个长为M的已排序数组，进行merge sort的复杂度是多少？

 O(N*N*M)


 ----------
 二分查找的代码？


 ----------
 N ^ 14 超过16位数字 ： 只能是10以内的数（包括10）

 10^ 14 = 1后面有14个零，是一个15位的数
 11 ^ 14 = 17位数
 > Written with [StackEdit](https://stackedit.io/).

	记人生的第一次笔试

	确实挺难的，好多题目都没来得及仔细思考，估计挂的很惨。。。

	跳跃链表的概念。
	参考数据结构，平均搜索、插入、删除的复杂度都是O(logp(n))
	maxLevel= (logp(n)上取整) -1
	对于有n个元素的跳表，搜索、插入、删除的时间复杂度O(n+maxLevel)
	最坏情况下，只有个1个maxLevel元素，其余都在0层上。
	i>0时，在i级花费时间为O(maxLevel),在0层花费O(n)


	求叶节点的个数？有公式的吧、
	n4 = 20 , n3 =10 , n2 = 1 , 求n0？
	树是没有回路的连通图，且，边数=节点数-1
	边数=所有节点的度数

	----------


	三个包，A（白白）、B（黑黑），C（黑白），随机选择一个包，随机拿一个球出来，发现是白球。
	问再次从这个包中拿出白球的概率？ p = 2/3


	----------

	生男孩、生女孩的概率相等。但生一个女孩后，会接着生第二个小孩，直到生出男孩为止。
	问每家平均有几个小孩？

	0个女孩：1/2
	1个女孩:1/4
	2个女孩: 1/8
	...
	k个女孩:(1/2)^ (k+1)
	Ex = 1 * (1/2)^2 + 2 * (1/2)^3 + ... + k * (1/2)^(k+1)
	= 1

	----------
	N个长为M的已排序数组，进行merge sort的复杂度是多少？

	O(NNM)


	----------
	二分查找的代码？


	----------
	N ^ 14 超过16位数字：只能是10以内的数（包括10）

	10^ 14 = 1后面有14个零，是一个15位的数
	11 ^ 14 = 17位数
	> Written with [StackEdit](https://stackedit.io/).
No results found