阿里巴巴2014年笔试题

阿里巴巴集团2014校园招聘笔试题（北京）第一部分单选题（前10题，每题2分；后10题，每题3分。选对得满分，选错倒扣1分，不选得0分）1、 一次内存访问，SSD硬盘访问和SATA硬盘随机访问的时间分别是（）A、几微秒，几毫秒，几十毫秒 B、几十纳秒，几十微秒，几十毫秒C、几十纳秒，几十微秒，几十毫秒D、几微秒，几十微秒，几十毫秒2、 8进制数256，转化成7进制数是（B）A、 356B、336C、338D、3463、 某网络的IP地址空间为/24,采用定长子网划分，子网掩码为48，则该网络的最大子网个数、每个子网内最大可分配地址个数各位（C）A、 8,32B、32,8C、32,6D、8,304、 以下关于链式存储结构说法错误的是（A）A、 查找节点时链式存储比顺序存储快B、 每个节点是由数据域和指针域组成C、 比顺序存储结构的存储密度小D、 逻辑上不相邻的节点物理上可能相邻5、 假定一个二维数组的定义语句为“inta⑶⑷={{3,4},{2,8,6}};”,则元素a[1][2]的值为（A）6、下面函数的功能是（C）intfun（char*s）{char*p=s;while（*p++）;returnp-s-1;}A、计算字符串的位（bit）数 B、复制一个字符串C、求字符串的长度 D、求字符串存放的位置7、 判断有向图是否存在回路，利用（A）方法最佳A、拓扑排序 B、求最短路径C、求关键路径 D、广度优先遍历8、 依次读入数据元素序列{a,b,c,d,e,f,g}进栈，元素进栈或出栈顺序是未知的，下列序列中，不可能成为栈空时弹出的元素构成序列的有（D）A、 {d,e,c,f,b,g,a}B、{c,d,b,e,f,a,g}C、{e,f,d,g,c,b,a}D、{f,e,g,d,a,c,b}9、 下列有关图的遍历说法中，不正确的是（C）A、 有向图和无向图都可以进行遍历操作B、 基本遍历算法两种：深度遍历和广度遍历C、 图的遍历必须用递归实现D、图的遍历算法可以执行在有回路的图中10、 在16位机器上跑下列foo函数的结果是（B）voidfoo（）{inti=65536;cout<<i<<”,”;i=65535;cout<<i;}A、-1,65535B、0,-1C、-1,-1 D、0,6553511、 有一段年代久远的C++代码，内部逻辑复杂，现在需要利用其实现一个新的需求，假定有以下可行的方案，应当优先选择（D）A、 修改老代码的接口，满足新的需求B、 将老代码抛弃，自己重新实现类似的逻辑C、 修改老代码的内部逻辑，满足新的需求D、 在这段代码之外写一段代码，调用该代码的一些模块，完成新功能需求12、 在5个页框上使用LRU页面替换算法，当页框初始为空时，引用序列为0、1、7、8、6、2、3、7、2、9、8、1、0、2,系统将发生（C）次缺页

分析：缺页为：0、1、7、8、6、2、3、9、8、1、0，共11次13、阿里巴巴有相距1500km的机房A和B,现有100GB数据需要通过一条FTP连接在100s的时间内从A传输到B。已知FTP连接建立在TCP协议之上，而TCP协议通过ACK来确认每个数据包是否正确传送。网络信号传输速度2*108m/s,假设机房间带宽足够高，那么A节点的发送缓冲区可以设置为最小(A)A、18MBA、18MB、 12MC、6MD、24MABACKABACKTCP协议原理：TCP每发送一个报文段，就启动一个定时器，如果在定时器超时之后还没有收到ACK确认，就重传该报文。如图所示，数据包由A的缓冲区发往B，B在收到数据包以后，回发一个ACK确认包给A，之后A将该数据包从缓冲区释放。因此，该数据包会一直缓存在A的缓冲区，直到一个ACK确认为止。题目要求在100s内发送100GB数据，网络的传输速率至少是1G/s，某个数据包n在A中缓存的时间就是数据包n从A到B,再加上该数据包的ACK从B到A的时间:2*1500km/(2*108m/s)=1.5*10-2s,该段时间A中缓存的数据量至少是1G/s*1.5*10-2s约为15M14、有3个节点的二叉树可能有(A)种A、5B、A、5B、13C、12D、1515、设某文件经内排序后得到100个初始归并段(初始顺串)，若使用多路归并排序算法，且要求三趟归并完成排序，问归并路数最少为(D)A、8 B、7 C、6 D、5分析：m个元素k路归并的归并趟数s=logk(m),代入数据：logk(100)W316、 一个优化的程序可以生成一n个元素集合的所有子集，那么该程序的时间复杂度是(B)A、O(n!) B、O(2n) C、O(n2) D、O(nlogn)17、 快速排序在已经有序的情况下效率最差，复杂度为(B)A、O(nlogn) B、O(n2) C、O(n1.5) D、O(n2logn)18、 从一副牌(52张，不含打小怪)里抽出两张牌，其中一红一黑的概率是(D)A、25/51 B、1/3 C、1/2 D、26/51分析：52张牌从中抽两张，就是C522种情况，一红一黑是C26i*C26i种情况，概率P=C26】*C261/C522=26/5119、 有一堆石子共100枚，甲乙轮流从该堆中取石子，每次可取2、4或6枚，若取得最后的石子的玩家为赢，若甲先取，则(C)A、谁都无法取胜 B、乙必胜 C、甲必胜 D、不确定分析：先取的人只需要保证最后剩8枚就胜了。而要保证最后剩8枚，则必须要保证每一个回合内取的数是一个可控的固定数，显然这个数字是8，所以只需要保证第一次取完后，剩下的数字是8的倍数，就一定能胜。100除以8余数为4，故而，甲先取4枚，之后每一个回合所取数与上一个回合乙所取数之和为8，就能保证必胜。

20、现有一完全的P2P共享协议，每次两个节点通讯后都能获取对方已经获取的全部信息，现在使得系统中每个节点都知道所有节点的文件信息，共17个节点，假设只能通过多次两个对等节点之间通讯的方式，则最少需要（C）次通讯A、32BA、32B、31C、30D、29图23斗23图224241080'bloy.^iriEi.Gorn.sn/lyiriybu图23斗23图224241080'bloy.^iriEi.Gorn.sn/lyiriybu第二部分不定项选择（每题五分，每题有1-5个正确选项，完全正确计5分，漏选计2分不选计0分，多选、错选计-2分）21、2-3树是一种特殊的树，它满足两个条件：（1） 每个内部节点有两个或三个子节点；（2） 所有的叶节点到根的路径长度相同；如果一颗2-3树有9个叶节点，下列数量个非叶节点的2-3树可能存在的有（BE）A、8B、7C、6D、5E、4分析：根据条件(2)，叶节点只能在同一层，根据条件(1)，上一层的父节点只能是3个或4个，只能是如下图所示的两种结果22、 下列有关进程的说法中，错误的是(ABC)A、进程与程序是一亿对应的 B、进程与作业时一一对应的C、进程是静态的 D、进程是动态的过程23、 下列函数定义中，有语法错误的是(D)A、 voidfun(intx,int*y){x*=*y;}B、 int*fun(int*x,inty){returnx+=y;}C、 voidfun(int*x,inty){*x+=y;}D、voidfun(intx,int*y){*x*=*y;}24、 有朋自远方来，他乘火车，轮船，汽车，飞机来的概率分别是0.3,0.2,0.1,0.4坐各交通工具迟到的概率分别是1/4,1/3,1/12,0,下列语句中正确的是(CD)A、如果他准点，那么乘飞机的概率大于等于0.5B、坐陆路(火车，汽车)交通工具准点机会比坐水路(轮船)要低C、如果他迟到，乘火车的概率是0.5D、如果他准点，坐轮船或汽车的概率等于坐火车的概率第三部分填空与问答25、（4分）文件分配表FAT是管理磁盘空间的一种数据结构，用在以链接方式存储文件的系统中记录磁盘分配和追踪空白磁盘块，整个磁盘仅设一张FAT表，其结构如下所示，如果文件块号为2,查找FAT序号为2的内容得知物理块2的后继物理块是5,再查FAT序号为5的内容得知物理块5的后继物理块是7,接着继续查FAT序号为7的内容为“A”即该文件结束标志，01234561&957At|t文件首块号2假设磁盘物理块大小为1KB,并且FAT序号以4bits为单位向上扩充空间。请计算下列两块磁盘的FAT最少需要占用多大的存储空间？（1）一块540MB的硬盘（2）—块1.2GB的硬盘分析：（1）磁盘块大小为1KB,540MB的硬盘可以分成540MB/1KB=5.4*105个磁盘块，因此至少需要5.4*105<220个编号，需要20bit存储空间（2）同理，1.2G至少需要1.2*106<221个编号，为21bit,由于FAT序号以4bits为单位向上扩充，因此需要24bit存储空间26、（4分）已知如下代码，并在两个线程中同时执行f1和f2,待两个函数都返回后，a的所有可能值是哪些？inta=2,b=0,c=0;voidf1（） voidf2（）{{a=a=b;}a=c;}分析：考虑四行代码的执行顺序即可1）b=a*2,c=a+11,a=c,a=ba=42）b=a*2,c=a+11,a=b,a=ca=133）b=a*2,a=b,c=a+11,a=ca=154）c=a+11,a=c,b=a*2,a=ba=2627、（6分）设计一个最优算法来查找一n个元素数组中的最大值和最小值，已知一种需要比较2n次的方法，请给一个更优的算法。请特别注意优化时间复杂度的常数。给出该算法最坏情况下的比较次数和该算法的步骤描述。（不用写代码，不给出比较次数的不得分）分析：已知的比较2n次的方法，显然是将每个元素和最大值、最小值各比一次，要减少比较次数，可以有多种优化方法：方法一：一个元素先和最大值比较，如果比最大值大，就不用再和最小值比较（或者先和最小值比较，如果比最小值小，就不用再和最大值比较），一般情况下，这种优化后的比较次数一定会少于2n方法二：将数组元素按两个，两个分组，组内两元素有序存放，之后最小值跟组内较小的值比较，最大值只需跟组内较大的值比较，这样每组的比较次数是3，共n/2组，总的时间复杂度是3n/2次。详情请参考/thebestdavid/article/details/11975809的第3题28、（8分）已知三个升序整数数组a[l]、b[m]、c[n]，请在三个数组中各找一个元素，使得组成的三元组距离最小，三元组的距离定义是：假设a[i]、b[j]和c[k]是一个三元组，那么距离为distance=max（la[i]-b[j]l,la[i]-c[k]l,lb[j]-c[k]l）,请设计一求最小三元组距离的最优算法，并分析时间复杂度。（不用写代码，不分析时间复杂度不得分）分析：详情请参考/thebestdavid/article/details/11975809的第4题29（8分）在黑板上写下50个数