【文章內(nèi)容簡(jiǎn)介】 (n 2). @param[out] right Value of T(n 3). @return Value of T(n 1). */ int find_trib(int n, int amp。 mid, int amp。 right) { if (3 == n) { mid = 1。 right = 1。 return 2。 } else { int temp。 mid = find_trib(n 1, right, temp)。 return mid right temp。 } } /** Find value of T(n). @param[in] The n in T(n). @return Value of T(n). @note T(n) = T(n 1) T(n 2) T(n 3) (n 2) T(0) = T(1) = 1, T(2) = 2. */ int tribonaci(int n) { if (n 0) { // Undefined feature. return 0。 } if (0 == n || 1 == n) { return 1。 } if (2 == n) { return 2。 } int mid, right。 int left = find_trib(n, mid, right)。 return left mid right。 } 啊啊，對(duì)了，答卷的時(shí)候我可沒(méi)心情寫(xiě)注釋 ……剛才到 2020上測(cè)試了一下，貌似沒(méi)有啥問(wèn)題。唉，看來(lái)我多少還是懂一點(diǎn)算法的 …… 第三個(gè)的題目： 在一個(gè)無(wú)向 圖中，尋找是否有一條距離為 K的路徑，描述算法即可，不用實(shí)現(xiàn)，分析算法的時(shí)間和空間復(fù)雜度，盡量?jī)?yōu)化算法。 05 年 Google 筆試題 要筆試考題如下，其他題目是基礎(chǔ)題，就不貼出了： 假設(shè)在 n 進(jìn)制下，下面的等式成立， n 值是（） 567*456=150216 a、 9 b、 10 c、 12 d、 18 文法 G:SuvSvu|w 所識(shí)別的語(yǔ)言是：（） a、 uvw*vu b、（ uvwvu） * c、 uv(uv)*wvu(vu)* d、 (uv)*w(vu)* 如下程序段輸出是：（） char str[][10]={Hello,Google}。 char *p=str[0]。 countstrlen(p 10)。 a、 0 b、 5 c、 6 d、 10 t=0 while(x!=1){ t=t 1。 if(xamp。1==0) x=x/2。 else x=3*x 1。 } counttend1。 當(dāng) n=11 時(shí)，輸出：（） a、 12 b、 13 c、 14 d、 15 寫(xiě)一段程序判定一個(gè)有向圖 G 中節(jié)點(diǎn) w 是否從節(jié)點(diǎn) v 可達(dá)。（假如 G 中存在一條 從 v 至 w 的路徑就說(shuō)節(jié)點(diǎn) w 是從 v 可達(dá)的）。以下算法是用 C 寫(xiě)成的，在 bool Reachable 函數(shù)中，你可以寫(xiě)出自己的算法。 class Graph{ public: int NumberOfNodes()。//返回節(jié)點(diǎn)的總數(shù) bool HasEdge(int u,int v)。//u,v 是節(jié)點(diǎn)個(gè)數(shù)，從零開(kāi)始依次遞增，當(dāng)有一條從 u 到 v 的邊時(shí)，返回 true }； bool Reachable(Graphamp。G, int v, int w){ //請(qǐng)寫(xiě)入你的算法 } 給定一棵所有邊的長(zhǎng)度均為整數(shù)的樹(shù)，現(xiàn)要求延 長(zhǎng)其中某些邊，使得從根到任意節(jié)點(diǎn)的路徑長(zhǎng)度相等。問(wèn)滿足要求的樹(shù)的邊長(zhǎng)度之和最小是多少 ?請(qǐng)寫(xiě)出你的算法，并分析時(shí)間復(fù)雜度。 ===================================================================== Google 筆試 題 兩個(gè)二進(jìn)制數(shù)的異或結(jié)果 遞歸函數(shù)最終會(huì)結(jié)束，那么這個(gè)函數(shù)一定（不定項(xiàng)選擇）： 1. 使用了局部變量 2. 有一個(gè)分支不調(diào)用自身 3. 使用了全局變量或者使用了一個(gè)或多個(gè)參數(shù) , O l+ f3 i8 v* a$ m , S0 d, ~39。 B, \ , { * L以下函數(shù)的結(jié)果？ 2 ^* s。 z/ O$ a$ z R+ ] int cal(int x) 1 r 9 P4 Lamp。 ?3 k( M8 P+ f $ q{ if(x==0) . s$ z0 I P! T1 O 39。 W! @ return 0。* z: T8 } 7 d+ R9 pelse return x+cal(x1)。 } 8 G H( }$ I( a: R d3 [。 } W 以下程序的結(jié)果？ void foo(int*a, int* b) ( \ 4 ^. o p, o7 c2 y9 M6 c0 S{ *a = *a+*b。 *b = *a*b。 *a = *a*b。3 s/ J: i9 L0 Y: y} 6 { 6 d/ } D3 f g2 v8 c) v void main() { amp。 t amp。 ~* ] amp。 i1 a! a5 Kint a=1, b=2, c=3。7 o U h1 o5 i, Efoo(amp。a,amp。b)。 foo(amp。b,amp。c)。 foo(amp。c,amp。a)。 printf(%d, %d, %d, a,b,c)。 } 下面哪項(xiàng)不是鏈表優(yōu)于數(shù)組的特點(diǎn)？ 1. 方便刪除 2. 方便插入 3. 長(zhǎng)度可變 4. 存儲(chǔ)空間小 T(n) = 25T(n/5)+n^2 的時(shí)間復(fù)雜度？ n 個(gè)頂點(diǎn)， m條邊的全連通圖，至少去掉幾條邊才能構(gòu)成一棵樹(shù)？ 正則表達(dá)式 (01|10|1001|0110)*與下列哪個(gè) 表達(dá)式一樣？ 4 V3 A3 w6 | H. q。 G % q3 E a5 D, j {5 D/ K 如何減少換頁(yè)錯(cuò)誤？ 3 C I : g/ r6 ^1. 進(jìn)程傾向于占用 CPU 2. 訪問(wèn)局部性（ locality of reference）滿足進(jìn)程要求 ) 3. 進(jìn)程傾向于占用 I/O （ shortest remaining time）的調(diào)度機(jī)制 5. 減少頁(yè)大小 ! B$ a5 } ! @9 V. C9 y 實(shí)現(xiàn)兩個(gè) N*N 矩陣的乘法，矩陣由一維數(shù)組表示 8 [7 M$ ^ { + v/ a3 ^6 } Y7 q/ D, \$ I39。 C1 z1找到單向鏈表中間那個(gè)元素，如果有兩個(gè)則取前面一個(gè) 2 t1 v4 U, h0 b3 D. d 1長(zhǎng)度為 n 的整數(shù)數(shù)組，找出其中任意 (n1)個(gè)乘積最大的那一組，只能用乘法，不可以用除法。要求對(duì)算法的時(shí)間復(fù)雜度和空間復(fù)雜度作出分析，不要求寫(xiě)程序。 google 浙大招聘筆試題（轉(zhuǎn)） 一、單選 80x8