google笔试.docx

google笔试
Google
写出这样一个函数 ,输入一个 n, 输出从1到这个数字之间的出现的1的个数,比如f(13)等于6; f(9)等于1; 网上有很多这道题的解法，大多采用穷举法。这把这个算法题变成了程序设计，这道题， 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;
}
　　啊啊，对了，答卷的时候我可没心情写注释…… 2003上测试了一下，貌似没有啥问题。唉，看来我多少还是懂一点算法的……
第三个的题目：
　　在一个无向图中，寻找是否有一条距离为K的路径，描述算法即可，不用实现，分析算法的时间和空间复杂度，尽量优化算法。
 
 
 
05年Google笔试题
要笔试考题如下，其他题目是基础题，就不贴出了：
1、假设在n进制下，下面的等式成立，n值是（）
567*456=150216
a、 9 b、 10 c、 12 d、 18
2、文法G:S->uvSvu|w所识别的语言是：（）
a、uvw*vu b、（uvwvu）* c、uv(uv)*wvu(vu)* d、(uv)*w(vu)*
3、如下程序段输出是：（）
char str[][10]={"Hello","Google"};
char *p=str[0];
count<<strlen(p 10);
a、0 b、5 c、6 d、10
4、cnt=0
　　while(x!=1){
　　　　cnt=cnt 1;
　　　　if(x&1==0)
　　　　　　x=x/2;
　　　　else
　　x=3*x 1;
}
count<<cnt<<end1;
当n=11时，输出：（）
a、12 b、13 c、14 d、15
5、写一段程序判定一个有向图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(Graph&G, int v, int w){
//请写入你的算法
}
6、给定一棵所有边的长度均为整数的树，现要求延长其中某些边，使得从根到任意节点的路径长度相等。问满足要求的树的边长度之和最小是多少?请写出你的算法，并分析时间复杂度。
=====================================================================
Google笔试题
1、 两个二进制数的异或结果
2、 递归函数最终会结束，那么这个函数一定（不定项选择）：
1.  使用了局部变量
2. 有一个分支不调用自身
3.  使用了全局变量或者使用了一个或多个参数, O- l+ f3 i8 v* a$ m
, S0 d, ~' B, \, {* L
3、以下函数的结果？2 ^* s; z/ O$ a$ z" R+ ]
int cal(int x) 1 r9 P4 L& ?3 k( M8 P+ f$ q
{
if(x==0) . s$ z0 I  P! T1 O' W! @
return 0;* z: T8 }7 d+ R9 p
else
return x+cal(x-1);
}
8 G  H( }$ I( a: R- d3 [; }# W
4、 以下程序的结果？
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()
{ & t& ~* ]& i1 a! a5 K
int a=1, b=2, c=3;7 o- U- h1 o5 i, E
foo(&a,&b);
foo(&b,&c);
foo(&c,&a);
printf(