淘宝2011.9.21校园招聘会笔试题
一、单选题
1、我们有很多瓶无色的液体，其中有一瓶是毒药，其它都是蒸馏水，实验的小白鼠喝了以后会在5分钟后死亡，而喝到蒸馏水的小白鼠则一切正常。现在有5只小白鼠，请问一下，我们用这五只小白鼠，5分钟的时间，能够检测多少瓶液体的成分（C）
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
只有C可以测试Web主机的网页服务器是否工作正常，假设该服务器的网页服务器使用的是默认端口，则可以使用命令telnet hostname 80 来测试其是否工作。
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
DNS是将域名www.taobao.com映射成主机的IP地址，ARP是将IP地址映射成物理地址，ICMP是报文控制协议，由路由器发送给执行ping命令的主机，而一个ping命令并不会建立一条TCP连接，故没有涉及TCP协议。
二、填空题
1、http属于（应用层）协议，ICMP属于（网络层）协议。
2、深度为k的完全二叉树至少有（2^(k-1)）个结点，至多有（2^k-1）个结点。
3、字节为6位的二进制有符号整数，其最小值是（-32）。
4、设有28盏灯，拟公用一个电源，则至少需有4插头的接线板数（9）个。
第一个板4个口，此后每增加1个板会消耗1个原来的口，总的只增加3个口，故N个接线板能提供 1+3*N个电源口。
三、综合题
1、有一颗结构如下的树，对其做镜像反转后如下，请写出能实现该功能的代码。注意：请勿对该树做任何假设，它不一定是平衡树，也不一定有序。
1 1
/ | \ / | \
2 3 4 4 3 2
/|\ /\ | | / \ / | \
6 5 7 8 9 10 10 9 8 7 5 6
答：以孩子、兄弟的存储结构来存储这棵树，使之成为一颗二叉树，然后对二叉树进行链表的转换。
- typedef struct TreeNode
- {
- int data;
- struct TreeNode *firstchild;
- struct TreeNode *nextsibling;
- }TreeNode,*Tree;
- void MirrorTree(Tree root)
- {
- if(!root)
- return ;
- if(root->firstchild)
- {
- Tree p=root->firstchild;
- Tree cur=p->nextsibling;
- p->nextsibling=NULL;
- while(cur)
- {
- Tree curnext=cur->nextsibling;
- cur->nextsibling=p;
- if(p->firstchild)
- MirrorTree(p);
- p=cur;
- cur=curnext;
- }
- root->firstchild=p;
- }
- }
- int main(void)
- {
- TreeNode *root=(TreeNode *)malloc(sizeof(TreeNode));
- Init();
- MirrorTree(root);
- OutPut();
- }
- typedef struct TreeNode
- {
- int data;
- struct TreeNode *firstchild;
- struct TreeNode *nextsibling;
- }TreeNode,*Tree;
- void MirrorTree(Tree root)
- {
- if(!root)
- return ;
- if(root->firstchild)
- {
- Tree p=root->firstchild;
- Tree cur=p->nextsibling;
- p->nextsibling=NULL;
- while(cur)
- {
- Tree curnext=cur->nextsibling;
- cur->nextsibling=p;
- if(p->firstchild)
- MirrorTree(p);
- p=cur;
- cur=curnext;
- }
- root->firstchild=p;
- }
- }
- int main(void)
- {
- TreeNode *root=(TreeNode *)malloc(sizeof(TreeNode));
- Init();
- MirrorTree(root);
- OutPut();
- }
2、假设某个网站每天有超过10亿次的页面访问量，出于安全考虑，网站会记录访问客户端访问的ip地址和对应的时间，如果现在已经记录了1000亿条数据，想统计一个指定时间段内的区域ip地址访问量，那么这些数据应该按照何种方式来组织，才能尽快满足上面的统计需求呢，设计完方案后，并指出该方案的优缺点，比如在什么情况下，可能会非常慢？
答：用B+树来组织，非叶子节点存储（某个时间点，页面访问量），叶子节点是访问的IP地址。这个方案的优点是查询某个时间段内的IP访问量很快，但是要统计某个IP的访问次数或是上次访问时间就不得不遍历整个树的叶子节点。答：
或者可以建立二级索引，分别是时间和地点来建立索引。
四、附加题
1、写出C语言的地址对齐宏ALIGN（PALGNBYTES），其中P是要对齐的地址，ALIGNBYTES是要对齐的字节数（2的N次方），比如说：ALIGN(13,16)=16
- ALIGN(P,ALIGNBYTES) ( (void*)( ((unsigned long)P+ALIGNBYTES-1)&~(ALIGNBYTES-1) ) )
- 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的作用是？
3、在现代web服务系统的设计中，为了减轻源站的压力，通常采用分布式缓存技术，其原理如下图所示，前端的分配器将针对不同内容的用户请求分配给不同的缓存服务器向用户提供服务。
分配器
/ | \
缓存 缓存 ...缓存
服务器1 服务器2 ...服务器n
1）请问如何设置分配策略，可以保证充分利用每个缓存服务器的存储空间（每个内容只在一个缓存服务器有副本）
2）当部分缓存服务器故障，或是因为系统扩容，导致缓存服务器的数量动态减少或增加时，你的分配策略是否可以保证较小的缓存文件重分配的开销，如果不能，如何改进？
3）当各个缓存服务器的存储空间存在差异时（如有4个缓存服务器，存储空间比为4：9：15：7），如何改进你的策略，按照如上的比例将内容调度到缓存服务器？
面试题目：
1、操作系统中的同步和异步有什么区别？分别应用在什么场合？
答：同步，就是说你的程序在执行某一个操作时一直等待直到操作完成。 最常见的例子就是 SendMessage。该函数发送一个消息给某个窗口，在对方处理完消息之前，这个函数不返回。当对方处理完毕以后，该函数才把消息处理函数所返回的 LRESULT值返回给调用者。
异步，就是说程序在执行某一个操作时，只是发出开始的指令；由另外的并行程序执行这段代码，当完成时再通知调用者。 当一个客户端通过调用 Connect函数发出一个连接请求后，调用者线程立刻可以朝下运行。当连接真正建立起来以后，socket底层会发送一个消息通知该对象。
--------------------------------------------------------------------------------------------------------------------
举个例子：打电话是同步，发消息是异步。
2、数据库的ACID特定是什么？以及他们分别应用的场合？
答：ACID是指数据库事务具有的四个特性：原子性、一致性、隔离性、持久性
原子性：事务是数据库的逻辑工作单位，事务中包括的操作要么都做，要么都不做。只有使据库事务中所有的操作都执行成功，才算整个事务成功；事务中任何一个SQL语句执行失败，那么已经执行成功的SQL语句也必须撤销，数据库状态应该回滚（ROLLBACK）到执行事务前的状态。
一致性：如果在执行事务之前数据库是一致的，那么在执行事务之后数据库也还是一致的；事务执行的结果必须是使数据库从一个一致性状态变到另一个一致性状态。因此当数据库只包含成功事务提交的结果时，就说数据库处于一致性状态。如果数据库系统运行中发生故障，有些事务尚未完成就*中断，这些尚未完成的事务对数据库所做的修改有一部分已写入物理数据库，这时数据库就处于一种不正确的状态，或者说是不一致的状态。例如某公司在银行中有A、B两个账号，现在公司想从A中减去一万元，存入账号B。那么就可以定义一个事务，该事务包括两个操作，第一个操作就是从账号A减去一万元，第二个操作就是向账号B中加入一万元。这两个操作要么全做，要么全不做，数据库都处于一致性状态。如果只做一个操作则用户逻辑上就会发生错误，少了一万元，这时数据库就处于不一致状态。可见一致性与原子性是密切相关的。
隔离性：一个事务的执行不能被其他事务干扰。即一个事务内部的操作及使用的数据对其他并发事务是隔离的，并发执行的各个事务之间不能互相干扰。独立的数据库事务集合以不相互冲突的方式执行。仍使用这个银行类比，考虑两个客户同时在帐户之间转移资金。数据库必须分别跟踪两个转帐；否则，资金可能进入错误的帐户。
持久性：指一个事务一旦提交，它对数据库中数据的改变就应该是永久性的。接下来的其他操作或故障不应该对其执行结果有任何影响。 只要事务成功结束，它对数据库所做的更新就必须永久保存下来。即使发生系统崩溃，重新启动数据库系统后，数据库还能恢复到事务成功结束时的状态。
3、TCP和UDP的区别以及应用有什么不同？
答：TCP与UDP的区别
TCP---传输控制协议,提供的是面向连接、可靠的字节流服务。当客户和服务器彼此交换数据前，必须先在双方之间建立一个TCP连接，之后才能传输数据。TCP提供超时重发，丢弃重复数据，检验数据，流量控制等功能，保证数据能从一端传到另一端。
UDP---用户数据报协议，是一个简单的面向数据报的运输层协议。UDP不提供可靠性，它只是把应用程序传给IP层的数据报发送出去，但是并不能保证它们能到达目的地。由于UDP在传输数据报前不用在客户和服务器之间建立一个连接，且没有超时重发等机制，故而传输速度很快。
应用： HTTP协议在运输层采用的就是TCP协议，在浏览器中输入IP地址后，与服务器建立连接，采用的就是TCP协议，是一种面向连接、可靠的字节流服务。
当强调传输性能而不是传输的完整性时，如：音频、多媒体应用和视频会议时，UDP是最好的选择。另外，腾讯QQ采用也是UDP协议。
4、判断字符串是否为IP地址。
思路：输入字符串的时候，把分隔符“.”读取出来，然后判断分隔符旁边的数字是否在0~~255之间，然后判断是否合法。
- #include <stdio.h>
- #include <string.h>
- int main(void)
- {
- char str[31],temp[31];
- int a,b,c,d;
- while(gets(str)!=NULL)
- {
- if(sscanf(str, "%d.%d.%d.%d ",&a,&b,&c,&d)==4 && a>=0 && a<=255 && b>=0 && b<=255 && c>=0 && c<=255 && d>=0 && d<=255)
- {
- sprintf(temp, "%d.%d.%d.%d",a,b,c,d); //把格式化的数据写入字符串temp
- if(strcmp(temp,str)==0)
- {
- printf("YES\n");
- }
- else
- {
- printf("NO\n");
- }
- }
- else
- {
- printf("NO\n");
- }
- }
- return 0;
- }
- #include <stdio.h>
- #include <string.h>
- int main(void)
- {
- char str[31],temp[31];
- int a,b,c,d;
- while(gets(str)!=NULL)
- {
- if(sscanf(str, "%d.%d.%d.%d ",&a,&b,&c,&d)==4 && a>=0 && a<=255 && b>=0 && b<=255 && c>=0 && c<=255 && d>=0 && d<=255)
- {
- sprintf(temp, "%d.%d.%d.%d",a,b,c,d); //把格式化的数据写入字符串temp
- if(strcmp(temp,str)==0)
- {
- printf("YES\n");
- }
- else
- {
- printf("NO\n");
- }
- }
- else
- {
- printf("NO\n");
- }
- }
- return 0;
- }
5、指针和引用的区别？
1、从现象上看：指针在运行时可以改变其所指向的值，而引用一旦和某个对象绑定后就不再改变。
2、从内存分配上看：程序为指针变量分配内存区域，而引用不分配内存区域。
3、从编译上看：程序在编译时分别将指针和引用添加到符号表上，符号表上记录的是变量名及变量所对应地址。指针变量在符号表上对应的地址值为指针变量的地址值，而引用在符号表上对应的地址值为引用对象的地址值。符号表生成后就不会再改，因此指针可以改变指向的对象（指针变量中的值可以改），而引用对象不能改。
引用：一个变量的别名，为什么引入别名呢？原因是我们想定义一个变量，他共享另一个变量的内存空间，使用别名无疑是一个好的选择。变量是什么？是一个内存空间的名字，如果我们给这个内存空间在起另外一个名字，那就是能够共享这个内存了，引用（别名）的由此而来。
指针：指向另一个内存空间的变量，我们可以通过它来索引另一个内存空间的内容，本身有自己的内存空间。
二者区别：（1）引用访问一个变量是直接访问，而指针是间接访问。
（2）引用是一个变量的别名，本身不单独分配自己的内存空间，而指针有自己的内存空间，指针是一个实体，而引用不是。
（3）引用在开始的时候就绑定到了一个内存空间(开始必须赋初值)，所以他只能是这个内存空间的名字，而不能改成其他的，当然可以改变这个内存空间的值。
例如
int i = 3，j = 4;
int &x = i; //成为i的别名
x = j; //不能否认x仍然引用i，并没有成为j的别名，只是修改了x和i共享的内存空间的值为4
6、指针和数组的区别？
答：（1）数组要么在全局数据区被创建，要么在栈上被创建；指针可以随时指向任意类型的内存块；
（2）修改内容上的差别：
char a[] = “hello”;
a[0] = ‘X’;
char *p = “world”; // 注意p 指向常量字符串
p[0] = ‘X’; // 编译器不能发现该错误，运行时错误
(3)用运算符sizeof 可以计算出数组的容量（字节数）。sizeof(p),p 为指针得到的是一个指针变量的字节数，而不是p 所指的内存容量。C++/C 语言没有办法知道指针所指的内存容量，除非在申请内存时记住它。注意当数组作为函数的参数进行传递时，该数组自动退化为同类型的指针。
7、进程和线程的区别？
答：（1）进程是程序的一次执行，线程是进程中的执行单元；
（2）进程间是独立的，这表现在内存空间、上下文环境上，线程运行在进程中；
（3）一般来讲，进程无法突破进程边界存取其他进程内的存储空间；而同一进程所产生的线程共享内存空间；
（4）同一进程中的两段代码不能同时执行，除非引入多线程。
8、两个进程之间的通信方式有哪几种？
管道，信号，消息队列，共享内存，信号量和套接字