百度2013研發工程師筆試卷B

三個基本元素：

封裝

繼承

多态

五個基本原則：

單一職責原則（single-resposibility principle）:一個類，最好隻做一件事，隻有一個引起它的變化。單一職責原則可以看做是低耦合、高内聚在面向對象原則上的引申，将職責定義為引起變化的原因，以提高内聚性來減少引起變化的原因。

開放封閉原則（open-closed principle）:軟體實體應該是可擴充的，而不可修改的。也就是，對擴充開放，對修改封閉的。

liskov替換原則（liskov-substituion principle）:子類必須能夠替換其基類。這一思想展現為對繼承機制的限制規範，隻有子類能夠替換基類時，才能保證系統在運作期内識别子類，這是保證繼承複用的基礎。

依賴倒置原則（dependecy-inversion principle）:依賴于抽象。具體而言就是高層子產品不依賴于底層子產品，二者都同依賴于抽象；抽象不依賴于具體，具體依賴于抽象。

接口隔離原則（interface-segregation principle）:使用多個小的專門的接口，而不要使用一個大的總接口。

産生死鎖的原因主要是：

因為系統資源不足。

程序運作推進的順序不合适。

資源配置設定不當等。

産生死鎖的四個必要條件：

互斥條件：一個資源每次隻能被一個程序使用。

請求與保持條件：一個程序因請求資源而阻塞時，對已獲得的資源保持不放。

不剝奪條件:程序已獲得的資源，在末使用完之前，不能強行剝奪。

循環等待條件:若幹程序之間形成一種頭尾相接的循環等待資源關系。

top-k問題，用個數為k的最小堆歸并處理

比如abcdefg，移3位變defgabc，要求空間複雜度o（1），時間複雜度o（n）。

現在有一個手機，手機上的鍵盤上有這樣的對應關系，2對應”abc”,3對應”def”…..手機裡面有一個userlist使用者清單，當我們輸入942的時候出來拼音的對應可能是“xia”，“zha”，“xi”，“yi”等，當我們輸入9264的時候出來是yang，可能是“樣”，“楊”，“往”等，現在我們輸入一個字元串數字，比如926等，要在電話簿userlist中查找出對應的使用者名和電話号碼并傳回結果。

答案：

1．對于每盞燈，拉動的次數是奇數時，燈就是亮着的，拉動的次數是偶數時，燈就是關着的。

2．每盞燈拉動的次數與它的編号所含約數的個數有關，它的編号有幾個約數，這盞燈就被拉動幾次。

3．1——100這100個數中有哪幾個數，約數的個數是奇數。我們知道一個數的約數都是成對出現的，隻有完全平方數約數的個數才是奇數個。 是以這100盞燈中有10盞燈是亮着的。 它們的編号分别是： 1、4、9、16、25、36、49、64、81、100。

分頁存儲管理基本思想：

使用者程式的位址空間被劃分成若幹固定大小的區域，稱為“頁”，相應地，記憶體空間分成若幹個實體塊，頁和塊的大小相等。可将使用者程式的任一頁放在記憶體的任一塊中，實作了離散配置設定。

分段存儲管理基本思想：

将使用者程式位址空間分成若幹個大小不等的段，每段可以定義一組相對完整的邏輯資訊。存儲配置設定時，以段為機關，段與段在記憶體中可以不相鄰接，也實作了離散配置設定。

段頁式存儲管理基本思想：

分頁系統能有效地提高記憶體的使用率，而分段系統能反映程式的邏輯結構，便于段的共享與保護，将分頁與分段兩種存儲方式結合起來，就形成了段頁式存儲管理方式。

在段頁式存儲管理系統中，作業的位址空間首先被分成若幹個邏輯分段，每段都有自己的段号，然後再将每段分成若幹個大小相等的頁。對于主存空間也分成大小相等的頁，主存的配置設定以頁為機關。

段頁式系統中，作業的位址結構包含三部分的内容：段号 頁号 頁内位移量

程式員按照分段系統的位址結構将位址分為段号與段内位移量，位址變換機構将段内位移量分解為頁号和頁内位移量。

為實作段頁式存儲管理，系統應為每個程序設定一個段表，包括每段的段号，該段的頁表始址和頁表長度。每個段有自己的頁表，記錄段中的每一頁的頁号和存放在主存中的實體塊号。