google筆試題目

訊石光通訊網(wǎng) 2009/9/2 8:22:46
 一、選擇題

  1、定義{1, 2, ... n}*{1, 2, ... n}上的等價(jià)關(guān)系~

  (a, b)~(c, d)當(dāng)且僅當(dāng)a+b=c+d。

  定義集合A(a, b) = {(x,y)|(x,y)~(a,b)},

  那么{1, 2, ... n}*{1, 2, ... n}上不同集合的數(shù)量為( )

  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、若二叉搜索樹有三個(gè)節(jié)點(diǎn),對應(yīng)于三個(gè)不同的值A(chǔ)、B、C,這樣的二叉搜索樹共

  有多少種可能的構(gòu)造?( ) zd.54yjs.cn

  A、1 B、2 C、3 D、4 E、5

  5、假設(shè)把整數(shù)關(guān)鍵碼K散列到有N個(gè)槽的散列表,以下哪些散列函數(shù)是好的散列函數(shù)

 ???( )

  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)返回一個(gè)0到N-1的整數(shù)

  A、1) B、2) C、3) D、4) E、3)和4)

  6、有如下遞歸函數(shù)f(n),其時(shí)間復(fù)雜度為( )

  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、進(jìn)程從擁塞狀態(tài)變?yōu)榫途w狀態(tài)是發(fā)生在( )

  A、分配給進(jìn)程的時(shí)間片用完

  B、進(jìn)程等待的事件發(fā)生

  C、進(jìn)程被調(diào)度程序選中

  D、進(jìn)程等待某一事件

  8、如果有多個(gè)中斷同時(shí)發(fā)生,系統(tǒng)將根據(jù)中斷優(yōu)先級響應(yīng)優(yōu)先級最高的中斷請求。

  若要調(diào)整中斷事件的響應(yīng)次序,可以利用( )

  A、中斷向量B、中斷嵌套C、中斷響應(yīng)D、中斷屏蔽

  9、在編譯原理里,上下文無關(guān)文法和正則文法的描述能力為( )

  A、上下文無關(guān)文法更強(qiáng)B、正則文法更強(qiáng)C、兩者相當(dāng)D、無法比

  較

  10、IP數(shù)據(jù)報(bào)分片的重組通常發(fā)生在以下哪個(gè)位置( )

  A、源主機(jī)B、目的主機(jī)C、路由器D、以太網(wǎng)交換機(jī)

  二、程序設(shè)計(jì)與算法

  1、通常在數(shù)學(xué)中一元n次多項(xiàng)式可表示成如下的形式:

  Pn(x) = a0 + a1*x + a2*x^2 + ... + an*x^n

  (1)請?jiān)O(shè)計(jì)一套接口用以表示和操作一元n次多項(xiàng)式

  (2)根據(jù)上述設(shè)計(jì)實(shí)現(xiàn)一元n次多項(xiàng)式的加法運(yùn)算

  (3)根據(jù)上述設(shè)計(jì)實(shí)現(xiàn)一元n次多項(xiàng)式的乘法運(yùn)算

  2、給定A、B兩個(gè)等長的數(shù)組,A和B中的數(shù)相同,但是順序不同,現(xiàn)在只能取A中某

  數(shù)和B中某數(shù)進(jìn)行比較只能知道大或者小或者相等,怎么將A和B中相同的數(shù)配對?分

  析你的算法的時(shí)間復(fù)雜度。解釋算

  法即可,不必寫代碼。

  三、

  1、你做過的最有創(chuàng)意的軟件項(xiàng)目是什么?請簡單描述一下。

  2、這個(gè)創(chuàng)意有沒有被人使用?

新聞來源:應(yīng)屆生網(wǎng)

相關(guān)文章