google筆試題目
訊石光通訊網
2009/9/2 8:22:46
一、選擇題
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、若二叉搜索樹有三個節(jié)點,對應于三個不同的值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、進程從擁塞狀態(tài)變?yōu)榫途w狀態(tài)是發(fā)生在( )
A、分配給進程的時間片用完
B、進程等待的事件發(fā)生
C、進程被調度程序選中
D、進程等待某一事件
8、如果有多個中斷同時發(fā)生,系統將根據中斷優(yōu)先級響應優(yōu)先級最高的中斷請求。
若要調整中斷事件的響應次序,可以利用( )
A、中斷向量B、中斷嵌套C、中斷響應D、中斷屏蔽
9、在編譯原理里,上下文無關文法和正則文法的描述能力為( )
A、上下文無關文法更強B、正則文法更強C、兩者相當D、無法比
較
10、IP數據報分片的重組通常發(fā)生在以下哪個位置( )
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、你做過的最有創(chuàng)意的軟件項目是什么?請簡單描述一下。
2、這個創(chuàng)意有沒有被人使用?