Google 筆試題

1、Google筆試是沒(méi)有門(mén)檻的。這樣說(shuō)是因?yàn)镚oogle根本沒(méi)有限制筆試的人數(shù)，開(kāi)了N個(gè)教室，讓N多人參加不過(guò)筆試本身卻有門(mén)檻，看了題目就知道。 本來(lái)想上午寫(xiě)寫(xiě)的，但是，嗯，出于攢人品的目的，還是等到現(xiàn)在才寫(xiě)現(xiàn)在，面試通知已經(jīng)發(fā)過(guò)，很顯然我又被無(wú)視了OK，那也不錯(cuò)，我也沒(méi)怎么準(zhǔn)備這些東西呢，倒不是說(shuō)我不重視，而是事情太多唔，多少算是一種經(jīng)驗(yàn)了。回來(lái)說(shuō)說(shuō)昨天的筆試。題目的量并不大，除了幾個(gè)單選題，剩下就是三個(gè)編程或算法題。單選就不說(shuō)了，考得比較基礎(chǔ)，涉及C語(yǔ)言常識(shí)、數(shù)據(jù)結(jié)構(gòu)、文法、操作系統(tǒng)，主要說(shuō)說(shuō)大題。大題雖然題型不一，但都有一個(gè)重要特點(diǎn)：考遞歸。精確點(diǎn)說(shuō)，我每一題都用到了遞歸。第一個(gè)的題目（嗯

2、，記的不是很完整）：在一棵（排序？）二叉樹(shù)中搜索指定值，數(shù)據(jù)結(jié)構(gòu)定義為（唉唉，數(shù)據(jù)結(jié)構(gòu)的具體名字都不記得了，my god）：struct Node    Node * lnext;    Node * rnext;    int value;函數(shù)定義為（情況同上，啥都記不清了）：Node * search(Node * root, int value)實(shí)現(xiàn)這個(gè)search函數(shù)。用遞歸，經(jīng)典的樹(shù)的遍歷，pass先。第二個(gè)的題目：計(jì)算Tribonaci隊(duì)列（嗯，九成九記錯(cuò)了那個(gè)單詞），規(guī)則是T(n) = T(

3、n - 1) + T(n - 2) + T(n -3)，其中T(0) = T(1) = 1，T(2) = 2。函數(shù)定義：int Tribonaci(int n) 備注，不考慮證整數(shù)溢出，盡可能優(yōu)化算法。這一題我一看就知道要考什么，很顯然的遞歸定義，但也是很顯然的，這里所謂的優(yōu)化是指不要重復(fù)計(jì)算。簡(jiǎn)單的說(shuō)，在計(jì)算T(n)的時(shí)候要用到T(n - 1)、T(n - 2)和T(n - 3)的結(jié)果，在計(jì)算T(n - 1)的時(shí)候也要用到T(n - 2)和T(n - 3)的結(jié)果，所以在各項(xiàng)計(jì)算的時(shí)候必須把以前計(jì)算的結(jié)果記錄下來(lái)，去掉重復(fù)計(jì)算。這里用到的一點(diǎn)小技巧就是要新寫(xiě)一個(gè)函數(shù)用來(lái)做這種事情，嗯，看看我寫(xiě)

4、的代碼吧！/*  Get the value of T(n - 1), and retrieve the result of  T(n - 2) and T(n - 3).  paramin n The n in T(n).  paramout mid Value of T(n - 2).  paramout right Value of T(n - 3).  return Value of T(n - 1). */int find_trib(int n, int & mid, int & right)

5、60;   if (3 = n)            mid = 1;        right = 1;        return 2;        else          &#

6、160; int temp;        mid = find_trib(n - 1, right, temp);        return mid + right + temp;    /*  Find value of T(n).  paramin The n in T(n).  return Value of T(n).  note T(n) = T(n - 1) + T(n

7、- 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;  

8、;      if (0 = n | 1 = n)            return 1;        if (2 = n)            return 2;        int mid, right;  

9、  int left = find_trib(n, mid, right);    return left + mid + right;啊啊，對(duì)了，答卷的時(shí)候我可沒(méi)心情寫(xiě)注釋剛才到VC.Net 2003上測(cè)試了一下，貌似沒(méi)有啥問(wèn)題。唉，看來(lái)我多少還是懂一點(diǎn)算法的第三個(gè)的題目：在一個(gè)無(wú)向圖中，尋找是否有一條距離為K的路徑，描述算法即可，不用實(shí)現(xiàn)，分析算法的時(shí)間和空間復(fù)雜度，盡量?jī)?yōu)化算法。OK，這個(gè)就是傳說(shuō)中的軟肋了我也就不把自己的答案寫(xiě)出來(lái)了（丟人?。?，雖然后來(lái)仔細(xì)想想，我那個(gè)挫挫的方法也能夠用只是效率That's all.粗體文字 取自"

10、;這都已經(jīng)是昨天的事啦。之所以起這個(gè)標(biāo)題是想有朝一日本博的文章也會(huì)被搜索引擎搜到，然后訪問(wèn)量就是指數(shù)級(jí)增長(zhǎng)，有沒(méi)有可能啊。 話(huà)說(shuō)某歌和某度居然在某一天的同一個(gè)時(shí)間搞宣講筆試，只不過(guò)一個(gè)在就業(yè)中心，一個(gè)在科學(xué)館，在我XJTU的廣袤土地上東西對(duì)峙，真是讓人不記住魚(yú)和熊掌的故事都難。Google的筆試時(shí)間一個(gè)月前就確定了，baidu一個(gè)周之前才得到消息，所以俺有理由認(rèn)為，這是百度要問(wèn)鼎中原的意思啦。夠豪邁呀，就不怕人都去了google冷場(chǎng)么？看來(lái)百度還是很自信的，贊一個(gè)，況且百度的中文搜索做得不比google差。俺堅(jiān)決支持民族自己的搜索引擎，雖然事實(shí)上俺是去了google 筆試。此事不怪俺，想想科學(xué)

11、館那昏暗的燈光吧，俺覺(jué)得，非常及其適合你在臺(tái)下看著你偶像的臉搞個(gè)人崇拜 今天聽(tīng)說(shuō)昨晚百度非常人性化，每人一瓶礦泉水，一塊巧克力蛋糕，后來(lái)因?yàn)樘鞜徇€每人發(fā)了紙巾擦汗，這下俺虧大了嘿嘿。 俺本來(lái)發(fā)文的目的是說(shuō)下筆試題，想想還是不說(shuō)了，想知道的可以私下跟俺討論，題目不難，全做對(duì)也不容易，不過(guò)錯(cuò)個(gè)兩三道基本也就kaka了?？疾斓煤苋?，算法數(shù)據(jù)結(jié)構(gòu)操作系統(tǒng)編譯原理網(wǎng)絡(luò)離散數(shù)學(xué)，還居然考了個(gè)中斷。 筆試之前的宣講會(huì)，略有收獲。獲知Google全球共有員工12000左右，其中總部8000左右，而google中國(guó)，北京195，上海45，臺(tái)北35，而在一年前這一數(shù)字分別是北京100，上海20（這個(gè)沒(méi)記準(zhǔn)確），

12、臺(tái)北10。我得到的唯一結(jié)論：google中國(guó)還差的遠(yuǎn)啊，不知道開(kāi)復(fù)能把它做成什么樣子，應(yīng)該不會(huì)撤攤子吧。 這是第二次筆試，作個(gè)記錄，以備日后參考，題目另行記錄。1、 兩個(gè)二進(jìn)制數(shù)的異或結(jié)果 2、 遞歸函數(shù)最終會(huì)結(jié)束，那么這個(gè)函數(shù)一定（不定項(xiàng)選擇）： 1. 使用了局部變量 2. 有一個(gè)分支不調(diào)用自身3. 使用了全局變量或者使用了一個(gè)或多個(gè)參數(shù)3、以下函數(shù)的結(jié)果？int cal(int x)if(x=0)return 0;elsereturn x+cal(x-1);4、 以下程序的結(jié)果？ void foo(int*a, int* b)*a = *a+*b;*b = *a-*b;*a = *a-*b

13、;void main()int a=1, b=2, c=3;foo(&a,&b);foo(&b,&c);foo(&c,&a);printf("%d, %d, %d", a,b,c); 5、下面哪項(xiàng)不是鏈表優(yōu)于數(shù)組的特點(diǎn)？ 1. 方便刪除 2. 方便插入 3. 長(zhǎng)度可變 4. 存儲(chǔ)空間小 6、T(n) = 25T(n/5)+n2的時(shí)間復(fù)雜度？ 7、n個(gè)頂點(diǎn)，m條邊的全連通圖，至少去掉幾條邊才能構(gòu)成一棵樹(shù)？ 8、正則表達(dá)式(01|10|1001|0110)*與下列哪個(gè)表達(dá)式一樣？ 1.(0|1)* 2.(01|01)* 3.(01

14、|10)* 4.(11|01)* 5.(01|1)* 9、如何減少換頁(yè)錯(cuò)誤？ 1. 進(jìn)程傾向于占用CPU 2. 訪問(wèn)局部性（locality of reference）滿(mǎn)足進(jìn)程要求3. 進(jìn)程傾向于占用I/O 4.使用基于最短剩余時(shí)間（shortest remaining time）的調(diào)度機(jī)制 5. 減少頁(yè)大小10、實(shí)現(xiàn)兩個(gè)N*N矩陣的乘法，矩陣由一維數(shù)組表示 11、找到單向鏈表中間那個(gè)元素，如果有兩個(gè)則取前面一個(gè) 12、長(zhǎng)度為n的整數(shù)數(shù)組，找出其中任意(n-1)個(gè)乘積最大的那一組，只能用乘法，不可以用除法。要求對(duì)算法的時(shí)間復(fù)雜度和空間復(fù)雜度作出分析，不要求寫(xiě)程序。 取自"早晨看SIN

15、A新聞，看到Google品牌價(jià)值已經(jīng)達(dá)到664.34億美元，躍居世界第一位。回憶昨晚陪朋友參加google在北大的招聘會(huì)，想和朋友們分享一些特別的感受?？傮w感覺(jué)這是一個(gè)無(wú)限富有，充滿(mǎn)驚喜的公司。</div> 05年9月google開(kāi)始在北京設(shè)立公司，目前已經(jīng)發(fā)展到100名員工。每個(gè)工程師將新配2臺(tái)30inch的液晶顯示器。經(jīng)常到美國(guó)，澳洲，韓國(guó)，日本，印度等國(guó)家TRAVEL，ENJOY great food and drink(喜歡吃喝玩樂(lè))，在中國(guó)有兩名外籍人士，統(tǒng)統(tǒng)講流利的普通話(huà)。其中美國(guó)人eric帶領(lǐng)的PSO（商務(wù)合作工程部）部門(mén)，9個(gè)人，穿著京劇戲服上班，他扮演孫悟空，開(kāi)玩

16、笑說(shuō)穿這些工作服上班還是要花些時(shí)間的。主要筆試考題如下，其他題目是基礎(chǔ)題，就不貼出了：1、假設(shè)在n進(jìn)制下，下面的等式成立，n值是（）567*456=150216a、 9 b、 10 c、 12 d、 182、文法G:S->uvSvu|w所識(shí)別的語(yǔ)言是：（）a、uvw*vu b、（uvwvu）* c、uv(uv)*wvu(vu)* d、(uv)*w(vu)*3、如下程序段輸出是：（）char str10="Hello","Google"char *p=str0;count<<strlen(p+10);a、0 b、5 c、6 d、104、c

17、nt=0while(x!=1)cnt=cnt+1;if(x&1=0)x=x/2;elsex=3*x+1;count<<cnt<<end1;當(dāng)n=11時(shí)，輸出：（）a、12 b、13 c、14 d、155、寫(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 Graphpublic:int NumberOfNodes();/返回節(jié)點(diǎn)的總數(shù)bool HasEdge(int u,int v);/u,v是節(jié)點(diǎn)個(gè)數(shù)，從零開(kāi)

18、始依次遞增，當(dāng)有一條從u到v的邊時(shí)，返回true；bool Reachable(Graph&G, int v, int w)/請(qǐng)寫(xiě)入你的算法6、給定一棵所有邊的長(zhǎng)度均為整數(shù)的樹(shù)，現(xiàn)要求延長(zhǎng)其中某些邊，使得從根到任意節(jié)點(diǎn)的路徑長(zhǎng)度相等。問(wèn)滿(mǎn)足要求的樹(shù)的邊長(zhǎng)度之和最小是多少?請(qǐng)寫(xiě)出你的算法，并分析時(shí)間復(fù)雜度。歡迎回復(fù)，給出你的解答。取自"從沒(méi)有找工作經(jīng)歷的我今天參加了Google的筆試，本來(lái)還自我感覺(jué)良好呢，誰(shuí)知道考題那是嗷嗷不會(huì)啊。 考的幾乎都是算法，指針特別的多，不過(guò)時(shí)間太久不用了都忘記了，數(shù)據(jù)結(jié)構(gòu)的也不少，考了隊(duì)列，還有一些編譯原理的題，關(guān)于表達(dá)式的； 三道大題第一個(gè)還蠻簡(jiǎn)

19、單，是向雙向列表插入一個(gè)節(jié)點(diǎn)，第二個(gè)問(wèn)題比較惡心，判斷A字符串中的各個(gè)字符數(shù)目是否不大于B字符串中的各個(gè)字符數(shù)目，由于沒(méi)時(shí)間了就沒(méi)寫(xiě)完，第三題更是相當(dāng)及其以及特別的惡心，找到整數(shù)數(shù)組中滿(mǎn)足A*B=C的元素，而且要更優(yōu)的，算了半天的時(shí)間復(fù)雜度還是沒(méi)寫(xiě)出來(lái)。 還是忙該忙的事吧，眼看期末考試了，不能掛課，加油！ 取自"1、有兩根不均勻分布的香，香燒完的時(shí)間是一個(gè)小時(shí)，你能用什么方法來(lái)確定一段15分鐘的時(shí)間？ 答：2根香同時(shí)點(diǎn)燃，第一根兩頭都點(diǎn)燃，第二根只點(diǎn)一頭， 第一根點(diǎn)完的時(shí)候是半個(gè)小時(shí)，接著把第二根兩頭都點(diǎn)燃，第二根點(diǎn)完的時(shí)候就是15分鐘。 、一個(gè)經(jīng)理有三個(gè)女兒，三個(gè)女兒的年齡加起來(lái)等

20、于13，三個(gè)女兒的年齡乘起來(lái)等于經(jīng)理自己的年齡，有一個(gè)下屬已知道經(jīng)理的年齡，但仍不能確定經(jīng)理三個(gè)女兒的年齡，這時(shí)經(jīng)理說(shuō)只有一個(gè)女兒的頭發(fā)是黑的，然后這個(gè)下屬就知道了經(jīng)理三個(gè)女兒的年齡。請(qǐng)問(wèn)三個(gè)女兒的年齡分別是多少？為什么？ 答：2，2，9， 1歲不可能 3、有三個(gè)人去住旅館，住三間房，每一間房$10元，于是他們一共付給老板$30，第二天，老板覺(jué)得三間房只需要$25元就夠了于是叫小弟退回$5給三位客人，誰(shuí)知小弟貪心,只退回每人$1，自己偷偷拿了$2，這樣一來(lái)便等于那三位客人每人各花了九元，于是三個(gè)人一共花了$27，再加上小弟獨(dú)吞了不$2，總共是$29?？墒钱?dāng)初他們?nèi)齻€(gè)人一共付出$30那么還有$1

21、呢？ 答：沒(méi)錯(cuò)，三個(gè)人付了27塊，老板拿了25塊，小弟拿了2塊 、有兩位盲人，他們都各自買(mǎi)了兩對(duì)黑襪和兩對(duì)白襪，八對(duì)襪了的布質(zhì)、大小完全相同，而每對(duì)襪了都有一張商標(biāo)紙連著。兩位盲人不小心將八對(duì)襪了混在一起。 他們每人怎樣才能取回黑襪和白襪各兩對(duì)呢？ 答：不知道，還要仔細(xì)想想 、有一輛火車(chē)以每小時(shí)15公里的速度離開(kāi)洛杉磯直奔紐約，另一輛火車(chē)以每小時(shí)20公里的速度從紐約開(kāi)往洛杉磯。如果有一只鳥(niǎo)，以30公里每小時(shí)的速度和兩輛火車(chē)同時(shí)啟動(dòng)，從洛杉磯出發(fā)，碰到另一輛車(chē)后返回，依次在兩輛火車(chē)來(lái)回飛行，直到兩輛火車(chē)相遇，請(qǐng)問(wèn)，這只小鳥(niǎo)飛行了多長(zhǎng)距離？ 答：記好兩車(chē)相遇時(shí)間，就是鳥(niǎo)飛行時(shí)間，乘以其飛行速度就得

22、到飛行距離。 、你有兩個(gè)罐子，50個(gè)紅色彈球，50個(gè)藍(lán)色彈球，隨機(jī)選出一個(gè)罐子，隨機(jī)選取出一個(gè)彈球放入罐子，怎么給紅色彈球最大的選中機(jī)會(huì)？在你的計(jì)劃中，得到紅球的準(zhǔn)確幾率是多少？ 答：不知道，還要仔細(xì)想想 、你有四個(gè)裝藥丸的罐子，每個(gè)藥丸都有一定的重量，被污染的藥丸是沒(méi)被污染的重量1.只稱(chēng)量一次，如何判斷哪個(gè)罐子的藥被污染了？ 答：不知道，還要仔細(xì)想想 、你有一桶果凍，其中有黃色，綠色，紅色三種，閉上眼睛，抓取兩個(gè)同種顏色的果凍。抓取多少個(gè)就可以確定你肯定有兩個(gè)同一顏色的果凍？ 答：4 、對(duì)一批編號(hào)為1100，全部開(kāi)關(guān)朝上(開(kāi))的燈進(jìn)行以下*作：凡是1的倍數(shù)反方向撥一次開(kāi)關(guān)；2的倍數(shù)反方向又撥

23、一次開(kāi)關(guān)；3的倍數(shù)反方向又撥一次開(kāi)關(guān)問(wèn)：最后為關(guān)熄狀態(tài)的燈的編號(hào)。 答：不知道，還要仔細(xì)想想 、想象你在鏡子前，請(qǐng)問(wèn)，為什么鏡子中的影像可以顛倒左右，卻不能顛倒上下？ 答：人的眼睛是左右對(duì)稱(chēng)的 、一群人開(kāi)舞會(huì)，每人頭上都戴著一頂帽子。帽子只有黑白兩種，黑的至少有一頂。每個(gè)人都能看到其它人帽子的顏色，卻看不到自己的。主持人先讓大家看看別人頭上戴的是什幺帽子，然后關(guān)燈，如果有人認(rèn)為自己戴的是黑帽子，就打自己一個(gè)耳光。第一次關(guān)燈，沒(méi)有聲音。于是再開(kāi)燈，大家再看一遍，關(guān)燈時(shí)仍然鴉雀無(wú)聲。一直到第三次關(guān)燈，才有劈劈啪啪打耳光的聲音響起。問(wèn)有多少人戴著黑帽子？ 答：3 取自"1 超級(jí)失敗的1：說(shuō)

24、8點(diǎn)開(kāi)始，考試時(shí)間100分鐘 ，怎么算都是9：10交卷；9點(diǎn)一到匆匆交卷了，晚上躺床上才發(fā)現(xiàn)錯(cuò)也； 2 超級(jí)失敗的2：把自個(gè)的生日又記錯(cuò)了； 3 怕怕的發(fā)現(xiàn)：發(fā)現(xiàn)mm還是超級(jí)可怕滴，眼睜睜看著一個(gè)騙局，哎，也得謹(jǐn)慎些以防上當(dāng)受騙??； 題目如下： T( 0 ) = 1  T(1)=1;T(2)=2;T(n)=T(n-1)+T(n-2)+T(n-3); 用最優(yōu)方式求T(n)  int?T(int?n)? 可以用最熟悉的語(yǔ)言寫(xiě) 在考場(chǎng)的第一個(gè)做法 ?1 public ? class ?T? ?2  ? public ? int ?

25、t( int ?n) ?3  ? if ?(n? = ? 0 )? ?4 ? return ? 1 ?5  ? ? else ? if ?(n? = ? 1 )? ?6 ? return ? 1 ?7  ? ? else ? if ?(n? = ? 2 )? ?8 ? return ? 2 ?9  ? ? else ? 10 ?

26、 return ?t(n - 1 )? + ?t(n - 2 )? + ?t(n - 3 );11 ? ?12 ? 13 當(dāng)時(shí)發(fā)現(xiàn)時(shí)間夠用，進(jìn)行了公式推理，但未得出規(guī)律的真諦每個(gè)都與T(3)可以直接發(fā)生關(guān)系，關(guān)系是2的冪次方，但最終沒(méi)有得出公式遂改進(jìn)如下：?1 public ? class ?T? ?2  ? public ? int ?t( int ?n) ?3  ? if ?(n? = ? 0 )? ?4 ? return 

27、;? 1 ?5  ? ? else ? if ?(n? = ? 1 )? ?6 ? return ? 1 ?7  ? ? else ? if ?(n? = ? 2 )? ?8 ? return ? 2 ?9  ? ? else ? 10 ? return ? 2 ? * ?t(n - 1 )? - ?t(n - 3 );11 ? 

28、;?12 ? 13 晚上躺床上，怎么可能這樣直接呢？突然想到最起碼的一點(diǎn)就是重復(fù)數(shù)的計(jì)算，應(yīng)該進(jìn)行保存；如果正向逐個(gè)求然后保存，可行；如果倒向如何保存，尚未想好大家來(lái)仁者見(jiàn)仁一下哦（有更好的思路的請(qǐng)指點(diǎn)）public class T ?Map values = new HashMap();?public int t(int n)?int result = 0;?if (n = 0) ? result = 1;? else if (n = 1) ?result = 1;? else if (n = 2) ?result = 2;? else ?result =? 2 * t(n-1)

29、- t(n-3);? ?return result;?取自"、一、單選 1、80x86中，十進(jìn)制數(shù)-3用16位二進(jìn)制數(shù)表示為？ 2、假定符號(hào)-、*、$分別代表減法、乘法和指數(shù)運(yùn)算，且 1)三個(gè)運(yùn)算符優(yōu)先級(jí)順序是：-最高，*其次，$最低； 2)運(yùn)算符運(yùn)算時(shí)為左結(jié)合。請(qǐng)計(jì)算3-2*4$1*2$3的值： (A)4096，(B)-61，(C)64，(D)-80，(E)512 3、下列偽代碼中，參數(shù)是引用傳遞，結(jié)果是？ calc(double p, double q, double r)q=q-1.0;r=r+pmain()double a = 2.5, b = 9.0;calc(b-a, a

30、, a);print(a);(A)1.5 (B)2.5 (C)10.5 (D)8 (E)6.5 4、求輸出結(jié)果： int foo(int x, int y)if(x <=0 | y <= 0) return 1;return 3 * foo(x - 1, y / 2);printf("%dn", foo(3, 5);(A)81 (B)27 (C)9 (D)3 (E)1 5、下列哪個(gè)數(shù)據(jù)結(jié)構(gòu)在優(yōu)先隊(duì)列中被最廣泛使用？ (A)堆 (B)數(shù)組 (C)雙向鏈表 (D)圖 (E)向量 6、以下算法描述了一個(gè)在n國(guó)元素的雙向鏈表中找到第k個(gè)元素的方法（k >= 1且k

31、 <= n）： 如果k <= n - k，從鏈表開(kāi)始往前進(jìn)k-1個(gè)元素。 否則，從終點(diǎn)出發(fā)，往回走n - k個(gè)元素。 這個(gè)算法的時(shí)間代價(jià)是？ (A)(nlogn) (B)(maxk, n - k) (C)(k + (n - k) (D)(maxk, k - n) (E)(mink, n - k) 7、有一個(gè)由10個(gè)頂點(diǎn)組成的圖，每個(gè)頂點(diǎn)有6個(gè)度，那么這個(gè)圖有幾條邊？ (A)60 (B)30 (C)20 (D)80 (E)90 8、正則表達(dá)式L = x*(x|yx+)。下列哪個(gè)字符串不符合L (A)x (B)xyxyx (C)xyx (D)yxx (E)yx 9、為讀取一塊數(shù)據(jù)而準(zhǔn)備

32、磁盤(pán)驅(qū)動(dòng)器的總時(shí)間包括 (A)等待時(shí)間 (B)尋道時(shí)間 (C)傳輸時(shí)間 (D)等待時(shí)間加尋道時(shí)間 (E)等待時(shí)間加尋道時(shí)間加傳輸時(shí)間 二、算法 1、打印出一個(gè)二叉樹(shù)的內(nèi)容。 2、在一個(gè)字符串中找到第一個(gè)只出現(xiàn)一次的字符。如abaccdeff，輸出b。 3、給定一個(gè)長(zhǎng)度為N的整數(shù)數(shù)組（元素有正有負(fù)），求所有元素之和，最大的一個(gè)子數(shù)組。分析算法時(shí)空復(fù)雜度。不必寫(xiě)代碼。 附上動(dòng)態(tài)規(guī)劃做法的答案: 最大子序列 問(wèn)題： 給定一整數(shù)序列A1， A2，. An （可能有負(fù)數(shù)），求A1An的一個(gè)子序列AiAj，使得Ai到Aj的和最大 例如：整數(shù)序列-2, 11, -4, 13, -5, 2, -5, -3,

33、12, -9的最大子序列的和為21。對(duì)于這個(gè)問(wèn)題，最簡(jiǎn)單也是最容易想到的那就是窮舉所有子序列的方法。利用三重循環(huán)，依次求出所有子序列的和然后取最大的那個(gè)。當(dāng)然算法復(fù)雜度會(huì)達(dá)到O(n3)。顯然這種方法不是最優(yōu)的，下面給出一個(gè)算法復(fù)雜度為O(n)的線性算法實(shí)現(xiàn)，算法的來(lái)源于Programming Pearls一書(shū)。在給出線性算法之前，先來(lái)看一個(gè)對(duì)窮舉算法進(jìn)行優(yōu)化的算法，它的算法復(fù)雜度為O(n2)。其實(shí)這個(gè)算法只是對(duì)對(duì)窮舉算法稍微做了一些修改：其實(shí)子序列的和我們并不需要每次都重新計(jì)算一遍。假設(shè)Sum(i, j)是Ai . Aj的和，那么Sum(i, j+1) = Sum(i, j) + Aj+1。利用這一個(gè)遞推，我們就可以得到下面這個(gè)算法： int max_sub(int a,int size)int i,j,v,max=a0;for(i=0;i<size;i+)v=0;for(j=i;j<size;j+)v=v+aj;/Sum(i, j+1) = S