google笔试题目
一、选择题
1、定义{1, 2, ... n}＊{1, 2, ... n}上的等价关系~
(a, b)~(c, d)当且仅当a+b=c+d。
定义集合a(a, b) = {(x,y)|(x,y)~(a,b)},
那么{1, 2, ... n}＊{1, 2, ... n}上不同集合的数量为( )
a、n b、2＊n-1 c、2＊n d、n＊n
2、下面一段代码的输出是( )
int a, b;
int ＊x, ＊y;
x = &a;
y = &b;
＊x = 10;
＊y = ＊x;
x = y;
＊x = 20;
cout<
f(&b, a);
cout<
}
a、baba b、abab c、abab d、bbab
4、若二叉搜索树有三个节点，对应于三个不同的值a、b、c，这样的二叉搜索树共
有多少种可能的构造？( ) zd.54yjs.cn
a、1 b、2 c、3 d、4 e、5
5、假设把整数关键码k散列到有n个槽的散列表，以下哪些散列函数是好的散列函数
？( )
1) h(k) = k / n;
2) h(k) = 1;
3) h(k) = k mod n;
4) h(k) = (k + random(n)) mod n, random(n)返回一个0到n-1的整数
a、1) b、2) c、3) d、4) e、3)和4)
6、有如下递归函数f(n)，其时间复杂度为( )
int f(int n){
int sum = 0;
for(int i=0; i
sum = sum + i;
return f(n/2) + f((n+1)/2) + sum;
}
a、o(n) b、o(nlongn) c、o(n^2) d、o(n^(3/2))
7、进程从拥塞状态变为就绪状态是发生在( )
a、分配给进程的时间片用完
b、进程等待的事件发生
c、进程被调度程序选中
d、进程等待某一事件
8、如果有多个中断同时发生，系统将根据中断优先级响应优先级最高的中断请求。
若要调整中断事件的响应次序，可以利用( )
a、中断向量b、中断嵌套c、中断响应d、中断屏蔽
9、在编译原理里，上下文无关文法和正则文法的描述能力为( )
a、上下文无关文法更强b、正则文法更强c、两者相当d、无法比
较
10、ip数据报分片的重组通常发生在以下哪个位置( )
a、源主机b、目的主机c、路由器d、以太网交换机
二、程序设计与算法
1、通常在数学中一元n次多项式可表示成如下的形式：
pn(x) = a0 + a1＊x + a2＊x^2 + ... + an＊x^n
(1)请设计一套接口用以表示和操作一元n次多项式
(2)根据上述设计实现一元n次多项式的加法运算
(3)根据上述设计实现一元n次多项式的乘法运算
2、给定a、b两个等长的数组，a和b中的数相同，但是顺序不同，现在只能取a中某
数和b中某数进行比较只能知道大或者小或者相等，怎么将a和b中相同的数配对？分
析你的算法的时间复杂度。解释算
法即可，不必写代码。
三、
1、你做过的最有创意的软件项目是什么？请简单描述一下。
2、这个创意有没有被人使用？
【google笔试题目】相关文章：
Google笔试题目分享11-21
google招聘笔试题02-18
google公司的招聘题目02-16
Google公司预选笔试试题02-18
华夏的笔试题目11-21
南航笔试题目06-23
ITT HR的笔试题目，笔试试题02-24
网易游戏笔试题目11-30
电子类笔试题目11-21
北京CONSULTING的笔试题目11-21