Google笔试题

1.单项选择题
1.  下面一段代码的输出是[ C ]
void fn(int* b){
    (*b)++;
}
int main(){
    int a=7;
    fn(&a);
    cout<    return 0;
}
A.0     B.7    C.8    D.undefined
分析：考察址传递的问题。

2.  定义int i,j,*p=&i; 那么下面哪条语句可以完成i=j的赋值[ B ]
A.i=*p;     B. *p=*&j;    C.i=&j;    D.I=**p;
分析：自己比较一下类型就可以了。A是自身赋值，肯定不对；C用一个地址赋值给int类型的变量，肯定不对；D中用一个int*赋值给i，显然不对了，呵呵

3.  用二叉搜索树和哈希表存储相同的数据集,对于以下何种操作,二叉搜索树比哈希表速度更快?[ E ]
A.检索    B. 插入    C.删除    D.更新    E.排序
分析：二叉排序树的优点，不多说了。

4.  包含N个几点和M条边的有向带权图G, 边的权为正, 以下操作中不可以在O(N+M)
的时间复杂度内完成的操作是:[ A ]
A.  求结点s到结点t之间的最短距离
B.  求距离结点s最近的结点
C.  已知起始结点, 对图G中的结点进行拓扑排序
D.  求图G的最大强连通子图
分析：第一个是O((N+M)logN)，所以肯定选A了。

5.  有如下递归函数f(n),其时间复杂度为[ D ]
int f(int n){
    if(n==0)
         return 0;
    if(n==1)
         return 1;
    return ( 5*f(n-1) - 6*f(n-2) );
}
A.O(n)     B. O(n^2)    C. O(n^3)    D. O(2^n)
分析：前序遍历完全二叉树的所有节点，显然是D。

6.  下面所述步骤中,哪一个不是创建经常所必需有的[ A ]
A.由调度程序为进程分配CPU       B.建立一个进程控制块
C.为进程分配内存                D.将进程控制块链入就绪队列
分析：这个是OS的基本知识。

7.  在多进程的系统中,为了保证公区变量的完整性,各进程应互斥进入临界区。所谓临界区是[ D ]
A.一个缓冲区        B.一个数据区        C.一个同步机构      D.一段程序
分析：这个是临界区的定义。

8.  能产生满足如下条件语言的正则表达式是：1.每一个a后至少紧跟两个c; 2.每一个b后至少紧跟一个c [ A ]
A.(acc|bc|c)*   B.(acc|bc)* C.(ac|bc)*  D.不是正则语言
分析：简单，不过要注意“至少”两个字。

9.  以下哪项不是RPC（远程过程调用）的特点[ A ]
A.速度快        B.降低系统耦合度        C.可以实现异构系统间的协作
分析：这个就不用说了吧，很明显的。

10. 有三个桶，容量分别是3升，5升，7升，你只能进行下面的操作：
把一个桶中所有的水倒掉；
把一个桶A中的水倒入桶B，直到桶A空了或者桶B满了；
假设一开始容量为3升和5升的桶是满的，7升的桶是空的，希望通过一系列操作使3个桶中任意一个中正好有4升水，那么至少需要[ A ]次操作。
A.3     B.5     C.7     D.不可能
分析：（1）3升桶中所有水倒入7升桶
       (2) 5升桶中水倒入7升桶，直到7升桶满，这样5升桶中还有1升
       (3) 7升桶中水倒满3升桶，7升桶还有4升水。
       非常简单，呵呵，显然是A。

2.  程序设计与算法
2.1 实现如下编码算法，对于重复2-9次数的字符，用两个数字表示，即NX（其中N为重复的次数，X为重复的字符，下同），超过九个则先输出9X，然后处理剩 下的字符。对于连续的不重复的字符，则两边加1来封字符串。如果被封的字符串其中有数字为1，则用1来转义。    示例： AAAAAABCCCC-> 6A1B14C,  12344 -> 11123124。。。（下面的框架是用C++语言写的。你可以用你熟悉的语言。）
void encode (const char* text, char* dest)
text 为需要编码的字符串，dest表示编码输出的目标空间，而空间足够大。
分析：只要懂基本的对字符串的处理就会解此题了，不详细说了，有问题可以和我讨论。

2.2 给定一颗有n个结点的二叉树。求它的所有结点数为m的连通子图数目。m<=n分析你的算法的时间复杂度，解释算法即可，不必写代码。
分析：树型DP。要考虑两种情况，一个是当前根节点是不是在连通子图上的情况；一个是当前根节点不在连通子图上的情况。设N(v, m)是根节点为v的树的所有节点数为m的连通子图的数目。那么：
       N(v, m) = ∑{N(v.lchild, i) * N(v.rchild, m-1-i)} +
                 N(v.lchild, m) + N(v.rchild, m)
复杂度取决于结果表的大小，每个N(v,m)的计算的代价为O(m)（因为里面有个sigma和的，呵呵），所以最终代价为O(n*m*m)。