某有名IT企业笔试题分析（篇一）
到了九月份就要找工作了，不太想到了找工作的时候再仓促的准备，平时没事的时候稍稍看看各种笔试题。因为涉及到保密规定，只能不透漏是哪家的笔试题了。今天就奉献下某杭州知名IT企业（如果你懂了就默默放在心里）。由于题目比较多，今天先分析下选择题，为了吃透知识点，其间还会穿插各种知识点补充。
单选题：
1. -7的二进制补码表示为：
A.01111000 B.01111001 C.11111000 D.11111001
这道题很基础，就是考考你关于补码、反码、源码的知识。记住下面规则即可：
1.正数的源码反码和补码都相同，所以没什么好计算的。
2.负数的反码：符号位为“1”，数值部分按位取反。负数的补码：源码的符号位不变，数值部分的各位取反，然后整个数加1。其实就是反码+1
所以答案果断为D。
2.以下四种介质带宽最大的是：
A.同轴电缆 B.双绞线 C.光纤 D.同步线
3.进程阻塞的原因不包括：
A.时间片切换 B.等待I/O C.进程sleep D.等待解锁
如果没有时间片轮转，那么进程就没法切换了，一个进程将独享CPU。但是不能称时间片切换导致进程阻塞。
4.设只含根节点的二叉树高度为1，现有一颗高度为h(h>1)的二叉树上只有出度为0和出度为2的节点，那么这颗二叉树节点最少为：
A.2^h-1 B.2h-1 C.2h D.2h+1
有个讨巧的方法：直接取h=3，画个图看下，显然是5，所以答案为B。
下面来分析下：如果每个节点出度要么为0要么为2，那么也就是要么自己为叶子，要么自己拥有左右儿子。那么什么情况下节点最少呢？直接沿着一条路下去保持出度为2，直到高度达到h，那么此时节点总数：2h-1。
5.给定下面程序，那么执行printf("%d\n",foo(20,13));结果是多少：
int foo(int x,int y)
{
if(x <= 0 || y <= 0)return 1;
return 3*foo(x-6,y/2);
}
A.3 B.9 C.27 D.81
对递归的简单考察，很easy。
6.对于以下说法错误的是：
A.Dijkstra是求两点间最短路径的，复杂度：O(n*n)。
B.Floyd-Warshall是求所有点对之间最短路径的，复杂度：O(n^3)。
C.求n个数中的中位数复杂度最低为：O(n*logn)。
D.基于比较的排序算法复杂度下界为：O(n*logn)。
7.给定一个m行n列的整数矩阵，每行从左到右和每列从上到下都是有序（假设都是升序）的。判断一个整数k是否在矩阵中出现的最优算法，在最坏情况下的时间复杂度是：
A.O(m*n) B.O(m+n) C.O(log(m*n)) D.O(log(m+n))
这道题我觉得可以使用类似二分的方法：直接找到中间一行的中间元素，进行二分，如果比当前元素大，则不可能在左上角那1/4区域内，如果比当前元素小则不可能在右下角那1/4区域内，所以比较一次可以去掉当前区域的1/4大小。那么复杂度就会降低为原先的3/4。T(n) = T(3n/4)+O(1)。解下还是O(log(m*n))。
8.一个包里有5个黑球，10个红球和17个白球。每次可以从中取两个球出来，放置在外面。那么至少取多少次，一定出现过取出一对颜色一样的球。
A.16 B.9 C.4 D.1
这个题目不知道想考察什么，觉得没什么陷阱，极限情况是：前十次每次取1个红球和1个白球，中间五次，每次取1个黑球和1个白球。最后当第十六次的时候才能取到一对颜色相同的球。所以至少要十六次。
9.题目过长，懒得type了，是一道估计内存的题目。
10.骑士只说真话，骗子只说假话。下列场景能确定一个骑士、一个骗子的有？
A.甲说：“我们中至少有一个人说真话”，乙什么也没说。
B.甲说："我们两个都是骗子"，乙什么也没说。
C.甲说：“我是个骗子或者乙是个骑士”，乙什么也没说。
D.甲乙都说：“我是个骑士”。
E.甲说：“乙是个骑士”，乙说：“我们俩一个是骑士一个是骗子”。
分析一下：是道逻辑题。
A.如果甲是骑士，那么因为至少一个人说真话，那么有可能乙也说真话。那么可能甲乙都是骑士。如果甲是骗子，那么没有一个人说真话，那么都是骗子。排除。
B.如果甲是骑士，那么不可能说这样的话，因为骑士不会说自己是骗子。那么甲是骗子，甲说的是假话，那么至少一个不是骗子。那么乙就是骑士。可以。
C.如果甲是骑士，那么必然乙也是骑士。不符合。如果甲是骗子，那么必然乙也不是骑士，这句话才能是假的。排除。
D.如果甲乙都是骑士，显然成立。排除。
E.如果甲是骑士，那么乙也是骑士，与乙说的话矛盾。如果甲是骗子，那么乙必然不是骑士。排除。
因为题目都是师兄们手机照下来的，所以需要type，累啊。今天先搞十道单选题吧。明天继续多选题。