阿里巴巴笔试题目

排序法平均时间最差情形额勺怪间

冒泡0(n2)O(n2)0(1)

交换0(n2)O(n2)0(1)

邮0(n2)O(n2)0(1)

0(n2)0(n2)0(1)

堂O(logRB)O(logRB)0(n)

ShellO(nlogn)O(ns)1<s<20(1)

螃O(nlogn)O(n2)O(logn)

丽O(nlogn)O(nlogn)0(n)

1.现有1G数据需要排序，计和资源只有1G内存可用，以下排序方法中最可能出现性能问

题的是。

A.堆排序

B•插入排序

C.归并排序

D.快速排序

E.选择排序

F.冒泡排序

正确答案：C

2.Linux下两个进程能够同时打开同一个文件，这时以下描述错误时是:

A.两个进程中分别产生生成两个独立的fd

B.两个进程能够任意对文件进行读写操作，操作系统并不确保写口勺原子性

C.进程能够经过系统调用对文件加锁，从而实现对文件内容H勺保护

D.任何一个进程删除该文件时，另外一个进程会立刻出现读写失败

E.两个进程能够分别读取文件H勺不一样部分而不会相互影响

F.一个进程对文件长度和内容的修改另外一个进程能够立刻感知

正确答案：D

一个进程删除该文件后，另一个进程能够继续操作，直到退出以后，才找不到该文件

3.现在有一个程序由A,B两个同学结对编程完成，在整个程序中口勺代码百分比

是3:5,据往常的I统计A同学的千行代码缺点率为10%。，B同学H勺千行代码缺

点率为15%,现在在改程序中发觉了一个缺点，那么是由A同学［I勺代码引发口勺

缺点的概率为—.

A.28.6%

B.37.5%

C.40.0%

D.47.4%

E.52.6%

F.71.4%

正确答案：A

记发觉BUG为事件BUG,A编写代码为事件A,B编写代码为事件B,则

A编写的代码中发觉BUG的概率为P(BUG|A)=0.01%

B编写的代码中发觉BUGH勺概率为P(BUG|B)=0.015%

对于已经编好口勺一个程序，P(A)=3/8,P(B)=5/8

依照贝叶斯公式得：

P(A|BUG)=P(A)P(BUG|A)/{P(A)P(BUG|A)+P(B)P(BUG|B)}=3/8*0.01%/(3/8*0.01%+5/8*0.015%)

4.猜数字游戏的过程是你输入一个4位数(数字选取0、9,不会重复)，电脑

会告诉你两个信息：A个数字和位置均正确，B个数字正确但位置错误。比如正

确答案是7890你输入0789,电脑会告诉你0A4B,表示有0个数字和位置完全

正确，但有4个数字正确但位置错误。现在牛妹猜了三次的结果分别是：

1234=>0A4B,2341=>1A3B,3412=>2A2B,那么牛妹最少还要猜次才能确保

一定得到4A0B口勺结果。

A.0

B.1

C.2

D.3

E.4

F.5

正确答案：D

经过分析，只有可能是以下四种情况

2413

3142

3421

4312

现在考虑是否能够知问询一次就得到答案。

A+B的总数量必定无法提供额外H勺信息。

所以我们只能经过OA,1A,2A,3A,4A来获取信息。

假如要达成3A,则只能最少猜一个1,2,3,4以外的数字。

这么的话，这个位置就废掉了，没啥意义。

所以我们只能经过OA,1A,2A,4A分别区分四种情况

假如用到4A,如猜2413

2413=>2A

3142=>0A

3421=>1A

4312=>1A

无法区分两个1AH勺情况，由对称性，猜其余三个类似,

所以我们最少再猜两次才能知道答案。

所以我们最少再猜三次才能确保得到4A

5.关于下述Java代码描述正确的选项是

IpublicclassTestClass{

2privatestaticvoidtestMethod(){

3System.out.printin(，，testMethod，/);

4)

5publicstaticvoidmain(String[]args){

6((TestClass)null).testMethod();

7)

8)

A.编译不经过

B.编译经过,运行异常，报NullPointerException

C.编译经过,运行异常，报T11egalArgumentException

D.编译经过,运行异常，报NoSuchMelhodExceplion

E.编译经过,运行异常,报Exception

F.运行正常,输出testMethod

正确答案:F

1）此处是类对方法H勺调用，不是对象对方法的调用。

2）方法是sialic静态方法，直接使用”类.方法〃即可，因为静态方法使用不依

赖对象是否被创建。

null能够被强制类型转换成任意类型（不是任意类型对象），于是能够经过它

来执行静态方法。

3）非静态的方法用“对象方法〃小J方式，必须依赖对象被创建后才能使用，若

将testMethod。方法前的Jstatic去掉，则会报空指针异常。此处也验证了

2）的观点

当然，不论是否静态方法，都是已经存在的，只是访问方式不一样。

6.以下函数中，和其余函数不属于一类的是。

A.fread

B.gets

C.getchar

D.pread

E.getline

F.scanf

正确答案：D

Pread是系统调用，其余为10函数

常见文件系统系统函数

fcntl文件控制

open打开文件

creat创建新文件

close关闭文件描述字

read读文件

write写文件

readv从文件读入数据到缓冲数组中

writev将缓冲数组里的数据写入文件

pread对文件随机读

pwrite对文件随机写

7.有一个类A,其数据组员以下:

1classA{

2...

3private:

4inta;

5public:

6constintb;

7float*&c;

8staticconstchar*d;

9staticdouble*e:

10};

则结构函数中，组员变量一定要经过初始化列表来初始化H勺是:

A.abc

B.bc

C.bcde

D.bcd

E.b

F.c

正确答案：B

结构函数中组员变量一定要经过初始化列表来初始化H勺有一下几个情况

（1）const常量组员，因为常量只能初始化，不能赋值，所以必须放在初始化列表中

（2）引用类型，引用类型必须在定义的时候初始化，不能重新赋值，所以必须放在初

始化列表中

（3）没有默认结构函数的类类型，因为使用初始化列表能够无须调用默认结构函数来

初始化，而是直接调用拷贝结构函数

注：static类要在类外初始化，不用再初始化列表中。

8.在以下8*6H勺矩阵中，请计克从A移动到B一共有一种走法。要求每次只能向上或向右

移动一格，而且不能经过P。

B

P

A

A:456

B:492

C:568

D:626

E:G80

F:702

正确答案：B

8*6时矩阵，从左下角A到右上角B,一共需要走12步，其中5步向上，7步向右，所以总

的走法一共有C(12,5)=792种，但题目要求不能经过P,所以需要减去经过P点的走法。

经过P的路径分为两部分，从A到P,从P到B。

同理，从A到PH勺走法：C(6,2)=15；

同理，从P到B的走法:C(6,3)=20；

所以从A到B经过P点的走法有15*20=300种，

所以从A到B不经过P点的走法有792-300=492种。

9.某单链表有5个元素，设单链表H勺节点结构为（data,next）,5个元素H勺data依次为（1、

2、3、4、5）,己知指针q指向节点3,指针p指向节点4,那么下面操作能将链表变为data

依次为（1、2、3、5）的）是—o（其中temp为节点类型指针，默认指向NULL）

A.q=p->next;

B.p=q->next;

C.p->next=q->next;

D.q->next=p->next;deleteq;

E.p->data=p->next->data;p->next=p->next->next;deletep->next;

F.temp=p->next;p->next=temp->next;p->data=temp->data;deletetemp;temp=NULL;

正确答案：F

//D:q->next=p->next;p->next=null;deletep;

把节点5I用值赋给节点4,然后移去节点5.

//E:p->data=p->next->data;p->next=p->next->next;deletep;

10.两人在一个n个点的无向完全图上进行游戏，每次能够选择当前图中两个端点度数奇偶

性相同的边删除，谁不能操作谁输，则在n=l,2,3，……,9,10中，有_个图先手有必胜策略

答：五个，N个点的无向完全图边数为：N*（N-1）/2：先手获胜必须总数为奇数：

N=l,2,3，……,9,10代入公式，为奇数的只有N=2,3,6,7,10这5个

11.A为整数数组，N为A内数组长度，请问执行以下代码，最坏情况下口勺时间复杂度为

1voidfunfintA[],intn){

2for(inti=n-1;i>=1;i-){

3for(intj=0;j<i;j++){

4if(A[j]>A[j+l]){

5inttmp=A[j+1];

6A[j+1]=A[j];

7A[j]=tmp;

8}

9)

10}

11)

•O(N)

•O(NA2)

•O(Nlog(N))

•O(log(N))

•O(NA3)

•无法确定

正确答案：B

国泡排序法,最坏情况为(n-l)+(n-2)+……+l=n(n-l)/2所以复杂度是N0

12.当前国内A股市场口勺新股发行采取口勺是抽签申购口勺方式。假设最多能够申购某新股XI

万股，以1T股为单位分配一个号码进行抽签，每个号码抽中是否是相互独立日勺且概率为

0.5%,X的发行价是10元，涨至15元和20元口勺概率均为50%,那么在最大申购的情况下盈

利的期望是—。

A.250

B.300

C.325

D.375

E.425

F.500

正确答案：D

最多申购10000股，1000股分配一个号，则顶格申购就会产生10个号，每个号码是否中签

独立，就是说中签号为伯努利事件，服从B(10,0.005),

中签的期望为E=n*p=10*0.005=0.05.发行价是10元，涨至15元和20元的概率均为50%,则

假如中签后每股收益的期望为(15-10)*0.5+(20-10)*0.5=75。所以总的收益为中签H勺

概率期望*中签后每股收益口勺期望♦股数=0.05”.5*1000=375

13.下而数据结构能够支持随机的插入和删除操作、并具备很好的性能的是一»

正确答案:B你的答案:A(错误)

A.数组和链表

B.链表和哈希表

C.哈希表和队列

D.队列和维栈

E.堆栈和双向队列

F.双向队列和数组

1，数组是在定义的时候中请一块连续日勺内存空间，访问某个元素只需要经过下标就能够，

不过随机插入和删除都要移动后面全部的元素，所以，数组必定不行；

2,链表，是非连续H勺空间，经过指针访问，所以随机插入和删除经过指针之间的操作很

方便，不过假如要查询一个数的时候还是得依次便利，不过题目问的是随机插入和删除，

所以，链表能够；

3,栈，全部口勺操作都是在栈顶，假如要随机插入或者删除某个数也必须依次对其余数就

行操作，所以，栈也排除；

4,队列，经过队头和队尾指针进行读入数据和删除数据，假如直接在队尾添加数据很方

便，不过，题目中是随机，所以，队列排序；

5,哈希表经过犍值对操作，只要知道相关曰勺key很轻易就行读取和删除，插入某个元素

也经过key很方便，所以，哈希表必定能够；

14.一个英雄基础攻击力为货0,携带了三件暴击武器，武器A有40%口勺概率打出2倍攻击，

武器B有20%的概率打出4倍攻击，武器C有10%概率打出6倍攻击，各暴击效果触发是

独立事件，不过多个暴击效果在一次攻击中同时触发时只有后面武器的暴击真正生效，比如

一次攻击中武器A判定不暴击，武器B和武器C都判定触发暴击，那么这次攻击实际是600

攻击力。那么这个英雄攻击力的数学期望是——。

正确答案:C你的答案:F(错误)

A.186.6

B.200

C.232.8

D.256.8

E.320

F.332.6

(600*10%)〃使用武器C

+(400*90%*20%)〃使用武器B,需要确保没有使用武器C,不然因为多个暴击效

果在一次攻击中同时触发时只有后面武器的暴击真正生效，武器B不生效

+(200*90%*80%*40%)//同理，使用武器A,需要偏保武器B和C都没有使用

+(100*60%*80%*90%)；/没有使用任何武器

=232.8

15.某操作系统采取分页存放管理方式，下列图给出了进程A和进程B的页表结构。假如

物理页的大小为512字节，那么进程A与进程B的物理内存总共使用了字节。

进程A页表：进程B页表：

逻辑页物理页逻辑页物理页

0901

1213

2424

3637

442

55

正确答案:B你的答案:E（错误）

A.4608

B.3584

C.4096

D.5120

E.2560

F.2048

物理页能够在进程间共享，两个进程共使用了1,2,34,6,7,9,共7个物理页。

故：7*512=3584

16.有1,2,3，……无穷个格子，你从1号格子出发，每次1/2概率向前跳一格，1/2概率向前

跳两格，走到格子编号为4的倍数时结束，结束时期望走的步数为—o

A.2

B.2.4

C.2.8

D.3

E.3.2

F.3.6

G.4

正确答案：E

还是设f(i)表示在第i号格子上时，期望再走多少步结束。

则从1号开始走，我们的目标是求f(l)

f(l)=0,5*(1+f(2))+0.5*(1+f(3))即有0.5概率走一步到2号，0.5概率走两步

到3号

f(2)=0.5♦(1+f(3))+0.5*(1+f(4))即有0.5概率走一步到3号，0.5概率走两步到

4号

f⑶=0.5*(1+f(4))+0.5*(1+f(l))即有0.5概率走一步到4号，0.5概率走两步到

5号(5号即可看做1号)

f(4)=0走到4号就结束了,故为0

能够解上述方程,得f(l)=18/5.

17.从1,2,3，……,49,50里选择一个集合里使得若x属于S,则2x不属于S,则5最多能有

个元素。

正确答案:D你的答案:D(正询)

A.25

B.27

C.30

E.33

F.36

H.37

18.考虑以卜.二分查找日勺代码：

/include<stdio.h>

intbsearch(intarrayf],intn,intv)

(

intleft,right,middle;

left=0,right=n-1;

while(left<=right){

middle=left+(right-left)/2;

if(array[middle]>v){

right=middle;

}elseif(array(middle]<v){

left=middle;

}else{

returnmiddle;

)

return-1;

)

对于输入array为：{2,6,8,10.13,25,36,45,53,76,88,100,127},n=13,v=127时，

运行bsearch函数，while循环调用的次数为一。

正确答案:F你的答案:F(止确)

A.1

B.3

C.4

D.5

E.6

F.无数次

本即是一个坑，这是不正确的二分查找法，当中间的没有找到的时候，left和right下标

应该左移或者右移(left++,right-),实质是(right=middle-1»left=middle+l),才不会出现

除以二向下取值的时候出现无限