*必填

信息

（笔试时间120分钟）

一、简答题（本题共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）用户输入的查询，常常还包含一些上下文的信息（如，“平果手机什么时候发布”），如何利用这些上下文改进纠错的效果？