1、百度2014校園招聘-研發(fā)工程師筆試題一、簡答題（30分）1, 當(dāng)前計(jì)算機(jī)系統(tǒng)一般會(huì)采用層次結(jié)構(gòu)存儲(chǔ)數(shù)據(jù)，請(qǐng)介紹下典型計(jì)算機(jī)存儲(chǔ)系統(tǒng)一般分為哪幾個(gè)層次，為什么采用分層存儲(chǔ)數(shù)據(jù)能有效提高程序的執(zhí)行效率？（10分）所謂存儲(chǔ)系統(tǒng)的層次結(jié)構(gòu)，就是把各種不同存儲(chǔ)容量、存取速度和價(jià)格的存儲(chǔ)器按層次結(jié) 構(gòu)組成多層存儲(chǔ)器，并通過管理軟件和輔助硬件有機(jī)組合成統(tǒng)一的整體，使所存放的程序和數(shù) 據(jù)按層次分布在各種存儲(chǔ)器中。目前，在計(jì)算機(jī)系統(tǒng)中通常采用三級(jí)層次結(jié)構(gòu)來構(gòu)成存儲(chǔ)系統(tǒng)，主要由高速緩沖存儲(chǔ)器 Cache、主存儲(chǔ)器和輔助存儲(chǔ)器組成。存儲(chǔ)系統(tǒng)多級(jí)層次結(jié)構(gòu)中，由上向下分三級(jí)，其容量逐漸增大，速度逐級(jí)降低，成本則逐 次

2、減少。整個(gè)結(jié)構(gòu)又可以看成兩個(gè)層次：它們分別是主存一輔存層次和cache 一主存層次。這個(gè)層次系統(tǒng)中的每一種存儲(chǔ)器都不再是孤立的存儲(chǔ)器，而是一個(gè)有機(jī)的整體。它們?cè)谳o助硬件 和計(jì)算機(jī)操作系統(tǒng)的管理下，可把主存一輔存層次作為一個(gè)存儲(chǔ)整體，形成的可尋址存儲(chǔ)空間 比主存儲(chǔ)器空間大得多。由于輔存容量大，價(jià)格低，使得存儲(chǔ)系統(tǒng)的整體平均價(jià)格降低。由于 Cache的存取速度可以和 CPU的工作速度相媲美，故 cache 一主存層次可以縮小主存和cPu之間的速度差距，從整體上提高存儲(chǔ)器系統(tǒng)的存取速度。盡管Cache成本高，但由于容量較小，故不會(huì)使存儲(chǔ)系統(tǒng)的整體價(jià)格增加很多。綜上所述，一個(gè)較大的存儲(chǔ)系統(tǒng)是由各種不同

3、類型的存儲(chǔ)設(shè)備構(gòu)成，是一個(gè)具有多級(jí)層次 結(jié)構(gòu)的存儲(chǔ)系統(tǒng)。 該系統(tǒng)既有與CPU相近的速度，又有極大的容量，而成本又是較低的。 其中 高速緩存解決了存儲(chǔ)系統(tǒng)的速度問題，輔助存儲(chǔ)器則解決了存儲(chǔ)系統(tǒng)的容量問題。采用多級(jí)層 次結(jié)構(gòu)的存儲(chǔ)器系統(tǒng)可以有效的解決存儲(chǔ)器的速度、容量和價(jià)格之間的矛盾。2，Unix/Linux系統(tǒng)中僵尸進(jìn)程是如何產(chǎn)生的？有什么危害？如何避免？（10分）一個(gè)進(jìn)程在調(diào)用exit命令結(jié)束自己的生命的時(shí)候，其實(shí)它并沒有真正的被銷毀，而是留下一個(gè)稱為僵尸進(jìn)程（Zombie ）的數(shù)據(jù)結(jié)構(gòu)（系統(tǒng)調(diào)用exit，它的作用是使進(jìn)程退出，但也僅僅限于將一個(gè)正常的進(jìn)程變成一個(gè)僵尸進(jìn)程，并不能將其完全銷毀）

4、。在Linux進(jìn)程的狀態(tài)中，僵尸進(jìn)程是非常特殊的一種，它已經(jīng)放棄了幾乎所有內(nèi)存空間， 沒有任何可執(zhí)行代碼，也不能被調(diào)度，僅僅在進(jìn)程列表中保留一個(gè)位置，記載該進(jìn)程的退出狀 態(tài)等信息供其他進(jìn)程收集，除此之外，僵尸進(jìn)程不再占有任何內(nèi)存空間。它需要它的父進(jìn)程來 為它收尸，如果他的父進(jìn)程沒安裝SIGCHLD信號(hào)處理函數(shù)調(diào)用 wait或waitpid（）等待子進(jìn)程結(jié)束，又沒有顯式忽略該信號(hào)，那么它就一直保持僵尸狀態(tài)，如果這時(shí)父進(jìn)程結(jié)束了，那么in it進(jìn)程自動(dòng)會(huì)接手這個(gè)子進(jìn)程，為它收尸，它還是能被清除的。 但是如果如果父進(jìn)程是一個(gè)循環(huán)，不會(huì)結(jié)束，那么子進(jìn)程就會(huì)一直保持僵尸狀態(tài)，這就是為什么系統(tǒng)中有時(shí)會(huì)有很

5、多的僵尸進(jìn)程。避免zombie的方法:1) 在SVR4中，如果調(diào)用signal或sigset將SIGCHLD的配置設(shè)置為忽略，則不會(huì)產(chǎn)生 僵死子進(jìn)程。另外，使用SVR4版的sigaction,則可設(shè)置SA_NOCLDWAIT 標(biāo)志以避免子進(jìn)程 僵死。Linux中也可使用這個(gè)，在一個(gè)程序的開始調(diào)用這個(gè)函數(shù)signal(SIGCHLD,SIG_IGN);2) 調(diào)用fork兩次。3) 用waitpid等待子進(jìn)程返回.3，簡述Unix/Linux系統(tǒng)中使用socket庫編寫服務(wù)器端程序的流程，請(qǐng)分別用對(duì)應(yīng)的socket通信函數(shù)表示(10分)TCP socket 通信服務(wù)器端流程如下：1. 創(chuàng)建 ser

6、verSocket2. 初始化serverAddr (服務(wù)器地址)3. 將 socket 和 serverAddr 綁定 bi nd4. 開始監(jiān)聽liste n5. 進(jìn)入while循環(huán)，不斷的 accept接入的客戶端socket，進(jìn)行讀寫操作 write和read6. 關(guān)閉 serverSocket客戶端流程：1. 創(chuàng)建 clientSocket2. 初始化 serverAddr3. 鏈接到服務(wù)器 connect4. 利用write和read進(jìn)行讀寫操作5. 關(guān)閉 clientSocket這個(gè)列表是一個(gè) Berkeley套接字API庫提供的函數(shù)或者方法的概要： socket()創(chuàng)建一個(gè)新的確

7、定類型的套接字，類型用一個(gè)整型數(shù)值標(biāo)識(shí)，并為它分配系統(tǒng)資源。 bind() 一般用于服務(wù)器端，將一個(gè)套接字與一個(gè)套接字地址結(jié)構(gòu)相關(guān)聯(lián)，比如，一個(gè)指定的本 地端口和IP地址。listen()用于服務(wù)器端，使一個(gè)綁定的TCP套接字進(jìn)入監(jiān)聽狀態(tài)。connect()用于客戶端，為一個(gè)套接字分配一個(gè)自由的本地端口號(hào)。如果是TCP套接字的話,它會(huì)試圖獲得一個(gè)新的TCP連接。accept()用于服務(wù)器端。它接受一個(gè)從遠(yuǎn)端客戶端發(fā)出的創(chuàng)建一個(gè)新的TCP連接的接入請(qǐng)求，創(chuàng)建一個(gè)新的套接字，與該連接相應(yīng)的套接字地址相關(guān)聯(lián)。send()和recv(),或者write()和read(),或者recvfrom()和se

8、ndto(),用于往/從遠(yuǎn)程套接字發(fā)送和 接受數(shù)據(jù)。close()用于系統(tǒng)釋放分配給一個(gè)套接字的資源。如果是TCP，連接會(huì)被中斷。gethostbyname()和gethostbyaddr()用于解析主機(jī)名和地址。select()用于修整有如下情況的套接字列表：準(zhǔn)備讀，準(zhǔn)備寫或者是有錯(cuò)誤。poll()用于檢查套接字的狀態(tài)。套接字可以被測試，看是否可以寫入、讀取或是有錯(cuò)誤。getsockopt()用于查詢指定的套接字一個(gè)特定的套接字選項(xiàng)的當(dāng)前值。setsockopt()用于為指定的套接字設(shè)定一個(gè)特定的套接字選項(xiàng)。二、算法與程序設(shè)計(jì)題1，使用C/C+編寫函數(shù)，實(shí)現(xiàn)字符串反轉(zhuǎn)，要求不使用任何系統(tǒng)函數(shù)

9、，且時(shí)間復(fù)雜度最小，函數(shù)原型：char* reverse_str(char* str) 。 (15 分)獲取首尾指針，然后將首尾指針指向的元素交換，將首指針指向下一個(gè)，將尾指針指向前一個(gè)，交換指針指向的元素，然后重復(fù)執(zhí)行，直到首尾指針相遇。2，給定一個(gè)如下格式的字符串(1,(2,3),(4,(5,6),7)括號(hào)內(nèi)的元素可以是數(shù)字，也可以是另一個(gè)括號(hào)，請(qǐng)實(shí)現(xiàn)一個(gè)算法消除嵌套的括號(hào)，比如把上面的表達(dá)式變成：(1,2,3,4,5,6,7)，如果表達(dá)式有誤請(qǐng)報(bào)錯(cuò)。(15分)使用棧和隊(duì)列實(shí)現(xiàn)備注說明，非正文，實(shí)際使用可刪除如下部分。本內(nèi)容僅給予閱讀編輯指點(diǎn)：1、本文件由微軟 OFFICE辦公軟件編輯而成

10、，同時(shí)支持 WPS。2、文件可重新編輯整理。3、建議結(jié)合本公司和個(gè)人的實(shí)際情況進(jìn)行修正編輯。4、因編輯原因，部分文件文字有些微錯(cuò)誤的，請(qǐng)自行修正，并不影響本文閱讀。Note: it is not the text. The following parts can be deleted for actual use. This content only gives reading and editingin structi ons:1. This docume nt is edited by Microsoft office office software and supports WPS.2. The files can be edited and reorga ni zed.3. It is suggested to revise and edit accord ing to the actual situati on of the compa ny and in dividua