Google笔试题-2011年

一、选择题

(1) 以下哪个字符串不能被正则表达式 a(bc)*d* 匹配到？

　　A. ad　　B. abcd　　C. abc　　D. abccd

(2) 在x86 cpu中，下面哪种运算速度最慢？

　　A. 加　　B. 减　　C. 乘　　D. 除

(3) 下面程序输出的结果是什么？

                void main()

                {

                    bool first=true;

                    int sum =0;

                    int current_value;

                    for(unsigned short i=65535;i>=0;--i )

                    {

                        if(first)

                        {

                            current_value=65535;

                            sum+=current_value%3;

                            first=false;

                        }

                        else

                        {

                            sum+=-current_value%3;

                            if(current_value<=0)

                            {

                                printf("%d,%d",sum,i);

                                break;

                            }

                        }

                    }

       }　　

       A. 65535, 0　　B. 65536, 1　　C. 65536, 65535　　D. 65536, 0

(4) 书架上有编号为1-19的19本书，从中拿5本，问5本编号都不相邻的拿法有多少种？

　　A. 2002　　B. 3003　　C. 11628　　D. 比C大的一个数，具体多少我忘记了。

(5) 现在有一套房子，价格200万，假设房价每年上涨10%，一个软件工程师每年固定能赚40万。如果他想买这套房子，不贷款，不涨工资，没有其他收入，那么他需要几年才能攒够钱买这套房子？

　　A. 5年　　B. 7年　　C. 8年　　D. 9年　　E. 永远买不起

(6) 一棵满二叉树，一共有n个叶子节点，请问该二叉树一共有多少个节点？

　　A. 2n-1　　B. 2n　　C. n-1　　D. n

(7) 下列哪种排序方法在最坏情况下的时间复杂度是 nlgn？

　　A. 归并排序　　B. 快速排序　　C. 冒泡排序　　D. 插入排序

(8) 有两个从小到大排好序的数组，长度分别是N和M，将这两个数组合并成一个有序数组的最小比较次数是：？

       A min(N,M)        B M+N-1        C N+M       D max(M,N)

(9) 关于TLB和Cache的说法中，哪个是错的？

　　A. TLB与Cache中保存的数据是不同的

　　B. TLB miss后，有可能直接在Cache中找到页表内容

　　C. TLB miss后会导致程序出错，但是Cache miss不会

　　D TLB和Cache的命中率都与程序的访存模式有关

(10) 关于数据库的说法，哪个是错误的？

　　A. 每个表都必须有主键

　　B. 跨表查询可能非常慢

　　C. 数据库不支持多个用户对同一个表进行写操作

　　D. 多维索引可以用KD树实现 

二、编程算法题

(1) 编程实现多项式求值：

f(n)=a0+ a1*x^1 + a2*x^2 +…+ an*x^n，

函数声明如下：double foo(double x, double *A, int N)。 

(2) 现在有n=2^k支足球队，编号为0，1，…，n-1，给出2维数组winner[][],winner[i][j]表示当编号i和j的会胜出的队伍的编号，并且没有平局，输入保证winner[i][j]==winner[j][i],现在给出一个单败淘汰赛的签位一维数组order[],order[i]表示第i个签位上的队伍的编号，order保证是0到n-1的一个排列。返回比赛最后的排名顺序，同一轮被淘汰的队伍名词并列，并列的队伍之间的顺序任意，要求时间和空间复杂度尽量的低，将结果写到一维数组result[]里面即可。

接口定义：

c++：

void calculate_result(int n,vector<vector<int>> winner,vector<int> order,vector<int> result);

例子：

N=4，winner={{0,1,2,3},{1,1,2,1},{2,2,2,3},{3,1,3,3}},order={0,1,2,3}

…

(3) KOF 游戏相关，玩过 KOF（拳皇）的人都知道，玩的时候如果按照一定的按键次序就会连招，连招的威力很大。现在题目的意思是：每招用一个大写字母表示，如 ABC … Z ，现给定 n 个连招公式：S→T，每个公式的S长度都相同，都为 m ，T 的长度为 1 。每个公式都代表一个连招规则，表示如果之前的m招为S，那么可以在后面连出一招T， 在前 m 招的时候可以随便连，但 m+1招后就必须遵循连招公式。现在要写一个算法，计算最长连招的长度；如果可以无限连招，则返回 def 。（1≤n, m≤100）

这里有一个例子：n=4, m=3，连招公式为：ABC→D，ABC→C，CCA→A，BCC→A。连招公式的意思是：A、B、C可以连出C，也可连出D，C、C、A可以连出A，B、C、A、可以连出B。这时候可以得到最长连招公式：ABC→C→A→A，即最长连招公式长度为 6 。