阿里巴巴2014笔试题详解(9月22北京)

第一部分 单选题(前10题,每题2分;后10题,每题3分。选对得满分,选错倒扣1分,不选得0分)

1、一次内存访问,SSD硬盘访问和SATA硬盘随机访问的时间分别是()

   A、几微秒,几毫秒,几十毫秒 B、几十纳秒,几十毫秒,几十毫秒

   C、几十纳秒,几十微秒,几十毫秒 D、几微秒,几十微秒,几十毫秒

解析:内存访问速度通常在50ns到80ns范围内,SSD硬盘的访问速度一般是SATA硬盘的一千多倍,所以答案选C

2、8进制数256,转化成7进制数是(B)    A、356    B、336    C、338    D、346

解析:进制转换

    八进制256转换为十进制:2*8*8 + 5*8 + 6*1 = 174

    十进制174转换为七进制:336

答案:D

3、某网络的IP地址空间为192.168.5.0/24,采用定长子网划分,子网掩码为255.255.255.248,则该网络的最大子网个数、每个子网内最大可分配地址个数各位(C)    A、8,32   B、32,8    C、32,6    D、8,30

知识点:子网划分

4、以下关于链式存储结构说法错误的是(A)    A、查找节点时链式存储比顺序存储快    B、每个节点是由数据域和指针域组成    C、比顺序存储结构的存储密度小    D、逻辑上不相邻的节点物理上可能相邻

5、假定一个二维数组的定义语句为“inta[3][4]={{3,4},{2,8,6}};”,则元素a[1][2]的值为(A)    A、6       B、4        C、2          D、8

解析:三行四列

3

4

0

0

2

8

6

0

0

0

0

0

答案:A

6、下面函数的功能是(C)    int fun (char *s)    {        char *p=s;        while(*p++);        return p-s-1;    }    A、计算字符串的位(bit)数            B、复制一个字符串    C、求字符串的长度                   D、求字符串存放的位置

解析:s指向字符串第一个字符,计算完后,p指向字符串末尾后一位

while(*p++);  当p指向\0时,还会再做一次+1
while循环跳出后,s和p的位置分别如下:

h

e

l

l

0

\0

random

s

p

p - s = 6

字符串长度为5,所以还要减一

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、图的遍历算法可以执行在有回路的图中

解析:A肯定是不正确的,用队列辅助的话,可以不必使用递归实现

          B对的,C对的,遍历并没有显示是否是有向,

          D应该是对的,只需要对访问过的节点进行标记,也就不用考虑是否有回路,或者说,无向图本身就不用考虑是否有回路

知识点:图的深度遍历和广度遍历的递归和非递归实现

10、在16位机器上跑下列foo函数的结果是(B)    void foo()    {        int i = 65536;        cout << i<<”,”;        i = 65535;        cout << i;    }    A、-1,65535   B、0,-1     C、-1,-1    D、0,65535

解析:16位机器的int型变量为16位

16位int的表示范围:-32768到32767 65535(十进制) = 1111111111111111(二进制) 65536(十进制) = 10000000000000000(二进制) 上面是原码表示 转换为补码,除了最高位,其它位取反,加一 补码表示:分别为0和-1

11、有一段年代久远的C++代码,内部逻辑复杂,现在需要利用其实现一个新的需求,假定有以下可行的方案,应当优先选择(D)    A、修改老代码的接口,满足新的需求    B、将老代码抛弃,自己重新实现类似的逻辑    C、修改老代码的内部逻辑,满足新的需求    D、在这段代码之外写一段代码,调用该代码的一些模块,完成新功能需求

解析:封装的思想

12、在5个页框上使用LRU页面替换算法,当页框初始为空时,引用序列为0、1、7、8、6、2、3、7、2、9、8、1、0、2,系统将发生(C)次缺页    A、13           B、12          C、11         D、8

分析:缺页为: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、18M         B、12M        C、6M        D、24M

解析:

   TCP协议原理: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约为15M

个人感觉这种方法不是十分准确,因为TCP连接有滑动窗口机制,可以在未收到ACK的时候继续发送数据,所以极端情况下A节点的发送缓冲区可以再减少一半,即在7.5M左右。不过题目里并没有说到滑动窗口机制,而是说通过ACK来确认每个数据报是否正确传送,所以应该不考虑这种极端情况。

14、有3个节点的二叉树可能有(A)种    A、5           B、13          C、12         D、15

解析:不考虑节点的排列组合

15、设某文件经内排序后得到100个初始归并段(初始顺串),若使用多路归并排序算法,且要求三趟归并完成排序,问归并路数最少为(D)    A、8           B、7           C、6          D、5

解析:m个元素k路归并的归并趟数s=logk(m),代入数据:logk(100)≦3

16、一个优化的程序可以生成一n个元素集合的所有子集,那么该程序的时间复杂度是(B)    A、O(n!)        B、O(2n)        C、O(n2)        D、O(nlog n)

解析:当数学题做吧 

17、快速排序在已经有序的情况下效率最差,复杂度为(B)    A、O(nlog n)    B、O(n2)        C、O(n1.5)       D、O(n2log n)

解析:基础 

18、从一副牌(52张,不含打小怪)里抽出两张牌,其中一红一黑的概率是(D)    A、25/51        B、1/3          C、1/2          D、26/51

解析:52张牌从中抽两张,就是C522种情况,一红一黑是C261* C261种情况,概率P= C261 * C261 /C522 =26/51

19、有一堆石子共100枚,甲乙轮流从该堆中取石子,每次可取2、4或6枚,若取得最后的石子的玩家为赢,若甲先取,则(C)    A、谁都无法取胜    B、乙必胜    C、甲必胜     D、不确定

解析:先取的人只需要保证最后剩8枚就胜了。而要保证最后剩8枚,则必须要保证每一个回合内取的数是一个可控的固定数,显然这个数字是8,所以只需要保证第一次取完后,剩下的数字是8的倍数,就一定能胜。100除以8余数为4,故而,甲先取4枚,之后每一个回合所取数与上一个回合乙所取数之和为8,就能保证必胜。

20、现有一完全的P2P共享协议,每次两个节点通讯后都能获取对方已经获取的全部信息,现在使得系统中每个节点都知道所有节点的文件信息,共17个节点,假设只能通过多次两个对等节点之间通讯的方式,则最少需要(C)次通讯    A、32      B、31      C、30       D、29

解析:搬砖的

   解法由@龙人920提供

分析:如上图1所示,假设有5个节点,按连线1、2、3、4通讯之后,节点4和5就掌握了所有节点的信息,之后,1、2、3节点只需跟4或5任一节点通讯一次即连线5、6、7就可保证每个节点都知道所有节点的信息,总的通讯次数是(n-1)+(n-2)=2n-3次。

如果将所有节点分成两组,如图2所示,两组中的节点分别按连线1-8顺序通讯之后,节点4和5就掌握了1-5所有节点的信息,节点9和0就掌握了6-0所有节点的信息,再按连线9、10通讯之后,节点4、5、9、0就掌握了1-0所有节点的信息,剩下的节点只需跟4、5、9、0任一节点通讯一次就可保证每个节点知道所有节点信息,和图1相比,多了9和10两次通讯,总的通讯次数是(2n1-3)+(2n2-3)+2=2n-4次(n1和n2分别表示分组中元素个数)。

分3组的情况是(2n1-3)+(2n2-3)+(2n3-3)+6=2n-3次

分4组的情况是(2n1-3)+(2n2-3)+(2n3-3)+(2n4-3)+8=2n-4次

  第二部分 不定项选择(每题五分,每题有1-5个正确选项,完全正确计5分,漏选计2分不选计0分,多选、错选计-2分)

21、2-3树是一种特殊的树,它满足两个条件: (1)每个内部节点有两个或三个子节点; (2)所有的叶节点到根的路径长度相同; 如果一颗2-3树有9个叶节点,下列数量个非叶节点的2-3树可能存在的有(BE)

   A、8 B、7 C、6 D、5 E、4

解析:根据条件(2),叶节点只能在同一层,根据条件(1),上一层的父节点只能是3个或4个,画一下就出来了。

22、下列有关进程的说法中,错误的是(ABC)    A、进程与程序是一亿对应的    B、进程与作业时一一对应的    C、进程是静态的              D、进程是动态的过程

23、下列函数定义中,有语法错误的是(D)    A、void fun(int x, int *y){x *=*y;}    B、int * fun(int *x, int y){return x +=y;}    C、void fun(int *x, int y){*x +=y;}    D、void fun(int x, int *y){*x *=*y;}

24、有朋自远方来,他乘火车,轮船,汽车,飞机来的概率分别是0.3,0.2,0.1,0.4,坐各交通工具迟到的概率分别是1/4,1/3,1/12,0,下列语句中正确的是(CD)    A、如果他准点,那么乘飞机的概率大于等于0.5    B、坐陆路(火车,汽车)交通工具准点机会比坐水路(轮船)要低    C、如果他迟到,乘火车的概率是0.5    D、如果他准点,坐轮船或汽车的概率等于坐火车的概率

第三部分  填空与问答

25、(4分)文件分配表FAT是管理磁盘空间的一种数据结构,用在以链接方式存储文件的系统中记录磁盘分配和追踪空白磁盘块,整个磁盘仅设一张FAT表,其结构如下所示,如果文件块号为2,查找FAT序号为2的内容得知物理块2的后继物理块是5,再查FAT序号为5的内容得知物理块5的后继物理块是7,接着继续查FAT序号为7的内容为“Λ”,即该文件结束标志,

假设磁盘物理块大小为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的所有可能值是哪些?

int a = 2, b = 0, c =0;

   voidf1()                        voidf2()

   {                                {

       b = a *2;                       c = a +11;

a =b;                           a = c;

   }                                }

解析:考虑四行代码的执行顺序即可

   (1)b=a*2,c=a+11,a=c,a=b          a=4

   (2)b=a*2,c=a+11,a=b,a=c           a=13

   (3)b=a*2,a=b,c=a+11,a=c          a=15

   (4)c=a+11,a=c,b=a*2,a=b           a=26

27、(6分)设计一个最优算法来查找一n个元素数组中的最大值和最小值,已知一种需要比较2n次的方法,请给一个更优的算法。请特别注意优化时间复杂度的常数。 给出该算法最坏情况下的比较次数和该算法的步骤描述。(不用写代码,不给出比较次数的不得分)

分析:已知的比较2n次的方法,显然是将每个元素和最大值、最小值各比一次,要减少比较次数,可以有多种优化方法:

  方法一:一个元素先和最大值比较,如果比最大值大,就不用再和最小值比较(或者先和最小值比较,如果比最小值小,就不用再和最大值比较),一般情况下,这种优化后的比较次数一定会少于2n

  方法二:将数组元素按两个,两个分组,组内两元素有序存放,之后最小值跟组内较小的值比较,最大值只需跟组内较大的值比较,这样每组的比较次数是3,共n/2组,总的时间复杂度是3n/2次。

 详情请参考http://blog.csdn.net/thebestdavid/article/details/11975809的第3题

28、(8分)已知三个升序整数数组a[l]、b[m]、c[n],请在三个数组中各找一个元素,使得组成的三元组距离最小,三元组的距离定义是:假设a[i]、b[j]和c[k]是一个三元组,那么距离为distance=max(|a[i]-b[j]|,|a[i]-c[k]|,|b[j]-c[k]|),请设计一求最小三元组距离的最优算法,并分析时间复杂度。(不用写代码,不分析时间复杂度不得分)

解析:用三个指针分别指向a,b,c中最小的数,计算一次他们最大距离的Distance ,然后在移动三个数中较小的数组指针,再计算一次,每次移动一个,直到其中一个数组结束为止,最慢(l+ m + n)次,复杂度为O(l+ m + n)

详情请参考http://blog.csdn.net/thebestdavid/article/details/11975809的第4题

29(8分)在黑板上写下50个数字:1至50。在接下来的49轮操作中,每次做如下动作:选取两个黑板上的数字a和b檫去,在黑板上写|b-a|。请问最后一次动作之后剩下数字可能是什么?为什么?(不用写代码,不写原因不得分)

解析:参考两个解法:

http://blog.csdn.net/qqsxdong/article/details/12184707

http://www.cnblogs.com/ksedz/p/3346294.html

【算法工程师 附加题】请设计一个算法,在满足质因数仅为3,5,7或其组合的数中,找出第K大的数。比如K=1,2,3时,分别应返回3,5,7。要求算法时间复杂度最优。

参考:

一些参考的链接都贴在解析里,其他的在此一并谢过。o(∩_∩)o 

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏计算机视觉与深度学习基础

本次新生赛部分题解

A poj1129 这题的愿意是考察四色原理(不是太难,主要是了解),但是模拟+暴力枚举也是可以过的,有几个WA点,注意看注释 #include<cstdio>...

22050
来自专栏大数据智能实战

tensorflow.models.rnn.rnn_cell.linear在tensorflow1.0版本之后找不到(附tensorflow1.0 API新变化)

由于版本更新关系,从原来的tensorflow低版本到升级到tensorflow1.0以上时,发现有很多API函数变化是很正常的事情,大多碰到的如: 如其中tf...

33270
来自专栏yw的数据分析

data.table包使用应该注意的一些细节

  注意默认nThread=getDTthreads(),即使用所有能用的核心,但并不是核心用的越多越好,本人亲自测试的情况下,其实单核具有较强的性能,只有在数...

8310
来自专栏magicsoar

Effective Modern C++翻译(5)-条款4:了解如何观察推导出的类型

条款4:了解如何观察推导出的类型 那些想要知道编译器推导出的类型的人通常分为两种,第一种是实用主义者,他们的动力通常来自于软件产生的问题(例如他们还在调试解决中...

21180
来自专栏图形学与OpenGL

WebGL画点程序v1

本文程序实现画一个点的任务,如下图。其中,点的位置直接给定(“硬编码”)在顶点着色器中。

8530
来自专栏漫漫深度学习路

tensorflow:AToolDeveloperGuideToTFModelFIles

Tensorflow Model Files 最近闲来无聊,想深入理解一下tensorlfow,也不知从何下手,突然间发现了官方文档的Extend模块下还有这个...

38350
来自专栏机器学习从入门到成神

字符串面试题(三)— 把一个字符串的大写字母放到字符串的后面

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/sinat_35512245/articl...

22010
来自专栏小樱的经验随笔

hihoCoder #1082 : 然而沼跃鱼早就看穿了一切(字符串处理)

#1082 : 然而沼跃鱼早就看穿了一切 时间限制:1000ms 单点时限:1000ms 内存限制:256MB 描述 ? fjxmlhx每天都在被沼跃鱼刷屏,因...

29550
来自专栏FreeBuf

使用Burpsuite扩展Hackvertor绕过WAF并解密XOR

最近,我一直在忙于开发自己的一个Burp扩展Hackvertor。这是一个具有基于标签转换功能的编码器,相比起Burp内置的解码器它的功能要强大的多。通过标签的...

15210
来自专栏Web 开发

做wordpress CMS必须用到的强力代码(转)

这个代码很强力,做一个wordpress cms的索引页面(index.php) 这个代码是必须要会使用,不然会走很多弯路。

11320

扫码关注云+社区

领取腾讯云代金券