Google笔试卷-2012年

一、单项选择题

1、下列关于整数的说法中哪个是正确的（）

 A、在采用补码的计算机的系统中，无符号整数和有符号整数很容易区分开        B、在32位系统中计算8位加法会比32位加法快

 C、作整数运算时应尽量避免溢出，因为溢出会占用额外的内存，影响系统性能        D、常见计算机系统中整数除法比乘法慢

2、按照OSI模型的层次概念，下列几个协议中哪一个协议在协议栈的最底层（）

 A、HTTP        B、FTP        C、IP        D、TCP

3、请阅读下面代码片段并且回答问题：

#define SIZE_20M (20*1024*1024)
void func_a()
{
    char *temp = malloc(SIZE_20M)
    return;
}
void func_b()
{
    char temp[SIZE_20M];
    //...do something using temp
    return;
}

关于这段代码，下列说法正确的是（）

 A、func_a 获得临时内存的方式效率通常更高        B、func_b 使用了太多的栈，程序可能会在运行时候崩溃

 C、func_b 存在内存泄露                                     D、func_a 和func_b 分配的内存会自动初始化0

4、与十进制数28.5625相等的四进制数是（）

 A、121.30        B、221.30        C、121.31        D、130.21

5、由3个a,5个b和2个c构成的所有长度为10的字符串中，仅包含一个“abc”子串 的共有几个（）

 A、40320        B、39600        C、840        D、780        E、60

6、一个有n个结点的连通图的生成树是原图的最小连通子图，且包含原图中所有n个结点，并且有保持图联通的最少的边。最大生成树就是权和最大生成树，现在给出一个无向带权图的邻接矩阵，权为0表示没有边。｛{0，4，5，0，3}，{4，0，4，2，3}，{5，4，0，2，0}，{0，2，2，0，1}，{3，3，0，1，0}｝，求这个图的最大生成树的权和（）

 A、11        B、12        C、13        D、14         E、15

7、一棵树（>=3个节点）最少需要删掉几个节点才能使得这棵树不连通（）

 A、0        B、1        C、2        D、3

8、以下算法不能用于文本加密的是（）

 A、MD5        B、RSA        C、RC4        D、DES

9、下面关于垃圾收集的描述哪个是错误的（）

 A、使用垃圾收集的程序不需要明确释放对象        B、现代垃圾收集能够处理循环引用问题

 C、垃圾收集能提高程序员效率                           D、使用垃圾收集的语言没有内在泄漏问题

10、下面关于操作系统的概念，哪个是错误的（）

 A、Micro-kernel和Monolithic-kernel都还是现代操作系统的常用技术        B、操作系统为应用软件提供运行环境

 C、操作系统的系统调用是应用软件与操作系统交互的接口        D、文件系统和设备驱动必须运行在内核态

二、问答题

11、某环形公路上有N个站点，分别记为A1......An，从Ai到A（ i+1）的距离为Di。An到A1的距离为Do，假设Do=Dn=1，保存在数组D（N）中，现在要求你与一个函数，能够高效的计算出公路上任意两点的最近距离，要求空间复杂度不能超过O(N)。

const int N=100;
double D(N);
...
Void preprocess(){
//Write your code here,        (1)
}
double Distance(int i, int j){
// Write your code bere         (2)
}

12、给定字符串s, 要求把s中多于一个的连续空压缩成一个空格，并将连续的非空格字符串倒序打印出来，例如，给定"abc def efg"，打印"cba fed gfe"。

13、给你一个数小于1000000，分别用100,50,20,10,5块表示出来，有多少种表示方法。写出算法即可。

参考答案

1、A    2、C    3、B    4、D    5、D    6、D    7、B    8、A    9、D    10、D

11、参考代码：

#include"iostream"
#include"math.h"
#define MAX 100
using namespace std;
int main(int argc, char* argv[])
{
    int N;
    double D[MAX],sum=0,SumD[MAX];
    cin>>N;
    for(int i=0;i<N;i++)
    {
        cin>>D[i];
        sum+=D[i];
        SumD[i] = sum;
    }
    while(true)
    {
        int a,b;
        cin>>a>>b;
        if(a>N||b>N)
            break;
        float temp = fabs(SumD[a-1]-SumD[b-1]);
        cout<<"result: "<<(temp>(sum-temp)?(sum-temp):temp)<<endl;
    }
    return 0;
}

12、参考代码：

#include <iostream> 
#include <stack> 
using namespace std; 

int main() 
{ 
    stack<char> s; 
    int flag=0; 
    char ch=getchar(); 
    while(1) 
    { 
        if(ch!='\n') 
        { 
            if(ch!=' '&&flag==0) 
            { 
                s.push(ch); 
            } 
            else 
            { 
                if(ch==' '&&flag==0) 
                { 
                    while(s.size()!=0) 
                    { 
                        cout<<s.top(); 
                        s.pop(); 
                    } 
                    cout<<" "; 
                    flag=1; 
                } 
                else 
                { 
                    if(ch!=' '&&flag==1) 
                    { 
                        flag=0; 
                        s.push(ch); 
                    } 
                } 
            } 
            ch=getchar(); 
        } 
        else 
        { 
            while(s.size()!=0) 
            { 
                cout<<s.top(); 
                s.pop(); 
            } 
            cout<<endl; 
            break; 
        } 
    } 
    system("pause"); 
    return 0; 
} 

13、参考代码：

public static int getCount(int sum){
    int count = 0;
    for(int i = 0; i <= sum/5; i++){
      for(int j = 0; j <= sum/10; j++){
        for(int k = 0; k <= sum/20; k++){
          for(int p = 0; p <= sum/50; p++){
            for(int q = 0; q <= sum/100; q++){
              if(5*i + 10*j + 20*k + 50*p + 100*q > sum){
                continue;
              } else if (5*i + 10*j + 20*k + 50*p + 100*q == sum){
                System.out.println(i+","+j+","+k+","+p+","+q);
                ++count;
              }
            }
          }
        }
      }
    }
    return count;
}