2014年阿里校招笔试题目
17.袋中有红球,黄球,白球各一个,每次任意取一个放回,如此连续3次,则下列事件中概率是8/9的是:
A: 颜色全相同 B:颜色全不相同C:颜色不完全相同 D:颜色无红色
C,解释:(1)颜色全相同:C(1,3) / 27 = 1 / 9(2)颜色全不相同:3 * 2 * 1 / 27 = 2 / 9 (4)颜色无红色: 2 * 2 * 2 / 27 = 8 / 27 (3)颜色不完全相同 = 1 - P(颜色完全相同) = 1 - 1 / 9 = 8 / 9
18.一个洗牌程序的功能是将n张牌的顺序打乱,以下关于洗牌程序的功能定义说法最恰当的是:
A: 每张牌出现在n个位置上的概率相等
B: 每张牌出现在n个位置上的概率独立
C: 任何连续位置上的两张牌的内容独立
D: n张牌的任何两个不同排列出现的概率相等
D,解释:乐乐说选D,其实我觉得A也挺对的,这到题目我写了一个测试洗牌的程序,但是自己测试问题很大,怀疑是随机数获取的问题,求大家帮忙指点:
19.用两种颜色去染排成一个圈的6个棋子,如果通过旋转得到则只算一种,一共有多少种染色:
A: 10 B:11 C:14: D:15
不会,这么多概率题目啊,我去
20.递归式的先序遍历一个n节点,深度为d的二叉树,则需要栈空间的大小为:
A: O(n) B:O(d) C:O(logn) D:(nlogn)
B,解释:需要考虑最坏的情况,A和B我不确定啊,蛋疼
二、多选题
21.两个线程运行在双核机器上,每个线程主线程如下,线程1:x=1;r1=y;线程2:y=1;r2=x;
X和y是全局变量,初始为0。以下哪一个是r1和r2的可能值:
A: r1=1,r2=1
B: r1=1,r2=0
C:r1=0,r2=0
D:r1=0,r2=1
ABD,解释:r1和r2不可能同时为0,当一个有赋值时,必然完成了对另一个x或y的赋值
22.关于Linux系统的负载,以下表述正确的是:
A: 通过就绪和运行的进程数来反映
B: 通过TOP命令查看
C: 通过uptime查看
D: Load:2.5,1.3,1.1表示系统的负载压力在逐渐变小
BC,解释:ALINUX系统还需要包含处于waitting状态的进程 D说明系统负载变大,load average分别是系统1分钟,5分钟,15分钟的平均负载
23.关于排序算法的以下说法,错误的是:
A: 快速排序的平均时间复杂度O(nlogn),最坏O(N^2)
B:堆排序平均时间复杂度O(nlogn),最坏O(nlogn)
C:冒泡排序平均时间复杂度O(n^2),最坏O(n^2)
D:归并排序的平均时间复杂度O(nlogn),最坏O(n^2)
D,解释:归并排序最坏的时间复杂度也是O(nlogn)
24.假设函数rand_k会随机返回一个【1,k】之间的随机数(k>=2),并且每个证书出现的概率相等。目前有rand_7,通过调用rand_7()和四则运算符,并适当增加逻辑判断和循环控制逻辑,下列函数可以实现的有:
A:rand_3 B:rand_21 C:rand_23 D:rand_49
ABCD
填空和问答
25.某二叉树的前序遍历-+a*b-cd/ef,后续遍历abcd-*+ef/-,问其中序遍历序列为
扯淡啊,根据前序和后序没法唯一确定中序好不好,我擦
26.某缓存系统采用LRU,缓存容量为4,并且初始为空,那么在顺序访问以下数据项的时候:1,5,1,3,5,2,4,1,2
出现缓存直接命中的次数为:(),最后缓存即将淘汰的是()
3,5
27.两个较长的单链表a和b,为了找出节点node满足node in a并且node in b。请设计空间使用尽量小的算法
求两个链表的公共节点题目
28.存储数据量超出单节点数据管理能力的时候,可以采用的办法有数据库sharding的解决方案,也就是按照一定的规律把数据分散存储在多个数据管理节点N中(节点编号为0,1,2,,,,N-1)。假设存储的数据时a 请完成为数据a计算存储节点的程序
#define N 5
int hash(int element){
return element*2654435761;
}
int shardingIndex(int a){
int p = hash(a);
_________________________; //这里是空格
return p;
}
p = p % N;解释:感觉没啥好解释的,基本的散列函数
29.宿舍内5个同学一起玩对战游戏,每场比赛有一些人作为红方,一些人作为蓝方,请问至少需要多少场比赛,才能使得任意两个人之间有一场红方对蓝方和蓝方对红方的比赛
4,被n多人指点之后的结果