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

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

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

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

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

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

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

現(xiàn)在需要你設(shè)計(jì)一個(gè)算法來實(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可以模糊匹配詞典中某個(gè)字符串，-1表示其它;

*/

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

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

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

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

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

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

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