一、簡答題(本題共30分)

1.簡述數據庫以及線程死鎖產生的原理及必要條件，簡述如何避免死鎖。(10分)

2.請列舉面向對象設計的三個基本要素及五種主要設計原則。(10分)

3.多線程如何同步。(10分)

二、算法與程序設計(本題共45分)

1.一百個燈泡排成一排，第一輪將所有燈泡打開;第二輪每隔一個燈泡關掉一個，即排在偶數的燈泡都被關掉。第三輪每隔兩個燈泡，將開著的燈泡關掉，關掉的燈泡打開。以此類推，第100輪結束的時候，還有幾盞燈泡亮著。編寫代碼實現。(15分)

2.有一個百萬級的字符串集合(worddic)，worddict中每個字符串的長度為2~5個漢字。對任意一個查詢串(query)，定義該query對worddic模糊匹配的條件為：該query內部移除最多6個連續漢字后，與worddic中某個詞完全匹配。例如：worddic中有"百度公司"這個字符串，query"北京百度網絡技術有限公司"，該query即可通過移除6個連續字符('網絡技術有限')來匹配"百度公司";

現在需要你設計一個算法來實現這樣的功能：

/*@brief: query match function

*@param worddcit:字符串集合，可以在這兒自定義詞典的數據結構worddic;

*@param query: query;

*@param querylen: query的長度;

*@param return: 1表示該query可以模糊匹配詞典中某個字符串，-1表示其它;

*/

int check_query(const dict *worddict, const char *query, const int querylen);

要求：給出數據結構dict的設計并完成check_query函數(20分)

三、系統設計題(本題共35分)

1.拼寫糾錯是搜索引擎具備的一個功能，指的是自動分析用戶輸入的查詢(query)，檢查是否有拼寫錯誤，如果有，則給出正確的拼寫建議。例如：把"聯想手機"輸錯為"聯想手機"。這時候搜索引擎一般會給出提示"您要找的是不是：聯想手機"。

一般來說，拼寫糾錯主要包括了兩個重要的步驟：一是識別用戶輸入的錯誤的詞語;二是把錯誤的詞語修改成正確的詞語。

問題：1)在中文中，常見的錯誤輸入是同音不同字：例如，"蘋果"輸錯為"果";在英文中，常見的錯誤輸入時拼寫錯誤，如"latest"錯輸為"latst"。針對以上兩種在中文和英文輸入中的錯誤，請分別給出一種解決方案。

2)用戶輸入的查詢，常常還包含一些上下文的信息(如，"果手機什么時候發布")，如何利用這些上下文改進糾錯的效果?