[转]Hulu 2013北京地区校招笔试题

时间:2021-10-01 03:51:55

填空题:

1、中序遍历二叉树,结果为ABCDEFGH,后序遍历结果为ABEDCHGF,逆序遍历结果为?

2、对字符串HELL0_HULU中的字符进行二进制编码,使得字符串的编码长度尽可能短,最短长度为?

3、对长度12的有序数组进行二分查找,目标等概率出现在数组的每个位置上,则平均比较次数为?

4、一副扑克(去王),每个人随机的摸两张,则至少需要多少人摸牌,才能保证有两个人抽到同样的花色。

分析:抽屉原理,C(4,2)=10

每个人摸到的两张牌的花色有10种情况: 

两张红桃、两张黑桃、两张方块、两张梅花、红桃和黑桃、红桃和方块、红桃和梅花、黑桃和方块、黑桃和梅花、方块和梅花。 

若10个人摸到的牌的花色分别是上述10种情况,则10个人中没有两个人摸到的牌的花色相同。 

若有11个人摸牌,由抽屉原理可知至少有两个人摸到的牌的花色相同。

5、x个小球中有唯一一个球较轻,用天平秤最少称量y次能找出这个较轻的球,写出y和x的函数表达式y=f(x)

分析:y=log3(x)

6、3的方幂及不相等的3的方幂的和排列成递增序列1,3,4,9,10,12,13……,写出数列第300项

7、无向图G有20条边,有4个度为4的顶点,6个度为3的顶点,其余顶点度小于3,则G有多少个顶点

8、桶中有M个白球,小明每分钟从桶中随机取出一个球,涂成红色(无论白或红都涂红)再放回,问小明将桶中球全部涂红的期望时间是?

9、煤矿有3000吨煤要拿到市场上卖,有一辆火车可以用来运煤,火车最多能装1000吨煤,且火车本身需要烧煤做动力,每走1公里消耗1吨煤,如何运煤才能使得运到市场的煤最多,最多是多少?

10、1,2,3,4…..n,n个数进栈,有多少种出栈顺序,写出递推公式(写出通项公式不得分)

11、宇宙飞船有100,000位的存储空间,其中有一位有故障,现有一种Agent可以用来检测故障,每个Agent可以同时测试任意个位数,若都没有故障,则返回OK,若有一位有故障,则失去响应。如果有无限多个Agent可供使用,每个Agent进行一次检测需要耗费1小时,现在有2个小时时间去找出故障位,问最少使用多少个Agent就能找出故障。



大题:

1、n个数,找出其中最小的k个数,写出代码,要求最坏情况下的时间复杂度不能高于O(nlogk)

2、写程序输出8皇后问题的所有排列,要求使用非递归的深度优先遍历。

3、有n个作业,a1,a2…..an,作业aj的处理时间为tj,产生的效益为pj,最后完成期限为dj,作业一旦被调度则不能中断,如果作业aj在dj前完成,则获得效益pj,否则无效益。给出最大化效益的作业调度算法。