google笔试题集锦(编辑修改稿)

google笔试题集锦(编辑修改稿)内容摘要：

(n 2). @param[out] right Value of T(n 3). @return Value of T(n 1). */ int find_trib(int n, int amp。 mid, int amp。 right) { if (3 == n) { mid = 1。 right = 1。 return 2。 } else { int temp。 mid = find_trib(n 1, right, temp)。 return mid right temp。 } } /** Find value of T(n). @param[in] The n in T(n). @return Value of T(n). @note T(n) = T(n 1) T(n 2) T(n 3) (n 2) T(0) = T(1) = 1, T(2) = 2. */ int tribonaci(int n) { if (n 0) { // Undefined feature. return 0。 } if (0 == n || 1 == n) { return 1。 } if (2 == n) { return 2。 } int mid, right。 int left = find_trib(n, mid, right)。 return left mid right。 } 啊啊，对了，答卷的时候我可没心情写注释 ……刚才到 2020上测试了一下，貌似没有啥问题。 唉，看来我多少还是懂一点算法的 …… 第三个的题目： 在一个无向 图中，寻找是否有一条距离为 K的路径，描述算法即可，不用实现，分析算法的时间和空间复杂度，尽量优化算法。 05 年 Google 笔试题 要笔试考题如下，其他题目是基础题，就不贴出了： 假设在 n 进制下，下面的等式成立， n 值是（） 567*456=150216 a、 9 b、 10 c、 12 d、 18 文法 G:SuvSvu|w 所识别的语言是：（） a、 uvw*vu b、（ uvwvu） * c、 uv(uv)*wvu(vu)* d、 (uv)*w(vu)* 如下程序段输出是：（） char str[][10]={Hello,Google}。 char *p=str[0]。 countstrlen(p 10)。 a、 0 b、 5 c、 6 d、 10 t=0 while(x!=1){ t=t 1。 if(xamp。 1==0) x=x/2。 else x=3*x 1。 } counttend1。 当 n=11 时，输出：（） a、 12 b、 13 c、 14 d、 15 写一段程序判定一个有向图 G 中节点 w 是否从节点 v 可达。 （假如 G 中存在一条 从 v 至 w 的路径就说节点 w 是从 v 可达的）。 以下算法是用 C 写成的，在 bool Reachable 函数中，你可以写出自己的算法。 class Graph{ public: int NumberOfNodes()。 //返回节点的总数 bool HasEdge(int u,int v)。 //u,v 是节点个数，从零开始依次递增，当有一条从 u 到 v 的边时，返回 true }； bool Reachable(Graphamp。 G, int v, int w){ //请写入你的算法 } 给定一棵所有边的长度均为整数的树，现要求延 长其中某些边，使得从根到任意节点的路径长度相等。 问满足要求的树的边长度之和最小是多少 ?请写出你的算法，并分析时间复杂度。 ===================================================================== Google 笔试 题 两个二进制数的异或结果 递归函数最终会结束，那么这个函数一定（不定项选择）： 1. 使用了局部变量 2. 有一个分支不调用自身 3. 使用了全局变量或者使用了一个或多个参数 , O l+ f3 i8 v* a$ m , S0 d, ~39。 B, \ , { * L以下函数的结果。 2 ^* s。 z/ O$ a$ z R+ ] int cal(int x) 1 r 9 P4 Lamp。 ?3 k( M8 P+ f $ q{ if(x==0) . s$ z0 I P! T1 O 39。 W! @ return 0。 * z: T8 } 7 d+ R9 pelse return x+cal(x1)。 } 8 G H( }$ I( a: R d3 [。 } W 以下程序的结果。 void foo(int*a, int* b) ( \ 4 ^. o p, o7 c2 y9 M6 c0 S{ *a = *a+*b。 *b = *a*b。 *a = *a*b。 3 s/ J: i9 L0 Y: y} 6 { 6 d/ } D3 f g2 v8 c) v void main() { amp。 t amp。 ~* ] amp。 i1 a! a5 Kint a=1, b=2, c=3。 7 o U h1 o5 i, Efoo(amp。 a,amp。 b)。 foo(amp。 b,amp。 c)。 foo(amp。 c,amp。 a)。 printf(%d, %d, %d, a,b,c)。 } 下面哪项不是链表优于数组的特点。 1. 方便删除 2. 方便插入 3. 长度可变 4. 存储空间小 T(n) = 25T(n/5)+n^2 的时间复杂度。 n 个顶点， m条边的全连通图，至少去掉几条边才能构成一棵树。 正则表达式 (01|10|1001|0110)*与下列哪个 表达式一样。 4 V3 A3 w6 | H. q。 G % q3 E a5 D, j {5 D/ K 如何减少换页错误。 3 C I : g/ r6 ^1. 进程倾向于占用 CPU 2. 访问局部性（ locality of reference）满足进程要求 ) 3. 进程倾向于占用 I/O （ shortest remaining time）的调度机制 5. 减少页大小 ! B$ a5 } ! @9 V. C9 y 实现两个 N*N 矩阵的乘法，矩阵由一维数组表示 8 [7 M$ ^ { + v/ a3 ^6 } Y7 q/ D, \$ I39。 C1 z1找到单向链表中间那个元素，如果有两个则取前面一个 2 t1 v4 U, h0 b3 D. d 1长度为 n 的整数数组，找出其中任意 (n1)个乘积最大的那一组，只能用乘法，不可以用除法。 要求对算法的时间复杂度和空间复杂度作出分析，不要求写程序。 google 浙大招聘笔试题（转） 一、单选 80x8。