*必填

信息

（笔试时间120分钟）

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

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

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

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

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

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

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

3.k近邻方法（k nearest neighbor）是常用的分类算法之一，给定训练数据集D=(xⁱ,yⁱ),i=1…n，其中xⁱ∈R^p是一个p维实数空间中的向量，yⁱ∈{0,1}是xi对应的类标。（15分）

①给定一个待分类样例x∈R^p，要求获得他的预测分类y∈{0,1}。请写出k邻近分类算法。

②给定一个变长的p维的立方体，训练数据D均匀的在立方体内，待预测样例x∈R^p是位于原点o。近似的，我们认为位于原点边长为l的p维立方体内的样本均为邻近，如下图所示。如果我们希望选所有数据中r(0

③接第二问，当p=10时，分别取r=0.01和r=0.1的情况下边长l分别等于多少？通过分析l的取值以及l随p变化的趋势，试简略解释机器学习中的维数灾难问题，（参考数据：10^-0.1=0.794; 10^-0.2=0.631; 10^-0.3=0.501; 10^-0.4=0.398）

④简要描述一种解决维灾的方法。