阿里巴巴2017秋招研发工程师笔试题
1、有个特殊的餐厅，对客人的要求是如果要离开餐厅一定要看下餐厅内有没有比你迟进来的人，一定要所有比你迟进来的人离开后你才能离开，有一天甲，乙，丙，丁四个客人先后进入了这家餐厅，那么他们离开的顺序不可能是：
正确答案: E
A、丙，乙，甲，丁
B、甲，乙，丙，丁
C、乙，甲，丙，丁
D、乙，丙，甲，丁
E、丁，丙，甲，乙
F、丁，丙，乙，甲
这个题目考查的就是元素入栈出栈的顺序问题。
只要小心一个思维误区：并不是要等到甲、乙、丙、丁全部按序进入餐厅后才开始有人离开。
否则离开顺序只能是丁、丙、乙、甲，其他都是错误顺序。
入栈的顺序是甲，乙，丙，丁，但是先进的人可能会先出来。如果是后进的人先出，那么他前面的人必然还在 栈中。E选项中，丁先出了，甲乙丙肯定还在栈中，且他们在栈中的顺序从栈顶到栈底必然是丙、乙、甲，那么他们的出栈顺序只能是丙、乙、甲。
2、在关系型是数据库中，有两个不同的事务同时操作数据库中同一表的同一行，不会引起冲突的是：
正确答案: F
A、其中一个DELETE操作，一个是SELECT操作
B、其中两个都是UPDATE
C、其中一个是SELECT，一个是UPDATE
D、其中一个SELECT
E、其中一个是DELETE，另一个是UPDATE
F、两个都是DELETE
答案是最后一个 ： 两个都是DELETE
当要删除的记录在数据库中不存在的时候，是不会报错的。
3、众所周知我们所处的宇宙的质能公式是E=mc 2 ，其中c是真空中的光速。和我们的宇宙平行的另一个宇宙meta，研究显示他们使用的质能公式是E=(2+ √3) m ，当一个物体的质量很大的时候，对应的能量E非常大，数据也非常的长。但meta宇宙里面的智慧生物非常的懒，他们只愿意把E取整，然后记录对应的能量E的最后一位整数，比如m=0时，他们会记录1，m=1时，他们会记录3，m=2时，他们会记录3.现在请问当m=80时，他们会记录多少？
正确答案: C
1
2
3
4
5
6
解析： m=0，记录1；m=1，记录3；m=2，记录3；
m=3，记录1；m=4，记录3；m=5，记录3；
… …
… …
m=78，记录1，m=79，记录3；m=80，记录3
规律就是从零开始，三个数为一个周期，一个周期当中记录是1，3，3。从0到80一共是81个数，正好能整除3，也就是说m=80落在一个周期里的第三个数，记录3。
4、页高速缓存是Linux kerne使用的主要的磁盘缓存技术。它允许系统把存放在磁盘上的一些数据保留在内存中，以便减少对磁盘的访问。进程对页高速缓存区中的数据修改之后，数据页被标记为“脏数据”在下列哪些条件下，脏数据不会被写入磁盘？
正确答案: B E
A、页高速缓存空间不足
B、突然断电
C、变脏以来，太久没有过更新
D、通过系统调用（sync（），fsync（），fdataasync（））来强行对将对快设备的更新同步到磁盘
E、内存足够大
F、磁盘足够大
ACD是脏数据写入磁盘的条件，而BE时，数据是不会写入磁盘的
5、设一组初始关键字记录关键字为（ 12,15,1,18,2,35,30,11 ），则以 12 为基准记录的一趟快速排序结束后的结果为
正确答案: D
A、11，1，2，12，35，18，30，15
B、11，2，1，12，15，18，35，30
C、1，2，11，12，15，18，35，30
D、11，2，1，12，18，35，30，15
E、1，2，11，12，15，18，30，35
F、以上都不是
首先我们先来回忆一下快速排序：
找到一个数作为基准数据，然后将所有比它小的数都放到它左边，所有比它大的数都放到它右边，这个过程称为一趟快速排序。值得注意的是，快速排序不是一种稳定的排序算法，也就是说，多个相同的值的相对位置也许会在算法结束时产生变动。
一趟快速排序的算法是：
1）设置两个变量i、j，排序开始的时候：i=0，j=N-1；
2）将关键数据，赋值给key，即key=A[0]；
3）从j开始向前搜索，即由后开始向前搜索(j–)，找到第一个小于key的值A[j]，将A[j]和A[i]的值交换；
4）从i开始向后搜索，即由前开始向后搜索(i++)，找到第一个大于key的A[i]，将A[i]和A[j]的值交换；
5）重复第3、4步，直到ij； (3,4步中，没找到符合条件的值，即3中A[j]不小于key,4中A[i]不大于key的时候改变j、i的值，使得j=j-1，i=i+1，直至找到为止。找到符合条件的值，进行交换的时候i， j指针位置不变。另外，ij这一过程一定正好是i+或j-完成的时候，此时令循环结束）。
题解：
以12为标准值，从右开始找出比12小的值，首先是11，把11放在12的那个位置，把12放在11的那个位置，再从左边找比12大的值15，把15放在12的新位置（原来11的位置）之后变成11，12，1，15，2，35，30，15.在新的一轮开始，从右边开始找比12小的数2，把2放在12的位置，12放在2的位置，再从左边找比12大的数18，把18放在12的新位置（原来2的位置）变成11，2，1，12，18，35，30，15
6、多项式 P(X)=a+bx+cx2+dx3 ，对于任意 x ，计算 P(X) 中最少需要用到乘法操作的次数是多少？
正确答案: A
A、3
B、4
C、5
D、6
E、1
F、2
原式可以分解成（b+(dx+c)*x)*x+a，所以只需要三次乘法操作
10、输入图片大小为200×200，依次经过一层卷积（kernel size 5×5，padding 1，stride 2），pooling（kernel size 3×3，padding 0，stride 1），又一层卷积（kernel size 3×3，padding 1，stride 1）之后，输出特征图大小为：
正确答案: C
A、95
B、96
C、97
D、98
E、99
F、100
公式： output_size = ( input_size + 2*padding - kernel_size ) / stride+1
题解：
计算尺寸不被整除只在GoogLeNet中遇到过。卷积向下取整，池化向上取整。
（200-5+2*1）/2+1 为99.5，取99
（99-3）/1+1 为97
（97-3+2*1）/1+1 为97
11、一个二叉树有100个子节点数为2的节点，100个子节点数为1的节点，那么个子节点数为0的节点（叶节点）的个数为：
正确答案: A
A、101
B、100
C、200
D、300
E、99
F、1
解析1：
度数（变数）=所有节点数-1，本题中，度数=2*100+100=300，节点数：100+100+叶节点数，所以，叶节点数=101
解析2：
首先，假设该二叉树有n个节点，则有n - 1条边，这是因为除了根节点，其余的每个节点都有且只有一个父节点，那么这n个节点恰好为树贡献了n-1条边。这是从下往上的思考，而从上往下(从树根到叶节点)的思考，容易得到每个节点的度数和 n0 + 1n1 + 2*n2 即为边的个数。
因此，我们有等式 n-1 = n1 + 2*n2，把n用n0+n1+n2替换，
得到n0 + n1 + n2 - 1 = n1 + 2*n2，于是有
n0 = n2 + 1。
n0=n2+1=100+1=101
12、某种类型的双核 CPU 的性能提升了 1/3 ，假定该提升是通过对每条指令缩短执行时间实现的，那么它每条指令执行时间缩短了 () 。
正确答案: A
A、1/4
B、1/8
C、1/3
D、1/6
E、1/5
F、1/2
题解：
设：原来：1秒执行1条指令
现在：1秒执行4/3条指令
则现在执行一条指令花费1秒/(4/3)=3/4秒
所以每条指令执行时间缩短了1秒-3/4秒=1/4秒
13、一个map-reduce任务由m个mapper和r个reducer构成，计算的效率可以认为正比于mr的乘积（数据管道的个数），在限定任务的mr乘积约等于10000的情况下，假定每个mapper和每个reducer的成本分别为1和7，那么最佳的资源分配最接近于以下哪个方案？
正确答案: C
A、Mapper100个，reducer100个
B、Mapper200个，reducer50个
C、Mapper264个，reducer38个
D、Mapper316个，reducer32个
E、Mapper500个，reducer20个
F、Mapper1000个，reducer10个
题解：
假定每个mapper和每个reducer的成本分别为1和7， 其实就是求最后和最小的方案
A : 100 + 100*7 = 800
B: 200 + 50*7 = 550
C: 264 + 38*7 = 530
D: 316 + 32*7 = 540
E: 500 + 20 * 7 = 640
F 1000 + 10*7 = 1070
所以C答案组合方式是最小成本组合。
C: Mapper264个，reducer38个
15、一个机器人玩抛硬币的游戏，一直不停的抛一枚不均匀的硬币，硬币有A,B两面，A面的概率为3/4，B面的概率为1/4。问第一次出现连续的两个A年的时候，机器人抛硬币的次数的期望是多少？
正确答案: F
A、9/4
B、11/4
C、15/4
D、4
E、5
F、28/9
题解：
假设T为扔的次数（期望）。 那么如果扔到B，则重新开始扔，即再扔T次。
第一次扔到B，则重新扔，即1/4*(1+T)；这时1+T是结束游戏所扔次数；
第一次扔到A，第二次扔到B，重新扔，即3/41/4(2+T)；2+T是结束游戏所仍次数；
第一次扔到A，第二次扔到A，结束游戏。3/43/42；2为结束游戏所仍次数；
所以T=1/4*(1+T)+3/4 1/4(2+T)+3/4 *3/4 *2；算得T为28/9
16、小a和小b一起玩一个游戏，两个人一起抛掷一枚硬币，正面为H，反面为T。两个人把抛到的结果写成一个序列。如果出现HHT则小a获胜，游戏结束。如果HTT出现则小b获胜。小a想问一下他获胜的概率是多少？
正确答案: C
A、3/4
B、1/2
C、2/3
D、5/9
E、1/3
F、1/4
题解：
在一层递归里面，b确定赢的概率是1/4，但是剩下的1/4中，b可能输，也可能赢，赢的概率也是1/4
所以b=1/4+(1/4)2+(1/4)3+……=1/3
相应的a赢的概率就是2/3
18、以下哪个行为，不会明显加剧客户端运行过程中的卡顿：
正确答案: C
A、在主线程集中处理耗时的操作
B、在子线程集中处理耗时的操作
C、在其它进程集中处理耗时的操作
D、提高后台线程的优先级
E、降低主线程的优先级
F、页面存在多个重叠显示的控件
在其他进程里面处理耗时操作，相当于在另外的虚拟机里面执行操作，因此和当前的虚拟机也就是客户端没有明显的关系，如过不理解可以类比一下AIDL，客户端的一次请求就相当于一次RPC，请求到了服务器之后会在Binder线程池执行操作，而如果后台软件过多，只是因为CPU轮换和内存不足。题目说的是不会明显加剧卡顿，这是会造成卡顿的。
行为，不会明显加剧客户端运行过程中的卡顿：
正确答案: C
A、在主线程集中处理耗时的操作
B、在子线程集中处理耗时的操作
C、在其它进程集中处理耗时的操作
D、提高后台线程的优先级
E、降低主线程的优先级
F、页面存在多个重叠显示的控件
在其他进程里面处理耗时操作，相当于在另外的虚拟机里面执行操作，因此和当前的虚拟机也就是客户端没有明显的关系，如过不理解可以类比一下AIDL，客户端的一次请求就相当于一次RPC，请求到了服务器之后会在Binder线程池执行操作，而如果后台软件过多，只是因为CPU轮换和内存不足。题目说的是不会明显加剧卡顿，这是会造成卡顿的。