校园招聘笔试面试题及部分答案(doc 33页)

摘要
一、 笔试题
1、 给你一个二叉树的前序序列和中序序列，求其后续序列？（淘宝）
先看三个公式：
PreOrder(T)=T的根节点+PreOrder（T的左子树）+PreOrder（T的右子树）；
InOrder(T)= InOrder（T的左子树）+T的根节点+ InOrder（T的右子树）；
PostOrder(T)= PostOrder（T的左子树）+ PostOrder（T的右子树）+T的根节点。
根据以上的三给公式就可以很容易解决一下两个问题：
前序+中序 后序；
中序+后序 前序。
当然也可把树画出来，再求他的各种序列。
2、 Cache替换算法命中率最高是？（淘宝）
这个组成原理就有讲到了，可以找组成原理的书看下，把各种替换算法在理解下，在书上的P98-P99讲得很详细。
3、 给一个顺序表，然后再给你一个码值，求在二分查找改码值的比较次数？（淘宝）
自己去做二分的查找的过程，我们知道二分查找是log(n)的，一次比较次数大于log(n)肯定是错的。具体可以看下数据结构的书，P17-P18讲的很详细。
4、 编译程序中安排中间代码生成的目的是？（淘宝）
把与机器相关的工作集中到目标代码生成阶段，难度和工作量下降。便于移直和维护。利于优化。
5、 假设在n进制下，17*456=8206成立，n是多少？（淘宝）
从上面的等式中可以看到8，则进制可定大于8，因此可以从9进制开始枚举，直至满足等式，就可以了。（建议：先都转换成十进制，在实现乘法运算）
6、 要从一亿会员中抽出100万会员，考虑到公平性、相对分散、相对随机，不能重复，抽取速度要快。有一个random函数，能产生0-9的随机数。请写出你能想到的抽取方法？并写明步骤。（淘宝）
用random函数产生两个数x1、x2，那么会员号mod 100 等于x1x2的话，该会与就被选中。这样每个会员的中奖概率是1/100。

..............................