资源描述：
《google 笔试题汇总 (转载)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、google笔试题汇总(转载).txt跌倒了，爬起来再哭~~~低调！才是最牛B的炫耀！！不吃饱哪有力气减肥啊？真不好意思，让您贱笑了。我能抵抗一切，除了诱惑……老子不但有车，还是自行的……google笔试题汇总(转载)2008-10-071726(分类默认分类)一、单选1、80x86中，十进制数-3用16位二进制数表示为？00100002、假定符号-、、$分别代表减法、乘法和指数运算，且1)三个运算符优先级顺序是：-最高，其次，$最低；2)运算符运算时为左结合。请计算3-24$12$3的值：(A)4096，(B)-61，(C)64，(D)-80，(E)512算符3、下列伪代码中，参数是
2、引用传递，结果是？calc(doublep,doubleq,doubler){q=q-1.0;r=r+p}main(){ doublea=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.54、求输出结果：intfoo(intx,inty){ if(x=0y=0)return1; return3foo(x-1,y2);}printf(%dn,foo(3,5));(A)81(B)27(C)9(D)3(E)15、下列哪个数据结构在优先队列中被最广泛使用？a(A)堆(B)数组(C)双向链表(D)图(E)向
3、量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个度，那么这个图有几条边？30(A)60(B)30(C)20(D)80(E)908、正则表达式L=x(xyx+)。下列哪个字符串不符合Lb(A)x(B)xyxyx(C)xyx(D)yxx(E)yx9、为读取一块数
4、据而准备磁盘驱动器的总时间包括e(A)等待时间(B)寻道时间(C)传输时间(D)等待时间加寻道时间(E)等待时间加寻道时间加传输时间二、算法1、打印出一个二叉树的内容。2、在一个字符串中找到第一个只出现一次的字符。如abaccdeff，输出b。3、给定一个长度为N的整数数组（元素有正有负），求所有元素之和，最大的一个子数组。分析算法时空复杂度。不必写代码。附上动态规划做法的答案最大子序列问题：给定一整数序列A1，A2，...An（可能有负数），求A1~An的一个子序列Ai~Aj，使得Ai到Aj的和最大例如：整数序列-2,11,-4,13,-5,2,-5,-3,12,-9的最大子序列的和
5、为21。对于这个问题，最简单也是最容易想到的那就是穷举所有子序列的方法。利用三重循环，依次求出所有子序列的和然后取最大的那个。当然算法复杂度会达到O(n^3)。显然这种方法不是最优的，下面给出一个算法复杂度为O(n)的线性算法实现，算法的来源于ProgrammingPearls一书。在给出线性算法之前，先来看一个对穷举算法进行优化的算法，它的算法复杂度为O(n^2)。其实这个算法只是对对穷举算法稍微做了一些修改：其实子序列的和我们并不需要每次都重新计算一遍。假设Sum(i,j)是A[i]...A[j]的和，那么Sum(i,j+1)=Sum(i,j)+A[j+1]。利用这一个递推，我们就
6、可以得到下面这个算法：intmax_sub(inta[],intsize){ inti,j,v,max=a[0]; for(i=0;isize;i++) { v=0; for(j=i;jsize;j++) { v=v+a[j];Sum(i,j+1)=Sum(i,j)+A[j+1] if(vmax) max=v; } } returnmax;}那怎样才能达到线性复杂度呢？这里运用动态规划的思想。先看一下源代码实现：intmax_sub2(inta[],intsize){ inti,max=0,temp_sum=0
7、; for(i=0;isize;i++) { temp_sum+=a[i]; if(temp_summax) max=temp_sum; elseif(temp_sum0) temp_sum=0; } returnmax;}在这一遍扫描数组当中，从左到右记录当前子序列的和temp_sum，若这个和不断增加，那么最大子序列的和max也不断增加(不断更新max)。如果往前扫描中遇到负
