第三波笔试题（Vmware EMC 完美时空）
VMware:
1. 猫和老鼠玩象棋，玩了M+N局，猫赢了M局 老鼠赢了N局 N>M，而且在整个过程中，猫的得分从来没有超过过老鼠，问共有多少种可能的比赛得分过程

2. 100个人排队上飞机，飞机上有100个座位，每个人对应一个座位，队首的人是个瞎子，上飞机后随便坐，后面的人都尽量找自己的座位，如果已经被占，则随机做，问第100个人坐到自己座位的概率

EMC
3.补充语句，使下面程序if判断语句始终为真，不能改动if判断语句，即只能在之前加语句

if ((*f = 0)||(void *)f == (void *)&f)
{
/* statements always executed*/
}

4.找一颗二叉树中随机两个节点的最近公共祖先

完美时空

5.定义一个结构体，来表示以下文件头结构

域名称 地址偏移 占用字节
文件名 0x0000 4
文件大小 0x0004 2
数据量大小 0x0006 4
x坐标 0x0010 2
y坐标 0x0012 2



[解决办法]
VMware 第一题，类似catalan数，c(m+n,m) - c(m+n,m-1)，以前讨论过。其他题等别人解答吧！
[解决办法]
4.找一颗二叉树中随机两个节点的最近公共祖先
应该可以在每个节点中包含指向父节点的指针，然后比较两个节点的所有父辈节点，看看是否有相等的，返回这个相等的节点.. 这样应该可以...
[解决办法]
题有点老啊,傻子上飞机那题三年前就看过了
[解决办法]
1.不懂，仔细想想。。。
2.编程之美的两个类似题中的第二个，
第i个人的概率是(n-i+1)/(n-i+2)N是总人数
5.dfs+并查集能处理一堆询问
随机的话，估计是这个解法
直接求的话
要预处理，时间复杂度要高些