2019年百度校園招聘筆試題精選(二)

　解答：(1)輪詢調度的原理是每一次把來自用戶的請求輪流分配給內部中的服務器，從1開始，直到N(內部服務器個數)，然后重新開始循環。只有在當前任務主動放棄CPU控制權的情況下(比如任務掛起)，才允許其他任務(包括高優先級的任務)控制CPU。其優點是其簡潔性，它無需記錄當前所有連接的狀態，所以它是一種無狀態調度。但不利于后面的請求及時得到響應。

　　(2)搶占式調度允許高優先級的任務打斷當前執行的任務，搶占CPU的控制權。這有利于后面的高優先級的任務也能及時得到響應。但實現相對較復雜且可能出現低優先級的任務長期得不到調度。

　　3. 列出數據庫中常用的鎖及其應用場景

　　解答：數據庫中的鎖是網絡數據庫中的一個非常重要的概念，它主要用于多用戶環境下保證數據庫完整性和一致性。各種大型數據庫所采用的鎖的基本理論是一致的，但在具體實現上各有差別。目前，大多數數據庫管理系統都或多或少具有自我調節、自我管理的功能，因此很多用戶實際上不 清楚鎖的理論和所用數據庫中鎖的具體實現。在數據庫中加鎖時，除了可以對不同的資源加鎖，還可以使用不同程度的加鎖方式，即鎖有多種模式，SQL Server中鎖模式包括：

　　1)共享鎖

　　SQL Server中，共享鎖用于所有的只讀數據操作。共享鎖是非獨占的，允許多個并發事務讀取其鎖定的資源。默認情況下，數據被讀取后，SQL Server立即釋放共享鎖。例如，執行查詢“SELECT FROM my_table”時，首先鎖定第一頁，讀取之后，釋放對第一頁的鎖定，然后鎖定第二頁。這樣，就允許在讀操作過程中，修改未被鎖定的第一頁。但是，事務 隔離級別連接選項設置和SELECT語句中的鎖定設置都可以改變SQL Server的這種默認設置。例如，“ SELECT FROM my_table HOLDLOCK”就要求在整個查詢過程中，保持對表的鎖定，直到查詢完成才釋放鎖定。

　　2)修改鎖

　　修 改鎖在修改操作的初始化階段用來鎖定可能要被修改的資源，這樣可以避免使用共享鎖造成的死鎖現象。因為使用共享鎖時，修改數據的操作分為兩步，首先獲得一 個共享鎖，讀取數據，然后將共享鎖升級為獨占鎖，然后再執行修改操作。這樣如果同時有兩個或多個事務同時對一個事務申請了共享鎖，在修改數據的時候，這些 事務都要將共享鎖升級為獨占鎖。這時，這些事務都不會釋放共享鎖而是一直等待對方釋放，這樣就造成了死鎖。如果一個數據在修改前直接申請修改鎖，在數據修 改的時候再升級為獨占鎖，就可以避免死鎖。修改鎖與共享鎖是兼容的，也就是說一個資源用共享鎖鎖定后，允許再用修改鎖鎖定。

　　3)獨占鎖

　　獨占鎖是為修改數據而保留的。它所鎖定的資源，其他事務不能讀取也不能修改。獨占鎖不能和其他鎖兼容。

　　4)結構鎖

　　結構鎖分為結構修改鎖(Sch-M)和結構穩定鎖(Sch-S)。執行表定義語言操作時，SQL Server采用Sch-M鎖，編譯查詢時，SQL Server采用Sch-S鎖。

　　5)意向鎖

　　意 向鎖說明SQL Server有在資源的低層獲得共享鎖或獨占鎖的意向。例如，表級的共享意向鎖說明事務意圖將獨占鎖釋放到表中的頁或者行。意向鎖又可以分為共享意向鎖、 獨占意向鎖和共享式獨占意向鎖。共享意向鎖說明事務意圖在共享意向鎖所鎖定的低層資源上放置共享鎖來讀取數據。獨占意向鎖說明事務意圖在共享意向鎖所鎖定 的低層資源上放置獨占鎖來修改數據。共享式獨占鎖說明事務允許其他事務使用共享鎖來讀取頂層資源，并意圖在該資源低層上放置獨占鎖。

　　6)批量修改鎖

　　批量復制數據時使用批量修改鎖。可以通過表的TabLock提示或者使用系統存儲過程sp_tableoption的“table lock on bulk load”選項設定批量修改鎖。

　　二、算法設計題1. 給定N是一個正整數，求比N大的最小“不重復數”，這里的不重復是指沒有兩個相等的相鄰位，如1102中的11是相等的兩個相鄰位故不是不重復數，而12301是不重復數。

　　算法：當然最直接的方法是采用暴力法，從N+1開始逐步加1判斷是否是不重復數，是就退出循環輸出，這種方法一般是不可取的，例如N=11000000，你要一個個的加1要加到12010101，一共循環百萬次，每次都要重復判斷是否是不重復數，效率極其低下，因此是不可取的。這里我采用的方法是：從N+1的最高位往右開始判斷與其次高位是否相等，如果發現相等的(即為重復數)則將次高位加1，注意這里可能進位，如8921―>9021，后面的直接置為010101...形式，如1121―>1201，此時便完成“不重復數”的初步構造，但此時的“不重復數”不一定是真正的不重復的數，因為可能進位后的次高位變為0或進位后變成00，如9921―>10001，此時需要再次循環判斷重新構造直至滿足條件即可，這種方法循環的次數非常少，我認為不超過3次就能滿足條件。