Google谷歌员工笔试试题及答案

google浙大招聘笔试题
一、单选
1、80x86 中，十进制数-3 用 16 位二进制数表示为？
2、假定符号-、*、$分别代表减法、乘法和指数运算，且
1)三个运算符优先级顺序是：-最高，*其次，$最低；
2)运算符运算时为左结合。请计算 3-2*4$1*2$3 的值：
(A)4096，(B)-61，(C)64，(D)-80，(E)512
3、下列伪代码中，参数是引用传递，结果是？
calc(double p, double q, double r)
{q=q-1.0;r=r p}
main(){
double a = 2.5, b = 9.0;
calc(b-a, a, a);
print(a);
}
(A)1.5 (B)2.5 (C)10.5 (D)8 (E)6.5
4、求输出结果：
int foo(int x, int y){
if(x <=0 || y <= 0) return 1;
return 3 * foo(x - 1, y / 2);
}
printf("%d\n", foo(3, 5));
(A)81 (B)27 (C)9 (D)3 (E)1

5、下列哪个数据结构在优先队列中被最广泛使用？
(A)堆 (B)数组 (C)双向链表 (D)图 (E)向量
6、以下算法描述了一个在 n 国元素的双向链表中找到第 k 个元素的
方法（k >= 1 且 k <= n） ：
如果 k <= n - k，从链表开始往前进 k-1 个元素。
否则，从终点出发，往回走 n - k 个元素。
这个算法的时间代价是？
(A)θ(nlogn) (B)θ(max{k, n - k}) (C)θ(k (n - k))
(D)θ(max{k, k - n}) (E)θ(min{k, n - k})
7、有一个由 10 个顶点组成的图，每个顶点有 6 个度，那么这个图有几条边？
(A)60 (B)30 (C)20 (D)80 (E)90
8、正则表达式 L = x*(x|yx )。下列哪个字符串不符号 L
(A)x (B)xyxyx (C)xyx (D)yxx (E)yx
9、为读取一块数据而准备磁盘驱动器的总时间包括
(A)等待时间 (B)寻道时间 (C)传输时间 (D)等待时间加寻道时间
(E)等待时间加寻道时间加传输时间
二、算法
1、打印出一个二叉树的内容。
2、在一个字符串中找到第一个只出现一次的字符。如 abaccdeff，输出 b。
3、给定一个长度为 N 的整数数组（元素有正有负） ，求所有元素之和
最大的一个子数组。分析算法时空复杂度。不必写代码。
Google笔试题，共享中 -2008.11
Google 笔试是没有门槛的。这样说是因为 Google 根本没有限制笔试的人数，开了 N 个教室，让 N 多人参加……不过笔试本身却有门槛，看了题目就知道。
本来想上午写写的，但是，嗯，出于攒人品的目的，还是等到现在才写——现在，面试通知已经发过，很显然我又被无视了……OK，那也不错，我也没怎么准备这些东西呢，倒不是说我不重视，而是事情太多……唔，多少算是一种经验了。
回来说说昨天的笔试。题目的量并不大，除了几个单选题，剩下就是三个编程或算法题。单选就不说了，考得比较基础，涉及 C 语言常识、数据结构、文法、操作系统，主要说说大题。
大题虽然题型不一，但都有一个重要特点：考递归。精确点说，我每一题都用到了递归。
第一个的题目（嗯，记的不是很完整） ： 在一棵（排序？）二叉树中搜索指定值，数据结构定义为（唉唉，数据结构的具体名字都不记得了，my god） ： struct Node
{
Node * lnext;
Node * rnext;
int value;
};
函数定义为（情况同上，啥都记不清了） ：
Node * search(Node * root, int value)
{
}
实现这个 search 函数。
用递归，经典的树的遍历，pass 先。
第二个的题目：
计算 Tribonaci 队列（嗯，九成九记错了那个单词……） ，规则是 T(n) = T(n - 1) T(n - 2) T(n -3)，其中
T(0) = T(1) = 1，T(2) = 2。
函数定义：
int Tribonaci(int n) {
}
备注，不考虑证整数溢出，尽可能优化算法。
这一题我一看就知道要考什么，很显然的递归定义，但也是很显然的，这里所谓的优化是指不要重复计算。
简单的说，在计算 T(n)的时候要用到 T(n - 1)、T(n - 2)和 T(n - 3)的结果，在计算 T(n - 1)的时候也要用到 T(n
- 2)和 T(n - 3)的结果，所以在各项计算的时候必须把以前计算的结果记录下来，去掉重复计算。这里用到的一点
小技巧就是要新写一个函数用来做这种事情，嗯，看看我写的代码吧！
14 /**
Get the value of T(n - 1), and retrieve the result of
T(n - 2) and T(n - 3).
@param[in] n The n in T(n).
@param[out] mid Value of T(n - 2).
@param[out] right Value of T(n - 3).
@return Value of T(n - 1).
*/
int find_trib(int n, int