Google笔试题

一、选择题

1） 机器指令与微指令的关系

一条机器指令对应一个微程序，这个微程序是由若干条指令序列组成，因此，一条机器指令的功能是由若干条微指令组成的序列来实现的。简言之，一条机器指令完成的，操作划分为若干条微指令来完成，由微指令进行解释和执行。

2） 2. 一颗21个节点10层的2叉树，第7层最多有多少个结点。

选8个，从第1层到第10层的个数如：

1 1 1 1 2 4 8 1 1 1

如果;第7层为9的话，则，第6层为>=5，第5层>=3,这3层就>=17, 其他7层最少要有7个结点，那么总数就超过了21了，所以8最大。

3） 虚拟内存的作用，（扩大内存存储速度？扩大内存存储容量？扩大外存存储速度？扩大外存存储容量）？

选择 扩大内存存储容量

4） x = 793, i = 100 while(!x){ x &= (x - 1); i ^=10; } 则i = ?

首先x=512+128+64+16+2+1,有6个‘1’，所以循环执行6次，而i ^= 10执行6次不变。所以i=100

5） 概率题，10个文件，每个文件传对的概率是90%，3次失败就失败。若成功，则应该传了多少次。

6） 组合题，7个相同的球放到4个不同的盒子里的方法有多少种？

120

分析：

用'#'表示挡板，O表示球，这此问题可以转化成在 'OOOOOOO'中插入3个‘#’的组合的总数，挡板相同。

为什么可以这样：例如：O#O#OOO#OO，这个‘#’把他们分成4个部分，可以看成装在4个不同的盒子里

个数分别是：1 1 3 2, 但盒子可以为空,所以这种也合法：###OOOOOOO，0 0 0 7。

下面来计算这个组合总数：

为了方便写，最左边为0位置，最后边为7位置，中间依次递增，像：OO##O#OOOO， 这3个“#”位置为：2,2,3

当第一个‘#’放在i位置范围 ( 0 = < i <= 7)，第二个‘#’可以放在j位置范围（i<= j <= 第3个‘#’可以方的位置范围k（j <= k <= 7)

所以总数为：S=

1+2+3+4+5+6+7+8+

1+2+3+4+5+6+7+

1+2+3+4+5+6+

1+2+3+4+5+

1+2+3+4+

1+2+3+

1+2+

1

= 120

7） 路由的相关概念，（下一跳，目标地址，源地址，路由权值哪个不包含）

二、编程题

1） x = (54321),翻转后的值y=(12345)，类似x=(-123)，翻转后y=(-321)

#include <stdio.h>

void reverse(int x, int *y)

{

int sign= 1;

if(x <0)

{

sign= -1;

x= -x;

}

*y = 0;

while(x)

{

*y= *y * 10 + x % 10;

x/= 10;

}

*y = *y *sign;

}

int main()

{

int x1 =54321;

int x2 =-123;

int *y1;

int *y2;

reverse(x1,y1);

reverse(x2,y2);

printf("beforereverse:%d; after reverse:%d\n", x1, *y1);

printf("beforereverse:%d; after reverse:%d\n", x2, *y2);

return 0;

}

注意的问题：

考虑全面，就可能会出现溢出的情况，但x的个位数是像大于2之类的数，并且x为10位数时，当翻转的时候就会溢出了，整型最大才21亿多

2） 输入n，k ， 打印出第k个排列(1,2,3...n)

如： n = 4， k = 5

1234 1243 1324 1342 1423 1432..... 4321

output：1423

思想：

初始：i = 0，输入n，k

a)j = k / (n-i - 1)!;

b)从[1,2,...,n]中打印第j个，（j=0,..., n-1) 如果前面已经打印了，跳过，这里要有一个标记，那些被打印过了。

c)k = k%(n-i -1)!

d)i++;

e)当 i < n 回到 1 继续执行

哎！在试卷上这思想没有写的这么清楚，比较乱，表达能力不行啊

3） 一个数轴，给定那条线段，（s，t），s是起点坐标，t是终点坐标，写算法算出总的长度。

参考线段树结构，不过不能直接用，这里的s，t可能是double型

转自：http://blog.csdn.net/dremi/article/details/3076233

atof()函数的实现