金山产品笔试题目

一、二进制数模式考虑n位二进制数，有多少个数中不存在两个相邻的1。例如，3位数中有5个数符合这一要求：000、001、010、100、101。

1、试找出其中的规律

2、请给出完整代码实现(参数输入代码可略)

3、试证明你找到的规律是正确的

二、对象速查表假设需要实现一个对象速查表，具体的要求如下：

1.该表中将保存大量(几千万个)对象地址(指针)，以下称为记录

2.支持频繁查询一个指针是否记录在表中3.支持频繁添加和删除记录请尝试给出几种可能的实现方式，并对其运行效率作出比较。对你认为最优的方案给出主要部分伪代码。

三、迷宫给定一个迷宫，它除了墙之外，还有门和钥匙。其中，钥匙和门放在不同的地方，并为双射关系(一扇门只对应一把钥匙，反之亦同)。

1、给定一个没有门的迷宫，以及起点和终点，请给出最短路径;

2、给定有门和钥匙的.迷宫、起点和终点，请给出一条路径;

3、给定有门和钥匙的迷宫、起点和终点，请给出最短路径;请给出上述算法思路，和主要部分伪代码。

四、软件设计

请从以下几个命题中任选一个，以自己熟悉的方式给出该软件的尽可能详细的设计： 

类似Winzip的压缩软件(压缩算法不需要设计) 

一个简单的绘图程序(类似Windows画笔)

一个多线程下载客户端(协议可以使用HTTP/FTP或自拟)