*必填

信息

（笔试时间120分钟）

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

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

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

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

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

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

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

3.有一个nxn的方格代表的迷宫，黑色格子表示无法通过，白色格子表示可用通过，人只可以在上下左右方向的可以通行的白色格子之间移动，假如人处于迷宫总某个位置，如何用最短的时间找出一条最短的路径，以便从迷宫中走出来？

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

设计一个日访问量大约百万级别类似百度空间这样的社交分享类的网站，（写消息或写文章请求数）：（浏览请求数）的比率小于1/5。请给出你系统的架构设计。如果日访问量达到10亿，那系统架构设计需要哪些优化，来保证服务7*24小时稳定运行。