google公司预选笔试题　

《google公司预选笔试题　》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、Google公司预选笔试题大家有兴趣看看吧，5/10sjtu的考卷。选择题3、8我蒙的，大牛给解答一下。1.单项选择题1.下面一段代码的输出是口voidfn(int*b){(*b)++;intmainO{inta=7;fn(a):cout2.定义inti,j，*p=i;那么下面哪条语句可以完成i=j的赋值[]=*p:B.*p=*j;=j;3.用二叉搜索树和哈希表存储相同的数据集，对于以下何种操作，二叉搜索树比哈希表It:br/>速度更快？[]A.检索B.插入C.删除D.更新E.排序1.包含N个几点和M条边的有向带权图G，边的权为正，以下操作中不可以在O(N+M)的

2、时间复杂度内完成的操作是：口A.求结点s到结点t之间的最短距离B.求距离结点s最近的结点C.已知起始结点，对图G中的结点进行拓扑排序D.求图G的最大强连通子图2.有如下递归函数f(n)，其时间复杂度为口intf(intn){if(n—0)returnO;if(n==l)returnl;return(5*f(n-1)-6*f(n-2)):(n)B.O(rf2)C.O(if3)D.0(2"n)3.下面所述步骤中，哪一个不是创建经常所必需有的口A.由调度程序为进程分配CPUB.建立一个进程控制块C.为进程分配内存D.将进程控制块链入就绪队列4.在多进程的系统中，为了保证

3、公区变量的完整性，各进程应互斥进入临界区。所谓临界区是[]A.—个缓冲区B.—个数据区C.一个同步机构D.—段程1.能产生满足如下条件语言的正则表达式是：1.每一个a后至少紧跟两个c;2.每一个b后至少紧跟一个c[]A.(acc

4、be

5、c)*B.(acc

6、bc)*C.(ac

7、bc)*D.不是正则语言2.以下哪项不是RPC(远程过程调用)的特点□A.速度快B.降低系统耦合度C.可以实现异构系统间的协作3.有三个桶，容量分别是3升，5升，7升，你只能进行下面的操作：把一个桶中所有的水倒掉；把一个桶A中的水倒入桶B，直到桶A空了或者桶B满了；假设一开始容量为3升和5升的

8、桶是满的，7升的桶是空的，希望通过一系列操作使3个桶中任意一个中正好有4升水，那么至少需要□次操作。D.不可能1.程序设计与算法实现如下编码算法，对于重复2-9次数的字符，用两个数字表示，即NX(其中N为重复的次数，X为重复的字符，下同），超过九个则先输出9X，然后处理剩下的字符。对于连续的不重复的字符，则两边加1来封字符串。如果被封的字符串其中有数字为1，则用1来转义。示例:AAAAAABCCCC-〉6A1B14C,12344->11123124。。。（下面的框架是用C++语言写的。你可以用你熟悉的语言。）voidencode（constchar氺text，ch

9、aradest）text为需要编码的字符串，dest表示编码输出的目标空间，而空间足够大给定一颗有n个结点的二叉树。求它的所有结点数为m的连通子图数目。m算法的时间复杂度，解释算法即可，不必写代码。