淘宝2011.9.21校园招聘会笔试题

淘宝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();
}

2、假设某个网站每天有超过10亿次的页面访问量,出于安全考虑,网站会记录访问客户端访问的ip地址和对应的时间,如果现在已经记录了1000亿条数据,想统计一个指定时间段内的区域ip地址访问量,那么这些数据应该按照何种方式来组织,才能尽快满足上面的统计需求呢,设计完方案后,并指出该方案的优缺点,比如在什么情况下,可能会非常慢?

答:用B+树来组织,非叶子节点存储(某个时间点,页面访问量),叶子节点是访问的IP地址。这个方案的优点是查询某个时间段内的IP访问量很快,但是要统计某个IP的访问次数或是上次访问时间就不得不遍历整个树的叶子节点。答:

或者可以建立二级索引,分别是时间和地点来建立索引。

四、附加题
1、写出C语言的地址对齐宏ALIGN(PALGNBYTES),其中P是要对齐的地址,ALIGNBYTES是要对齐的字节数(2的N次方),比如说:ALIGN(13,16)=16

  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底层会发送一个消息通知该对象。

打个比喻:
有一个男的 看上了两个漂亮MM 想通过写信的方式跟他们交流感情 这两个MM分别是 A女、B女
同步:他先给A女写了封信 然后发了出去。等了好几天 A女给他回了信,之后他才给B女写信。就是说等到一个任务返回或者结束 他才继续往下做他想做的任务。
异步:他先给A女写了封信,然后发了出去,马上又给B女写了封信 也发了出去。  就是说不用等到一个任务结束就去做下一个任务。

但是如果第一个任务需要第二个任务的返回值 那就得用同步让第一个任务等待第二个任务结束后,获取第二个任务的返回值,在继续往下做。
并行:两个帅哥同时给这两个妹妹写信。
同步和异步的简单区别:
举个例子:普通B/S模式(同步)AJAX技术(异步)
同步:提交请求->等待服务器处理->处理完毕返回 这个期间客户端浏览器不能干任何事
异步: 请求通过事件触发->服务器处理(这是浏览器仍然可以作其他事情)->处理完毕
——————————————————————————————————————–
同步就是你叫我去吃饭,我听到了就和你去吃饭;如果没有听到,你就不停的叫,直到我告诉你听到了,才一起去吃饭。
异步就是你叫我,然后自己去吃饭,我得到消息后可能立即走,也可能等到下班才去吃饭。
所以,要我请你吃饭就用同步的方法,要请我吃饭就用异步的方法,这样你可以省钱。
——————————————————————————————————————–
举个例子:打电话是同步,发消息是异步。

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协议。

原文:http://blog.csdn.net/hackbuteer1/article/details/6845406

发表评论

电子邮件地址不会被公开。 必填项已用*标注