2021年阿里巴巴程序员面试题.docx

《2021年阿里巴巴程序员面试题.docx》由会员分享，可在线阅读，更多相关《2021年阿里巴巴程序员面试题.docx（28页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、2021年阿里巴巴程序员面试题解析：双绞线也称为双扭线，是最古老但又最常用的传输媒体。把两根相互绝缘的铜导线并排放在一起，然后用规则的方法绞合起来这样做是为了减少相邻的导线的电磁干扰而构成双绞线。双绞线分为1类到5类，局域网中常用的为3类，4类和5类双绞线。3类线用于语音传输及最高传输速率为10Mbps的数据传输；4类线用于语音传输和最高传输速率为16Mbps的数据传输；5类线用于语音传输和最高传输速率为100Mbps的数据传输同轴电缆由内导体铜质芯线，绝缘层，网状编制的外导体屏蔽层及保护塑料外层组成,内导体和外导体构成一组线对。由于外导体屏蔽层的作用，同轴电缆具有很好的抗干扰性。同轴电缆能够

2、将10Mb/S的基带数字信号传送1千米到1.2千米，因而被广泛用于局域网中光纤通信就是利用光导纤维传递光脉冲来进行通信，而光导纤维是光纤通信的媒体。光纤在任何时间都只能单向传输，因而，要实行双向通信，它必须成对出现，一个用于输入，一个用于输出，光纤两端接到光学接口上。光纤的传输系统比同轴电缆大的多，一般小同轴电缆的最大传输带宽为20MHz左右，中同轴电缆的最大传输带宽为60MHz左右。单根光导纤维的数据传输速率能达几Gbps，在不使用中继器的情况下，传输距离能达几十公里。答案：C第3题：进程阻塞的原因不包括_。A时间片切换B等待I/OC进程sleepD等待解锁答案：A解析：进程有3个状态：就绪

3、态。执行态、阻塞态。三种状态的转换包含有：就绪-执行，执行-就绪，执行-阻塞，阻塞-就绪等待I/O、进程sleep、等待解锁等原因都会导致进程暂停。关于时间片切换，当进程已经获得了除cpu外所有的资源，这时的状态就是就绪态，当分配到了时间片就成了执行态，当时间片用完之前一直未进入阻塞态的话，此后便继续进入就绪态。所以进程的就绪与阻塞是完全不同的。答案：A第4题：设只含根节点的二叉树高度为1，现有一颗高度为h(h1)的二叉树上只要出度为0和出度为2的结点，则此二叉树中所包含的结点数至少为_个。A2h-1B2h-1C2hD2h+1答案：B解析：保证树的高度就只要最左边的左子树有节点能保证最少，画出

4、来后发现答案是B答案：B第5题：给定下列程序，那么执行printf(%dn,foo(20,13);的输出结果是_。intfoo(intx,inty)if(x=0|y=0)return1;return3*foo(x-6,y/2);A3B9C27D81答案：D3*6204*6,递归4层。log13log16=4;所以结果为34=81.第6题：对于下面讲法，错误的是_。ADijkstra算法用于求解图中两点间最短途径，其时间复杂度O(n2)BFloyd-Warshall算法用于求解图中所有点对之间最短途径，其时间复杂度为O(n3)C找出n个数字的中位数至少需要O(n*logn)的时间D基于比拟的排序

5、问题的时间复杂度下界是O(n*logn)答案：C解析：AB正确，考察基本算法。D正确，基于比拟的话，怎么样都至少需要O(n*logn)的时间。找一个数能否是中位数，能够利用快排的经过而不是快排，就和O(N)第K数一样。答案：C第7题：一个包里有5个黑球，10个红球和17个白球。每次能够从中取两个球出来，放置在外面。那么至少取_次以后，一定出现过取出一对颜色一样的球。A16B9C4D1答案：A题目要求是一定出现，是必然情况，此题能够以为是鸽巢问题。考虑最坏情况黑球用B表示红球用R表示白球用W表示前面15次取球情况B,WB,WB,WB,WB,WR,WR,WR,WR,WR,WR,WR,WR,WR,W

6、R,W最后只剩下两个白球了W,W所以致少16次，才一定出现。第8题：某地电信局要对业务号码进行梳理，需要检测开通的市话号码能否存在某一个是另一个的前缀的情况，以简化电话交换机的逻辑。例如：某用户号码是“11001100，但与110报警电话产生前缀配对。已知市话号码最长8位，最短3位，并且所有3位的电话号码都以1开始。由于市话号码诸多，长度也未必一直，高效的算法能够用O(n)的时间复杂度完成检测n为开通市话号码个数，数量是千万级的。那么，该算法最坏情况下需要消耗大约_内存空间。A5GBB500MBC50MBD5MB答案：C解析：千万级，也就是10,000,000。市话最长8位，也就是一个字节的空

7、间，那么全部存下这些号码所消耗的空间为：1B*1000*1000*10=10MB不必纠结1000还是1024，只要代表了千万级的数量就行了。所以是两位数的级别。答案：C第9题：骑士只讲真话，骗子只讲谎言。下列场景中能确定一个骑士、一个骗子的有_。A甲讲：“我们中至少有一个人讲真话，乙什么也没讲。B甲讲：我们两个都是骗子，乙什么也没讲。C甲讲：“我是个骗子或者乙是个骑士，乙什么也没讲。D甲和乙都讲：“我是个骑士。E甲讲：“乙是个骑士，乙讲：“我们俩一个是骑士一个是骗子。答案：B假如甲是骑士，那么骑士讲真话，就不会是骗子，而他讲他们两个都是骗子，那么甲必然是骗子，讲的是谎言，所以二个人中至少有一个

8、是骑士，那么就只要乙是骑士了。第10题：给定一个m行n列的整数矩阵如图，每行从左到右和每列从上到下都是有序的。判定一个整数k能否在矩阵中出现的最优算法，在最坏情况下的时间复杂度是_。1579461015811121914161821AO(m*n)BO(m+n)CO(log(m*n)DO(log(m+n)答案：B杨氏矩阵查找算法lispanspanboolstepWise(spanintmatN_MAX,spanintN,spaninttarget,spanspanintrow,spanintcol)/span/span/span/span/span/span/span/spanlispansp

9、anif(targetmat00|targetmatN-1N-1)spanreturnspanfalse;spanrow=0;/span/span/span/span/spanlispancol=N-1;spanspanwhile(row=N-1col=0)/span/span/spanlispanspanif(matrowcoltarget)spanrow+;/span/span/spanlispanspanelsespanif(matrowcoltarget)spancol-;/span/span/span/spanlispanspanelsespanspanreturnspantrue;

10、/span/span/span/span/spanlispanspanspanreturnspanfalse;/span/span/span/spanlispan/span/li/ol第11题：二、不定项选择某服务请求经负载平衡设备分配到集群A、B、C、D进行处理响应的概率分别是10%、20%、30%和40%。已知测试集群所得的稳定性指标分别是90%、95%、99%和99.9%。如今该服务器请求处理失败，且已排除稳定性以外的问题，那么最有可能在处理该服务请求的集群是_。答案：AB解析：选中该集群，并且处理失败了的概率为：10%*10%、20%*5%、30%*1%、40%*0.1%。A与B的概率

11、最高。答案：A、B第12题：甲乙两人捡到一个价值10元的购物卡。协商后打算通过这样的拍卖规则来确定归属：两人单独出价能够出0元，出价高者得到购物卡同时将与出价一样数量的前给对方。假如两人出价一样，则通过掷硬币来决定购物卡的归属。例如：甲和乙都出价1元，他们通过掷硬币来决定购物卡的归属。此时，得到购物卡的人赚9元，另一人赚1元。两人都同意用手头的现金来进行出价。甲和乙都知道甲有6元、乙有8元，两人都期望本人尽可能多赚。那么_。A乙最终赚的比甲多B甲最终赚的比乙多C甲乙两人中可能有一人会有损失D甲乙两人赚的一样多答案：D首先甲乙都不会出5块钱以上的，由于那样本人会亏。但出5块钱下面，比方4块，对方

12、能够出5块，这样本人就输了，所以也不会出5块钱下面的。最后博弈后双赢的结果就是一方出五块，一方出0块，然后各得5块第13题：下面_状态为TCP连接关闭经过中的出现的状态。ALISTENBTIME-WAITCLAST-ACKDSYN-RECEIVED答案：BC主要部分，四次握手：断开连接其实从我的角度看不区分客户端和服务器端，任何一方都能够调用close(orclosesocket)之类的函数开场主动终止一个连接。这里先暂时讲正常情况。当调用close函数断开一个连接时，主动断开的一方发送FIN(finish报文给对方。有了之前的经历，我想你应该明白我讲的FIN报文时什么东西。也就是一个设置了F

13、IN标志位的报文段。FIN报文可以能附加用户数据，假如这一方还有数据要发送时，将数据附加到这个FIN报文时完全正常的。之后你会看到，这种附加报文还会有很多，例如ACK报文。我们所要把握的原则是，TCP肯定会力所能及地到达最大效率，所以你能够想到的优化方法，我想TCP都会想到。当被动关闭的一方收到FIN报文时，它会发送ACK确认报文(对于ACK这个东西你应该很熟悉了)。这有个东西要注意，由于TCP是双工的，也就是讲，你能够想象一对TCP连接上有两条数据通路。当发送FIN报文时，意思是讲，发送FIN的一端就不能发送数据，也就是关闭了其中一条数据通路。被动关闭的一端发送了ACK后，应用层通常就会检测

14、到这个连接即将断开，然后被动断开的应用层调用close关闭连接。第14题：假如在一个排序算法的执行经过中，没有一对元素被比拟过两次或以上，则称该排序算法为节省排序算法，下面算法中是节省排序算法的有_。A插入排序B选择排序C堆排序D归并排序答案：AD【解析】A每个未排序的元素只会与已经有序的元素进行至多一次比拟D每个有序列表内的元素不进行比拟；列表之间的元素比拟一次之后就进入了同一个列表第15题：三、填空题请补全下面的快速排序代码，答案中请不要包含空格。voidqsort(int*array,intlen)intvalue,start,end;if(len=1)return;value=arra

15、y0;start=0;end=len-1;while(startend)for(;startend;-end)if(arrayendvalue)_break;for(;startend;+start)if(arraystartvalue)_break;_qsort(array,_);qsort(_,_);arraystart+=arrayend;arrayend-=arraystart;arraystart=value;startarray+start+1len-start-1第16题：四、解答题某公司有这么一个规定：只要有一个员工过生日，当天所有员工全部放假一天。但在其余时候，所有员工都没有

16、假期，必须正常上班。假设一年有365天，每个员工的生日都概率均等地分布在这365天里。那么，这个公司需要雇用多少员工，才能让公司一年内所有员工的总工作时间期望值最大？你的第一感觉或许是，公司应该雇用100多人，或者200多人吧。答案或许会让你大吃一惊：公司应该雇用365个人。注意，雇用365个人并不意味着全体员工全年的总工作时间为0，由于365个人的生日都是随机的，恰好天天都有一个人过生日的概率极小极小。下面我们就来证明，这个问题的最优解就是365人。由于期望值知足线性关系即对于随机变量X和Y有E(X)+E(Y)=E(X+Y)，因而我们只需要让每一天员工总工作时间的期望值最大就能够了。假设公司

17、里有n个人，那么在特定的一天里，没有人过生日的概率是(364/365)n。因而，这一天的期望总工作时间就是n(364/365)n个工作日。为了考察函数n(364/365)n的增减性，我们来看一下(n+1)(364/365)n+1)/(n(364/365)n)的值，它等于(364(n+1)/(365n)。假如分子比分母小，解得n364。可见，要到n=365以后，函数才是递减的。答案：365第17题：给定一个排好升序的数组A1、A2、An，其元素的值都两两不相等。请设计一高效的算法找出中间所有Ai=i的下标。并分析其复杂度。不分析复杂度不得分解析：首先分析一下这个数组，假设其中某个位置的Ai=i，

18、那么能够肯定的值，之前的Axx，之后的Axx。还有一个显而易见的性质就是中间的Ai=i一定是连续存在的，不可能跨区域存在，由于这个数组是升序的。我给出的方法是二分查找，详细的做法是：我们假设一个新数组B，其元素是Ai-i的值，这样的话，Bi=0的时候Ai=i，而且把B数组划分成了三个部分，左边的小于零的区域，中间的等于零的区域，右边的大于零的区域。我第一次的想法是：二分搜索这个想象中的新数组，找到值为零的下标，但是这个下标不一定是最左边的知足条件的下标，所以我们还需要写一个while来往左移动这个下标，直到找到最左边的符合条件的下标，如下代码假设已经通过二分查找找到了符合条件的一个下标idx：

19、while(Aidx-1=(idx-1)idx-;这样的话其时间复杂度就是O(logn)+O(n)，还是属于On)的范畴。后来我想到，为什么只去随机命中一个目的下标呢！假如二分查找这个数据的边界的话，就能直接得到最左边符合条件的下标了！其实二分查找不仅仅适用于对一个元素的搜索，可以以用于两个、三个特定相对位置元素的搜索。每次查找的时候，假设当前位置是mid，那么只要判定当前Amid-mid能否小于零，以及后一个元素Amid+1-(mid+1)=0就行了。#includeiostreamusingnamespacestd;intBinarySearch(intcc,intlen)intl=0,r

20、=len,mid;while(l=r)mid=l+(r-l)1);if(mid=0ccmid=mid)/若数组一开场就符合条件return0;/若知足条件的下标不是从0开场，则边界是前一个0，且后一个=0if(ccmid-mid0ccmid+1-(mid+1)=0)returnmid+1;/二分查找边界：前一个0，且后一个=0if(ccmid-mid=0)r=mid-1;elsel=mid+1;return-1;intmain()/intcc=0,1;/intcc=0,1,2,3,4,5,6,7;/intcc=-9,-8,-4,-2,4,5,9;/intcc=-5,-4,-3,5,6,7;in

21、tlen=sizeof(cc)/sizeof(int);intidx=BinarySearch(cc,len);if(idx!=-1)while(ccidx=idx)printf(%d,idx);idx+;elseprintf(Notfoundn);getchar();return0;OK!由于程序是原生的二分查找，所以时间复杂度为O(logn)，没有占用额外的空间。并且不需要区分正整数还是负整数，数据类型可以以改成double没问题。第18题：某怪物被海水冲上一个孤岛。醒来时他发现本人处于险境。周围有N条鳄鱼都虎视眈眈的盯着他。每条鳄鱼看上去都饿得足以把他吞下去。不过，事情也未必真的那么糟糕

22、。鳄鱼吞下他是要花费体力的。这些鳄鱼如今的体力都相当，由于猎食需要花费体力，所以吞下怪物的鳄鱼会由于体力下降而可能被周围的某条鳄鱼吞了。类似的，吞鳄鱼的这条鳄鱼可以能被其他鳄鱼吞了。因而，固然有食物可猎，但他们本人并不想成为其他鳄鱼的猎食对象。正所谓，螳螂捕蝉，黄雀在后。所以鳄鱼们在确保本人生命安全的情况下才会发动进攻。那么，怪物到底安全么？为什么？假如只要一条鳄鱼，怪物显然是危险的；两条鳄鱼的时候，先下手的鳄鱼会成为另外一条鳄鱼的食物，所以怪物显然很安全；三条鳄鱼的时候，把先下手的鳄鱼当做怪物，就会回到两条鳄鱼的状态，此时先下手的鳄鱼非常安全，也就是讲怪物显然很危险；四条鳄鱼的时候，先下手的

23、鳄鱼会面临三条鳄鱼的状态，此时也就没有鳄鱼准备先下手，所以怪物很安全；我们很容易发现，吞吃过怪物的鳄鱼会成为下一个怪物，成为N-1条鳄鱼的猎物，也就是讲，假如N-1的时候安全，则N的时候危险；综上所述，奇数条鳄鱼怪物不安全，偶数条鳄鱼怪物安全。第19题：当你在阅读器输入一个网址，如taobao，按回车之后发生了什么？请从技术的角度描绘，如阅读器、网络UDP、TCP、HTTP等，以及服务器等各种介入对象上由此引发的一系列活动，请尽可能的涉及到所有的关键技术点。首先是查找阅读器缓存，阅读器会保存一段时间你之前访问过的一些网址的DNS信息，不同阅读器保存的时常不等。假如没有找到对应的记录，这个时候阅

24、读器会尝试调用系统缓存来继续查找这个网址的对应DNS信息。假如还是没找到对应的IP，那么接着会发送一个请求到路由器上，然后路由器在本人的路由器缓存上查找记录，路由器一般也存有DNS信息。假如还是没有，这个请求就会被发送到ISP注：InternetServiceProvider，互联网服务提供商，就是那些拉网线到你家里的运营商，中国电信中国移动什么的，ISP也会有相应的ISPDNS服务器，一听中国电信就知道这个DNS服务器的规模肯定不会小，所以基本上都能在这里找得到。题外话：会跑到这里进行查询是由于你没有改动过网络中心的ipv4的DNS地址，万恶的电信联通能够改动了这个DNS服务器，换句话讲他们

25、能够让你的阅读器跳转到他们设定的页面上，这也就是人尽皆知的DNS和HTTP劫持，ISP们还美名曰“免费推送服务。强烈鄙视这种霸王行为。我们可以以自行修改DNS服务器来防止DNS被ISP污染。假如还是没有的话，你的ISP的DNS服务器会将请求发向根域名服务器进行搜索。根域名服务器就是面向全球的顶级DNS服务器，共有13台逻辑上的服务器，从A到M命名，真正的实体服务器则有几百台，分布于全球各大洲。所以这些服务器有真正完好的DNS数据库。假如到了这里还是找不到域名的对应信息，那只能讲明一个问题：这个域名本来就不存在，它没有在网上正式注册过。或者卖域名的把它回收掉了通常是由于欠费。这也就是为什么打开一

26、个新页面会有点慢，由于本地没什么缓存，要这样递归地查询下去。多讲一句，例如mp3.baidu，域名先是解析出这是个的域名，然后跑到管理域名的服务器上进行进一步查询，然后是.baidu，最后是mp3，所以域名构造为：三级域名.二级域名.一级域名。阅读器终于得到了IP以后，阅读器接着给这个IP的服务器发送了一个请求，方式为get，例如访问这个get请求包含了主机host、用户代理(User-Agent)，用户代理就是本人的阅读器，它是你的代理人，Connection连接属性中的keep-alive表示阅读器告诉对方服务器在传输完如今请求的内容后不要断开连接，不断开的话下次继续连接速度就很快了。其他

27、的顾名思义就行了。还有一个重点是Cookies，Cookies保存了用户的登陆信息，在每次向服务器发送请求的时候会重复发送给服务器。Corome上的F12与Firefox上的firebug(快速键shift+F5)均可查看这些信息。发送完请求接下来就是等待回应了，当然了，服务器收到阅读器的请求以后其实是WEB服务器接收到了这个请求，WEB服务器有iis、apache等，它会解析这个请求读请求头，然后生成一个响应头和详细响应内容。接着服务器会传回来一个响应头和一个响应，响应头告诉了阅读器一些必要的信息，例如重要的StatusCode，2开始如200表示一切正常，3开始表示重定向，4开始，如404

28、，呵呵。响应就是详细的页面编码，就是那个./，阅读器先读了关于这个响应的讲明书响应头，然后开场解析这个响应并在页面上显示出来。在下一次CF的时候不是穿越火线，是codeforces/，由于经常难以承受几千人的同时访问，所以CF页面经常会出现崩溃页面，到时候能够点开火狐的firebug或是Chrome的F12看看状态，不过这时候一般都急着看题和提交代码，似乎根本就没心情理睬这个状态吧-.-。假如是个静态页面，那么基本上到这一步就没了，但是如今的网站几乎没有静态的了吧，基本全是动态的。所以这时候事情还没完，根据我们的经历，阅读器打开一个网址的时候会渐渐加载这个页面，一部分一部分的显示，直到完全显示，最后标签栏上的圈圈就不转了。这是由于，主页index页面框架传送过来以后，阅读器还要继续向服务器发送请求，请求的内容是主页里面包含的一些资源，如图片，视频，css样式等等。这些非静态的东西要一点点地请求过来，所以标签栏转啊转，内容刷啊刷，最后全部请求并加载好了就终于好了。需要讲明的是，对于静态的页面内容，阅读器通常会进行缓存，而对于动态的内容，阅读器通常不会进行缓存。缓存的内容通常也不会保存很久，由于难保网站不会被改动。