2009 网易 校园招聘 笔试试题汇总+详细答案解答

《2009 网易 校园招聘 笔试试题汇总+详细答案解答》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、网易2009年校园招聘笔试题第一部分(必做):计算机科学基础1.(单选)软件设计中模块划分应该遵循的准则是:B   A.低内聚低耦合B.高内聚低耦合C.低内聚高耦合D.高内聚高耦合2.(单选)最坏情况下时间复杂度不是n(n-1)/2的排序算法是:D   A.快速排序(n^2)B.冒泡排序(n^2)C.直接插入排序(n^2)D.堆排序(nlogn)3.哈希表中解决冲突的方法通常可以分为openaddressing和chaining两类,请分别解释这两类冲突解决方法的大致实现原理一开散列法--------chaining又叫做拉链法。即有多个元素hash到同一位置，就拉出一个

2、链表储存。这样做最坏情况变成了O(n)。但是只要hash函数选取得当，拉链法都能得到相当优秀的效率二闭散列法--------openaddressing又叫做开放寻址法。这种方法不需另外建链表，而是所有元素都存在散列表里。插入时当一个元素对应位置已满，它就寻找下一个空位置储存。亦即，一个元素可能不在它应在的地方。这时，如何寻找下一个位置就非常重要。主要有三种方法：1线性探查。即当第i个位置已经有了元素，就考虑第i+1个位置。即，探测的位置关于探测次数是线性函数。线性探查随着插入的增多，会出现连续被占用的位置，使得平均查找时间不断增加，称为一次群集。线性探查效率比较低下。2

3、二次探查。二次探查每次并不直接探查下一个元素，而是增加一个偏移量，使得探测的位置关于探测次数是二次函数。二次探查比线性探查有所改进，但是对于hash函数的选取限制较大。而且，初始位置相同的元素探查的位置也会完全相同，这就导致了比一次群集程度轻的二次群集。因此二次探查效率也并不理想。3双重散列。即构造两个hash函数。当发生冲突时，向下寻找hash2(k)的位置。这样，探查的序列就与元素本身的值有关，发生冲突的概率小了很多。而hash2的选取也有限制：hash2(k)要始终与整个表的大小互质，才能取遍所有位置。实际测试中，拉链法速度最快，双重散列稍慢。而线性探查和二次探查速

4、度较为低下。4.简单的链表结构拥有很好的插入，删除节点性能,但随机定位(获取链表第n个节点)操作性能不佳,请你设计一种改进型的链表结构优化随机定位操作的性能,给出设计思路及其改进后随机定位操作的时间复杂度。大概地说，节点构成多棵相连的完全二叉树来表示（为了不浪费节点），存取顺序为前序遍历。复杂度为O(log n )这里有代码http://www.cs.oberlin.edu/~jwalker/ra-list/5.什么是NP问题?列举典型的NP问题(至少两个)?对于一个给定的问题你通常如何判断它是否为NP问题?P(Polynomial,多项式)问题.P问题是可以在多项式时间

5、内被确定机(通常意义的计算机)解决的问题.NP(Non-DeterministicPolynomial,非确定多项式)问题,是指可以在多项式时间内被非确定机(它可以猜,他总是能猜到最能满足你需要的那种选择,如果你让他解决n皇后问题,他只要猜n次就能完成----每次都是那么幸运)解决的问题.这里有一个著名的问题----千禧难题之首,是说P问题是否等于NP问题,也即是否所有在非确定机上多项式可解的问题都能在确定机上用多项式时间求解.NPC(NPComplete)问题（NP完全），可以这么认为，这种问题只有把解域里面的所有可能都穷举了之后才能得出答案，这样的问题是NP里面最难的

6、。1.旅行商问题TSPTravellingSalesmanProblem（有一个推销员，要到n个城市推销商品，他要找出一个包含所有n个城市的具有最短路程的环路。）2.子集和问题3.Hamilton回路要满足两个条件：　　1.封闭的环　　2.是一个连通图，且图中任意两点可达　　经过图（有向图或无向图）中所有顶点一次且仅一次的通路称为哈密顿通路。　　经过图中所有顶点一次且仅一次的回路称为哈密顿回路。4.最大团问题给定无向图G=(V,E)，其中V是非空集合，称为顶点集；E是V中元素构成的无序二元组的集合，称为边集，无向图中的边均是顶点的无序对，无序对常用圆括号“()”表示。如果

7、U∈V，且对任意两个顶点u，v∈U有(u,v)∈E，则称U是G的完全子图。G的完全子图U是G的团当且仅当U不包含在G的更大的完全子图中。G的最大团是指G中所含顶点数最多的团。6.以下是一个tree的遍历算法,queue是FIFO队列,请参考下面的tree,选择正确的输出.A1/2  3//4567queue.push(tree.root)while(true){node=queue.pop();output(node.value);//输出节点对应数字if(null==node)  break;for(child_nod