淘宝2011春季校园招聘笔试试题（答案+个人解析版）
星期五晚上淘宝面试试题，我给出自己的答案，不一定正确，仅供参考。
选择题：
1. 这题是有关网络的题，由于计算机网络开始学，以前也没怎么去研究过网络这方面的东西，直接pass了！那晚坐公交回来的时候，听到几个人讨论这题，题目说的是“哪种方式的性能成本最高”，仔细琢磨这句话，意思就是哪种方式性能最差了，其实这题我做的时候还真理解错了。答案未知，以后补上！
2. 这题考的是几种排序算法，观察所给的顺列（2，1，4，9，8，10，6，20），冒泡排序经过两趟之后必然会冒出两个最大或最小的值；选择排序亦是；了解快速排序的思想之后就能发现，第一趟之后就有一个数将顺列分成两部分，左边的值都比它大（或小），右边的值都比它小（或大），而题目中这个顺列显然不满足这个特征；插入排序的思想是将顺列分成两部分，左边有序，右边无序，每趟从右边拿出一个插入到左边使有序，所以这题2，1是一个降序的序列，故应该是选择插入排序。
3. 这题倒是像考概率论的了， 由于题目说“不一致的数据与原始数据进行比较，纠正错误”，这样最后出错的情况只有一种可能——甲乙在同一个位置均出错，甲乙同时出错的概率是1/1000000，再加上在同一个位置出错，这样结果远小于1/1000000了。
4. 这题完全是考程序设计基础语法， 首先排序A、D，因为char val=’A’; val并不是通过new或者malloc在堆上分配内存，故不能用delete或者free进行回收。Val如果是全局变量，就在数据区；若是局部变量，就在内存的栈区。如果要想在堆上分配一块内存给程序，可以使用new或者malloc，一定要强调的是程序中new与delete、malloc与free是成对出现的，如果一直在分配内存而不释放，在C/C++中很容易就出现内存泄漏的错误。如果一个区域已经delete或者free释放之后，那么指向这个内存区域的指针就变成野指针，此时正确的做法就是让它赋为NULL，以防后面再次使用它导致很隐蔽的错误。还有就是一个内存块也不能多次释放，否则也会出现问题。关于指针要注意的问题很多很多，也是各公司笔试都很青睐的题目。
5. 这题是我这张卷子做的第一道题，选的是A。不过最后检查的时候，才发现还有猫腻的，说的是“深度优先中序遍历”，你应该知道不是选择A了。
6. 这题考察栈的数据结构特点——First In Last Out(FILO)，然后检查每个选项就能找出正确答案A和D。看到这题我就想到2010年全国研究生考试计算机专业统考一道题，是这样的：
“若a，b，c，d，e，f依次进栈，允许进栈、出栈交替操作，但不允许连续三次出栈，问不可能得到的序列是()”，是不是很相似啊~
7. Cache替换策略命中率最高的肯定是最少使用的算法，但付出代价应该比其它的要大吧。根据程序的局部性原理，最后进来的很可能还会用到。
8. 这个二分查找，应该是很简单的，如果你知道原理的话。但是我万万想不到我身边坐的一位科大的硕士生竟然会选择2次…难道真的应了那句话，后面再说那句是什么话。
填空题：
1. 这题，淘宝是在考我们的智商吗？？？
2. 又出现了一个二分查找，接着上面没说完的那句话吧，这是我在《编程珠玑》这本书上第一次看到的——“只有10%的程序员可以写出二分查找算法”！作者说了一个故事，说在贝尔实验室做过实验，那些专业的程序员有几个小时的时间，可以用他们选择的语言去写一个二分查找算法，即使写出高级伪代码也可以。考试结束后，差不多所有程序员都认为自己写出了正确的程序。但是最后对他们编写的代码经过测试用例验证的结果，一百多人的结果相差无几：90%的程序员写的程序中有bug！
说到这，你不妨不看下面自己动手写写二分查找算法的程序，用你熟悉的语言，看看你是属于10%还是90%。
言归正传，我写了一个程序，画线的地方是考试让我们填的空，很简单不是吗？
3. 又来了一个指针的题了，这题我想小闵肯定会做，记得他某天在QQ空间写了一篇日志，就是关于二维数组指针的问题，我还是看到他的日志没看太明白，最后翻了下书，正好还用上了，我回来测了一下我写的是对的，答案应该是*（*（p+2）+3）;
我上学期看了不少C语言的书，都是蛮经典的，其中有《C和指针》、《C专家编程》等等，我认为你如果能将下面这句解释的很清楚，你C指针这块就应该没什么大问题了：
这是一个系统调用函数，用于通知运行时系统，当某种特定的“软件中断”发生时调用特定的程序。
4. 这题也很水啊，如果平时你编程时没注意可能会出现这样的错误，调试之后才能发现；但这是考试，你肯定会多一个心眼儿，就能知道每个case分量如果没有break，会一直执行下去的，因此结果应该是 000122 。
客观题
1. 算是智力题吧，也是一个比较老的题目了，去网上一搜就出现很多解法，我目前还没发现一个最好的，我当时写的是：
让一个人P1去将汤分成3份；
第二人P2将3份汤分成两组A和B，A组一份，B组有两份；
第三人P3如果选择A的话，那么P1、P2将B组两份混合，按照一个人分汤，一个人先选汤来分配。
如果选择B的话，那么将A给P1，P2、P3按照上面方法分汤。
2. 这题算是一个经典的动态规划题目吧：
令sum(i)表示数组下标为前i个数的最大连续下标最大的和，那么，当我们加上一个正数时，和会增加；当我们加上一个负数时，和会减少。如果当前得到的和是个负数，那么这个和在接下来的累加中应该抛弃并重新清零，不然的话这个负数将会减少接下来的和。这样可以得到如下的式子：
Sum(i) = max{s(i-1)+a[i], a[i], 0} i>0 && i<N;
Sum(0)=max{a[0], 0}
程序代码为：
此题为动态规划的思想应用，上序算法的时间复杂度仅仅为O(n)，空间复杂度为O(1)。如果是用暴力搜索的话时间复杂度将达到O(n^3)，如果写这样的程序我想在这次笔试中是不会有分的。关于这种题目的变种，也是运用DP思想的，有很多很多题目，可以去网上找找看。
关于算法这块，我强烈推荐《编程之美》这本书，如果你能将这本书上的算法都能实现一遍，我想任何公司的笔试算法这块都没有问题了。我特地买了这本书，但一直没有时间去阅读，实为遗憾啊！
3. 这题我还没有什么好的算法，待以后补上。