一、簡(jiǎn)答題(本題共30分)

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

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

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

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

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

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

現(xiàn)在需要你設(shè)計(jì)一個(gè)算法來(lái)實(shí)現(xiàn)這樣的功能：

/@brief: query match function

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

@param query: query;

@param querylen: query的長(zhǎng)度;

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

一般來(lái)說(shuō)，拼寫(xiě)糾錯(cuò)主要包括了兩個(gè)重要的步驟：一是識(shí)別用戶(hù)輸入的錯(cuò)誤的詞語(yǔ);二是把錯(cuò)誤的詞語(yǔ)修改成正確的詞語(yǔ)。

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

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