京东校招技术类选择题考点解析：数据结构算法与计算机基础

秋招那段日子白天泡图书馆刷题晚上守着牛客网看面经手机里存了十几张截图全是“京东2017校招技术类选择题一”这种标题。后来我自己整理了一套笔记把当年那批技术选择题的考点、易错点、复习方法全理了一遍才发现这种卷子其实非常有套路基础扎实的人四十分钟能做完还富余基础不牢的人两个小时都不够用。今天把这份整理分享出来给正在准备校招、或者想检验一下自己计算机基础的朋友做个参考尤其是Java后台、C研发、算法方向的岗位这套选择题覆盖的几乎都是笔试必考的底层能力。1. 整体项目复盘技术类选择题到底在筛什么1.1 这套题的考试定位与命题风格先说结论京东2017校招技术类选择题一并不是那种偏题怪题满天飞的卷子它更像是一次“计算机基础知识体检”。我当时对照着参加笔试的同学回忆版题目整理完后发现所有题几乎都能在《数据结构》《计算机网络》《操作系统》的课本里找到原型少数编程语言题考的是Java或C的基础语法和集合类难度大概在“本科课程期末考试中等偏上”的水平。为什么要用选择题这种形式因为校招简历数量太大技术面试官精力有限必须先用一套客观题快速过滤掉基础不扎实的候选人。选择题能覆盖的知识面比编程题宽得多从时间复杂度到TCP状态机从哈希冲突到死锁条件几十道题就能把一门课的核心考点全部测一遍。所以这套题本质上考的不是“你会不会做难题”而是“你有没有认真上过课、有没有真正理解核心概念”。从命题风格来看选择题有一个明显特点大量题目喜欢在“边界条件”上做文章。比如数组下标从0开始还是从1开始、循环结束条件是i n还是i n、二分查找的mid是向上取整还是向下取整这些都是出题人最喜欢埋坑的地方。后面我会专门开一节讲这些陷阱。1.2 考点分布与复习优先级我把这份回忆版选择题按照考点维度做了归类大致分布如下考点模块占比典型题目类型复习优先级数据结构30%二叉树遍历、栈与队列、哈希表、链表极高算法与复杂度15%时间/空间复杂度计算、排序算法稳定性极高计算机网络15%TCP三次握手、HTTP状态码、DNS高操作系统15%进程线程、死锁、内存管理高Java/C基础15%集合类、关键字、内存区域高数据库/设计模式10%索引、SQL、单例模式中这个分布比例是我根据多份考生回忆版拼出来的可能和真实试卷有出入但大方向不会有太大偏差。值得注意的一个细节是数据结构和算法加起来接近一半这和京东技术岗的实际工作内容是匹配的——不管是做商城后台还是做物流系统数据结构能力直接决定你能不能写出高效的代码。所以复习优先级上我强烈建议把时间按“数据结构 操作系统 网络 语言基础 其他”的顺序来排。如果你时间紧张只有一周那就盯死二叉树、排序、复杂度、死锁、TCP这几个板块拿到的分就能覆盖卷面的60%以上。1.3 备考资料与刷题策略我当时用的资料其实很朴素王道考研系列的数据结构、操作系统、计算机网络三本书加上牛客网上的历年校招真题库再加一本《Java编程思想》当工具书。这三样东西足够应付京东2017校招技术类选择题的绝大部分考点不需要去买所谓的高价机密题库那些基本上就是把公开资料重新排版。刷题策略上我的建议是三轮走第一轮按知识点刷每复习完一章就刷对应题目目的是建立概念和题型之间的映射。比如学完二叉树遍历就刷所有和先序中序后序相关的选择题把规则彻底吃透。第二轮成套刷按照考试时间模拟45分钟做完30题训练速度和取舍能力。这一轮你会发现很多题知识点都会但就是做不快原因是不熟悉出题套路需要通过整套卷子来适应。第三轮专门看错题把每次做错的题集中到一个错题本里标注出错原因是概念不清还是计算失误还是题目看漏。我自己的经验是第三轮比前两轮更重要因为校招选择题翻来覆去考的就是那些经典坑踩过一次的坑记下来考场基本不会再踩。2. 核心考点详解数据结构和算法是拿分主战场2.1 二叉树遍历序列的“无脑还原法”数据结构里最常考也最容易拿分的我觉得是二叉树遍历。京东这套选择题里至少有四到五道是和二叉树相关的包括已知先序中序求后序、已知中序后序求先序、计算二叉树深度和节点数等。这类题的核心就一句话中序序列帮你确定左右子树分界先序或后序帮你确定根节点。我来举个例子假设某二叉树先序遍历结果是ABDCE中序遍历结果是DBACE问后序遍历是什么。解题步骤是这样先序遍历第一个节点A是根节点然后在先序序列里把A划掉剩下BDCE。再到中序序列里找到AA左边的DB是左子树节点A右边的CE是右子树节点。接着从剩余先序序列BDCE中从前往后找第一个出现在左子树节点集合DB里的节点是B说明B是左子树的根。再看B在中序序列里的位置B左边只有一个D所以D是B的左孩子B右边没有节点所以B没有右孩子。同理右子树先序序列里剩下CEC是右子树根C在中序里右边是EE就是C的右孩子。整个树结构还原出来后后序遍历就是DBCEA。实际操作中不需要画图也能推但新手建议还是把树画出来熟练之后可以直接按照“先序定根、中序分组、递归推进”的口诀心算。特别注意一个常见陷阱题目给你的是层次遍历和先序遍历这种情况下单靠这两个序列是无法唯一确定一棵二叉树的出题人偶尔会在选项中放一个“无法确定”来阻止你惯性套公式。2.2 排序算法时间复杂度与稳定性对照表排序算法在选择题里的出镜率非常高尤其是快速排序、堆排序、归并排序这三种高级排序的时间复杂度和稳定性对比。2017年这套题里我记得至少有两道是直接考排序的一道给序列让判断用了哪种排序另一道考不稳定的排序算法有哪些。先把最核心的结论列出来排序算法平均时间复杂度最坏时间复杂度空间复杂度稳定性冒泡排序O(n²)O(n²)O(1)稳定直接插入排序O(n²)O(n²)O(1)稳定简单选择排序O(n²)O(n²)O(1)不稳定希尔排序O(n^1.3左右)O(n²)O(1)不稳定快速排序O(nlogn)O(n²)O(logn)不稳定堆排序O(nlogn)O(nlogn)O(1)不稳定归并排序O(nlogn)O(nlogn)O(n)稳定基数排序O(d(nr))O(d(nr))O(nr)稳定这个表是选择题的送分题来源也是失分重灾区。很多同学把稳定性的概念搞混了稳定排序的定义是如果两个相等的元素在排序前后的相对位置不变那这个排序就是稳定的。可能有人会问相等元素还分什么先后但在实际应用中比如先按学号排序再按成绩排序稳定性就决定了第二次排序能不能保住第一次排序的顺序。所以考场上如果拿不准可以手动模拟两个相同的数走一遍排序过程用三秒钟换一道题的正确性。还有一个高频考点是快速排序的最坏情况很多人记不住快排最坏是O(n²)。其实只要抓住一个事实当每轮选择的基准值都恰好是当前区间最值最大或最小时每次划分只能分割出一个长度为n-1的子区间递归深度变成n层每层比较n次合计就是n²。这个推导过程比死记结论可靠得多考场上如果忘了也能现场推出来。2.3 哈希表与冲突处理平均查找长度怎么算哈希表在选择题里一般不会考得太深但会考两个点一个是哈希函数和冲突处理方式下的查找成功平均长度另一个是哈希表的扩容阈值。冲突处理的两种常见方式是开放定址法线性探测再散列和链地址法。链地址法在选择题中更好算因为每个链表内部的查找长度就是链表的长度平均查找长度等于所有链表节点深度之和除以关键字数量。线性探测再散列则要注意“堆积”现象越是靠后的空位越容易被多个冲突元素抢占导致平均查找长度明显上升。举个例子假设哈希函数是H(key) key % 7依次插入关键字序列8、15、16、22、30、32采用线性探测再散列处理冲突问查找成功的平均查找长度。计算过程8 % 7 1放在位置1查找长度115 % 7 1位置1被占往后找位置2查找长度216 % 7 2位置2被占往后找位置3查找长度222 % 7 1位置1和2和3都被占放到位置4查找长度430 % 7 2位置2到4都被占放到位置5查找长度432 % 7 4位置4被占位置5被占放到位置6查找长度3。总和为16除以6个关键字平均查找成功长度约为2.67。这种题每一步都要把冲突次数数清楚特别是“被占位置”的个数不要数错。我见过很多同学在这里丢掉不该丢的分不是因为不会而是因为算到一半数错了空位。建议做题时在草稿纸上画一张表把位置编号和元素逐个填进去填一个勾一个。2.4 栈与队列出栈序列的判断技巧栈和队列的选择题也是必考的最常见的问题是一个栈的入栈序列是1、2、3、4、5判断以下哪个序列不可能是出栈序列。这种题我以前总是模拟一遍但后来发现有一个效率更高的技巧。核心规律是对于任意一个元素i在它之前入栈而且比它大的元素在出栈序列中必须按照降序排列。换句话说假设栈内压入了1到5出栈时如果某个元素的后面出现了比它先入栈的大元素那这些大元素的顺序必须从大到小。举个反例序列5、4、3、1、2是可能的先入1到55出栈4出栈3出栈然后2出栈前1已经在栈底要出1必须先把2出掉所以1在2后面也是可以的。但序列3、1、5、2、4就不可能因为3出栈后栈内还有1和24还没入栈1出栈后2在栈底此时不可能跳过2先出4而且4还没入栈出栈顺序就乱了。这种题如果时间充裕老老实实模拟永远是最稳妥的办法建议考场上遇到拿不准的直接画栈结构逐步模拟虽然慢但准确率几乎是100%。如果题目量很大就用“大元素逆序”的规律快速筛选。3. 计算机网络TCP、HTTP和DNS的选择题高频套路3.1 TCP三次握手为什么连接要三次、断开要四次京东技术岗的选择题里TCP三次握手几乎每次都会出现但考法很固定基本就是问“为什么连接只需三次握手而释放需要四次”或者“第三次握手失败时会发生什么”先说三次握手的本质客户端发SYN服务端回SYNACK客户端再回ACK这三次握手完成两件关键的事——双方确认自己的发送能力和接收能力都正常同时交换初始序号。有人可能会问两次不行吗如果只有两次握手服务端在收到SYN后直接进入ESTABLISHED状态但此时客户端可能因为网络延迟没有收到SYNACK会认为连接没建立成功然后重发SYN服务端就会同时维护两个连接造成资源浪费。第三次握手就是让服务端确认客户端确实收到了自己的SYNACK。而断开连接要四次挥手是因为TCP连接是全双工的每一侧都要独立关闭自己的数据通道。主动关闭方发FIN被动关闭方回ACK这是第一次关闭发送方向的数据但被动关闭方可能还有数据要发送所以不能立刻也发FIN必须先发完剩余数据再发FIN然后再等对方回ACK所以是四次。这个“被动方还有数据要发”就是四次挥手的根本原因。关于第三次握手失败的处理这是选择题里的经典陷阱。如果服务端发出的SYNACK后一直没有收到客户端的ACK服务端会超时重传SYNACK重传次数达到上限后服务端主动调用close并删除半连接。考生常见错误是认为这个连接会被一直挂起实际上操作系统都有半连接超时和重传上限机制不会无限等待。3.2 HTTP状态码5开头是服务器错4开头是客户端错HTTP状态码这一块基本属于送分题但很多人平时开发只用过200、404、500其他状态码一问就懵。选择题常考的有几个301永久重定向、302临时重定向、304未修改、403禁止访问、404未找到、500服务器内部错误、502网关错误、503服务不可用。里面最容易混淆的是304和302。304表示资源未修改浏览器可以继续使用本地缓存这是协商缓存的响应码302表示资源临时被重定向但搜索引擎会继续抓取旧地址。还有502和503502是网关收到了后端服务器的无效响应503是服务器暂时无法处理请求通常是过载或维护中。做题时抓住“502是前后端之间出问题503是服务器自己扛不住”这个区别就够用了。另外有个网络基础知识也常混在HTTP题里在浏览器输入域名到页面展示经历了哪些步骤。标准答案顺序是DNS解析、TCP连接、发送HTTP请求、服务器处理并返回HTTP响应、浏览器解析渲染页面、断开连接。选择题如果给了乱序选项直接按这个顺序套即可。注意其中TCP连接一般写成三次握手断开连接是四次挥手这两个细节都可能成为判断选项对错的关键点。3.3 DNS解析过程递归和迭代要分清DNS的递归查询和迭代查询也是选择题的常客。简单理解递归查询客户端给本地DNS服务器发一个请求本地DNS服务器负责把这个域名最终解析成IP并返回结果中间如果它自己不知道它会替客户端去问其他服务器整个过程客户端只发一次请求。迭代查询则不同本地DNS服务器自己不知道答案时会告诉客户端“你去问根服务器”客户端再自己发起下一次请求客户端会收到多次指引。一个常见的题型是给出一系列DNS服务器问某个域名的解析过程是递归还是迭代。这里有一个考点要注意从客户端到本地DNS服务器以及本地DNS服务器到根服务器、顶级域服务器、权威服务器之间的查询方式。现实中严格来说本地DNS服务器在内部迭代询问根和顶级域服务器时是迭代而客户端到本地DNS服务器通常是递归。但选择题往往会简化这个模型所以答题时先看题目是“从用户角度”还是“从DNS服务器角度”。这个考点相对来说不是重难点但性价比很高只要把递归和迭代的两个流程图在脑子里过一遍就能做对几乎不需要额外记忆。4. 操作系统和语言基础选择题里的“隐形分仓”4.1 进程与线程资源共享、切换开销、通信方式操作系统在技术选择题里占的份额不小考得最多的是进程和线程的对比。核心结论是进程是资源分配的基本单位线程是CPU调度的基本单位同一进程内的多个线程共享进程的地址空间、全局变量、打开的文件等资源但每个线程有独立的栈、寄存器状态和程序计数器进程之间相互独立切换开销大线程切换开销小。选择题的陷阱常出在“共享”这个词上。很多同学只记得线程共享进程的资源却忘了栈是不共享的所以在“以下哪项是线程私有”的题里选了栈。这类题基本每年都有我印象里京东这套选择题里也有类似选项做的时候一定要把“线程私有 栈 寄存器 程序计数器”当成固定组合来记。进程间通信方式也是高频考点常考的有管道、消息队列、共享内存、信号量和套接字。特别注意共享内存是效率最高的IPC方式因为它不需要内核在进程间拷贝数据但同时需要同步机制比如信号量来避免竞态条件。有题目可能会在选项里故意说“共享内存不需要同步”这种错误选项就是用来坑新手的。4.2 死锁四个必要条件与处理策略死锁考的其实是死记硬背加一点逻辑判断。四个必要条件必须记住互斥、请求与保持、不可剥夺、循环等待。选择题常常给四个场景让你判断哪个满足死锁条件或者问破坏哪个条件可以预防死锁。要灵活运用不能只会背定义。比如“一个进程持有一把锁又去请求另一把锁而另一个进程持有第二把锁又请求第一把锁”这就是典型的循环等待破坏办法是让所有进程按固定顺序加锁这就是死锁预防中的“资源有序分配法”。而银行家算法属于死锁避免不是预防选择题里喜欢在“预防”和“避免”这两个词上做文章看题时一定要先看清问的是哪个。4.3 Java基础集合、String、继承与多态Java基础在京东这种电商公司的校招题里几乎必考而且喜欢考集合类的底层结构。常考的几个点HashMap的底层在JDK8是数组链表红黑树链表转红黑树的阈值是8红黑树转回链表的阈值是6ArrayList基于动态数组LinkedList基于双向链表HashSet基于HashMap实现。选择题可能会给一个使用场景问应该选哪个集合类比如“需要频繁随机访问且很少增删中间元素”应该选ArrayList而不是LinkedList。String和StringBuilder的区别也是经典考点String是不可变对象每次拼接都会创建新对象StringBuilder是可变对象拼接效率高但线程不安全StringBuffer线程安全但性能相对低。选择题常常会问“以下哪种方式拼接字符串效率最高”如果是在循环里拼接答案是StringBuilder。继承和多态方面的题则比较常规考多态时通常会给出父类引用指向子类对象然后调用一个被重写的方法问输出什么。关键在于弄明白动态绑定的规则调用哪个方法在运行时由对象的实际类型决定而不是引用类型决定。但如果子类重载方法而没重写父类方法调用的还是父类方法这里很容易被绕进去。4.4 内存管理堆、栈、方法区与垃圾回收JVM内存区域的选择题常见的问法成员变量存在哪里、局部变量存在哪里、字符串常量存在哪里。规则是对象实例和数组分配在堆中局部变量和方法调用帧在虚拟机栈中类的元信息、静态变量、常量池常驻在方法区JDK8之后元空间替代了永久代但选择题一般不会追问到这个层面。垃圾回收方面常见的是判断哪些对象可以被回收核心是可达性分析法从GC Roots出发找不到引用链的对象会被标记回收。选择题常迷惑点是将“引用计数法”和“可达性分析”混在一起说某个对象被循环引用所以不能回收实际上现代JVM用的是可达性分析循环引用的对象只要不可达照样会被回收。5. 常见问题与答题技巧实战排查5.1 审题陷阱自查表我把自己和周围同学当年做这套选择题踩过的坑整理成了一张清单每条后面附了规避方法供大家对照自查陷阱类型常见表现错误后果规避方法单位不敏感时间复杂度问的是最坏而不是平均选错复杂度读题时圈出“最坏/平均/最好”边界漏读i n看成i n循环次数判断失误把代码里的符号抄到草稿纸上概念混淆预防死锁vs避免死锁选错策略做题前先默写定义稳定性丢词排序稳定性问题只看了复杂度选错排序算法先圈关键词再作答选项倒装问“不属于”而不是“属于”正确答案被忽略在“不/错误/无法”上画重点符号计算粗心哈希表冲突次数数错平均查找长度算错画表逐步填数不要心算这套表我自己贴在了错题本的第一页每次模拟练习前看一遍能明显减少低级失误。特别提醒那些平时代码写得还不错但笔试分数上不去的同学很多时候不是不会而是审题时太自信了。5.2 时间分配与做题顺序建议30道选择题45分钟平均每道题只有1分半钟时间其实非常紧。我推荐的做题顺序是先做数据结构、语言基础等自己最有把握的题把该拿的分稳稳拿下再做网络、操作系统最后啃那种计算量较大的复杂度题和哈希表题。如果某道题超过两分钟还没有思路果断先跳过等做完后面所有题再回头处理。为什么这样安排因为选择题的分数是均匀分布的一道难题和一道简单题同样是一分但难题消耗的时间可能是简单题的三到四倍。先把简单题拿完心态会稳很多再回头做难题时不会因为前面的空白而焦虑。我有一个同学当年考试就是在第一道二叉树题上纠结了十分钟导致后面十几道题都是乱赶做完的结果只得了不到一半的分数非常可惜。5.3 错题复盘的具体操作方法错题复盘不是把正确答案抄在旁边就完事了我的做法是把每道错题拆成三个问题第一这个知识点我懂不懂第二我是因为什么原因错的第三下次遇到同类型的题应该用什么流程来解举个例子如果一道HashMap的题我做错了我会在错题本上写知识点懂原因是把JDK8的链表转红黑树阈值8记成了7下次遇到类似题先默写“8转红黑树、6转链表、默认负载因子0.75”再去看选项。这样复盘过一次后续基本不会再错。复盘的时间也很关键建议当天做完题当天复盘隔夜之后当时的思路可能就模糊了很多判断的依据会被遗忘。每天花二十分钟复盘十道错题比第二天再做一套新卷子效果要好得多。5.4 选择题之外的延伸准备虽然这篇文章讲的是选择题但我要多提醒一句选择题的考点和面试的基础题高度重合。在京东2017校招后续的面试环节里面试官很可能直接问“你在选择题里遇到过二叉树遍历吧现在手写一个非递归中序遍历。”所以准备选择题的时候不要把知识点当成一次性工具要把它们当成后续面试的素材库。每复习一个考点顺手想一想如果面试官让我在纸上写出来、或者让我解释给别人听我能不能说清楚如果你能对着镜子或者找同学讲明白“为什么快速排序是不稳定的”那这个知识点你是真的掌握了不管它换什么题型出现你都不会太吃亏。我个人在实际备考中的体会是技术类选择题就像是一场基础功的随堂测验它不考天赋考的是你有没有把该背的概念背熟、把该算的例子算清、把该踩的坑踩完。刷京东这套题也好刷其他大厂的选择题也好最重要的是把一套题吃透而不是囫囵吞枣地刷十套。最后再分享一个小技巧考前一天不需要再刷题了把错题本上的陷阱清单翻一遍比什么复习资料都管用这大概是我整个秋招备考里性价比最高的一步。