淘宝2012秋季校园招聘 笔试试题.doc

答题时间：60分钟一 单选选择题（15题，每题3分，共45分；每题答对计3分，答错减1分，不答计0分）1 若系统中有6个队列，有多个进程均需要使用其中的3个，规定每个进程一次只允许申请一个队列，那么最多允许多少个进程参与竞争，才不会造成死锁？（）A 1个B 2个C 3个D 4个2 假设双链表节点的类型如下：Typedef struct linknodeInt data; /*数据域*/Struct linknode *llink,*rlink /*llink和rlink是分别指向前驱节点和后继节点的指针域*/bnode下面给出的（）是要把一个q所指新节点作为非空双向链表中的p所指节点的前驱节点。A q-rlink=p;q-llink=p-llink;p-llink=q;p-llink-rlink=q;B p-llink=q;q-rlink=p;p-llink-rlink=q;q-llink=p-llink;C q-llink=p-llink;q-rlink=p;p-llink-rlink=q;p-llink=q;D 以上都不对3 给定一个关键字序列24，18，32，43，38，7，13，22，采用堆排序时的初始化大项堆是（）。A 22，18，13，7，24，38，43，32B 43，38，32，22，24，7，13，18C 22，13，18，7，24，38，43，32D 43，38，32，22，24，13，7，184 设有28盏灯，拟公用一个电源，则至少需要有4个插头的接线板数几个？（） A 7 B 8 C 9 D 105 下列哪种不是平衡二叉树？（） A 红黑树 B avl树 C Treap树 D b+树6 网页搜索引擎因为要索引的网页数量巨大，所以会把索引分布在非常多的服务器上，而最终搜索结果则一般返回最符合搜索条件的前1000个，你认为获取最终搜索结果的排序算法是一下哪种？（）A 快速排序B 堆排序C 插入排序D 希尔排序7 TCP/IP模型的体系结构中，ICMP协议属于（）A 应用层B 网络层C 数据链路层D 传输层8 设A、B、C为三个事件，p(AB)0且p(C|AB)=1,则有（）A p(A) = p(A) + p(B) - 1B p(C) = p(A) + p(B) 1D p(C) =p(AUB)9 某班同学要订A、B、C、D四种报纸，没人至少订一种，最多订四种，那么每个同学有（）种不同的订报方式？A 7种B 12种C 15种D 21种10 假设某计算机具有1M字节的内存（目前使用的计算机往往具有64M字节以上的内存），并按字节编址，为了能存取该内存个地址的内容，其地址寄存器至少需要二进制（）位。A 10B 16C 20D 3211 当待排序的所有元素的排序码都相等时，下列哪种排序算法是最慢的？（）A 直接插入排序B 简单选择排序C 冒泡排序D 基数排序12 因特网中的协议应该满足规定的层次关系，下面选项中正确的协议层析和对应关系是（）SNMPTFTPUDPTCPIPA SNMPHTTPTCPUDPIPBCHTTPTFTPTCPUDPIPDSNMPTelnetTCPUDPIP13 下面关于二分查找的叙述正确的是（）A 表必须有序，表可以顺序方式存储，也可以链表方式存储B 表必须有序且表中数据必须是整数，实型或字符型C 表必须有序，而且只能从小到大排列D 表必须有序，且表只能以顺序方式存储14 有一口老钟，1点敲一下，2点敲两下，6点敲6下用了6秒，那么11点的时候，这口钟敲钟需要多久？（）A 6秒B 11秒C 12秒D 不确定15 32位操作系统char *a = 123,sizeof(a)是多少？（）A 2B 3C 4D 5二 填空题（4题，每题4分，共16分）1 请填写四种硬盘借口类型：（）、（）、（）、（）。2 为了避免需要在服务器上保存用户的登录信息，通常互联网网站都采用（）来在浏览器中记录用户是否登录等信息。3.pulic class ArithmeticResultsOutputPublic static void main(String args)Int I = 0;Int j = 0;If(i+ = +j)System.out.println(“True:i=”+i+”,j=”+j);ElseSystem.out.println(“False:i=”+i+”,j=+j);运行输出结果为（）4 已知A桶中有4个白球8个黑球，B桶中有2个红球3个黑球，某人从其中一个桶任取一球，这个球是黑色。请问这个黑球来自B桶的概率是（）三 综合题（2题，共39分）1 (14分)一颗树上有海量节点，假设在亿这个级别，现在给定任意2个结点（非根结点），请找出他们共同的祖先结点，请在节省空间的前提下，高效查找。注意：请勿对该树做任何假设，它不一定是平衡树，也不一定有序。2 (25分)请使用C语言完成strnicmp的编码实现，要求不能调用任何其他函数。Strnicmp完成两个ascii字符串的比较，忽略大小写（两个英文字母比较时，认为大小写无差别），最多比较n个字符（当两个字符串长度超过n时，就认为它们的长度都等于n），返回0表示第一个字符串大于第二个字符串，返回等于0时表示两个字符串相等。函数声明如下：int strnicmp(char const* s1,char const *s2,int n)四 附加题（3题，不计分）1 下面哪个字符串不能被正则表达式”a(bc)*d?”匹配？A adB abcdC abcD abccd2 假如我们要设计一个高效的服务器判断浏览器的算法，要求能根据User-Agent字符串判断浏览器的类型和版本，请描述一下你的思路。3 假设你现在维护了某次考试的三个科目成绩，科目A、B、C。每科成绩范围为0-100，整数分；考生人数N（百万级别）。提供给你的是一个N行的文本文件，每行四个数字分别是考生编号科A、B、C的成绩，允许使用的资源是两个512M的硬盘和64M内存。需求：（1） 现在要求你提供一个服务，输入考生编号，返回该考生的三科成绩。请说明你的磁盘文件组织和内存数据结构。并尽量对性能做优化。（2） 假设由于地区区域不同，考生的编号不连续，范围改变为1-10亿之间，N不变，请对你上述的方案做出对应的修改。（3） 在主干题目条件不变的情况下，