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

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

2.請列舉面向?qū)ο笤O(shè)計的三個基本要素及五種主要設(shè)計原則。(10分)

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

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

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

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

現(xiàn)在需要你設(shè)計一個算法來實現(xiàn)這樣的功能：

/@brief: query match function

@param worddcit:字符串集合，可以在這兒自定義詞典的數(shù)據(jù)結(jié)構(gòu)worddic;

@param query: query;

@param querylen: query的長度;

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

/

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

要求：給出數(shù)據(jù)結(jié)構(gòu)dict的設(shè)計并完成check_query函數(shù)(20分)

三、系統(tǒng)設(shè)計題(本題共35分)

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

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

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

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