阿里巴巴2013实习生招聘笔试题

[2014年阿里校招笔试题目]前言我明天上午9点还有面试，今天突然看到某大牌IT公司笔试题目，必须做一下了题目一、单选题 1.假设把整数关键码K散列到N个槽列表，以下哪些散列函数是好的散列函数 A: h(K)=...+阅读

答题说明：

1.答题时间90分钟，请注意把握时间;

2.试题分为四个部分：单项选择题(10题，20分)、不定向选择题(4题，20分)、填空问答(5题，40分)、综合体(1题，20分);

3.其他一些乱七八糟的考试说明。

一、单项选择题

1.下列说法不正确的是：(D)

A.SATA硬盘的速度速度大约为500Mbps/s

B.读取18XDVD光盘数据的速度为1Gbps

C.前兆以太网的数据读取速度为1Gpbs

D.读取DDR3内存数据的速度为100Gbps

解析：

DDR3内存读取速度约为1.6Gbps

2.(D)不能用于Linux中的进程通信

A.共享内存

B.命名管道

C.信号量

D.临界区

3.设在内存中有P1,P2,P3三道程序，并按照P1,P2,P3的优先级次序运行，其中内部计算和IO操作时间由下表给出(CPU计算和IO资源都只能同时由一个程序占用)：

P1:计算60ms---》IO 80ms---》计算20ms

P2:计算120ms---》IO 40ms---》计算40ms

P3:计算40ms---》IO 80ms---》计算40ms

完成三道程序比单道运行节省的时间是(C)

A.80ms

B.120ms

C.160ms

D.200ms

4.两个等价线程并发的执行下列程序，a为全局变量，初始为0，假设printf、++、--操作都是原子性的，则输出不肯哪个是(A)

void foo() {

if(a = 0) {

a++;

}

else {

a--;

}

printf(%d, a);

}

A.01

B.10

C.12

D.22

5.给定fun函数如下，那么fun(10)的输出结果是(C)

int fun(int x) {

return (x==1) ? 1 : (x + fun(x-1));

}

A.0

B.10

C.55

D.3628800

6.在c++程序中，如果一个整型变量频繁使用，最好将他定义为(D)

A.auto

B.extern

C.static

D.register

7.长为n的字符串中匹配长度为m的子串的复杂度为(B)

A.O(N)

B.O(M+N)

C.O(N+LOGM)

D.O(M+LOGN)

解析： KMP算法

8.判断一包含n个整数a[]中是否存在i、j、k满足a[i] + a[j] = a[k]的时间复杂度为()

A. O(n3)

B.O(n2lgn)

C.O(n2)

D.O(nlgn)

解析：O(N2)的算法能想一大堆，虽然最终我选的C，比如说用hash的话，三维遍历可以轻松编程二维遍历，但是总感觉是不是应该有nlgn的算法。

9.三次射击能中一次的概率是0.95，请问一次射击能中的概率是多少?(A)

A.0.63

B.0.5

C.**

D.0.85

10.下列序排算法中最坏复杂度不是n(n-1)/2的是_(D)

A.快速序排 B.冒泡序排 C.直接插入序排 D.堆序排

二、不定向选择题

1.阻塞、就绪、运行的三态转换

2.一个栈的入栈数列为：

1、

2、

3、

4、

5、6;下列哪个是可能的出栈顺序。(选项不记得)

3.下列哪些代码可以使得a和b交换数值。(选项不记得)

4.A和B晚上无聊就开始数星星。每次只能数K个(20=k=30)A和B轮流数。最后谁把星星数完谁就获胜，那么当星星数量为多少时候A必胜?

A.2013 B.2886 C.4026 D......E.....(选项不记得)

三、填空问答题

1.给你一个整型数组A[N]，完成一个小程序代码(20行之内)，使得A[N]逆向，即原数组为1，2，3，4，逆向之后为4，3，2，1

void revense(int * a,int n) {

}

2.自选调度方面的问题，题目很长，就是给你三个线程，分别采用先来先分配的策略和最短执行之间的调度策略，然后计算每个线程从提交到执行完成的时间。题目实在太长，还有几个表格。考察的是操作系统里面作业调度算法先进先出和最短作业优先。

3.有个苦逼的上班族，他每天忘记定闹钟的概率为0.2，上班堵车的概率为0.5，如果他既没定闹钟上班又堵车那他迟到的概率为1.0，如果他定了闹钟但是上班堵车那他迟到的概率为0.9，如果他没定闹钟但是上班不堵车他迟到的概率为0.8，如果他既定了闹钟上班又不堵车那他迟到的概率为0.0，那么求出他在60天里上班迟到的期望。

4.战报交流：战场上不同的位置有N个战士(n4)，每个战士知道当前的一些战况，现在需要这n个战士通过通话交流，互相传达自己知道的战况信息，每次通话，可以让通话的双方知道对方的所有情报，设计算法，使用最少的通话次数，是的战场上的n个士兵知道所有的战况信息，不需要写程序代码，得出最少的通话次数。

5.有N个人，其中一个明星和n-1个群众，群众都认识明星，明星不认识任何群众，群众和群众之间的认识关系不知道，现在如果你是机器人R2T2，你每次问一个人是否认识另外一个人的代价为O(1)，试设计一种算法找出明星，并给出时间复杂度(没有复杂度不得分)。

解答：这个问题等价于找未知序列数中的最小数，我们将reg这个函数等价为以下过程：，如果i认识j，记作i大于等于j,同样j不一定大于等于i,满足要求，i不认识j记作i

int finds(S,N)

{

int flag=0; 用于判定是否有明星，即当前最小数另外出现几次

int temp=0; 存放最小数在S中的位置

for(i=1;i

{

if(!reg(S[i],S[temp]) 如果temp标号的数小于i标号的数

{

temp=i;