届校园招聘笔试面试题及部分答案

笔试面试题汇总一、笔试题1、给你一个二叉树的前序序列和中序序列，求其后续序列？（淘宝）先看三个公式：PreOrder(T)=T的根节点+PreOrder（T的左子树）+PreOrder（T的右子树）；InOrder(T)=InOrder（T的左子树）+T的根节点+InOrder（T的右子树）；PostOrder(T)=PostOrder（T的左子树）+PostOrder（T的右子树）+T的根节点。根据以上的三给公式就可以很容易解决一下两个问题：前序+中序后序；中序+后序前序。当然也可把树画出来，再求他的各种序列。2、Cache替换算法命中率最高是？（淘宝）这个组成原理就有讲到了，可以找组成原理的书看下，把各种替换算法在理解下，在书上的P98-P99讲得很详细。3、给一个顺序表，然后再给你一个码值，求在二分查找改码值的比较次数？（淘宝）自己去做二分的查找的过程，我们知道二分查找是log(n)的，一次比较次数大于log(n)肯定是错的。具体可以看下数据结构的书，P17-P18讲的很详细。4、编译程序中安排中间代码生成的目的是？（淘宝）把与机器相关的工作集中到目标代码生成阶段，难度和工作量下降。便于移直和维护。利于优化。5、假设在n进制下，17*456=8206成立，n是多少？（淘宝）从上面的等式中可以看到8，则进制可定大于8，因此可以从9进制开始枚举，直至满足等式，就可以了。（建议：先都转换成十进制，在实现乘法运算）6、要从一亿会员中抽出100万会员，考虑到公平性、相对分散、相对随机，不能重复，抽取速度要快。有一个random函数，能产生0-9的随机数。请写出你能想到的抽取方法？并写明步骤。（淘宝）用random函数产生两个数x1、x2，那么会员号mod100等于x1x2的话，该会与就被选中。这样每个会员的中奖概率是1/100。7、Malloc和new的区别？8、++、--、sizeof（字符串、结构体）（融通）9、字符串函数的实现（strlen、strcpy等）（网龙、亿联网络）10、字符串以单词逆序11、CSTRING类的一些基本函数的实现12、DEBUG和RELESE两种调试的区别13、CONST的用法我只要一听到被面试者说：const意味着常数，我就知道我正在和一个业余者打交道。去年DanSaks已经在他的文章里完全概括了const的所有用法，因此ESP(译者：EmbeddedSystemsProgramming)的每一位读者应该非常熟悉const能做什么和不能做什么.如果你从没有读到那篇文章，只要能说出const意味着只读就可以了。尽管这个答案不是完全的答案，但我接受它作为一个正确的答案。（如果你想知道更详细的答案，仔细读一下Saks的文章吧。）如果应试者能正确回答这个问题，我将问他一个附加的问题：下面的声明都是什么意思？constinta;intconsta;constint*a;int*consta;intconst*aconst;前两个的作用是一样，a是一个常整型数。第三个意味着a是一个指向常整型数的指针（也就是，整型数是不可修改的，但指针可以）。第四个意思a是一个指向整型数的常指针（也就是说，指针指向的整型数是可以修改的，但指针是不可修改的）。最后一个意味着a是一个指向常整型数的常指针（也就是说，指针指向的整型数是不可修改的，同时指针也是不可修改的）。如果应试者能正确回答这些问题，那么他就给我留下了一个好印象。顺带提一句，也许你可能会问，即使不用关键字const，也还是能很容易写出功能正确的程序，那么我为什么还要如此看重关键字const呢？我也如下的几下理由：1)关键字const的作用是为给读你代码的人传达非常有用的信息，实际上，声明一个参数为常量是为了告诉了用户这个参数的应用目的。如果你曾花很多时间清理其它人留下的垃圾，你就会很快学会感谢这点多余的信息。（当然，懂得用const的程序员很少会留下的垃圾让别人来清理的。）2)通过给优化器一些附加的信息，使用关键字const也许能产生更紧凑的代码。3)合理地使用关键字const可以使编译器很自然地保护那些不希望被改变的参数，防止其被无意的代码修改。简而言之，这样可以减少bug的出现。14、虚基类抽象基类的用法答：在派生类继承基类时，加上一个virtual关键词则为虚拟基类继承，如：classderive:virtualpublicbase{};虚基类主要解决在多重继承时，基类可能被多次继承，虚基类主要提供一个基类给派生类，如：classB{};classD1:publicB{};classD2:publicB{};classC:publicD1,publicD2{};这里C在D1,D2上继承，但有两个基类，造成混乱。因而使用虚基类，即：classB{};classD1:virtualpublicB{};classD2:virtualpublicB{};classC:publicD1,publicD215、Java线程中的sleep,yeild,notify的作用和区别sleep:让线程睡眠yeild：暂停当前正在执行的线程对象，并执行其他线程notify:唤醒线程16、面向对象的特征有哪些方面封装、继承、多态17、ServletConfig对象与ServletContext对象的作用和区别servletconfig对象可以使用一个或多个init-param标签为servlet配置一些初始化参数，servlet配置了初始化参数后，web容器在创建servlet实例对象时，会自动将这些初始化参数封装到ServletConfig对象中，并在调用servlet的init方法时，将ServletConfig对象传递给servlet。进而，程序员通过ServletConfig对象就可以得到当前servlet的初始化参数信息。WEB容器在启动时，它会为每个WEB应用程序都创建一个对应的ServletContext对象，它代表当前web应用。ServletConfig对象中维护了ServletContext对象的引用，开发人员在编写servlet时，可以通过ServletConfig.getServletContext方法获得ServletContext对象。18、编程：链表的反转、两个排好序链表结合成一个有序链表19、写一个程序实现字符串反转。（新大陆）20、多态性意味着一个操作在不同的类中可以有不同的实现方式。（淘宝）21、二分搜索算法具体可以看下数据结构的书，P17-P18讲的很详细。22、树：节点个数与树高的计算这个可以用深搜和广搜实现，节点个数没遇到一个还没标记的节点就加1并标记该节点。把根节点记为1，然后对于还没标记的节点就等于他父亲的值+1，这过程中出现的最大值就是树高。对于树的一些定义数据结构书上有P138-P139。23、操作系统：内存的大小端，生产者、消费者问题1-2.生产者消费者问题：生产者与消费者问题可以被描述为：一个有限缓冲区和两类线程，它们是生产者和消费者，生产者把产品放入缓冲区，相反消费者便是从缓冲区中拿走产品。生产者在缓冲区满时必须等待，直到缓冲区有空间才继续生产。消费者在缓冲区空时必须等待，直到缓冲区中有产品才能继续读取。P,V操作来解决进程同步与进程通信的问题。信号量是最早出现的用来解决进程同步与互斥问题的机制，包括一个称为信号量的变量及对它进行的两个原语操作。信号量为一个整数，我们设这个信号量为：sem。很显然，我们规定在sem大于等于零的时候代表可供并发进程使用的资源实体数，sem小于零的时候，表示正在等待使用临界区的进程的个数。根据这个原则，在给信号量附初值的时候，我们显然就要设初值大于零。p操作和v操作是不可中断的程序段，称为原语。P,V原语中P是荷兰语的Passeren，相当于英文的pass,V是荷兰语的Verhoog,相当于英文中的incremnet。P原语操作的动作是：（1）sem减1；（2）若sem减1后仍大于或等于零，则进程继续执行；（3）若sem减1后小于零，则该进程被阻塞后进入与该信号相对应的队列中，然后转进程调度。V原语操作的动作是：（1）sem加1；（2）若相加结果大于零，则进程继续执行；（3）若相加结果小于或等于零，则从该信号的等待队列中唤醒一等待进程，然后再返回原进程继续执行或转进程调度。需要提醒大家一点就是P,V操作对于每一个进程来说，都只能进行一次。而且必须成对使用。且在P,V愿语执行期间不允许有中断的发生。24、软件工程的类图类图(Classdiagram)是最常用的UML图，显示出类、接口以及它们之间的静态结构和关系；它用于描述系统的结构化设计。类（Class）一般包含3个组成部分。第一个是类名；第二个是属性（attributes）；第三个是该类提供的方法。类与类间关系常见的关系有：继承（Generalization），关联关系（Association），聚合关系（Aggregation），组合关系（Composition），依赖关系（Dependency）。其中，聚合关系（Aggregation），组合关系（Composition）属于关联关系（Association）。详见软件工程教材。25、C语言：c语言的关键字、运算符的优先级与结合性、宏、指针的理解、typedef等3-1.c语言的关键字关键字是由C语言规定的具有特定意义的字符串，通常也称为保留字。用户定义的标识符不应与关键字相同。c语言关键字共32个：1、数据类型关键字（12个）：(1).char：声明字符型变量或函数(2).double：声明双精度变量或函数(3).enum：声明枚举类型(4).float：声明浮点型变量或函数(5).int：声明整型变量或函数(6).long：声明长整型变量或函数(7).short：声明短整型变量或函数(8).signed：声明有符号类型变量或函数(9).struct：声明结构体变量或函数(10).union：声明联合数据类型(11).unsigned：声明无符号类型变量或函数(12).void：声明函数无返回值或无参数，声明无类型指针（基本上就这三个作用）2、控制语句关键字（12个）：A.循环语句(1).for：一种循环语句(可意会不可言传）(2).do：循环语句的循环体(3).while：循环语句的循环条件(4).break：跳出当前循环(5).continue：结束当前循环，开始下一轮循环B.条件语句(1).if:条件语句(2).else：条件语句否定分支（与if连用）(3).goto：无条件跳转语句C.开关语句(1).switch:用于开关语句(2).case：开关语句分支(3).default：开关语句中的“其他”分支D.return：子程序返回语句（可以带参数，也看不带参数）3、存储类型关键字（4个）：(1).auto：声明自动变量一般不使用(2).extern：声明变量是在其他文件正声明（也可以看做是引用变量）(3).register：声明积存器变量(4).static：声明静态变量4、其它关键字（4个）：(1).const：声明只读变量(2).sizeof：计算数据类型长度(3).typedef：用以给数据类型取别名（当然还有其他作用）(4).volatile：说明变量在程序执行中可被隐含地改变3-2.运算符的优先级与结合性、宏、指针的理解、typedef等注：谭浩强那本书附录很详细。c语言运算符1级优先级左结合()圆括号[]下标运算符-指向结构体成员运算符.结构体成员运算符2级优先级右结合!逻辑非运算符~按位取反运算符++前缀增量运算符--前缀增量运算符+正号运算符-负号运算符(类型)类型转换运算符*指针运算符&地址与运算符sizeof长度运算符3级优先级左结合*乘法运算符/除法运算符%取余运算符4级优先级左结合+加法运算符-减法运算符5级优先级左结合左移运算符右移运算符6级优先级左结合、=、、=关系运算符7级优先级左结合==等于运算符!=不等于运算符