主题：据说google今年在北大清华招聘出了这样一道题 -- SkyWalkerJ

1．

哪个表达式不能用这个匹配：a(bc)*d?

A.

ad

B. abcd

C.abc

D.abccd

2．

INTEL X86 CPU中，哪种运算最慢：

A．

加

B. 减

C.乘

D.除

3．

下面程序的输出：

Fun(){

bool first =true;

int sum = 0;

int cur;

for(unsignedshort i=65535; i>=0; --i){

if(first){

cur=65536;

sum+=cur%3;

first=false;

}else{

sum+=--cur%3;

if(cur<=0)

printf(“%d,%d”, sum, i)break;

}

}

}

A.

65535, 0

B.65536,1

C.65536,65535

D.65536,0

4．

有19本书，分别编号为1-19，从中选出5本，要求任意两本不相邻，一共有多少种选法？

A． 2002

B. 3003

C.11628

D.360360

5．

一套房子200万，每年价格上涨10% ，一个工程师每年固定收入40万，假定他不贷款，不涨工资，问几年能买的起房子

A．5

B.7

C.8

D.永远也买不起

6．

有N个叶节点的满二叉树节点，其共有多少个节点？

A．2N-1

B.2N

C.N-1

D.N

7．

以下哪个排序算法的最坏时间复杂度是O(nlogn)?

A.

归并排序

B. 快速排序

C. 冒泡排序

D.插入排序

8．

两个排好序的数组大小为N,M，合并成一个有序数组，则最小比较次数：

A.min(N,M)

B.M+N-1

C.N+M

D.max(N,M)

9．

关于TLB和Cache，下面哪个说法是错的

A．

TLB和cache中存的数据不同

B．

TLB miss后，可能在Cache中直接找到页表内容

C．

TLB miss会造成程序执行出错，但是cachemiss不会

D．

这两者的命中率都与访存模式有关

10．

对于数据库，以下哪种说法是错的

A．

每个表都必须有主键

B．

跨表查询很慢

C．

数据库不支持多个客户端同时对一个表进行写操作

D．

多维索引可以用KD树

编程题（前两个写程序，最后一个写思路或者伪代码）

1.

用一个数组A[N+1]存储一个多项式：a0+a1x+a2x2+….anxn，用一个程序计算这个多项式的值。

函数原型：double eval(double x, double *A)

2.

有n个队伍，n=2^k。有一个二维数组，winner[j]代表第i队和第j队的比赛结果中胜出队伍的编号，winner[j]和winner[j]相同。另有一个代表单淘汰赛签位的一维数组order[0]…[n-1]，order代表i签位上的队伍编号。现在要求输出一个最终队伍排名，如果在同一轮中淘汰的认为排名相同，并且时间和空间复杂度尽可能低

如n=4时有一个例子（例子不记得了）

函数原型：void fun(int **winner, int *order, int *result)

0<n<=1000

3.

KOF里的连招。连招表达式S->T，比如ABC->C,ABD->E, BDE->F, DEF->G，那么连招输出就可以是ABD->E->F>G。现在要求一个程序，能够输出最大连招的长度

判卷准则：

1．

前10个小题答对了至少6个才会判后面的大题

2．

大题最低分数为20（每题10分），需满足其最低分数线。