2014年阿里巴巴实习生笔试题

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

研发工程师、算法工程师、测试开发工程师、安全工程师、客户端开发工程师、前端开发工程师、用户体验研究专员、视觉设计师、交互设计师、数据分析师、产品经理

面向学生：2015年及以后毕业的在校生

实习时间：可灵活安排实习时间，在2014年9月之前实习满1个月即可。

网申时间：即日起至2014年3月24日

笔试时间：全国统一3月29日

关于转正：实习的同学可以在2014年秋季校招启动之前，参加内部面试，通过后即可提前拿到正式校招Offer。

通过实习生面试，但不能实习的同学，也可以在秋季校招中直接进入终面。

实习补助：我们会为实习生提供具有竞争力的实习薪资、午餐和晚餐补贴、商业保险并报销入职交通费，还为异地同学(户籍、学校所在地不在实习工作地)提供一周的酒店住宿补贴，并按月发放住房补贴。

1、设栈S初始状态为空。元素a,b,c,d,e,f依次通过栈S，若出栈的顺序为c,f,e,d,b,a，则栈S的容量至少应该为______ 。

2、10个相同的糖果，分给三个人，每个人至少要得一个。有种不同分法。

3、小数值1.5625的二进制表示是____。

101.1001

0.001

101.111

1.1001

4、某二叉树的先序遍历是12453，中序遍历是42513，那么其后续遍历是______。

45231

42351

12345

54321

5、主机甲和主机乙间已建立一个TCP连接，主机甲向主机乙发送了两个连续的TCP段，分别包含300字节和500字节的有效载荷，第一个段的序列号为200，主机乙正确接收到两个段后，发送给主机甲的确认序列号是。

500

700

800

1000

6、在N个乱序数字中查找第k大的数字，时间复杂度可以减小至。

O(N*logN)

O(N)

O(1)

O(N^2)

7、平均速度最快的排序算法是______。

Shell排序

快速排序

冒泡排序

插入排序

8、以下指令集架构属于复杂指令集架构的是____。

ARM

MIPS

SPARC

以上皆不是

9、有两个N*N的矩阵A和B，想要在PC上按矩阵乘法基本算法编程实现计算A*B。假设N较大，本机内存也很大，可以存下A、B和结果矩阵。那么，为了计算速度，A和B在内存中应该如何存储(按行存指先存储第一行，再第二行，直到最后一行;按列存指先存储第一列，再第二列，直到最后一列)

A按行存，B按行存。

A按行存，B按列存。

A按列存，B按行存。

A按列存，B按列存。

10、设一棵二叉树中有3个叶子节点，有8个度为1的节点，则该二叉树中总的节点数为______。

11、IP数据报头采用______字节序，在此字节序下从低地址到高地址01234的表示形式为______。

big_endian， 012 034 0 0

little_endian，034 012 0 0

big_endian， 0 0 012 034

little_endian，0 0 034 012

12、下列叙述中正确的是____。

循环队列有队头和队尾两个指针，因此，循环队列是非线性结构

在循环队列中，只需要队头指针就能反映队列中元素的动态变化情况

在循环队列中，只需要队尾指针就能反映队列中元素的动态变化情况

循环队列中元素的个数是由队头指针和队尾指针共同决定

13、将一个从大到小的数组，用以下排序方法排序成从小到大的，______最快。

插入排序

冒泡排序

快速排序

堆排序

14、在一个元素个数为N的数组里，找到升序排在N/5位置的元素的最优算法时间复杂度是______。

O(n)

O(n log n)

O(n(log n)2)

O(n 3/2)

15、已有变量定义和函数调用语句;编程-代码

int a=25;

print_value(a);

则下面函数的正确输出结果是______。

void print_value(int* x)

{

printf(%x\n,++*x);

}

16、在二进制数据中，小数点向右移一位，则数据______。

除以10

除以2

乘以2

乘以10

17、设集合A={1,2,3},A上的关系R={(1,1),(2,2),(2,3),(3,2),(3,3)}，则R不具备。

自反性

传递性

对称性

反对称性

18、下列叙述中正确的是。

循环队列有队头和队尾两个指针，因此，循环队列是非线性结构

在循环队列中，只需要队头指针就能反映队列中元素的动态变化情况

在循环队列中，只需要队尾指针就能反映队列中元素的动态变化情况

循环队列中元素的个数是由队头指针和队尾指针共同决定

19、假定x=500，求下面函数的返回值______ 。

int fun(int x)

{

int countx = 0;

while (x)

{

countx++;

x = x (x 1);

}

return countx;

｝

20、有一台带一个千兆网卡的服务器A，会把接收到的消息转发给另外两台带一个千兆网卡的服务器B和C，B和C上面的一个服务进程处理一条10K字节的消息需要2毫秒。如果在B和C上面各跑80个服务进程，在不考虑CPU负载和进程切换、内存占用、传输损耗和交互损耗的情况下，B和C服务器每秒一共大约可以处理______条10K字节的消息。

50000

60000

70000

80000

1、以下措施中，有可能改进分布式系统读写(IO)性能的有____。

网络从千兆网升级为万兆网

优化调度系统，尽量做到任务与数据相近(Locality)

数据预取机制

实现异步读写机制

2、无锁化编程有哪些常见方法?______ 。

针对计数器，可以使用原子加

只有一个生产者和一个消费者，那么就可以做到免锁访问环形缓冲区(Ring Buffer)

RCU(Read-Copy-Update)，新旧副本切换机制，对于旧副本可以采用延迟释放的做法

CAS(pare-and-Swap)，如无锁栈，无锁队列等待

3、程序

struct T {

char a;

int *d;

int b;

int c:16;

double e;

};

T *p;

在64位系统上以下描述正确的是。

sizeof(p) == 8

sizeof(*p) == 32

sizeof(p-a) == 1

sizeof(p-e) == 4

4、下面所述步骤中，是创建进程所必须的步骤是_____。

由调度程序为进程分配CPU

建立一个进程控制块

为进程分配内存

为进程分配文件描述符

5、有一种用左右值表示树形结构的存储格式，其中左右值有一些相当有用的场景，但是每个节点的左右值需要遍历树形结构计算出来。一个示例：

N[1,12]

|__N[2,7]

| |__N[3,4]

| |__N[5,6]

|__N[8,11]

|__N[9,10]

请完成遍历算法给节点赋左右值。

typedef struct node_t {

int left;

int right;

int n_children;

1 children;

} NODE;

int visit(NODE * node, int value) {

node-left = value;

int i = 0;

for(i=0; in_children; i++) {

}

return value;

}

int initLR(NODE* root) {

return visit(root, 1);

}

6、我们需要在淘宝的商品中提取一批优质商品(有特色、质量好、服务好等)，比如需要提取100万件，准确率要求是95%。我们有n个不同的方法可以提取这些商品，但每个方法在保持准确率满足要求的情况下都不能做到提取完整的100万件商品。因此可以把这n个方法得到的满足要求的商品集按如下方法合并起来：如果一个商品被k个方法选为优质商品，则将它的分数设为k;按照k从大到小排序选取前100万件。但实际中发现这样选出的100万件商品不符合精度要求，请解释可能的原因。还可以向哪个方向努力?

7、有个学校的15个女生一直3个一群上学。请问该如何安排才能使这些女生每周7天每天都和两个不同的同伴结伴同行呢?例如：用A到O来标识这些女孩，7天A正好和B到O这14个女孩各同行一次。而B到O每个人和都和其他14个女孩各同行一次。

8、长度为100的环形双向链表，A指针顺时针方向每次走3步，B指针逆时针方向每次走5步，每次走完判断是否相遇，初始状态B在A逆时针方向相距20，走100次，AB指针能相遇几次?

9、某招聘笔试共有120人参加，考试有6道题。1-6道分别有86人，88人，92人，76人，72人和70人答对，如果答对3道或3道以上通过笔试，问至少有多少人通过?

30、Wait()和sleep()的区别