人力资源：研发工程师招聘真题

第一部分单选题（前10题，每题2分；后10题，每题3分，共50分。选对得满分，选错倒扣1分，不选得0分）1．12345*123451105266261所采用的是多少进制的计算？（）A、2进制B、8进制C、10进制D、16进制2.关于HTTP协议的说明，一下哪项是错误的？（）A、在CS模式下，作为一种request-response协议B、无状态，对每一个请求看成独立的C、HTTP是、HTTP响应包括数字状态码，404经常代表“PageNotFound”3.以下程序输出结果是哪个？（）charmsg[]=“AAAA”;strcpy(msg,“BBB”);strcpy(msg,“CC”);strcpy(msg,“D”);printf(“%s”,msg);A、DCBAB、ABCDC、DD、A4．使用gcc默认对齐规则的情况下，下列两个数据结构的sizeof各是多少？（）structFirstStruct{chara;uint64_tb;uint32_tc;uint32_td;};structSecondStruct{chara;uint32_tb;uint32_tc;};A、17,13B、24,16C、24,24D、32,165.关于内联函数，以下哪项叙述是错误的？（）A、递归函数不能定义为内联函数B、内联函数只能先定义后使用C、任何源文件，使用内联函数必须包含函数定义D、Main函数可以内联6.执行IO时，直接调用内核异步API，内核完成IO操作后再回调用户，这种IO模式是什么？（）A、BIOB、NIOC、AIOD、FIO7.若系统中有5台打印机，有多个进程需要使用两台，规定每个进程一次仅允许申请一台，则至多允许多少个进程参与竞争，而不会发生死锁？（）A、2B、3C、4D、58.一个栈的入栈序列为abcde，则不可能的输出序列为哪个？（）A、edcbaB、dceabC、decbaD、abedc9.关于C程序运行内存空间的说法错误的是哪项？（）A、全局变量，static变量位于数据区，无需应用程序分配B、局部变量的作用域是当前的函数或程序块，出作用域之后无效C、在堆上分配内存需要调用malloc函数，并且需要调用free函数释放D、递归程序的递归深度主要受限于堆的空间大小，超过大小限制程序会崩溃10.以下关于数组说法正确的是哪项？（）A、建立公用数组，在模块声明阶段用private语句B、数组设定没有上下界C、二维数组初始化时要在类型说明时给各下标变量赋予初值D、对数组元素赋予初始值时一定要标注长度说明11.下列情况中，不能使用栈（stack）来解决问题的是哪个？（）A、将数学表达式转化为后缀形式B、实现递归算法C、高级编程语言的过程调用D、操作系统分配资源（如CPU）12.已知数据表中每个元素距其最终位置不远，为节省时间，应该采用的算法是什么？（）A、直接选择排序B、堆排序C、快速排序D、直接插入排序13.SkipList是一个非常优秀的数据结构，实现简单的插入、删除、查找复杂度为（logN），当该数据结构中插入一个元素遇到最坏情况下的时间复杂度是多少？（）A、O(N)B、O(logN)C、O(√N)D、O(NlogN)14.设一棵二叉树中有3个叶子结点，8个“深度”为1的结点，则该二叉树中总的节点数为多少？（）A、11B、12C、13D、1415.数据表中有10000个元素，如果仅要求求出其中最大的10个元素，采用什么算法最节省时间？（）A、堆排序B、希尔排序C、快速排序D、直接选择排序16.有A和B两路公交车，平均发车间隔分别为5分钟和10分钟。某乘客在站点S可以任意选择两者之一乘坐，假设A和B到达S的时刻无法确定，那么该乘客的平均等待时间约为多少？（）A、1分钟20秒B、1分钟40秒C、2分钟30秒D、3分钟20秒17．有一堆石子共100枚，甲乙轮流从该堆中取石子，每次可以取2,4,6枚，取得最后的石子的玩家为赢家，若家先取，则以下说法正确的是哪项？（）A、甲有必胜策略B、乙有必胜策略C、双方都没有必胜策略D、不确定18.有4人抬着三个货物出门，遇到一条河，他们四个人游过河的时间分别为1,3,8,15（分钟）。每个货物必须要由两个人托起才不会被浸湿，为防止货物失窃，所有货物需要有人看守，请问他们最少要花几分钟才能完成渡河？（）A、15B、20C、23D、2519.某班有25名学生，其中14人会打篮球，12人会打排球，6人会打篮球和排球，5人会打篮球和网球，还有2人这三种球都会打。而6个会打网球的人都会打另外一种球。请问25人中这三种球都不会打的人数是多少？（）A、3B、4C、5D、620.在一个N*N个方格的国际象棋盘上，knight从任意一个指定的方格出发，按照1横2竖或者1竖2横的跳马规则（如下图从X开始可以走到任意一个Y）。走遍棋盘的每个格子，且每个格子只走一次的跳法叫做一个骑士征程。请问，N最小为多少时，一个knight可以完成骑士征程？（）A、5B、7C、8D、9YYYYXYYYY第二部分不定项选择（4题，每题5分。每题1-5个正确选项，完全正确计5分，漏选计2分，不选计0分，多选、错选扣2分）21.一段时间内只允许一个进程访问的资源被称作临界资源，针对临界资源，以下说法错误的是哪些？（）A、对临界资源是不能实现资源共享B、只要能是程序并发执行，这些并发执行的程序可以对临界资源实现共享C、为临界资源配上相应的设备控制块后，便能实现共享D、对临界资源采用互斥访问方式，便能实现共享22.设存在三个函数f,g,h,分别为f(n)=53n~3+26n+18,g(n)=1500n~3+n~2,h(n)=15n~(1.5)+45nlg(n)。下列哪些关系是成立的，是哪几个？（）A、f(n)O(g(n))B、g(n)O(f(n))C、h(n)O(n~1.5)D、h(n)O(nlg(n))23.假设在树中，节点x是节点y的双亲时，用（x,y）来代表树边。已知一棵树边的集合为{(i,m),(i,n),(e,i),(b,e),(b,d),(a,b),(g,j),(g,k),(c,g),(c,f),(h,i),(c,h),(a,c)}，则下列说法正确的是哪几个？（）A、a是根节点B、g,h,i是f的兄弟C、c是g的双亲D、树的深度是524.根据一项对程序员的界面和收入的调查发现：i)10%喜欢白底黑字，60%喜欢黑底绿字；ii)50%是高收入的。下面描述可能正确的是哪几个？（）A、一半的程序员是低收入的B、30%喜欢黑底绿字的程序员是高收入的C、没有程序员既喜欢白底黑字，又是高收入的D、所有喜欢黑底绿字的程序员都不是高收入的第三部分填空与问答（5题，共30分）25.（4分）在操作系统的生产者消费者问题中，能否将生产者进程wait(empty)和wait(mutex)语句交换？为什么？26.（5分）某人提着两个空水壶到池塘边打水，两个水壶的容积分别是5L和6L，而他被要求只需要带回3L水，请问至少需要多少次操作才能使得两个水壶中只有3L水。（提示：注水、倒水均算一个步骤，给出操作步骤和最终次数）27.（6分）请指出二叉树后序遍历栈操作算法的关键，并给出最简单的算法思路。28.（8分）请给出分别满足下面条件的所有二叉树。（1）前序序列和中序序列相同（2）中序序列和后序序列相同（3）前序序列和后序序列相同（4）前序、中序、后序序列都相同29.（7分）以下的代码是一种广度优先搜索算法，请以下图中V0为源点执行以下算法，并回答问题：（1）顶点Vn+1需要入队多少次？被重复访问了多少次？（2）加黑斜体算法部分该如何做修改才能避免重复访问一个顶点的错误？V0V1V2VnVn+1voidBFS(ALGraph*G,intk){//以下省略局部变量的说明，visited各初始值为FalseInitQueue(&Q);//置空队列EnQueue(&Q,k);//k入队while(!QueueEmpty(&Q)){iDeQueue(&Q);//Vi出列visited[i]True;//设置访问标记print(%c,G-adjlist[i].vertex);//访问Vifor(pG-adjlist[i].firstedge;p;pp-next)//依次搜索Vi的邻近点if(!visited[p-adjvex])//若Vi没有访问过EnQueue(&Q,p-adjvex);//Vi入列}//endofwhile}//BFS第四部分：JAVA选做题（注：阿里有大量JAVA研发工程师需求；选作以下题目有机会增加该方向面试机会）1.请画出工厂模式的uml图，并简要描述这些要素的作用；列举以下这个模式的优势；给出一个jdk源码中的例子。2.Map是非常重要的数据结构，设计出一个Map的接口，用基于hash的算法简单实现这个Map，如果对你实现的HashMap做支持高并发场景下的线程安全的优化，怎么改进？更进一步，可以基于此HashMap如何最简单实现支持LRU算法的cache？如果要让这个cache支持分布式缓存服务，导入了哪些要解决的问题？请列举出来并给出你的解决方法。