一篇完整的网易笔试题

一篇完整的网易笔试题发布时间:2010-11-04来源:应届毕业生求职网卷(研发类笔试题)第一部分(必做):计算机科学基础1.(单选)软件设计中模块划分应该遵循的准则是:A.低内聚低耦合B.高内聚低耦合C.低内聚高耦合D.高内聚高耦合2.(单选)最坏情况下时间复杂度不是n(n-1)/2的排序算法是:A.快速排序(n^2)B.冒泡排序(n^2)C.直接插入排序(n^2)D.堆排序(nlogn)3.哈希表中解决冲突的方法通常可以分为openaddressing和chaining两类,请分别解释这两类冲突解决方法的大致实现原理//见书4.简单的链表结构拥有很好的插入删除节点性能,但随机定位(获取链表第n个节点)操作性能不佳,请你设计一种改进型的链表结构优化随机定位操作的性能,给出设计思路及其改进后随机定位操作的时间复杂度具体参见PurelyFunctionalRandom-AccessLists.pdf大概地说，节点构成多棵相连的完全二叉树来表示（为了不浪费节点），存取顺序为前序遍历。复杂度为O(logn)这里有代码~jwalker/ra-list/5.什么是NP问题?列举典型的NP问题(至少两个)?对于一个给定的问题你通常如何判断它是否为NP问题?NP(NondeterministicPolynomial问题)。但是对于很多问题来说，他们找不到一个多项式的解决方法，，只能“尝试”很多种方案才能够得出一个答案，这显然是很费时的，这种问题未NP问题。NPC(NPComplete)问题，可以这么认为，这种问题只有把解域里面的所有可能都穷举了之后才能得出答案，这样的问题是NP里面最难旅行商问题TSPTravellingSalesmanProblem子集和问题Hamilton回路要满足两个条件：1.封闭的环2.是一个连通图，且图中任意两点可达经过图（有向图或无向图）中所有顶点一次且仅一次的通路称为哈密顿通路。经过图中所有顶点一次且仅一次的回路称为哈密顿回路。最大团问题6.以下是一个tree的遍历算法,queue是FIFO队列,请参考下面的tree,选择正确的输出.1/\23/\/\4567queue.push(tree.root)while(true){node=queue.pop();output(node.value);//输出节点对应数字if(null==node)break;for(child_nodeinnode.children){queue.push(child_node);}}A.1234567B.1245367C.1376254D.1327654第二部分(选作):C/C++程序设计1.有三个类ABC定义如下,请确定sizeof(A)sizeof(B)sizeof(C)的大小顺序,并给出理由structA{A(){}~A(){}intm1;intm2;};structB{B(){}~B(){}intm1;charm2;staticcharm3;};structC{C(){}virtual~C(){}intm1;shortm2;};//8//8//122.请用C++实现以下print函数,打印链表I中的所有元素,每个元素单独成一行voidprint(conststd::listint&I){}#includelist#includeiostreamvoidprint(conststd::listint&I){std::listint::const_iteratoriter;for(iter=I.begin();iter!=I.end();iter++)printf(%d\n,*iter);}intmain(){std::listintL;L.push_back(1);L.push_back(2);L.push_back(3);print(L);return0;}3.假设某C工程包含a.c和b.c两个文件,在a.c中定义了一个全局变量foo,在b.c中想访问这一变量时该怎么做?增加一个a.h,写上externintfoo,然后让a.c和b.c都包含a.h4.C++中的new操作符通常完成两个工作,分配内存及其调用相应的构造函数初始化请问:1)如何让new操作符不分配内存,只调用构造函数?2)这样的用法有什么用?解答：（要求new显式调用构造函数，但不分配内存。）题目要求不能生成内存还要调用构造函数说明这个类里面没有对内部操作但可以对外部操作比如static的数摘录：如果我是用new分配对象的，可以显式调用析构函数吗？可能不行。除非你使用定位放置new.classFred{public:Fred(){coutfuck;}};intmain(){Fred*f=new((void*)10000)Fred();system(pause);}其中这个10000可以是任意数，但不能为02）定位放置new（placementnew）有很多作用。最简单的用处就是将对象放置在内存中的特殊位置。这是依靠new表达式部分的指针参数的位置来完成的：#includenew//必须#include这个，才能使用placementnew#includeFred.h//classFred的声明voidsomeCode(){charmemory[sizeof(Fred)];//Line#1void*place=memory;//Line#2Fred*f=new(place)Fred();//Line#3(详见以下的“危险”)//Thepointersfandplacewillbeequal//...}Line#1在内存中创建了一个sizeof(Fred)字节大小的数组，足够放下Fred对象。Line#2创建了一个指向这块内存的首字节的place指针（有经验的C程序员会注意到这一步是多余的，这儿只是为了使代码更明显）。Line#3本质上只是调用了构造函数Fred::Fred()。Fred构造函数中的this指针将等于place。因此返回的f将等于place。Line#3本质上只是调用了构造函数Fred::Fred()。*********************************************************placementnew的作用就是：创建对象但是不分配内存，而是在已有的内存块上面创建对象。用于需要反复创建并删除的对象上，可以降低分配释放内存的性能消耗。#includeiostream#includenewconstintchunk=16;classFoo{public:intval(){return_val;}Foo(){_val=0;}private:int_val;};//预分配内存，但没有Foo对象char*buf=newchar[sizeof(Foo)*chunk];intmain(void){//在buf中创建一个Foo对象Foo*pb=new(buf)Foo;//检查一个对象是否被放在buf中if(pb-val()==0){coutnewexpressioworked!endl;}//到这里不能再使用pbdelete[]buf;return0;}{intmV;public:void*operatornew(size_tsize,void*mem){returnmem;}a(intv){printf(aconstructor\n);mV=v;}~a(){printf(adestructor\n);}voidpr(){printf(%d\n,mV);}};intmain(){aa1(1);a1.pr();void*p=&a1;a*a2=new(p)a(2);a2-pr();a1.pr();return0;}5.下面这段程序的输出是什么?为什么?classA{public:A(){p();}virtualvoidp(){print(A)}virtual~A(){p();}};classB{public:B(){p();}voidp(){print(B)}~B(){p();}};intmain(int,char**){A*a=newB();deletea;}6.什么是C++Traits?并举例说明可以说是一个小小的信息体，其它对象或算法可以根据它来选择不同的执行政策功实现细节。比如std中numeric_limitsdouble::max()第三部分(选作):JAVA程序设计1.(单选)以下Java程序运行的结构是:publicclassTester{publicstaticvoidmain(String[]args){Integervar1=newInteger(1);Integervar2=var1;doSomething(var2);System.out.print(var1.intValue());System.out.print(var1==var2);}publicstaticvoiddoSomething(Integerinteger){integer=newInteger(2);}}A.1trueB.2trueC.1falseD.2falsejava中的值传递和引用传递值传递：方法调用时，实际参数把它的值传递给对应的形式参数，方法执行中形式参数值的改变不影响实际参数的值。引用传递：也称为传地址。方法调用时，实际参数的引用(地址，而不是参数的值)被传递给方法中相对应的形式参数，在方法执行中，对形式参数的操作实际上就是对实际参数的操作，方法执行中形式参数值的改变将会影响实际参数的值。下面举例说明：传值---传递基本数据类型参数publicclassPassValue{staticvoidexchange(inta,intb){//静态方法，交换a,b的值inttemp;temp=a;a=b;b=temp;}publicstaticvoidmain(String[]args){inti=10;intj=100;System.out.println(beforecall:+i=+i+\t+j=+j);//调用前exchange(i,j);//值传递，main方法只能调用静态方法System.out.println(aftercall:+i=+i+\t+j=+j);//调用后}}运行结果：beforecall:i=10j=100aftercall:i=10j=100说明：调用exchange(i,j)时，实际参数i，j分别把值传递给相应的形式参数a，b,在执行方法exchange()时，形式参数a，b的值的改变不影响实际参数i和j的值，i和j的值在调用前后并没改变。引用传递---对象作为参数如果在方法中把对象（或数组）作为参数，方法调用时，参数传递的是对象的引用（地址），即在方法调用时，实际参数把对对象的引用（地址）传递给形式参数。这是实际参数与形式参数指向同一个地址，即同一个对象（数组），方法执行时，对形式参数的改变实际上就是对实际参数的改变，这个结果在调用结束后被保留了下来。classBook{Stringname;privatefolatprice;Book(Stringn,float){//构造方法name=n;price=p;}staticvoidchange(Booka