一、选择题(20*3)
1. 考查改变C++运算符的顺序，输出结果是否一致。例：int a1= b * c / d; int a2 = b / d * c;
int b1 = x << y >> z; int b2 = x >> y << z; int c1 = a + b -c; int c2 = a - c + b;
a1与a2结果是否一致（若b 3. 考栈的，类似考研题，很easy，只要知道栈是FILO的性质就OK。 4.考察栈 5.考察组合数学。比较麻烦。（1）有6*8的表格，求从A->B且不经过C的路径数：（IDK） 6.有3个人到图书馆还书，还有3个人到图书馆借书，若他们要还和借的书是同一种书且图书馆内现在没有此书，求他们要怎么排队才能保证每个人都能借到书。方案数（IDK）。 7. “www.qq.com”中子串的数目，字母相同为同一串。（IDK） 8.考完全二叉树。给出完全儿叉树的节点数，求叶子节点数。 9.考排序。各个排序算法的时间复杂度。 10. 各排序算法是否是稳定的排序。 11.考图论。问从哪个点可以将图一笔画出来。 12.考数据库的操作。问删除表的sql语句。（drop 表名） 13.考网络。（1）问TCP连接断开后的操作，比较麻烦，需要搞懂RST,Finished等的含义及操作。 14. 2）计算机中哪些端口是不能被占用的。（应该是0~1024端口，为专有端口） 15.三个考编译的。（1）问程序预编译、编译、链接、生成过程相关的问题。 16. 2）关于编译优化的说法是否正确。（IDK） 17. （2）关于动态链接和静态链接的说法（动态链接或静态链接是否导致可执行文件变大；动态链接或静态链接哪个速度更快）（IDK） 二、填空题（10*4） 21.是考二进制、十进制和十六进制的运算，会各种进制之间的转换即可。 22.题递归很麻烦，原题如下： int ack(m,n) { if(m==0) return n+1; else if (n==0) return ack(m-1,1); else return ack(m-1,ack(m,n-1)); } 计算ack（3,3）的结果。 23. 有一款网游24小时平均在线人数是5000，平均每人在线2个小时，求平均每分钟有多少人上线。（IDK） 24. 数据库操作，从论坛帖子列表中查出前20个帖子的标题，按照时间排序。（SELECT titles FROM posts ORDER BY create_time DESC LIMIT 0, 20） 25.考查设计模式，是享元模式。 26.很麻烦，涉及到搜索和概率的知识。（IDK） 27. 下1个题是读程序，写出运算结果（easy）。如下 ： int fun(int m, int n) { if(m%n == 0) return n; else return fun(n, m%n); } 求fun(2012, 2102)的值。（fun是求m、n的最大公约数的算法，因此结果为2） 三、附加题（2*10） 1. 已知数组a[n],求数组b[n].要求：b[i]=a[0]*a[1]*……*a[n-1]/a[i]，不能用除法。 a.时间复杂度O(n),空间复杂度O(1)。 b.除了迭代器i,不允许使用任何其它变量（包括栈临时变量等）。 分析：思路是前累加，后累加，然后相乘。即：令a[i] = a[0]*a[1]*……a[i]，b[i] = b[i+1]*b[i+2]*……b[n-1]，则b[i] = a[i-1]*b[i]。关键伪代码如下： int f() { b[n-1] = 1; for(i = n-2; i >= 0; i--) // n >= 2 b[i] = a[i+1]*b[i+1]; for(i = 1; i < n; i++) a[i] = a[i]*a[i-1]; for(i = 1; i < n; i++) b[i] = b[i] * a[i-1]; } 注意：经过以上过程，数组a遭到了破坏。 2. 有一个xx定理，说平均每一个QQ用户可以通过6个其它QQ用户与任一QQ用户发生关系。现有10亿QQ用户的数据，分布在1000台服务器上，好像 让你设计一个算法，来查找A用户与B用户是否可以通过6个其它QQ用户发生关系，若是，则通过的最少QQ用户数目是多少。（IDK）参考：http://blog.csdn.net/v_july_v/article/details/7382693下载本文
