其实考得很基础，不过N久没有复习，很多概念都生疏了
发个题目，积累下人品吧，hoho～～
发信人: csyoung (Youngster), 信区: IBMClub
标 题: [07.5.21]Google实习生招聘笔试题目
发信站: 华南木棉BBS (Tue May 22 09:40:40 2007), 转信
一、选择题
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，这样的二叉搜索树共
有多少种可能的构造？( )
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中某 法即可，不必写代码。 三、 1、你做过的最有创意的软件项目是什么？请简单描述一下。 2、这个创意有没有被人使用？
若要调整中断事件的响应次序，可以利用( )
较
数和B中某数进行比较只能知道大或者小或者相等，怎么将A和B中相同的数配对？分
析你的算法的时间复杂度。解释算