金山软件技术笔试试题及答案

今天参加了金山软件的笔试。地点：华工A4-301，时间：14:00~17：00
参加C 、服务端开发的人比较多一个教室只剩下很少的空位，实在太满了，另有一些人安排到其它教室。
人虽然很多，但是不少人是来“考察”的。我旁边就有一位，只填了最后边的一道软件设计题，然后就交卷了。
题目分为三部分，第一部分是C 、第二部分是算法、第三部分是程序设计。
C 的考察内容包括：
1。（1） 写出C 的四种类型转换。
我的理解：
四种，答题的时候我忘了reinterpret_cast怎么拼写。要求写成示例代码， 不过我没写（没上下文环境，还得我自个去自定义类型，太费事了） 。
（2）explicit关键字的作用。
我的理解：
去除隐式转换。
（3）虚析构函数。
我的理解： 在一个继承体系中，基类的析构函数必须设置为虚函数，不然可能存在析构不完整的危险。
2、 是一个改错题。大概考察的知识是：vector、多态、虚函数表指针。
我的理解：
（1）要实现多态，vector里边保存的必须是地址（指针） ，而不能是基类、引用。
（2）定义vector的const_iterator。
（3）派生类的构造函数是在派生类对象构造的最后阶段才被调用的，当调用构造函数的时候，对象的基类子对象、成员变量（对象）已经初始化完毕。所以派生类的构造函数不可以乱来。
3、容器的传参和erase操作
给出的是一个函数，其中关键的部分大概是这样：
for(vector::iterator iter = ivec.begin(); iter != ivec.end(); iter)
{
if (*iter == N)
ivec.erase(iter);
}
我的理解：
（1） 容器类对象传参的时候最好用引用。
（2） erase操作之后会导致迭代器失效。
（3） 可能会导致删除不彻底，因为erase之后iter指向了下一个元素，而for循环中又 iter，这样会跳过一个元素，而且可能跳到vector对象之外的地方，最后导致出错。 （我只考虑到会跳过一个元素，没有想到如果最后一个被删元素刚好是vector对象的后一个元素，那么会跳出对象之外的地方。其实这个问题几个星期前在csdn上回答过，不过我通过上机得出的答案一下子就被我抛到脑后）
4、 智能指针。
大概意思是：引用计数型的智能指针存在循环引用的缺陷，需要一个“弱引用”智能指针。大概是要求实现这两个智能指针。
我的理解：
很遗憾。我想题目是想答题者实现boost库里的shared_ptr和weak_ptr，我知道这两个指针的存在，但问题是我没考虑过它们是怎么实现的。主要是弱指针不知道该怎么做。引用计数型的智能指针凑合着写了出来，不过写得超乱，而且构造函数有错误。
一方面是很少用手写代码，一方面是几乎没有自己亲手写过智能指针，虽然分析学习了不少简单例子。虽然以前看书的时候看到“循环引用”这回事，只是当时不知道是什么，现在依然不知道，忘了问why。
算法考察的内容：
1、 有一个N位二进制数，找出其中没有相邻11的数的个数。例如：N=2时，00,01,10,11，其中没有
相邻11的数的个数有3个。
我的理解：
求相邻11的数的个数。
N位数跟N-1位数有关系。如果一个数在N-1中是“相邻11” ，那么在这个数前面添加上0或1它还是一个相邻11的数。这里边就至少有两倍的关系了。另外，如果N-1中有数是这样的： “10XXX” ，那么在N位数中，在它前面添加上1这个数就是“相邻11”了。那么N-1位数中有多少个“10XXX”这样的数字呢？对于N-1位的数来说， 如果头一两位是“10” ，后边就还有N-3位的二进制位，所以以“10”开头的数有2的(N-3)次方个。
列出如下：N就是在N-1的数前面加上1、0。
N=2
00 01 10 11

N=3
000 001 010 011
100 101 110 111

N=4
0000 0001 0010 0011
1000 1001 1010 1011

0100 0101 0110 0111
1100 1101 1110 1111
感觉这就是数字的组合的问题。另外，上边是我个人的理解，也不一定是对的。

（结果证明，我真的错了，唯一一道会写的算法题，泪奔……）
修正：非相邻11的数字的个数正如楼下所说是斐波那契序列。因为我一开始就没往“非相邻11”方向想，而是往“相邻11”方向考虑，所以没发觉另一个方向其实有捷径可通…….但我还是想把这条路走完，虽然走了弯路。
我的分析出差错的原因在这里： “所以以 “10” 开头的数有2的(N-3)次方个” ， 这句话没错， 但是没考虑到这(N-3)个位里也有可能存在“相邻11” ，导致了重复计算“相邻11”的数。必须减去才行。计算“相邻11”个数的函数如下：
int fun(int n)
{
if (n <= 1)
return 0;
if (n == 2)
return 1;
if (n == 3)
return 3;
return ((fun(n-1))*2 (2<}
以上方式实现比较垃圾。比较好的方式有（第二种更好一些，但第一种的思路很值得学习） ：

实现：动态规划，递推算法
*参考：
用动态规划的东西 "[j]保存i位长的二进制位，最后一位是j" 的时候的个数，那么
[0] = [i - 1][1] [i - 1][0];
[1] = [i - 1][0];
*/
//2010.9.19
#include
using namespace std;
int fun(int N);
int main()
{
int N;
cout << "Input N:" << endl;
cin >> N;
cout << fun(N) << endl;
return 0;
}
/////////////////////////////////////////////////////////////////////
int fun(int N)
{
//申请空间。时间换空间
int **p = new int*[N];
for (int i = 0; i != N; i)
{
p = new int[2];
}
//算法核心。递推。
p[0][0] = 1;
p[0][1] = 1;
for (int i = 1; i < N; i)
{




//求i个二进制位以0结尾的非11相邻数：i-1个二进制位的非"11相邻"数，后边填加上一个0,必定也是
非11相邻数
p[0] = p[i-1][0] p[i-1][1];
//求i个二进制位以1结尾的非11相邻数：i-1个二进制位的非"11相邻"数必须以0结尾.
p[1] = p[i-1][0];
}
//保存返回值
int ret = p[N-1][0] p[N-1][1];
//释放空间
for (int i = 0; i != N; i)
{
delete[] p;
}
delete[] p;
return ret;
}
(2)
//实现：斐波那契数列实现
/*参考：
通过列出非相邻11的数的个数，可以发现其实这个就是斐波那契数列。2,3,5,8,13，……
*/
//2010.9.19
#include
using namespace std;
int fun(int n);
int main()
{
int n;
cout << "Input N:" << endl;
cin >> n;
cout << fun(n) << endl;
return 0;
}
int fun(int n)
{
if (n == 1)
return 2;
if (n == 2)
return 3;
int f1 = 2;
int f2 = 3;
int f3;
for (int i = 2; i < n; i)
{



22
f3 = f1 f2;
f1 = f2;
f2 = f3;
}
return f3;
}
2、 对一个服务器日志的分析。
日志里边记录了IP登录信息，信息内容有时间和IP地址。现在要统计
（1） 每一天登录次数最多的1000个IP。以登录次数为序，从高到低排序
（2） 每一周登录次数最多的1000个IP。以登录次数为序，从高到低排序
每一天大概有10亿条IP信息记录。
我的理解：
开始以为是位图的内容，后来又想可不可以分段。结果都是错误的想法。这类题不懂。
3、 图相关的内容
第一个小问就是求一个有向图是否有环路，另一个小问题忘了记。感觉这种题有点熟悉，但就是忘了该怎么做。可能大二在anyview里边做过类似的。可惜，数据结构的知识在我做完anyview里边的题之后就几乎没碰它了。
算法题对于有经常学算法的人来说应该是很容易的，第二题在csdn上经常看到类似的，就是一大堆数然后让你排序或者记录不出现的大概这些，不过我都没有深入的去记忆、理解。第三题如果有复习数据结构的第七章那应该就没问题了。第一题就更不用说了，不懂算法的我都会写，学过算法的应该可以轻松搞定。
程序设计考察的内容：
有很多的题目让你选择，选择一个题目然后尽可能详细的实现它。记得有聊天室相关的、windows画图功能相关的、多线程客户端下载相关的。
我的理解：
因为软件工程的课程设计就是做FTP客户端，所以就选择那个多线程客户端下载。不过，我之前写的那个并没有多线程下载，虽然有用到多线程，但那只是用来区分工作线程跟界面线程而已，而且完全是API实现，跟面向对象不相干。所以这道题我也是写得很马虎，就说设计几个类，然后把线程封装在类里边，写了跟没写差不多。

总结：
对于C 某些方面我学得很深入 （花了整个暑假的大部分时间） ， 某些方面只是了解而已 （如模板、 RTTI、异常处理、IO库） ，还有的完全不懂（如模板元编程、boost库） 。对于算法，还没复习，几乎完全不懂，数据结构也是。对于程序设计，没有经历过大的项目，很多面向对象的思路仅仅是听说了一点，可以说是不懂。
对于这次笔试，题目比较意外。我报的方向是C 开发，涉及到一点安全。我本来以为应该会有windows相关的知识（如：dll、内存映射、钩子、进程、线程等） ，应该会有X86相关的知识（如：一些基本的指令，调试必须懂的） ，应该会有很经典的：内存对齐、链表操作、动态内存操作等等这些。可能是因为C 开发跟其它开发混合在一起了，所以那些内容都没有了。~~想我放弃复习图，转而复习win32汇编，可怜我昨夜复习win32汇编到1点半，导致慢性咽炎又严重爆发…………
不管怎么样，总算是参加了C 的笔试，虽说答得乱七八糟，但我还是希望第一次就成功。

之前题目的第一题忘了部分题目，之前算法的第一题思路有错误。应该差不多了。--