while(!q.empty())

　　{

　　temque.push(q.front());

　　q.pop();

　　}

　　while(!temque.empty())

　　{

　　node_t *tem = temque.front();

　　temque.pop();

　　if(tem->left)

　　q.push(tem->left);

　　if(tem->right)

　　q.push(tem->right);

　　}

　　k--;

　　}

　　if(k > 0)

　　return NULL;

　　while(!q.empty() && m)

　　{

　　q.pop();

　　m--;

　　}

　　if(m > 0)

　　return NULL;

　　return q.front();

　　}

　　第三題、系統(tǒng)設(shè)計(jì)題

　　百度打算開(kāi)發(fā)一個(gè)投票系統(tǒng)，它提供創(chuàng)建、查看、參與和管理投票功能。用戶創(chuàng)建一個(gè)投票時(shí)，有如下信息可知：創(chuàng)建者、標(biāo)題、各選項(xiàng)內(nèi)容、截止時(shí)間、可投票數(shù)。另外，該投票是否對(duì)所有用戶可見(jiàn)繼承于創(chuàng)建者的個(gè)性設(shè)置。查看一個(gè)投票時(shí)，除了顯示上述信息外，還需要顯示每個(gè)選項(xiàng)的投票數(shù)。在截止時(shí)間之前，用戶可以參與投票。管理投票功能為創(chuàng)建者提供刪除一個(gè)投票和調(diào)整進(jìn)行中投票截止時(shí)間的功能。

　　預(yù)計(jì)該投票系統(tǒng)會(huì)很受用戶歡迎，每天可望創(chuàng)建超過(guò)1萬(wàn)個(gè)投票。每天瀏覽次數(shù)達(dá)數(shù)百萬(wàn)，并且有約一百萬(wàn)人次參與投票。經(jīng)驗(yàn)還表明，用戶更喜歡新近的內(nèi)容。

　　實(shí)習(xí)生小A針對(duì)上述需求，打算用數(shù)據(jù)庫(kù)來(lái)實(shí)現(xiàn)這個(gè)投票系統(tǒng)，他給出了數(shù)據(jù)庫(kù)的表設(shè)計(jì)如下：

　　user_info：

　　vote_info：

　　(紅色為主鍵)

　　問(wèn)題：

　　1、小A的設(shè)計(jì)存在什么問(wèn)題，如何改善?

　　2、如果想增加一個(gè)功能，即每個(gè)用戶對(duì)每個(gè)投票只能投一次。如何設(shè)計(jì)?

　　3、系統(tǒng)運(yùn)行了較長(zhǎng)一段時(shí)間之后，用戶反饋使用中速度變慢。請(qǐng)分析可能的原因，并提出解決辦法。

　　4、請(qǐng)完整給出新系統(tǒng)下各功能的實(shí)現(xiàn)流程。涉及數(shù)據(jù)庫(kù)查詢的，請(qǐng)給出SQL語(yǔ)句。

　　B卷(共三道大題)

　　【請(qǐng)先閱讀卷首的試卷說(shuō)明，在A、B卷選擇一套試卷作答，同時(shí)作答試卷無(wú)效】

　　第一題、算法和程序設(shè)計(jì)題

　　1、請(qǐng)編寫(xiě)函數(shù)foo(int x, int y, int n)計(jì)算：隨機(jī)生成x個(gè)大小為[1,y]的正整數(shù)，它們的和為n的概率是多少?語(yǔ)言僅限于PHP、C/C++、Java中的一種。

　　2、設(shè)計(jì)函數(shù)，輸入為一個(gè)字符串，里邊包含中文、英文、數(shù)字等字符，編碼為GBK。中文字符的編碼規(guī)則假定為：雙字節(jié)組成，高字節(jié)大于0x80，低字節(jié)任意。

　　a) 用常用語(yǔ)言(c/c++/php/java)編寫(xiě)函數(shù)，實(shí)現(xiàn)功能為：按順序提取輸入文本中的中文字符，形成新的文本串返回調(diào)用者。

　　b) 如果調(diào)用者有時(shí)希望得到輸入串的全中文內(nèi)容，有時(shí)希望得到英文內(nèi)容，那么該函數(shù)應(yīng)如何設(shè)計(jì)。

　　c) 如果調(diào)用者希望獲取輸入串中包含中文、英文、數(shù)字這三種字符中的一種或多種的需求不定時(shí)，函數(shù)應(yīng)如何設(shè)計(jì)。

　　3、有一個(gè)圖書(shū)館系統(tǒng)，含有Book和BookMaster兩個(gè)類。Book可以用來(lái)設(shè)置書(shū)的屬性(如title)，BookMaster每天做的事情就是根據(jù)上級(jí)的要求重設(shè)設(shè)定某些書(shū)的title，以增加借閱

　　者的注意力，讓更多的人對(duì)書(shū)有新的興趣。

　　有一天，上級(jí)需要BookMaster在setTitle的操作之前都要在日志中記錄一條log。但不幸的是由于一些很特別的原因，沒(méi)有辦法去修改Book類，無(wú)法在Book類的setTitle()方法

　　中增加記錄log的操作。更不幸的是上級(jí)不信任BookMaster自己的統(tǒng)計(jì)結(jié)果，使BookMaster不能在做setTitle()之前自己做log記錄。

　　請(qǐng)問(wèn)如何做才能達(dá)到目標(biāo)，請(qǐng)寫(xiě)出必要的實(shí)現(xiàn)代碼。

　　相關(guān)類定義如下：

　　public interfaceBook {

　　public voidsetTitle(String title);

　　public StringgetTitle();

　　}

　　public classBookException extends Exception {

　　publicBookException() {

　　}

　　}

　　public classBookImpl implements Book {

　　private Stringtitle;

　　public voidsetTitle(String title) {

　　this.title =title;

　　}

　　public StringgetTitle() {

　　returnthis.title;

　　}

　　}

　　public classBookMaster {

　　public staticvoid main(String[] args) {

　　Book book =new BookImpl();

　　out.println("set a book’s title today"); //不能添加這行語(yǔ)句，因?yàn)樯霞?jí)不信任BookMaster自己的統(tǒng)計(jì)結(jié)果

　　book.setTitle("I feel good.");

　　out.println(book.getTitle());

　　}

　　}

　　注：題目中所提供類的定義為Java實(shí)現(xiàn)，但您可以根據(jù)您的喜好自由選擇其它語(yǔ)言完成題目要求。

　　第二題、簡(jiǎn)答題

　　1、網(wǎng)站如何維護(hù)用戶的登錄狀態(tài)?百度知道、百度貼吧、百度百科三個(gè)網(wǎng)站域名不同，但同在.baidu.com主域下，它們之間如何共享用戶登錄狀態(tài)?如果兩個(gè)網(wǎng)站域名也不在一個(gè)主域下，例如www.baidu.com和www.qiyi.com，那么要如何共享用戶登錄狀態(tài)?

　　要求：請(qǐng)盡量提供多種方案并分析各種方案的優(yōu)劣。

　　2、在炎炎夏日，你十分口渴，想要買(mǎi)一瓶冰汽水，商店中有三瓶汽水供你選擇(如ABC)，其中只有一瓶是冰過(guò)的。當(dāng)你選定了其中的某一瓶后(設(shè)為A)，店員摸了下剩余兩瓶中的一瓶(設(shè)為B)，并告訴你B不是冰的，此時(shí)你會(huì)將你的選擇變更為剩余的那瓶嘛(C)?請(qǐng)?jiān)斒瞿愕睦碛?

　　3、TCP服務(wù)器在啟動(dòng)時(shí)，需要經(jīng)過(guò)socket、bind、listen和accept四個(gè)步驟。

　　一個(gè)單進(jìn)程的服務(wù)器的偽代碼如下：

　　01. listen_fd =socket(TCP);

　　02. bind(listen_fd,my_addr);

　　03.listen(listen_fd, backlog);

　　04.

　　05. while(true)

　　06. {

　　07. client_fd = accept(listen_fd);

　　08. read(client_fd, request);

　　09. response = process(request);

　　10. write(client_fd, response);

　　11. close(client_fd);

　　12. }

　　某客戶端的偽代碼如下：

　　13. fd =connect(server_addr);

　　14. write(fd,request);

　　15. read(fd,response);

　　16.display(response);

　　17. close(fd);

　　假設(shè)服務(wù)器在04行執(zhí)行了sleep(1000000)：

　　問(wèn)題1：請(qǐng)簡(jiǎn)介服務(wù)器四個(gè)步驟的意義或作用是什么?

　　問(wèn)題2：當(dāng)1個(gè)客戶端訪問(wèn)該服務(wù)器時(shí)，客戶端執(zhí)行到哪行會(huì)失敗?會(huì)發(fā)生阻塞嗎?為什么?

　　問(wèn)題3：當(dāng)50個(gè)客戶端從50臺(tái)機(jī)器幾乎同時(shí)訪問(wèn)該服務(wù)器時(shí)，各個(gè)客戶端的反應(yīng)有差別嗎?為什么?(注：忽略防火墻因素)

　　第三題、系統(tǒng)設(shè)計(jì)題

　　1、假設(shè)系統(tǒng)里有很多模板文件，每個(gè)模板文件都有一個(gè)唯一的文件名，其內(nèi)容是一個(gè)長(zhǎng)字符串，其中包含很多通過(guò)$...$方式標(biāo)記起來(lái)的模板變量，如：

　　my name is $spname$,i’m $spage$ years old ...

　　其中spname,spage就是我們所謂的模板變量，請(qǐng)?jiān)O(shè)計(jì)一個(gè)簡(jiǎn)單高效的模板解析系統(tǒng)，要求上游模塊向該系統(tǒng)提供一個(gè)模板文件名和一個(gè)模板變量值字典時(shí)，

　　系統(tǒng)能夠返回經(jīng)過(guò)模板變量解析后的文本內(nèi)容，例如：

　　假設(shè)模板文件A.tpl的內(nèi)容為：

　　my name is $spname$,i’m $spage$ years old ...

　　提供的模板變量值字典dict為：

　　array(’spname’ =>’robin928’, ’spage’ => ’29’)，

　　則解析后的文本內(nèi)容應(yīng)該為：

　　my name is robin928,i’m 29 years old ...

　　(訪問(wèn)字典時(shí)可以通過(guò)dict[’spname’]訪問(wèn)到模板變量spname的參數(shù)值)

　　2、目前最流行的, 被稱為微革命的互聯(lián)網(wǎng)應(yīng)用Twitter中, 人民可以在Twitter中互相關(guān)注, 被關(guān)注的人發(fā)出的每一條微型博客(一般都在140字以內(nèi)), 都會(huì)被關(guān)注他的人看到. 而一個(gè)人可能被幾萬(wàn),幾十萬(wàn), 甚至上百萬(wàn)的人關(guān)注; 當(dāng)然, 理論上, 一個(gè)人也可以關(guān)注幾萬(wàn),幾十萬(wàn),甚至上百萬(wàn)的人.

　　1) 請(qǐng)?jiān)O(shè)計(jì)出這樣的一個(gè)系統(tǒng),并詳細(xì)說(shuō)明你的設(shè)計(jì).

　　2) 請(qǐng)指出你設(shè)計(jì)中的缺點(diǎn), 并給出改進(jìn)后的設(shè)計(jì).

　　3) 請(qǐng)?jiān)u述你的最終設(shè)計(jì)的優(yōu)點(diǎn)和缺點(diǎn).

　　· 您可先離線完成所有答案，再把整份答案內(nèi)容剪貼到這里;所有內(nèi)容都將以.txt文件格式保存。

　　· 如果您長(zhǎng)時(shí)間未進(jìn)行任何操作，答題頁(yè)面可能會(huì)超時(shí)失效;若失效請(qǐng)重新登錄，以防止提交失敗。

　　· 請(qǐng)務(wù)必在筆試時(shí)間結(jié)束前提交您的答案，以保證我們能及時(shí)處理。

　　· 答案一旦提交成功，則您的筆試結(jié)束，您將不能繼續(xù)提交答案。

　　答題區(qū)(請(qǐng)?jiān)谙逻呂谋緟^(qū)域填寫(xiě)答案)

　　答案附件:(500K以內(nèi)，可以為doc,zip,pdf,jpg文件)

　　?2009 Baidu 使用百度前必讀

　　B卷

　　第一題、算法和程序設(shè)計(jì)題

　　2(a)讀取中文

　　public static String getChinese(String src)throws UnsupportedEncodingException {

　　Stringdesc="";

　　for(int i = 0; i < src.length(); i++) {

　　charch=src.charAt(i);

　　byte[]buf=(ch+"").getBytes("GBK");

　　if(buf.length>1){

　　desc+=ch;

　　}

　　}

　　returndesc;

　　}

　　2(b)讀取中文或英文

　　public class GetPart {

　　publicstatic final int CHINESE=1;

　　publicstatic final int ENGLISH=2;

　　/**

　　* @param src

　　* @param type 當(dāng)type為CHINESE,得到中文,當(dāng)type為ENGLISH時(shí),得到英文

　　* @return

　　* @throws UnsupportedEncodingException

　　*/

　　publicstatic String getPart(String src,int type)throws UnsupportedEncodingException{

　　if(type==CHINESE){

　　returndoGetChinese(src);

　　}elseif(type==ENGLISH){

　　returndoGetEnglish(src);

　　}else{

　　thrownew IllegalArgumentException("參數(shù)type應(yīng)該為1,2,3");

　　}

　　}

　　privatestatic String doGetEnglish(String src) throws UnsupportedEncodingException {

　　Stringdesc="";

　　for(int i = 0; i < src.length(); i++) {

　　charch=src.charAt(i);

　　byte[]buf=(ch+"").getBytes("GBK");

　　if(buf.length==1&& Character.isLetter(ch)){

　　desc+=ch;

　　}

　　}

　　returndesc;

　　}

　　privatestatic String doGetChinese(String src) throws UnsupportedEncodingException {

　　Stringdesc="";

　　for(int i = 0; i < src.length(); i++) {

　　charch=src.charAt(i);

　　byte[]buf=(ch+"").getBytes("GBK");

　　if(buf.length>1){

　　desc+=ch;

　　}

　　}

　　returndesc;

　　}

　　publicstatic void main(String[] args) throws UnsupportedEncodingException {

　　System.out.println(getPart("123你好ok",ENGLISH));

　　}

　　}

　　2(c)可以同時(shí)讀取任意的文本

　　public class GetPart {

　　publicstatic final int CHINESE=0x1;

　　publicstatic final int ENGLISH=0x2;

　　publicstatic final int DIGIT=0x4;

　　/**

　　* @param src

　　* @param type 當(dāng)type為CHINESE,得到中文,當(dāng)type為ENGLISH時(shí),得到英文

　　* @return

　　* @throws UnsupportedEncodingException

　　*/

　　publicstatic Result getPart(String src,int type)throws UnsupportedEncodingException{

　　Resultresult=new Result();

　　if((type& CHINESE) == CHINESE){

　　result.setChinese(doGetChinese(src));

　　}

　　if((type& ENGLISH) == ENGLISH){

　　result.setEnglish(doGetEnglish(src));

　　}

　　if((type& DIGIT) == DIGIT){

　　result.setDigit(doGetDigit(src));

　　}

　　returnresult;

　　}

　　privatestatic String doGetDigit(String src) throws UnsupportedEncodingException {

　　Stringdesc="";

　　for(int i = 0; i < src.length(); i++) {

　　charch=src.charAt(i);

　　byte[]buf=(ch+"").getBytes("GBK");

　　if(buf.length==1&& Character.isDigit(ch)){

　　desc+=ch;

　　}

　　}

　　returndesc;

　　}

　　privatestatic String doGetEnglish(String src) throws UnsupportedEncodingException {

　　Stringdesc="";

　　for(int i = 0; i < src.length(); i++) {

　　charch=src.charAt(i);

　　byte[]buf=(ch+"").getBytes("GBK");

　　if(buf.length==1&& Character.isLetter(ch)){

　　desc+=ch;

　　}

　　}

　　returndesc;

　　}

　　privatestatic String doGetChinese(String src) throws UnsupportedEncodingException {

　　Stringdesc="";

　　for(int i = 0; i < src.length(); i++) {

　　charch=src.charAt(i);

　　byte[]buf=(ch+"").getBytes("GBK");

　　if(buf.length>1){

　　desc+=ch;

　　}

　　}

　　returndesc;

　　}

　　publicstatic void main(String[] args) throws UnsupportedEncodingException {

　　Resultresult=getPart("123你好ok",CHINESE|ENGLISH|DIGIT);

　　System.out.println(result.getChinese());

　　System.out.println(result.getEnglish());

　　System.out.println(result.getDigit());

　　}

　　}

　　public class Result {

　　privateString chinese;

　　privateString english;

　　privateString digit;

　　publicResult() {

　　}

　　publicString getChinese() {

　　returnchinese;

　　}

　　publicvoid setChinese(String chinese) {

　　this.chinese= chinese;

　　}

　　publicString getEnglish() {

　　returnenglish;

　　}

　　publicvoid setEnglish(String english) {

　　this.english= english;

　　}

　　publicString getDigit() {

　　returndigit;

　　}

　　publicvoid setDigit(String digit) {

　　this.digit= digit;

　　}

　　}

　　3.

　　答:很多方法能解決這個(gè)問(wèn)題.第一:用動(dòng)態(tài)代理為Book生成個(gè)代理.

　　第二:用設(shè)計(jì)模式的代理設(shè)計(jì)模式完成.

　　第三:用spring的aop.

　　這里我們選用設(shè)計(jì)模式的方式:

　　class BookProxy implements Book{

　　privateBook target;

　　publicBookProxy(Book target) {

　　this.target= target;

　　}

　　publicString getTitle() {

　　returntarget.getTitle();

　　}

　　publicvoid setTitle(String title) {

　　System.out.println("seta book’s title today");//增加的日志信息

　　target.setTitle(title);

　　}

　　}

　　class BookMaster {

　　publicstatic void main(String[] args) {

　　Bookbook = new BookImpl();

　　book=newBookProxy(book);

　　book.setTitle("Ifeel good.");

　　}

　　}

　　第二題、簡(jiǎn)答題

　　1。網(wǎng)站如何維護(hù)用戶的登錄狀態(tài)

　　答:有以下幾種方式:

　　(1):如果在同一域下,可以用cookie共享方式實(shí)現(xiàn).

　　在服務(wù)器把cookie信息寫(xiě)到response時(shí),需要加密.

　　當(dāng)服務(wù)器讀取cookie時(shí),需要解密.

　　(2)如果在不同的域,可用一個(gè)服務(wù)器群集來(lái)存放用戶的登錄信息.

　　當(dāng)需要session信息,直接到服務(wù)器群集去取得.

　　2。在炎炎夏日，你十分口渴，想要買(mǎi)一瓶冰汽水此時(shí)你會(huì)將你的選擇變更為剩余的那瓶嘛(C)?請(qǐng)?jiān)斒瞿愕睦碛?

　　答:若A已經(jīng)是冰的，那就不用選擇C;若A不是冰的，并且店員已經(jīng)確認(rèn)B不是冰的，所以只有C是冰的。

　　3。

　　問(wèn)題1：請(qǐng)簡(jiǎn)介服務(wù)器四個(gè)步驟的意義或作用是什么?

　　答:socket是建立套接字.

　　bind是讓建立的套接字指定到具體的網(wǎng)絡(luò)接口(如果一個(gè)機(jī)器有多個(gè)網(wǎng)絡(luò)接口)和

　　端口號(hào).

　　listen:監(jiān)聽(tīng)客戶端的請(qǐng)求

　　accept:如果有請(qǐng)求到來(lái),accept返回一個(gè)客戶端套接字.此時(shí)可以通信了.

　　問(wèn)題3：當(dāng)50個(gè)客戶端從50臺(tái)機(jī)器幾乎同時(shí)訪問(wèn)該服務(wù)器時(shí)，各個(gè)客戶端的反應(yīng)有差別嗎?為什么?(注：忽略防火墻因素)

　　答:有差別,因?yàn)闆](méi)有用多個(gè)線程或者多進(jìn)程技術(shù),那么50個(gè)請(qǐng)求會(huì)放在操作系統(tǒng)的隊(duì)列里面.

　　每一次只能處理一個(gè)請(qǐng)求,1,2，...,50等待時(shí)間各不相同.也許后面的會(huì)因?yàn)槌瑫r(shí)重傳.

　　建議換成多線程技術(shù)來(lái)處理,也可以用非阻塞IO來(lái)處理.那么用戶的體驗(yàn)沒(méi)有那么差.

　　第三題、系統(tǒng)設(shè)計(jì)題

　　1。模板解析

　　答:因?yàn)槟０逦募�的�?nèi)容比較長(zhǎng),不能用正則表達(dá)式,這樣的效率很低.

　　因?yàn)槟０遄兞坑忻鞔_的標(biāo)志${}.那么一遍全文查找就可以了.遇到${,就開(kāi)始記錄便利,

　　遇到}就讀取了變量var,那么查字典dict['var'],就能得到其值,然后填充在里面.

　　特別需要說(shuō)明:字典用散列表建立,這樣效率很高.

　　偽代碼:

　　public class TemplateUtil {

　　/**字典*/

　　privatefinal static Map dict=new HashMap();