Google谷歌员工笔试试题及答案

1．1 关于 IP 协议那个正确
A IP 是 TCP 上层协议 B IP 协议是应用层协议 C 由于两个属于同一层协议，他们之间可以直接通信 DIP 协议不提供可靠的通信
1.2 关于内存正确的是
A 内存的存取速度不能低于 cpu 速度，否则会造成数据丢失
B 程序只有在数据和代码等被调入内存后才能运行
C 采用虚拟内存技术后程序可以在硬盘上直接运行
D 某计算机的内存容量为 16MB，那么他的地址总线为 24 位
1.3 单链表中结点的结构为（data，link） ，若想删除结点 p（不是头节点或者尾结点）的直接后继，则应执行下列哪个操作
A p=p->link ; p->link=p->link->linkB p->link->link=p->link;C p=p->link->link Dp->link=p->link->link
1.4 已知 x>=y and y>=z 为真，那么 x>z or y=z 值为
A 真 B 假 C 无法确定 Dx y z 同为正数时为真
1.5 某请求被随即分配到四台机器进行处理，分配到每台机器的概率 A15% B20% C 30% D 35%, 处理请求的失败概
率分别为 5% ，4%， 3% 2%，现在请求失败，问由 C 造成的概率最接近 A26% B28% C 30% D 32%
1.6 假设我们用 d=(a1,a2,….a5)表示无向无环图 G 的 5 个顶点的度数，下面给出的哪组值是可能的
A{3,4,4,3,1}B{4,2,2,1,1}C{3,3,3,2,2}D{3,4,3,2,1}
1.7 设栈 S 和队列 Q 的初始状态为空，元素 e1，e2，e3，e4，e5，e6 一次压入栈 S,一个元素出栈后即进入队列 Q，若出队列的顺序为 e2,e4,e3,e6,e5,e1 则栈 S 的容量要求最小值为 A2B3C4D5
1.8 在堆排序算法中我们用一个数组 A 来模拟二叉树 T，如果该 A[0]存放的是 T 的根节点，那么 A[K](K>0)的父亲节点是
A (K-1)/2 B K/2 C(K 1)/2 D 都不对
1.9 现有如下任务需要安排在若干机器上并行完成，每个任务都有开始时间和结束时间（开始和结束时间都包括在任务执行时间内）的要求 任务名称 开始时间 结束时间
a 1 7
b 8 9
c 2 5
d 7 11
e 3 6
f 7 9
g 10 13
则最少需要使用的机器数目为


A1B2C3D4
1.10 在设计一个操作系统时，哪项不是必须考虑的
A 设备管理模块 B 文件系统模块 C 用户管理模块 D 进程管理模块
2.1 正整数序列 Q 中的每个元素都至少能被正整数 a 和 b 中的一个整除，现给定 a 和 b，需要计算出 Q 中的前几项，
例如，当 a=3，b=5，N=6 时，序列为 3，5，6，9，10，12
（1）设计一个函数 void generate（int a,int b,int N ,int * Q）计算 Q 的前几项
（2）设计测试数据来验证函数程序在各种输入下的正确性
2.2 有一个由大小写组成的字符串，现在需要对他进行修改，将其中的所有小写字母排在答谢字母的前面（大写或
小写字母之间不要求保持原来次序） ， 如有可能尽量选择时间和空间效率高的算法 c 语言函数原型 void proc （char
*str） 也可以采用你自己熟悉的语言
2.3 已知一颗无向无环连通图 T 的所有顶点和边的信息，现需要将其转换为一棵树，要求树的深度最小，请设计一
个算法找到所有满足要求的树的根结点，并分析时空复杂度（描述算法即可，无需代码）