淘宝2012笔试（研发类）
请给位大牛给出参考答案
一、单选题
1、我们有很多瓶无色的液体，其中有一瓶是毒药，其它都是蒸馏水，实验的小白鼠喝了以后会在5分钟后死亡，而喝到蒸馏水的小白鼠则一切正常。现在有5只小白鼠，请问一下，我们用这五只小白鼠，5分钟的时间，能够检测多少瓶液体的成分（）
a 5瓶 b 6 c 31 d 32
2、若某链表最常用的操作是在最后一个结点之后插入一个结点和删除最后一个结点，则采用（）存储方式最节省时间？
A 单链表 B 带头结点的非循环双链表 C 带头节点的双循环链表 D 循环链表
3、如果需要对磁盘上的1000W条记录构建索引，你认为下面哪种数据结构来存储索引最合适？（）
A Hash Table B. AVL-Tree C. B-Tree D. List
4、可用来检测一个web服务器是否正常工作的命令是（）
A ping B tracert C. telnet D. ftp
5、下面哪个操作是Windows独有的I/O技术（）
A. Select B.Poll C.IOCP D. Epoll
6、IPV6地址包含了（）位
A. 16 B. 32 C. 64 D.128
7、数据库里建索引常用的数据结构是（）
A 链表 B队列 C 树 D 哈希表
8、在公司局域网上ping www.taobao.com没有涉及到的网络协议是（）
A. ARP B. DNS C. TCP D. ICMP
二、填空题
1、http属于（）协议，ICMP属于（）协议
2、深度为k的完全二叉树至少有（）个结点，至多有（）个结点
3、字节为6位的二进制有符号整数，其最小值是（）
4、设有28盏灯，拟公用一个电源，则至少需有4插头的接线板数（）个。
三、综合题
1、有一颗结构如下的树，对其做镜像反转后如下，请写出能实现该功能的代码。注意：请勿对该树做任何假设，它不一定是平衡树，也不一定有序。
1 1
/ | \ / | \
2 3 4 4 3 2
/|\ /\ | | / \ / | \
6 5 7 8 9 10 10 9 8 7 5 6
2、假设某个网站每天有超过10亿次的页面访问量，出于安全考虑，网站会记录访问客户端访问的ip地址和对应的时间，如果现在已经记录了1000亿条数据，想统计一个指定时间段内的区域ip地址访问量，那么这些数据应该按照何种方式来组织，才能尽快满足上面的统计需求呢，设计完方案后，并指出该方案的优缺点，比如在什么情况下，可能会非常慢？
四、附加题
1、写出C语言的地址对齐宏ALIGN（PALGNBYTES），其中P是要对齐的地址，ALIGNBYTES是要对齐的字节数（2的N次方），比如说：ALIGN(13,16)=16
2、在高性能服务器的代码中经常会看到类似这样的代码：
typedef union
{
erts_smp_rwmtx_t rwmtx;
byte cache_line_align_[ERTS_ALC_CACHE_LINE_ALIGN_SIZE(sizeof(erts_smp_rwmtx_t))];
}erts_meta_main_tab_lock_t;
erts_meta_main_tab_lock_t main_tab_lock[16];
请问其中用来填充的cache_line_align的作用是？
3、在现代web服务系统的设计中，为了减轻源站的压力，通常采用分布式缓存技术，其原理如下图所示，前端的分配器将针对不同内容的用户请求分配给不同的缓存服务器向用户提供服务。
分配器
/ | \
缓存 缓存 ...缓存
服务器1 服务器2 ...服务器n
1）请问如何设置分配策略，可以保证充分利用每个缓存服务器的存储空间（每个内容只在一个缓存服务器有副本）
2）当部分缓存服务器故障，或是因为系统扩容，导致缓存服务器的数量动态减少或增加时，你的分配策略是否可以保证较小的缓存文件重分配的开销，如果不能，如何改进？
3）当各个缓存服务器的存储空间存在差异时（如有4个缓存服务器，存储空间比为4：9：15：7），如何改进你的策略，按照如上的比例将内容调度到缓存服务器？
[解决办法]
一、单选题1、我们有很多瓶无色的液体，其中有一瓶是毒药，其它都是蒸馏水，实验的小白鼠喝了以后会在5分钟后死亡，而喝到蒸馏水的小白鼠则一切正常。现在有5只小白鼠，请问一下，我们用这五只小白鼠，5分钟的时间，能够检测多少瓶液体的成分（D）a 5瓶 b 6 c 31 d 322、若某链表最常用的操作是在最后一个结点之后插入一个结点和删除最后一个结点，则采用（C）存储方式最节省时间？A 单链表 B 带头结点的非循环双链表 C 带头节点的双循环链表 D 循环链表3、如果需要对磁盘上的1000W条记录构建索引，你认为下面哪种数据结构来存储索引最合适？（C）A Hash Table B. AVL-Tree C. B-Tree D. List4、可用来检测一个web服务器是否正常工作的命令是（C）A ping B tracert C. telnet D. ftp5、下面哪个操作是Windows独有的I/O技术（C）A. Select B.Poll C.IOCP D. Epoll6、IPV6地址包含了（D）位A. 16 B. 32 C. 64 D.1287、数据库里建索引常用的数据结构是（C）A 链表 B队列 C 树 D 哈希表8、在公司局域网上ping www.taobao.com没有涉及到的网络协议是（C）A. ARP B. DNS C. TCP D. ICMP二、填空题1、http属于（应用层）协议，ICMP属于（网络IP层）协议2、深度为k的完全二叉树至少有（2^k）个结点，至多有（2^(k+1)-1）个结点3、字节为6位的二进制有符号整数，其最小值是（-2^48+1）4、设有28盏灯，拟公用一个电源，则至少需有4插头的接线板数（9）个。
[解决办法]
具体算法不推导了 鄙人给出一个规律
1只老鼠 可以最多判断2瓶毒药 2^1
2只最多判断 4瓶毒药 2^2
3只 8 2^3
1 喝 1357
2 喝 2356
3 喝 4567
如果1 死 2 3 活 则 第1瓶有毒 二进制 也就是 001
如果2 死 1 3 活 则 第2瓶有毒 二进制 也就是 010
如果1 2 死 3 活 则 第3瓶有毒 二进制 也就是 011
如果3 死 1 2 活 则 第4瓶有毒 二进制 也就是 100
如果1 3 死 2 活 则 第5瓶有毒 二进制 也就是 101
如果2 3 死 1 活 则 第6瓶有毒 二进制 也就是 110
如果1 2 3 全死 则 第7瓶有毒 二进制 也就是 111
如果1 2 3 全活 则 第8瓶有毒 二进制 也就是1000
第4只老鼠的话要用图表示了
[解决办法]
1）请问如何设置分配策略，可以保证充分利用每个缓存服务器的存储空间（每个内容只在一个缓存服务器有副本）
Round-robin：轮询分配
或者
与各服务器保持心跳，随时更新分配器端的负载记录，每次找一个负载最小的Cache.
或者
对数据做哈希散列,这个不太靠谱.
2）当部分缓存服务器故障，或是因为系统扩容，导致缓存服务器的数量动态减少或增加时，你的分配策略是否可以保证较小的缓存文件重分配的开销，如果不能，如何改进？
啥叫缓存文件冲分配，不懂啊。 分配器发现缓存服务器心跳木有了，就不给它分配就是了。
3）当各个缓存服务器的存储空间存在差异时（如有4个缓存服务器，存储空间比为4：9：15：7），如何改进你的策略，按照如上的比例将内容调度到缓存服务器？
分配器统计各服务器的负载用户量,计算各自占总负载比例,与存储空间比例做差值,取4个服务器中最小的.
比如:服务器1有2人,4台服务器总共20人,那么2/20=0.1 , 计算4/(4+9+15+7)=4/35=0.11。
0.11-0.1=0.01 每台服务器都计算出这个差值来，看谁大就用谁。
[解决办法]
格式不对，再发一遍
一、单选题
1) C ，海明码纠错原理，本题有r位(5位)监督位可用，根据海明码需要满足的关系式 2^r ≥ n+1，其中n是待检测的信息位数，得出 n ≤ 2^5 - 1 ，即 n ≤ 31，选C
2)C，只有C能在O(1)时间内满足题目中要求的“在最后一个结点之后插入一个结点和删除最后一个结点”，C答案最省时间
3)C，B-Tree 常被文件系统用来组织文件索引
4)C，只有C可以测试Web主机的网页服务器是否工作正常，假设该服务器的网页服务器使用的是默认端口，则可以使用命令
telnet hostname 80 来测试其是否工作
5)不知道，应该是CD中选，肯定不是AB，因为AB在Unix-like中有
6)D，常识
7)C，应该指B+树
8)C，DNS是将域名www.taobao.com映射成主机的IP地址，ARP是将IP地址映射成物理地址，ICMP是报文控制协议，由路由器发送给执行ping命令的主机，而一个ping命令并不会建立一条TCP连接，故没有涉及TCP协议
二、
1)应用层、网络层
2)2^(k-1)、2^k-1
3) -32 (用补码)
4) 10
三、综合题
第 1) 题
typedef struct TriNode{ unsigned int id; /* 节点编号 */ TriNode *lchild; /* 左子树 */ TriNode *mchild; /* 中间子树 */ TriNode *rchild; /* 右子树 */}TriNode;void exchange_node(TriNode *root){ TriNode *tmp; if(root != NULL){ /* 递归解决子树的交换 */ exchange(root->lchild); exchange(root->rchild); exchange(root->mchild); /* 将左右子树交换 */ tmp = root->lchild; root->rchild = root->lchild; root->lchild = tmp; }}