*必填

信息

（笔试时间120分钟）

一、简答题（本题共30分）

1.简述数据库以及线程死锁产生的原理及必要条件，简述如何避免死锁。（10分）

2.请列举面向对象设计的三个基本要素及五种主要设计原则。（10分）

3.简述windows内存管理的几种方式以及优缺点。（10分）

二、算法与程序设计（本题共45分）

1．公司组织一次羽毛球比赛，采用淘汰制，假设公司共有1001个人，如果要评出“公司羽毛球第一高手”的称号，至少需要进行多少场比赛？请简述设计过程，并编写代码模拟比赛过程（语言不限，可以使用伪代码）。（15分）

2.一百个灯泡排成一排，第一轮将所有灯泡打开；第二轮每隔一个灯泡关掉一个，即排在偶数的灯泡都被关掉。第三轮每隔两个灯泡，将开着的灯泡关掉，关掉的灯泡打开。以此类推，第100轮结束的时候，还有几盏灯泡亮着？（15分）

3.实现字符串循环左移算法，函数定义为：void StringRotate(char* pszString, int nCharsToRotate)，执行后pszString为旋转后字符串

说明：字符串循环左移n位定义为：把字符串头部n个字符移动到字符串尾部。如：对字符串ABCDEFG左旋转3位则得到DEFGABC

要求：对长度为N的字符串操作的时间复杂度为O(N)，空间复杂度为O(1))（15分）

三、系统设计题（本题25分）

现在由10万条数据需要放到内存中，并对外提供查询服务；数据的格式是一个key，对应一个value，key定长是16字节，每个key是唯一的，value是定长1M字节；有6台机器，每台机器的内存是64G；请设计一个存储系统，要求7×24小时的服务。描述其实现思路。

注：有些机器不稳定，有可能随时down机。