2013.5.05--阿里巴巴--实习生笔试
总体而言，这份笔试题还比较正常，只是这次做题采取的方式不对，最后的综合题有20分但是没仔细看就没时间了， 还是要总结经验教训。就其它题目而言，这次倒都没什么难度，有些可以预料的会考的是排序、多线程、操作系统、概率问题和C的基本知识。趁着脑袋里面还记着一些题目，我把一些我有印象的记录下来供各位参考。 阿里笔试竟然没考大数据，神奇！
一、单项选择题
1.下列说法错误的是：
A.SATA硬盘的速度大约为500Mbps
B.读取18XDVD光盘数据的速度为1Gbps
C.千兆以太网的数据读取速度为1Gpbs
D.读取DDR3内存数据的速度为100Gbps
思路：这种题目看似要是记住了就好了，其实记住常识就好了， 首先，C肯定是对的，因为就是定义嘛，内存比较快比较正常，所以D应该是对的，500Mbps大概就是62.5M/s的传输速度，显然符合我们对硬盘的预期，于是B显然是错的，光盘怎么可能有硬盘快。
如果要严格意义上分析这个题目的意思的话，SATA 3.0的速度约为600Mbps，18XDVD前面的18X是倍速的意思，1X约为150KB/s(1.2288Mbps),18X最多不过24Mbps，所以说B太离谱了，至于DDR3，可以看到，DDR3-2133的极限传输速度大概150Gbps。
2.（）不能用于Linux中的进程通信
A.共享内存
B.命名管道
C.信号量
D.临界区
思路：见深刻理解Linux进程间通信，需要注意的是，这个题目要是概念清楚点就没啥问题了，临界区是保证在某一时刻只有一个线程能访问数据的方法，也就是说它是实现进程同步互斥的控制机制，信号量虽然也能用来控制进程线程的同步互斥，但是~
3. 设在内存中有P1,P2,P3三道程序，并按照P1,P2,P3的优先级次序运行，其中内部计算和IO操作时间由下表给出（CPU计算和IO资源都只能同时由一个程序占用）：
P1:计算60ms—》IO 80ms—》计算20ms
P2:计算120ms—》IO 40ms—》计算40ms
P3:计算40ms—》IO 80ms—》计算40ms
完成三道程序比单道运行节省的时间是（）
A.80ms
B.120ms
C.160ms
D.200ms
思路：没什么好解释的
4. 两个等价线程并发的执行下列程序，a为全局变量，初始为0，假设printf、++、–操作都是原子性的，则输出不可能是（）
void foo() {if(a <= 0) {a++;}else{a--;}printf("%d", a);}A.01
B.10
C.12
D.22
思路：当时我的直觉告诉我应该选奇数，回来想了一下，好像得到了答案：看答案可知每个线程进foo函数不止一次，那么我们暂且假设两个线程分别进入foo函数X次，假设给线程编号，线程1有m次被堵在a++,线程2有n次被堵在a++处，那么线程1必然会执行（X-m)次a- -，线程2必然会执行（X-n)次a- -，那么最终a的值为（m+n)-((X-m)+(X-n))=2(m+n)-2X，也就是说a最后的值必然是偶数
5.给定fun函数如下，那么fun(10)的输出结果是（）
int fun(intx){return(x==1)? 1 : (x + fun(x-1));}A.0
B.10
C.55
D.3628800
思路：10+9+…+1=55
6.在c++程序中，如果一个整型变量频繁使用，最好将他定义为（）
A.auto
B.extern
C.static
D.register
思路：寄存器快嘛，而且整型也正好能放进寄存器，详见变量的存储类型
7.长为n的字符串中匹配长度为m的子串的复杂度最短为（）
A.O(N)
B.O(M+N)
C.O(N+LOGM)
D.O(M+LOGN)
思路：KMP算法的时间复杂度是O(M+N)，但是BM算法会相对而言更快，但是也是O(M+N)。当时选的是B,但是加个“最”总让人不放心，回来查看资料，用后缀数组的方法可以在O(M+LOGN)时间内完成，但是这没有包含后缀数组预处理所需的时间（一般为NLOGN)。（ps:以后如果不确定还是跟着直觉走吧）
8.判断一包含n个整数a[]中是否存在i、j、k满足a[i] + a[j] = a[k]的最小的时间复杂度为（）
A. O(n3) B.O(n2lgn) C.O(n2) D.O(nlgn)
思路：O(N2)的算法能想一大堆，虽然最终我选的C，比如说用hash的话，三维遍历可以轻松编程二维遍历，但是总感觉是不是应该有nlgn的算法。
9.三次射击至少能中一次的概率是0.95，请问一次射击能中的概率是多少？
A.0.63B.0.5
C.**
D.0.85
思路：简单的概率计算，1-（1-P）3 =0.95
10.下列序排算法中最坏复杂度不是n(n-1)/2的是_
A.快速排序 B.冒泡排序 C.直接插入排序 D.堆排序
思路：由堆排序的过程可知堆排序最好最坏的时间复杂度都是O(NlgN)
二、不定项选择题
1.阻塞、就绪、运行的三态转换
2.一个栈的入栈序列是：1,2,3,4,5,6，问下面的答案哪个是可能的出栈顺序？
思路：入栈出栈，没什么好说的。但是从这个题目就可以知道阿里这次出题的水平一般，好多题目给的条件都不严谨，比如说这题，栈大小限定不限定也不说。
3.不用中间变量交换两个整型数字的值
4.无聊的人数星星
A和B很无聊，然后数天上的星星（所以还真是无聊），然后每个人能力有限，每次只能数K颗星星，其中20<=K<=30,A先数，B接着数，谁先数完最后一批谁赢，问星星有多少颗的时候能保证A先数总是能赢。答案有五个选项。
A.2013 B.2886 C.4026 D……E…..
思路：排除法就好了，如果天上有x颗星星，必定有2n*k<x<=(2n+1)*k，先用k=20排除几个答案，然后用21排除就只剩一个答案了。貌似我当时排除完之后只剩下E了。
三、填空问答题
1.整型数组的就地逆置：给你一个整型数组A[N]，完成一个小程序代码（20行之内），使得A[N]逆向，即原数组为1，2，3，4，逆向之后为4，3，2，1
void reverse(int * a,int n) {assert(a!=NULL);//当时写了这么一句，貌似有点画蛇添足了，因为要求不要用到任何库for(int i=0;i<n/2;++i){//swapa[i]=a[i]+a[n-1-i];a[n-1-i]=a[i]-a[n-1-i];a[i]=a[i]-a[n-1-i];}}
2.多道程序设计与作业调度–先来先服务与短作业优先算法的比较，给定了三个作业，已知三个作业的进入时间，处理时间，作业一旦进入不会被打断，求周转时间。
思路：没啥特别的
3.有个苦逼的上班族，他每天忘记定闹钟的概率为0.2，上班堵车的概率为0.5，如果他既没定闹钟上班又堵车那他迟到的概率为1.0，如果他定了闹钟但是上班堵车那他迟到的概率为0.9，如果他没定闹钟但是上班不堵车他迟到的概率为0.8，如果他既定了闹钟上班又不堵车那他迟到的概率为0.0，那么求出他在60天里上班迟到的期望。
思路：按照概率一步步算就好了，先求出每天迟到的概率。
4.士兵战报交换：有n个士兵，每个士兵知道一些不同的战报，n>4,每个战士都知道一些不同的战报，战士之间可以通过比如说打电话互相交流，交流完成之后二者信息汇总，且两人都知道所有信息，设计一种交流次数最少的交流算法，使得最后每个士兵都知道所有信息
思路：我当时给出的答案是将n个士兵两个一组，组内交换信息，然后每组任意选一个出来得到（n+1）/2个士兵，其中每个士兵知道的信息是交换前的2倍，然后将这些士兵再两两分组，以此类推，这样的话，最终会有一个人知道所有的信息，然后依次分发给其余n-1个人即可，需要通话的次数是
+n-1,但是我不确定这样是不是最快，这篇文章给出了解答，稍微看了一下，思路跟我差不多，只是汇总人的个数作为变量，据说有证明，对这一题不感兴趣，最终答案是2n-4.
5.明星和群众问题：有N个人，其中一个明星和n-1个群众，群众都认识明星，明星不认识任何群众，群众和群众之间的认识关系不知道，现在如果你是机器人R2T2，你每次问一个人是否认识另外一个人的代价为O(1)，试设计一种算法找出明星，并给出时间复杂度（没有复杂度不得分）。
思路：从第一个人开始问，问他是不是认识旁边的人，如果他认识，那么他肯定不是明星，直接把这个人去掉，如果他不认识，那么被问的人肯定不是明星，被问的人从集合中去掉，这样问一次就可以删掉一个人，最后剩下的就是明星了，时间复杂度O(N)
四、综合问题
皇冠用户仓库开销：某淘宝金冠用户在多个城市有仓库，每个仓库的储货量不同，现在要通过货物运输，将每次仓库的储货量变成一致的，n个仓库之间的运输线路围城一个圈，运输只能在相邻的仓库之间进行，设计最小的运送成本（运货量*路程）
思路：这个在各种online-judge平台上都有答案，纯粹的数学问题，
如图，这是一个仓库分布的模拟，假设从第i个仓库向第i+1个仓库转移的物品为Pi个单位，其中Pi为负表示思是从i+1个仓库转移到第i个仓库，第n个仓库转移到第一个仓库即为Pn，设最后每个仓库平均后的货物为ave个单位，则有要最小化|P1|+|P2|+…+|Pi|+…+|Pn|
ave[i]=ave=A[i]-Pi+Pi-1
ave[1]=A[1]-P1+Pn
然后设W[i]=ave[i]-A[i]=-Pi+Pi-1
于是S[i]=W[1]+W[2]+….W[i]=Pn-Pi
即Pi=Pn-S[i] ，所以问题归结到最小化|Pn-S[1]|+|Pn-S[2]|+…+|Pn-S[n]|
所以Pn是S中位数的时候最小
目前能记起来的就这么多了，后面再查吧