阿里巴巴2015笔试题-研发工程师
发布于 2014-10-22 03:15:20 | 214 次阅读 | 评论: 0 | 来源: 网友投递
阿里巴巴
阿里巴巴（中国电子商务公司） 即 阿里巴巴集团 。
阿里巴巴集团经营多元化的互联网业务，致力为全球所有人创造便捷的交易渠道。自成立以来，阿里巴巴集团建立了领先的消费者电子商务、网上支付、B2B网上交易市场及云计算业务，近几年更积极开拓无线应用、手机操作系统和互联网电视等领域。
1、int main(){ fork()||fork(); }共创建几个进程？
答：3个。
【知识点】
• 一个现有进程可以调用fork函数创建一个新进程。由fork创建的新进程被称为子进程（child process）。fork函数被调用一次但返回两次。两次返回的唯一区别是子进程中返回0值而父进程中返回子进程ID。
• 子进程是父进程的副本，它将获得父进程数据空间、堆、栈等资源的副本。注意，子进程持有的是上述存储空间的“副本”，这意味着父子进程间不共享这些存储空间。
• UNIX将复制父进程的地址空间内容给子进程，因此，子进程有了独立的地址空间。在不同的UNIX (Like)系统下，我们无法确定fork之后是子进程先运行还是父进程先运行，这依赖于系统的实现。所以在移植代码的时候我们不应该对此作出任何的假设。
如图所示：相同颜色的为同一进程，共有三种进程。
2.下列正则表达式不可以匹配 “www.alibaba-inc.com”的是______。
• ^\w+\.\w+\-\w+\.\w+$
• [w]{0,3}.[a-z\-]*.[a-z]+
• [c-w.]{3,10}[.][c-w.][.][a]
• [w][w][w][alibaba-inc]+[com]+
• ^\w.*com$
• [w]{3}.[a-z\-]{11}.[a-z]{3}
【知识点】正则表达式请参考：http://msdn.microsoft.com/zh-cn/library/ae5bf541(v=vs.90).aspx
3.下列描述中唯一错误的是______。
A. 本题有五个选项是正确的
B. B正确
C. D正确
D. DEF 都正确
E. ABC 中有一个错误
F. 如果 ABCDE 都正确，那么 F 也正确
【知识点】推理判断
根据题意，选项中只有唯一一个错误，所以A选项正确。再看C选项，如果C选项错误，那 么D错误和唯一错误矛盾，所以C正确。进而D正确，那么DEF都正确，只有B错误。我们再看，如果B正确，根据前面的分析我们肯定CDE都是正确的，在E 选项中，A正确，B正确，进而推导出C错误，这和前面我们推导C正确矛盾，因此B错误。
4、个数约为50K的 数列需要进行从小到大排序，数列特征是基本逆序（多数数字从大到小，个别乱序），以下哪种排序算法在事先不了解数列特征 的情况下性能大概率最优（不考虑空间限制）______。
• 冒泡排序
• 改进 冒泡排序
• 选择排序
• 快速排序
• 堆排序
• 插入排序
【知识点】各大排序的适用场合以及特点
个数约为50K，基本可以秒杀一般的冒泡，改进冒泡，选择，插入等基本的排序。加上数列的特征是基本逆序，而快速排序的worst case就是基本逆序或者基本有序的情况。综上所述，堆排序应该是大概率最优的。
5、下列方法中，______不可以用来程序调优 ?
• 改善数据访问方式以提升缓存命中率
• 使用多线程的方式提高I/O密集型操作的效率
• 利用数据库连接池替代直接的数据库访问
• 使用迭代替代递归
• 合并多个远程调用批量发送
• 共享冗余数据提高访问效率
【知识点】程序调优常见的途径。
• I/O密集型问题一般是硬件层面的问题，比如硬盘，它的I/O就摆在那里，无论你在怎么多线程，瓶颈就在硬盘那，所以B的说法是不可行的。
• 对于“I/O密集型”的应用程序可以采用I/O效率较高的SCSI硬盘，或者采用集群的方式。
6、设 m 和 n 都是 int 类型，那么以下 for 循环语句，__
for(m=0,n=-1;n=0;m++,n++)
n++;
A.循环体一次也不执行
B.循环体执行一次
C.是无限循环
D.有限次循环
E.循环结束判断条件不合法
F.运行出错
【知识点】循环，=和==区别
n=0，条件永远为假，所以循环体一次也不会执行
【扩展】
若改为for(m=0,n=-1;n>0;m++,n++)n++;循环体应该会执行有限次，存在溢出的问题。
7、计算三个稠密矩阵A、B、C的乘积ABC，假定三个矩阵的尺寸分别为m*n, n*p, p*q，且m<n<p<q，以下计算顺序效率最高的是：______？
• (AB)C
• A(BC)
• (AC)B
• (BC)A
• (CA)B
• 以上效率相同
【知识点】矩阵及简单的算法复杂度
• 根据简单的矩阵知识，可以排除后面四项，因为A*B，A的列数必须和B的行数相等。
• 再看选项1和选项2，如下图所示，一个m*n的矩阵A乘以n*q的矩阵B。我们会用矩阵A的第一行，乘以矩阵B的第一列并相加。这一运算需要耗费n次乘法以及n-1次加法，矩阵B有q列，矩阵A有m行，所以A*B的复杂度为m*(2n-1)*q。
• 根据上面的分析，我们可以知道选项1的复杂度为m*(2n-1)*p + m*(2p-1)*q，而选项2的复杂度为m*(2n-1)*q+ n*(2p-1)*q，很显然选项1的效率高于选项2。
8、若干个等待访问磁盘者依次要访问的磁道为19,43,40,4,79,11,76,当前磁头位于40号柱面，若用最短寻道时间优先磁盘调度算法，则访问序列为？
A. 19,43,40,4,79,11,76
B. 40,43,19,11,4,76,79
C. 40,43,76,79,19,11,4
D. 40,43,76,79,4,11,19
E. 40,43,76,79,11,4,19
F. 40,19,11,4,79,76,43
【知识点】磁盘寻道算法
9、程序出错在什么阶段__？
Int main(void)
{
http://www.taobao.com
cout<<”welcome to taobao”<<endl
}
A. 预处理阶段出错
B. 编译阶段出错
C. 汇编阶段出错
D. 链接阶段出错
E. 运行阶段出错
F. 程序运行正常
【知识点】编译程序的基本知识
• Gcc编译器对程序的编译可分为4个阶段：预编译、编译和优化、汇编、链接，之后就是运行了。
• 预编译：将程序引用的头文件包含进源代码中，并对一些宏进行替换；
• 编译：将用户据可识别的语言翻译成一组处理器可识别的操作码，生成目标文件，通常翻译成汇编语言，而汇编一眼和机器操作码之间是一对一的关系；
• 所有的目标文件必须用某种方式组合起来才能运行，这就是链接的作用。目标文件中通常仅解析了文件内部的变量和函数，对于引用的函数和变量还没有解析，这需 要将其他已经编写好的目标文件引用进来，将没有解析的变量和函数进行解析，通常引用的目标是库。链接完成后会生成可执行文件。
10、以下操作中，数组比线性表速度更快的是____
A. 原地逆序
B. 头部插入
C. 返回中间节点
D. 返回头部节点
E. 选择随机节点
【知识点】线性表和数组
线性表的定义请参见百度百科：http://baike.baidu.com/view/178622.htm
11、在一个请求页式存储管理中，一个程序的页面走向为 3、4、2、 1、4、5、3、4、5、1、2，并采用 LRU 算法。设分配给改程序的存储 快熟 S 分别为 3 和 4，在该访问中发生的缺页次数 F 是
A. S=3,F=6;S=4,F=5
B. S=3,F=7;S=4,F=6
C. S=3,F=8;S=4,F=5
D. S=3,F=8;S=4,F=7
E. S=3,F=10;S=4,F=8
F. S=3,F=11;S=4,F=9
【知识点】缺页次数的计算LRU和FIFO
12、每台物理计算机可以虚拟出 20 台虚拟机，假设一台虚拟机发生故障当且仅当它所宿主的物理机发生故障。通过 5 台物理机虚拟出100 台虚拟机，那么关于这 100 台虚拟机的故障的说法正确的是：____?
A. 单台虚拟机的故障率高于单台物理机的故障率
B. 这 100 台虚拟机发生故障是彼此独立的
C. 这100台虚拟机单位时间内出现故障的个数高于100台物理机单位时 间内出现故障的个数
D. 无法判断这 100 台虚拟机和 100 台物理机哪个更可靠
E. 如果随机选出 5 台虚拟机组成集群， 那么这个集群的可靠性和 5 台物 理机的可靠性相同
F. 可能有一段时间只有 1 台虚拟机发生故障
【知识点】理解题意吧
13村长带着 4 对父子参加爸爸去哪儿第三季第二站某村庄的拍摄。 村里为了保护小孩不被拐走有个前年的规矩， 那就是吃饭的时候小孩 左右只能是其他小孩或者自己的父母。那么 4 对父子在圆桌上共有 ___种坐法。 （旋转一下， 每个人面对的方向变更后算是一种新的坐法）
A. 144
B. 240
C. 288
D. 480
E. 576
F. 960
【知识点】排列组合
根据题意，可以知道位置排列只有以下两种可能，如下图所示：
对于第一种方式：孩子和孩子是面对面的，父亲和父亲是面对面的。所以8个位置可以等效为4个位置，孩子的位置定了，父亲的位置也就定了。而孩子的排列数为4*3*2，旋转只有4中可能（因为等效下来只有4个位置）。所以总可能输为4*4*3*2 = 96
对于第二种方式：孩子的排列有4*3*2*1，孩子的位置定了，其中两位父亲的位置就定了，剩下两位父亲就可以随意排了，此外可以旋转8次，总可能输为8 * 4 * 3 * 2 * 2 = 384
综上所述，总有384 + 96 = 450中可能。
14、如果一个博物馆参观者到达的速率是每分钟 20 人，平均每个人在馆内停留 20 分钟，那么该博物馆至少需要容纳多少人？
A. 100
B. 200
C. 300
D. 400
E. 500
F. 600
【知识点】20 * 20 = 400
16、对立的两 方争夺一个价值为1的物品，双方可以采取的策略可以分为鸽子策略和鹰策略，如果双方都是鸽子策略，那么双方各有1/2的几率获得该物品；如果双方均为鹰策 略，那么双方各有1/2的概率取胜，胜方获得价值为1的物品，付出价值为1的代价，负方付出价值为1的代价；如果一方为鸽子策略，一方为鹰策略，那么鹰策 略获得价值为1的物品，在争夺的结果出来之前，没人知道对方是鸽子策略还是鹰策略，当选择鸽子策略的人的比例是某一个值时，选择鸽子策略和选择鹰策略的预 期收益是相同的，那么该值是：
A. 0.2
B. 0.4
C. 0.5
D. 0.7
E. 0.8
F. 以上都不对
【知识点】
不会，求指点。
17、已知一个二叉树的前序遍历结果是（ACDEFHGB） ，中序遍历结果是（DECAHFBG）,请问后续遍历结果是_____
A. HGFEDCBA
B. EDCHBGFA
C. BGFHEDCA
D. EDCBGHFA
E. BEGHDFCA
F. BGHFEDCA
【知识点】前序遍历、中序遍历、后序遍历
18、在一个单链表中，q 的前一个节点为 p，删除 q 所指向节点，则执行
A. Delete q
B. q->next=p->nerx;delete p;
C. p-next=q->next;delete p;
D. p->next=q->next;delete q;
E. delete p;
F. q->next=p->next;delete q
【知识点】单链表
简单，无需多言
19、下列 C 代码中，不属于未定义行为的有___
A. Int i=0;i=(i++);
B. Char *p=”hello”;p[1]=’E’;
C. Char *p=”hello”;char ch=*p++;
D. Int i=0;printf(“%d%d\n”,i++,i--);
E. 都是未定义行为
F. 都不是未定义行为
【知识点】啥叫未定义行为啊？
我只觉得反正编译都不会出错，但是B肯定会运行出错。因为p指向一个const char，p指向的东西不能被改变。而相对而言，选项C中没有改变P所指向的东西，只是修改了p指针。说回来，未定义行为，好吧，好像都不是未定义行为。
20、int func(unsigned int i)
{
Unsigned int temp=i
Temp=(temp & 0x55555555)+((temp & 0xaaaaaaaa)>>1);
Temp=(temp & 0x33333333)+((temp & 0xccccccccc)>>2);
Temp=(temp & 0x0f0f0f0f)+((temp & 0xf0f0f0f0>>4);
Temp=(temp & 0xff00ff)+((temp & 0xff00fff00)>>8);
Temp=(temp & 0xffff)+((temp & 0xffff0000)>>16);
Return temp;
}
请问 func(0x11530828)的返回值是：(9)
【知识点】位运算
乍一眼看去，肯定不可能死算，这道题肯定有诀窍。总之就是求二进制比特中1的个数。具体怎么回事，自己慢慢摸索吧。
21、把校园中同一区域的两张不同比例尺的地图叠放在一起，并且使 其中较小尺寸的地图完全在较大尺寸的地图的覆盖之下。 每张地图上 都有经纬度坐标，显然，这两个坐标系并不相同。我们把恰好重叠在 一起的两个相同的坐标称之为重合点。 下面关于重合点的说法中正确 的是？
A. 可能不存在重合点
B. 必然有且只有一个重合点
C. 可能有无穷多个重合点
D. 重合点构成了一条直线
E. 重合点可能在小地图之外
F. 重合点是一小片连续的区域
【知识点】极限思想
如下图所示：假设蓝色的为大地图，黄色的为小地图，他们是成比例放大的。大地图中的黄色区域，必然也存在在小地图当中，我们假设为黄色区域。那么大地图的 黄色区域，必然也存在于小地图中，我们假设为灰色区域。按照此思想，两地图重合的区域越来越小，最后会趋近于一个点。所以选B。
22、毕业典礼后，某宿舍三位同学把自己的毕业帽扔了，随后每个人随机地拾起帽子，三个人中没有人选到自己原来带的帽子的概率是
A. 1/2
B. 1/3
C. 1/4
D. 1/6
E. 1/8
F. 1/9
【知识点】简单的概率论
不考虑任何情况，捡到帽子的情况有3*2*1=6种
每个人都不能捡到自己的帽子，情况有两种，A-c, B-a, C-b或者A-b, B-c, C-b，其中A,B,C代表三位同学，a,b,c分别代表A,B,C的帽子。
23、一个合法的表达式由()包围，()可以嵌套和连接，如(())()也是合法 表达式；现在有 6 对()，它们可以组成的合法表达式的个数为____
A. 15
B. 30
C. 64
D. 132
E. 256
F. 360
【知识点】卡特兰数
感谢这世界上有那么多大神存在。
24、某路由器接受的 IP 豹纹的目的地址不是路由器的接口 IP 地址， 并且未匹配的路由项，则采取的策略是
A. 丢掉该分组
B. 将该分组分片
C. 转发该分组
D. 将分组转发或分片
E. 将分组保留存储
F. 以上都有可能
【知识点】应该和网络有关，恶心没学过。当时不知道出了丢掉还能干什么。
25、有字符序列 ｛Q,H,C,Y,P,A,M,S,R,D,F,X｝ ,新序列{F,H,C,D,P.A.M,Q,R,S,Y,X}，是下列____排序算法一趟扫描的结果。
A. 二路归并排序
B. 快速排序
C. 步长为 4 的希尔排序
D. 步长为 2 的希尔排序
E. 冒泡排序
F. 堆排序
【知识点】排序
很显然是拿Q作为pivot的一趟扫描的结果。我们看看其他选项，比如C，如果是步长为4的希尔排序，那么Q将和P相比，P要排在Q前面，和新序列不符。其它依次类推，考试的时候，选B就可以啦。肯定是对的。
26、MySQL 主从结构的主数据库中不可能出现以下哪种日志？
A. 错误日志
B. 事务日志
C. 中继日志
D. Redo log
【知识点】数据库日志，看完此文，便可秒杀此题。