2007年Google笔试题

2007 年 Google 招聘考试笔试题 1、 两个二进制数的异或结果 2、 递归函数最终会结束，那么这个函数一定（不定项选择）： 1). 使用了局部变量 2). 有一个分支不调用自身 3). 使用了全局变量或者使用了一个或多个参数 3、以下函数的结果？ int cal(int x) { if(x==0) return 0; else return x+cal(x-1); } 4、 以下程序的结果？ void foo(int*a, int* b) { *a = *a+*b; *b = *a-*b; *a = *a-*b; } void main() { int a=1, b=2, c=3; foo(&a,&b); foo(&b,&c); foo(&c,&a); printf("%d, %d, %d", a,b,c); }1–3-2 5、下面哪项不是链表优于数组的特点？ 1). 方便删除 2). 方便插入 3). 长度可变 4). 存储空间小 6、T(n) = 25T(n/5)+n^2 的时间复杂度？ 7、n 个顶点，m 条边的全连通图，至少去掉几条边才能构成一棵树？ 8、正则表达式(01|10|1001|0110)*与下列哪个表达式一样？ 1.(0|1)* 2.(01|01)* 3.(01|10)* 4.(11|01)* 5.(01|1)* 9、如何减少换页错误？ 1). 进程倾向于占用 CPU 2). 访问局部性（locality of reference）满足进程要求 3). 进程倾向于占用 I/O 4).使用基于最短剩余时间（shortest remaining time）的 调度机制 5). 减少页大小 10、实现两个 N*N 矩阵的乘法，矩阵由一维数组表示 11、找到单向链表中间那个元素，如果有两个则取前面一个 12、长度为 n 的整数数组，找出其中任意(n-1)个乘积最大的那一组，只能用乘法，不可 以用除法。要求对算法的时间复杂度和空间复杂度作出分析，不要求写程序