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