1.平均速度最快的排序算法是______。
Shell排序
快速排序
冒泡排序
插入排序
2014-03-29 18:36:02
2.某服务进程的QPS(没秒处理的请求个数)较低，在空闲时间RT(响应时间)比较合理。在压力下CPU占用率20%左右。那么可能存在的问题是______。
该进程的某个处理过程的代码需要提高速度
该进程依赖的服务可能存在性能瓶颈
该进程需要增加线程数
该进程可能有一个锁的粒度太大
2014-03-29 18:36:16
3.无锁化编程有哪些常见方法?______ 。
针对计数器，可以使用原子加
只有一个生产者和一个消费者，那么就可以做到免锁访问环形缓冲区(Ring Buffer)
RCU(Read-Copy-Update)，新旧副本切换机制，对于旧副本可以采用延迟释放的做法
CAS(Compare-and-Swap)，如无锁栈，无锁队列等待
2014-03-29 18:37:00
2014-03-29 18:37:00
4.假设栈S和队列Q的初始状态为空，元素a、b、c、d、e、f依次通过S和Q，即每一个元素必须先进栈，之后再出栈进入队列。若这6个元素出队的顺序是b、d、c、f、e、a，则栈S的容量至少应该为______。
3
4
5
6
2014-03-29 18:37:11
5.设栈S初始状态为空。元素a,b,c,d,e,f依次通过栈S，若出栈的顺序为c,f,e,d,b,a，则栈S的容量至少应该为______ 。
3
4
5
6
2014-03-29 18:37:25
6.一个单向链表，头指针和尾指针分别为p，q，以下_____项操作的复杂度受队列长度的影响?
删除头部元素
删除尾部元素
头部元素之前插入一个元素
尾部元素之后插入一个元素
2014-03-29 18:37:33
7.集合A={1,2,3},A上的关系R={(1,1),(2,2),(2,3),(3,2),(3,3)}，则R不具备 。
自反性
传递性
对称性
反对称性
2014-03-29 18:37:44
8.件设备的寿命通常符合指数分布，即无记忆性，也就是如果一个设备当前正常工作，那么剩余预期寿命和已经工作的时间无关。假定某种设备1000台，在一年之内坏掉500台(无维修)，那么在有维修(设备坏掉立刻换新的)的情况下，一年之内需要换______台该设备。
400台
500台
753台
1000台
2014-03-29 18:37:53
9.一个int64_t类型的变量转换成一个double类型的变量，可能存在的问题是______。
精度损失
大小溢出
转换失败
无以上问题
2014-03-29 18:38:04
10.标准unix环境下，一个拥有3个线程的进程调用fork产生的子进程中，其线程个数为______。
1
2
3
4
2014-03-29 18:38:15
11.你有一个3X3X3的立方体。你现在在正面左上的顶点，需要移动到对角线的背面右下的顶点中。每次移动不限距离，但只能从前至后、从左至右、从上至下运动，即不允许斜向或后退。有______种方法。
9
90
180
1680
2014-03-29 18:38:28
12 两个N*N的矩阵A和B，想要在PC上按矩阵乘法基本算法编程实现计算A*B。假设N较大，本机内存也很大，可以存下A、B和结果矩阵。那么，为了计算速度，A和B在内存中应该采用的存储方法是______。(按行存指先存储第一行，再第二行，直到最后一行;按列存指先存储第一列，再第二列，直到最后一列)
A按行存，B按行存
A按行存，B按列存
A按列存，B按行存
A按列存，B按列存
2014-03-29 18:38:37
13.知一个递归算法的算法复杂度计算公式为T(n)=T(n/2)+n,则T(n)的算法复杂度为____。
O(n)
O(logn) O(n2)
O(nlogn)
2014-03-29 18:38:53
14.虑如下程序存在的问题是__________。
class A {
public:
A(B* b) : _b(b) {}
~A() { b;}
private:
B* _b;
};
int main()
{
B b;
A(&b);
return 0;
}
double free 重复释放
stack free 堆栈释放
memory leak 内存泄露
无以上问题
2014-03-29 18:39:01
2014-03-29 18:39:01
15.21、26、65、99、10、35、18、77分成若干组，要求每组中任意两个数都互质，至少要分成______组。
3
4
2
5
2014-03-29 18:39:09
16.设某虚拟存储系统的物理内存只有3个页(page)，当进程A访问虚拟页的序列依次是1, 2, 3, 4, 2, 7, 5, 3, 5, 7, 4, 3, 当页面淘汰算法为先进先出(FIFO)且内存在刚开始为空，那进程A遭遇的页面失效次数为_____。
7次
8次
9次
10次
2014-03-29 18:39:18
17.于一个二叉查找树，以下遍历方式中，______可以得到一个递增数列。 先序遍历
中序遍历
后序遍历
层次遍历
2014-03-29 18:39:25
18. 两个N*N的矩阵A和B，想要在PC上按矩阵乘法基本算法编程实现计算A*B。假设N较大，本机内存也很大，可以存下A、B和结果矩阵。那么，为了计算速度，A和B在内存中应该如何存储(按行存指先存储第一行，再第二行，直到最后一行;按列存指先存储第一列，再第二列，直到最后一列) A按行存，B按行存。
A按行存，B按列存。
A按列存，B按行存。
A按列存，B按列存。
2014-03-29 18:39:31
19.个容器类数据结构，读写平均，使用锁机制保证线程安全。如果要综合提高该数据结构的访问性能，最好的办法是______。
只对写操作加锁，不对读操作加锁
读操作不加锁，采用copyOnWrite的方式实现写操作
分区段加锁
无法做到
2014-03-29 18:39:40
20.设炮弹发射3次，射中目标区域的概率是0.95，那么，发射1次射中目标区域的概率约是 。
0.32
0.63 0.50
0.73
2014-03-29 18:39:47
21正则表达式 2[0-4]d|25[0-5]|[01]?dd?$ 能匹配以下哪个表达式 ?
255
256
2
25a
2014-03-29 18:39:54
22.叉树的广度优先遍历序列为A B C D E F G H I，已知A是C的父结点，D 是G 的父结点，F 是I 的父结点，树中所有结点的最大深度为3(根结点深度设为0)，可知E的父结点可能是 _____。 A
B
C
D
F
2014-03-29 18:40:02
23.服务进程的QPS(没秒处理的请求个数)较低，在空闲时间RT(响应时间)比较合理。在压力下CPU占用率20%左右。那么可能存在的问题是______。
该进程的某个处理过程的代码需要提高速度
该进程依赖的服务可能存在性能瓶颈
该进程需要增加线程数
该进程可能有一个锁的粒度太大
2014-03-29 18:40:09
24.无锁化编程有哪些常见方法?______ 。
针对计数器，可以使用原子加
只有一个生产者和一个消费者，那么就可以做到免锁访问环形缓冲区(Ring Buffer)
RCU(Read-Copy-Update)，新旧副本切换机制，对于旧副本可以采用延迟释放的做法
CAS(Compare-and-Swap)，如无锁栈，无锁队列等待
2014-03-29 19:18:33
25.有个学校的15个女生一直3个一群上学。请问该如何安排才能使这些女生每周7天每天都和两个不同的同伴结伴同行呢?例如：用A到O来标识这些女孩，7天A正好和B到O这14个女孩各同行一次。而B到O每个人和都和其他14个女孩各同行一次。
26.含有n个关键字的`B树上查找时，从根节点到关键字节点的路径上涉及的节点数不超过__________。
2014-03-29 19:18:59
27.下是一段基于链表的栈的实现代码，请补充空白处的代码。
class Stack {
Node top;
Object pop() {
if (top != null) {
Object item = ;
(1) top=;
return item;
}
return null;
}
void push(Object item) {
Node t = new Node(item);
(2)
top = t;
}
}
class Node{
Node next;
Object data;
public Node(Object item){
data = item;
}
}
(1) top=
(2)=top
2014-03-29 19:19:09
选做题(注：阿里有大量JAVA研发工程师需求;选作以下题目有机会增加该方向面试机会)
天猫双十一有个积分换墨盒的活动，总共有50万台天猫魔盒(box)，每个用户(user)可以用99个天猫积分(point)兑换一台魔盒，且每人限换一台。 请设计一套java接口并实现下单(order)逻辑。
参考(但不局限于)下面的下单逻辑：
1、创建订单
2、扣减用户积分
3、扣减魔盒库存
4、下单成功
同时请回答：
1、数据库表结构如何设计，有哪些表，分别有什么作用?
2、下单过程中哪些地方可能成为瓶颈?如何解决或改善?
3、是否会用到数据库事务，哪些地方会用到?如果不用数据库事务，如何保证数据的一致性?
java接口那个你看书上的定义，安要求定义函数
函数明用英文就可以了。不过接口这个不一定对
数据表格三张，魔盒表，用户表，和魔盒与用户关系表
瓶颈会存在与对各个表格存储过程中。比如魔盒数量修改，用户分数修改，用户兑换魔盒记录等
改善的一个方法就是用户创建顶点时先读取用户和魔盒关系表，如果有记录，则不必读取后两张表，尽量节约时间爱你
尽量节约时间
其他方法也可以考虑，可以在表格设计和处理顺序上考虑下
需要数据库事物，只要用在数据表格的数据修改中，比如修改积分，魔盒数量等，用数据库事物是做安全的保证数据一致性的方法。不用其实也可以，需要在代码中体现。但不利于以后的维护等
基本是些意思吗，具体的记不清了
2014-03-29 19:19:23
29.长度为100的环形双向链表，A指针顺时针方向每次走3步，B指针逆时针方向每次走5步，每次走完判断是否相遇，初始状态B在A逆时针方向相距20，走100次，AB指针能相遇几次?
30.下C语言程序片段用于估测CPU的cache参数(容量，延迟等)： #define MAX_SIZE (64*1024*1024L)
#define STRIDE (128)
#define STEP (4096)
#define REPEAT (1000*1000L)
double t[MAX_SIZE/STEP];
int d[MAX_SIZE/sizeof(int)];
t[0] = 0;
long foot_print;
for (foot_print = STEP; foot_print < MAX_SIZE; foot_print += STEP) {
long i;
for (i = 0; i < foot_print; i += STRIDE)
{
long next = (i + STRIDE) % foot_print;
d[i/sizeof(int)] = next/sizeof(int);
}
int m = 0;
double t1 = get_time_second();
for (i = 0; i < REPEAT; ++i)
{
; // **
}
double t2 = get_time_second();
t[foot_print/STEP] = t2 t1;
printf(“%dt”, x); // avoid compiler optimization
}
// record t[] ?
假设CPU具有L1/L2/L3三层cache，cache line长度小于128B，硬件预取已经关闭。
请补全标记**的行，完成其功能;