淘宝招聘笔试题目

淘宝招聘笔试题目

　　一、单选题

　　1、我们有很多瓶无色的液体，其中有一瓶是毒药，其它都是蒸馏水，实验的小白鼠喝了以后会在5 分钟后死亡，而喝到蒸馏水的小白鼠则一切正常。现在有5 只小白鼠，请问一下，我们用这五只小白鼠，5 分钟的时间，能够检测多少瓶液体的成分(d) a 5 瓶 b 6 c 31 d 32

　　2、若某链表最常用的操作是在最后一个结点之后插入一个结点和删除最后一个结点，则采用(c)存储方式最节省时间?

　　A 单链表 B 带头结点的非循环双链表 C 带头节点的双循环链表 D 循环链表

　　3、如果需要对磁盘上的1000W条记录构建索引，你认为下面哪种数据结构来存储索引最合适?(B)

　　A Hash Table B. AVL-Tree C. B-Tree D. List

　　一个B-tree 的典型例子就是硬盘中的结点。与内存相比，硬盘必须花成倍的时间来存取一个数据元素，这是因为硬盘的机械部件读写数据的速度远远赶不上纯电子媒体的内存。与一个结点两个分支的二元树相比，B-tree 利用多个分支(称为子树)的结点，减少获取记录时所经历的结点数，从而达到节省存取时间的目的。

　　4、可用来检测一个web 服务器是否正常工作的命令是(B)

　　A ping B tracert C. telnet D. ftp

　　5、下面哪个操作是Windows 独有的I/O 技术(D)

　　A. Select B.Poll C.IOCP D. Epoll

　　6、IPV6 地址包含了(D)位

　　A. 16 B. 32 C. 64 D.128

　　7、数据库里建索引常用的数据结构是(D)

　　A 链表 B 队列 C 树 D 哈希表

　　8、在公司局域网上ping www.taobao.com没有涉及到的网络协议是(A)

　　A. ARP B. DNS C. TCP D. ICMP

　　二、填空题

　　1、http 属于(超文本传输)协议，ICMP 属于(Internet 控制报文协议)协议

　　2、深度为k 的完全二叉树至少有(2^(k-1)+1)个结点，至多有(2^k-1)个结点

　　3、字节为6 位的二进制有符号整数，其最小值是(-15)

　　4、设有28 盏灯，拟公用一个电源，则至少需有4 插头的接线板数(9)个。

　　三、综合题

　　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

　　答：

　　ALIGN(P,ALIGNBYTES) \

　　( (void*)( ((unsigned long)P+ALIGNBYTES-1)&(ALIGNBYTES-1) ) )

　　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 的作用是? 利用union 的'特性，看到cache_line_align 的大小已经扩展到sizeof(erts_smp_rwmtx_t) 向上对齐了，这样寻址都是 sizeof(long) 的倍数地址上，寻址快，有利于下边数组 erts_meta_main_tab_lock_t main_tab_lock[16]; 的访问速度。

　　3、在现代web 服务系统的设计中，为了减轻源站的压力，通常采用分布式缓存技术，其原理如下图所示，前端的分配器将针对不同内容的用户请求分配给不同的缓存服务器向用户提供服务。

　　分配器

　　/ | \

　　缓存 缓存 ...缓存

　　服务器1 服务器2 ...服务器n

　　1)请问如何设置分配策略，可以保证充分利用每个缓存服务器的存储空间(每个内容只在一个缓存服务器有副本)

　　2)当部分缓存服务器故障，或是因为系统扩容，导致缓存服务器的数量动态减少或增加时，你的分配策略是否可以保证较小的缓存文件重分配的开销，如果不能，如何改进?

　　3)当各个缓存服务器的存储空间存在差异时(如有 4 个缓存服务器，存储空间比为 4：9： 15：7)，如何改进你的策略，按照如上的比例将内容调度到缓存服务器?

　　求树中两个节点的公共祖先，树的结点的数量很大，要求用效率越高越好。

　　TREE* CommonFather(TREE *root, TREE *A, TREE *B)

　　{

　　if(root == NULL)

　　return root; if(root == A)//如果找到A，则后面的都不再找了，如果其他分支没找到B，则B 必定在 A 下面

　　return A;

　　if(root == B)//同上

　　return B;

　　TREE *leftChild == NULL;

　　TREE *rightChild == NULL;

　　leftChild = CommonFather(root->left, A, B);//返回A，B 或结果

　　rightChild = CommonFather(root->right, A, B);//返回A，B 或结果

　　if(leftChild != NULL && rightChild != NULL)//如果都不为空，则必定一个是A，一个是B;

　　return root;

　　if(leftChild != NULL)//如果不为空，则必定是A 或B 或结果;

　　return leftChild;

　　if(rightChild != NULL)

　　return rightChild;//如果不为空，则必定是A 或B 或结果;

　　}