计算机博士面试题汇总计算机网络 | 操作系统 | 算法与数据结构 | 人工智能说在前面西南交大和成电的面试心得西南交大老师和蔼一点专业课抽两道题有主观的题也有问文件系统的题电科老师比较严肃专业课是计组、操作系统、数据结构及C语言三个方向各一道比较经典。英语部分电科自我介绍完了会针对你的简历提问西南交大是抽题读一遍并翻译 目录一、计算机网络1. TCP 和 UDP 的主要区别及应用场景2. OSI 七层模型 vs TCP/IP 四层模型3. TCP/IP 协议栈结构及常见协议4. TCP 拥塞控制算法5. TCP 三次握手与四次挥手6. HTTP 与 HTTPS 的区别二、操作系统1. 进程与线程的区别及线程优势2. 死锁及预防3. 乐观锁与悲观锁三、算法与数据结构1. 哈希表2. 二叉树遍历与重建3. 栈与队列4. 快速排序5. 动态规划6. 最短路径算法Dijkstra vs Floyd7. 拓扑排序四、人工智能1. 过拟合及防止方法2. 卷积神经网络CNN一、计算机网络1. TCP 和 UDP 的主要区别及应用场景特性TCPUDP连接方式面向连接无连接可靠性可靠传输确认、重传、排序不可靠传输传输效率较低开销大较高开销小数据边界字节流无边界报文保留边界拥塞控制有无应用场景TCP文件下载FTP、网页浏览HTTP/HTTPS、邮件传输SMTPUDP实时音视频通话、在线游戏、DNS 查询、直播推流2. OSI 七层模型 vs TCP/IP 四层模型OSI 七层模型层级名称主要功能7应用层为应用程序提供网络服务接口HTTP、FTP、SMTP6表示层数据格式转换、加密解密、压缩解压SSL/TLS5会话层建立、管理、终止会话同步、断点续传4传输层端到端可靠/不可靠传输、端口寻址、流量控制TCP/UDP3网络层主机到主机的逻辑寻址、路由选择、分组转发IP2数据链路层相邻节点间可靠传输、物理寻址MAC、帧同步1物理层比特流的物理传输电压、接口、线缆TCP/IP 四层模型层级对应 OSI主要功能常见协议应用层应用层表示层会话层直接面向用户程序HTTP、FTP、DNS、SSH、SMTP传输层传输层端到端通信TCP、UDP网络层网络层跨网络路由、IP 寻址IP、ICMP、IGMP网络接口层数据链路层物理层物理传输帧封装Ethernet、WiFi、ARP3. TCP/IP 协议栈结构及常见协议┌─────────────────────────────────────┐ │ 应用层报文 │ HTTP/HTTPS/FTP/SSH/DNS/SMTP ├─────────────────────────────────────┤ │ 传输层段/数据报 │ TCP可靠、滑动窗口、拥塞控制 │ │ UDP无连接、快速 ├─────────────────────────────────────┤ │ 网络层包/分组 │ IP无连接、尽力交付 │ │ ICMP控制报文/ IGMP组管理 ├─────────────────────────────────────┤ │ 网络接口层帧/比特流 │ Ethernet、WiFi、ARPIP→MAC └─────────────────────────────────────┘核心要点发送方自上而下逐层添加首部封装接收方自下而上逐层解封装提取首部后交付上层本质链路层传帧 网络层寻址路由 传输层端到端 应用层定语义4. TCP 拥塞控制算法算法核心思想慢启动Slow Start初始拥塞窗口cwnd1每轮 RTT 翻倍慢慢探测网络可用带宽避免一开始就洪泛网络拥塞避免Congestion Avoidance当cwnd达到慢启动阈值ssthresh后改为线性增长接近网络容量时保守增长快重传Fast Retransmit收到3 个重复 ACK时立即重传丢失报文段不等待超时快恢复Fast Recovery配合快重传将ssthresh设为当前cwnd的一半cwnd也设为一半直接进入拥塞避免阶段替代慢启动面试常考点快重传和快恢复是配套使用的目的是避免一丢包就回到慢启动提高网络吞吐量。5. TCP 三次握手与四次挥手三次握手建立连接客户端 A 服务端 B │ ─────── SYN, seqx ─────── │ │ │ │ ── SYN-ACK, seqy, ackx1 ─ │ │ │ │ ─────── ACK, acky1 ────── │ │ │ │◄──────── ESTABLISHED ───────►│第一次客户端发送SYN携带初始序列号seqx第二次服务端回复SYN-ACK携带自己的初始序列号seqy并确认ackx1第三次客户端回复ACK确认acky1连接建立❓为什么是三次防止历史重复连接请求造成错误同时确保双方收发能力正常。四次挥手断开连接客户端 A 服务端 B │ ─────── FIN, sequ ──────── │ │ │ │ ──────── ACK, acku1 ────── │ 服务端继续发送剩余数据 │ │ │ ── FIN, seqw, acku1 ──── │ 服务端数据发完请求关闭 │ │ │ ─────── ACK, ackw1 ────── │ │ │ │ 等待 2MSL 后彻底关闭 │第一次客户端发送FIN请求关闭发送通道第二次服务端回复ACK但可能还有数据要发第三次服务端数据发完发送FIN请求关闭自己的发送通道第四次客户端回复ACK进入TIME_WAIT状态等待2MSL后彻底关闭2MSL 的作用确保最后一个 ACK 能被服务端收到让网络中滞留的旧报文段全部消失。6. HTTP 与 HTTPS 的区别特性HTTPHTTPS全称超文本传输协议超文本传输安全协议安全性明文传输加密传输TLS/SSL端口80443证书无需需要 CA 证书握手过程TCP 三次握手后直接传输TCP 握手 TLS 握手后传输层级应用层 → TCP应用层 → TLS/SSL → TCPTLS 握手简述客户端和服务端协商加密算法、交换公钥、生成会话密钥后续通信使用该密钥对称加密。二、操作系统1. 进程与线程的区别及线程优势特性进程Process线程Thread基本单位资源分配的基本单位CPU 调度的基本单位地址空间独立的地址空间共享所属进程的地址空间切换开销大需切换页表、刷新 TLB小只需保存寄存器、栈通信方式IPC管道、消息队列、共享内存等直接读写共享变量崩溃影响不影响其他进程可能导致整个进程崩溃线程引入的优势创建开销小无需分配独立地址空间资源共享线程间可直接共享内存数据响应性提高单进程多线程模型中某线程阻塞时其他线程仍可响应请求并发性提升多核 CPU 上可真正实现并行计算⚠️代价线程以共享地址空间换取效率但也带来了线程安全问题竞态条件、死锁等。2. 死锁及预防什么是死锁一组线程/进程因循环等待对方持有的资源而永久阻塞的现象。若无外力干预这些进程/线程将永远无法继续执行。死锁的四个必要条件Coffman 条件条件说明互斥条件一段时间内资源仅被一个进程占用请求和保持进程因请求新资源而阻塞时对已获得的资源不释放非剥夺条件进程已获得的资源只能在使用完成后才能被释放不能被强制抢占循环等待发生死锁时必然存在一个进程-资源的循环等待链死锁的预防策略策略方法预防死锁设置限制条件破坏四个必要条件中的一个或多个避免死锁动态分配资源时用算法如银行家算法防止系统进入不安全状态检测与恢复允许死锁发生定期检测并强制剥夺资源或终止进程忽略死锁鸵鸟策略假设死锁不会发生如大多数操作系统采用银行家算法核心在资源分配前模拟分配检查系统是否仍处于安全状态存在安全序列若安全则分配否则拒绝。3. 乐观锁与悲观锁悲观锁Pessimistic Locking核心思想假设冲突一定会发生每次访问数据时先加锁确保其他线程无法同时修改。实现方式数据库中的SELECT ... FOR UPDATE、Java 的synchronized、ReentrantLock适用场景写多读少、并发冲突激烈的场景优点数据安全性高不会出现脏读、幻读缺点加锁开销大容易引发死锁降低并发性能// 悲观锁示例Javasynchronized(obj){// 临界区只有获得锁的线程能执行balance-amount;}乐观锁Optimistic Locking核心思想假设冲突很少发生先不加锁执行操作提交时检查数据是否被其他线程修改过若被修改则重试或报错。实现方式版本号Version、时间戳Timestamp、CASCompare-And-Swap适用场景读多写少、并发冲突较少的场景优点无锁开销不会死锁并发性能高缺点冲突频繁时重试开销大存在 ABA 问题CAS 特有// 乐观锁示例版本号机制UPDATEaccountSETbalancebalance-100,versionversion1WHEREid1ANDversion#{currentVersion};// 若返回影响行数为0说明数据已被修改需重试// CAS 示例Java AtomicIntegerAtomicIntegercounternewAtomicInteger(0);counter.compareAndSet(0,1);// 期望值0更新值1对比总结维度悲观锁乐观锁思想先加锁再操作先操作提交时校验锁机制真正的锁互斥锁、行锁无锁版本号、CAS适用场景写多读少、冲突频繁读多写少、冲突稀少性能冲突多时更稳定冲突少时性能极高死锁风险有无ABA 问题无CAS 实现需注意面试扩展Redis 分布式锁是悲观锁思想的延伸StampedLock是 Java 8 引入的乐观读锁实现。三、算法与数据结构1. 哈希表定义通过哈希函数将键Key映射到数组下标实现快速数据存取的数据结构。本质是空间换时间。时间复杂度平均情况O(1)查找、插入、删除最坏情况O(n)所有键冲突退化为链表冲突Collision不同键通过哈希函数计算后得到相同的数组下标。解决冲突的方法方法原理链地址法Separate Chaining每个槽位维护一个链表/红黑树冲突元素链入其中开放寻址法Open Addressing冲突时按探测序列线性探测、二次探测、双重哈希寻找下一个空槽再哈希法Rehashing使用多个哈希函数冲突时换另一个函数计算JavaHashMap实现数组 链表 红黑树链表长度 ≥ 8 时转为红黑树提升最坏情况性能。2. 二叉树遍历与重建三种遍历方式遍历方式顺序前序遍历Pre-order根 → 左 → 右中序遍历In-order左 → 根 → 右后序遍历Post-order左 → 右 → 根重建二叉树核心条件必须包含中序遍历因为中序可以确定左右子树的边界。前序 中序→ 可重建唯一二叉树后序 中序→ 可重建唯一二叉树前序 后序→ 无法重建唯一二叉树无法确定左右子树边界⚠️例外若树是满二叉树或所有节点度为 0/2完全二叉树则前序后序可重建。复杂度时间O(n)空间O(n)递归栈 哈希表存储中序索引。3. 栈与队列特性栈Stack队列Queue原则先进后出LIFO先进先出FIFO操作端仅在栈顶插入/删除队尾插入队首删除实现数组 / 链表数组循环队列/ 链表典型应用场景数据结构应用场景栈函数调用栈、表达式求值、括号匹配、DFS 深度优先遍历、递归回溯算法队列操作系统进程调度、消息队列、BFS 广度优先遍历、缓存实现LRU4. 快速排序基本思想基于分治Divide and Conquer选择一个基准值pivot将数组划分为小于 pivot和大于 pivot的两部分递归排序。复杂度分析情况时间复杂度空间复杂度最好O(n log n)O(log n)递归栈平均O(n log n)O(log n)最坏O(n²)已排序数组pivot 选端点O(n)优化策略随机选 pivot避免最坏情况三数取中法取头、中、尾的中位数小区间改用插入排序三路快排处理大量重复元素5. 动态规划DP核心思想将复杂问题分解为重叠子问题通过记忆化或递推避免重复计算以空间换时间。适用问题类型最优化问题求最大/最小值如背包问题计数问题求方案数如爬楼梯存在性问题判断是否可行如单词拆分经典例题问题状态定义转移方程0/1 背包dp[i][w]前 i 个物品容量 w 的最大价值dp[i][w] max(dp[i-1][w], dp[i-1][w-weight[i]] value[i])最长递增子序列LISdp[i]以 nums[i] 结尾的最长递增子序列长度dp[i] max(dp[j] 1)其中j i且nums[j] nums[i]最长公共子序列LCSdp[i][j]text1[0…i] 和 text2[0…j] 的 LCS 长度若相等dp[i][j] dp[i-1][j-1] 1否则max(dp[i-1][j], dp[i][j-1])旅行商问题TSP状态压缩 DPdp[mask][i]枚举子集转移解题步骤定义状态 → 找状态转移方程 → 确定初始条件和边界 → 确定遍历顺序 → 优化空间可选。6. 最短路径算法Dijkstra vs Floyd问题定义给定带权图G(V, E)寻找从起点到终点或所有点对之间的路径权重之和最小的路径。算法DijkstraFloyd-Warshall核心思想贪心策略每次选择距离源点最近的未确定顶点松弛其邻边动态规划逐轮允许经过更多中间顶点更新所有点对距离适用图非负权图任意权图可处理负权但不能有负权环时间复杂度O((VE) log V)优先队列优化O(V³)空间复杂度O(V)O(V²)求解目标单源最短路径全源最短路径Dijkstra 伪代码dist[inf]*n dist[start]0pq[(0,start)]# (距离, 节点)whilepq:d,uheappop(pq)ifddist[u]:continueforv,wingraph[u]:ifdist[u]wdist[v]:dist[v]dist[u]w heappush(pq,(dist[v],v))Floyd 核心递推式dp[k][i][j] min(dp[k-1][i][j], dp[k-1][i][k] dp[k-1][k][j])表示从 i 到 j只允许经过前 k 个顶点作为中间点的最短距离。可滚动数组优化为二维。7. 拓扑排序问题背景拓扑排序Topological Sort是对**有向无环图DAG, Directed Acyclic Graph**的节点进行线性排序使得对于图中的每一条有向边(u, v)节点u在排序结果中始终位于节点v之前。典型应用课程选修计划先修课问题、任务调度依赖关系、编译顺序、Makefile 依赖解析。核心思想repeatedly find vertices with no incoming edges一个 DAG 中入度为 0 的节点表示没有前置依赖可以最先执行。每处理完一个节点将其所有邻接节点的入度减 1新的入度为 0 的节点继续入队。算法步骤Kahn 算法BFS 实现1. 计算所有节点的入度indegree 2. 将所有入度为 0 的节点加入队列 3. while 队列不为空 a. 取出队首节点 u加入结果列表 b. 遍历 u 的所有邻接节点 v - 将 v 的入度减 1 - 若 v 的入度变为 0将 v 入队 4. 若结果列表中节点数 总节点数则排序成功 否则图中存在环无法进行拓扑排序代码实现Pythonfromcollectionsimportdequedeftopological_sort(n,edges):# 建图 计算入度graph[[]for_inrange(n)]indegree[0]*nforu,vinedges:graph[u].append(v)indegree[v]1# 入度为 0 的节点入队queuedeque([iforiinrange(n)ifindegree[i]0])result[]whilequeue:uqueue.popleft()result.append(u)forvingraph[u]:indegree[v]-1ifindegree[v]0:queue.append(v)# 判断是否有环iflen(result)!n:return[]# 图中存在环returnresult复杂度分析时间复杂度O(V E)每个节点和边各访问一次空间复杂度O(V E)邻接表 入度数组 队列DFS 实现思路deftopological_sort_dfs(n,edges):graph[[]for_inrange(n)]foru,vinedges:graph[u].append(v)visited[0]*n# 0未访问, 1访问中, 2已访问result[]defdfs(u):ifvisited[u]1:# 遇到访问中的节点说明有环returnFalseifvisited[u]2:returnTruevisited[u]1# 标记访问中forvingraph[u]:ifnotdfs(v):returnFalsevisited[u]2# 标记已访问result.append(u)# 后序遍历加入结果returnTrueforiinrange(n):ifvisited[i]0:ifnotdfs(i):return[]# 有环returnresult[::-1]# 逆序输出BFS vs DFSKahnBFS更直观适合求字典序最小的拓扑序用优先队列DFS 利用后序遍历特性代码更简洁。面试常考点拓扑排序可以检测有向图是否存在环若要求所有可能的拓扑排序需用回溯法。四、人工智能1. 过拟合及防止方法定义模型在训练集上表现很好但在测试集上表现很差的现象。本质是模型学到了训练数据中的噪声和特异性而没有学到数据的通用规律。防止过拟合的方法方法原理正则化RegularizationL1/L2 正则化在损失函数中增加对模型参数的惩罚迫使参数趋向简单Dropout训练时以概率p随机关闭部分神经元强制网络不依赖特定路径仅用于训练阶段早停Early Stopping当验证集性能连续多轮不再提升时提前终止训练数据增强Data Augmentation通过旋转、翻转、裁剪等变换扩充训练样本多样性降低模型复杂度减少网络层数、神经元数量或使用更简单的模型交叉验证Cross-ValidationK 折交叉验证更充分地利用数据评估模型泛化能力集成学习EnsembleBagging、Boosting通过多个模型投票降低方差2. 卷积神经网络CNN定义一种专门处理图像、时间序列等网格结构数据的深度学习框架核心在于用卷积运算代替全连接层通过局部感知和参数共享高效提取特征。核心组成层级作用卷积层Convolutional Layer通过卷积核滤波器提取局部特征边缘、纹理、形状等激活层Activation Layer引入非线性ReLU、Sigmoid、Tanh增强模型表达能力池化层Pooling Layer降采样Max Pooling / Average Pooling减少参数量增强平移不变性全连接层Fully Connected Layer将提取到的高层特征映射到分类空间输出最终预测结果批归一化Batch Normalization加速训练收敛起到一定正则化效果Dropout 层防止过拟合核心优势参数共享同一个卷积核在整个输入上滑动大幅减少参数量局部连接每个神经元只连接输入的局部区域符合图像局部相关性平移不变性池化操作使模型对目标位置变化具有一定鲁棒性层次化特征提取浅层提取边缘/纹理深层提取语义/部件/物体经典架构LeNet → AlexNet → VGGNet → ResNet残差连接解决梯度消失→ EfficientNet。 面试建议理解原理优于背诵能画图解释三次握手、能手写快排代码、能推导 DP 转移方程结合项目经验回答时关联自己的科研或项目经历体现深度思考关注前沿了解 HTTP/3QUIC、eBPF、Transformer 架构等最新技术趋势准备手撕代码拓扑排序、二叉树重建、最短路径等高频题建议熟练默写
计算机博士面试题汇总计算机网络 | 操作系统 | 算法与数据结构 | 人工智能说在前面西南交大和成电的面试心得西南交大老师和蔼一点专业课抽两道题有主观的题也有问文件系统的题电科老师比较严肃专业课是计组、操作系统、数据结构及C语言三个方向各一道比较经典。英语部分电科自我介绍完了会针对你的简历提问西南交大是抽题读一遍并翻译 目录一、计算机网络1. TCP 和 UDP 的主要区别及应用场景2. OSI 七层模型 vs TCP/IP 四层模型3. TCP/IP 协议栈结构及常见协议4. TCP 拥塞控制算法5. TCP 三次握手与四次挥手6. HTTP 与 HTTPS 的区别二、操作系统1. 进程与线程的区别及线程优势2. 死锁及预防3. 乐观锁与悲观锁三、算法与数据结构1. 哈希表2. 二叉树遍历与重建3. 栈与队列4. 快速排序5. 动态规划6. 最短路径算法Dijkstra vs Floyd7. 拓扑排序四、人工智能1. 过拟合及防止方法2. 卷积神经网络CNN一、计算机网络1. TCP 和 UDP 的主要区别及应用场景特性TCPUDP连接方式面向连接无连接可靠性可靠传输确认、重传、排序不可靠传输传输效率较低开销大较高开销小数据边界字节流无边界报文保留边界拥塞控制有无应用场景TCP文件下载FTP、网页浏览HTTP/HTTPS、邮件传输SMTPUDP实时音视频通话、在线游戏、DNS 查询、直播推流2. OSI 七层模型 vs TCP/IP 四层模型OSI 七层模型层级名称主要功能7应用层为应用程序提供网络服务接口HTTP、FTP、SMTP6表示层数据格式转换、加密解密、压缩解压SSL/TLS5会话层建立、管理、终止会话同步、断点续传4传输层端到端可靠/不可靠传输、端口寻址、流量控制TCP/UDP3网络层主机到主机的逻辑寻址、路由选择、分组转发IP2数据链路层相邻节点间可靠传输、物理寻址MAC、帧同步1物理层比特流的物理传输电压、接口、线缆TCP/IP 四层模型层级对应 OSI主要功能常见协议应用层应用层表示层会话层直接面向用户程序HTTP、FTP、DNS、SSH、SMTP传输层传输层端到端通信TCP、UDP网络层网络层跨网络路由、IP 寻址IP、ICMP、IGMP网络接口层数据链路层物理层物理传输帧封装Ethernet、WiFi、ARP3. TCP/IP 协议栈结构及常见协议┌─────────────────────────────────────┐ │ 应用层报文 │ HTTP/HTTPS/FTP/SSH/DNS/SMTP ├─────────────────────────────────────┤ │ 传输层段/数据报 │ TCP可靠、滑动窗口、拥塞控制 │ │ UDP无连接、快速 ├─────────────────────────────────────┤ │ 网络层包/分组 │ IP无连接、尽力交付 │ │ ICMP控制报文/ IGMP组管理 ├─────────────────────────────────────┤ │ 网络接口层帧/比特流 │ Ethernet、WiFi、ARPIP→MAC └─────────────────────────────────────┘核心要点发送方自上而下逐层添加首部封装接收方自下而上逐层解封装提取首部后交付上层本质链路层传帧 网络层寻址路由 传输层端到端 应用层定语义4. TCP 拥塞控制算法算法核心思想慢启动Slow Start初始拥塞窗口cwnd1每轮 RTT 翻倍慢慢探测网络可用带宽避免一开始就洪泛网络拥塞避免Congestion Avoidance当cwnd达到慢启动阈值ssthresh后改为线性增长接近网络容量时保守增长快重传Fast Retransmit收到3 个重复 ACK时立即重传丢失报文段不等待超时快恢复Fast Recovery配合快重传将ssthresh设为当前cwnd的一半cwnd也设为一半直接进入拥塞避免阶段替代慢启动面试常考点快重传和快恢复是配套使用的目的是避免一丢包就回到慢启动提高网络吞吐量。5. TCP 三次握手与四次挥手三次握手建立连接客户端 A 服务端 B │ ─────── SYN, seqx ─────── │ │ │ │ ── SYN-ACK, seqy, ackx1 ─ │ │ │ │ ─────── ACK, acky1 ────── │ │ │ │◄──────── ESTABLISHED ───────►│第一次客户端发送SYN携带初始序列号seqx第二次服务端回复SYN-ACK携带自己的初始序列号seqy并确认ackx1第三次客户端回复ACK确认acky1连接建立❓为什么是三次防止历史重复连接请求造成错误同时确保双方收发能力正常。四次挥手断开连接客户端 A 服务端 B │ ─────── FIN, sequ ──────── │ │ │ │ ──────── ACK, acku1 ────── │ 服务端继续发送剩余数据 │ │ │ ── FIN, seqw, acku1 ──── │ 服务端数据发完请求关闭 │ │ │ ─────── ACK, ackw1 ────── │ │ │ │ 等待 2MSL 后彻底关闭 │第一次客户端发送FIN请求关闭发送通道第二次服务端回复ACK但可能还有数据要发第三次服务端数据发完发送FIN请求关闭自己的发送通道第四次客户端回复ACK进入TIME_WAIT状态等待2MSL后彻底关闭2MSL 的作用确保最后一个 ACK 能被服务端收到让网络中滞留的旧报文段全部消失。6. HTTP 与 HTTPS 的区别特性HTTPHTTPS全称超文本传输协议超文本传输安全协议安全性明文传输加密传输TLS/SSL端口80443证书无需需要 CA 证书握手过程TCP 三次握手后直接传输TCP 握手 TLS 握手后传输层级应用层 → TCP应用层 → TLS/SSL → TCPTLS 握手简述客户端和服务端协商加密算法、交换公钥、生成会话密钥后续通信使用该密钥对称加密。二、操作系统1. 进程与线程的区别及线程优势特性进程Process线程Thread基本单位资源分配的基本单位CPU 调度的基本单位地址空间独立的地址空间共享所属进程的地址空间切换开销大需切换页表、刷新 TLB小只需保存寄存器、栈通信方式IPC管道、消息队列、共享内存等直接读写共享变量崩溃影响不影响其他进程可能导致整个进程崩溃线程引入的优势创建开销小无需分配独立地址空间资源共享线程间可直接共享内存数据响应性提高单进程多线程模型中某线程阻塞时其他线程仍可响应请求并发性提升多核 CPU 上可真正实现并行计算⚠️代价线程以共享地址空间换取效率但也带来了线程安全问题竞态条件、死锁等。2. 死锁及预防什么是死锁一组线程/进程因循环等待对方持有的资源而永久阻塞的现象。若无外力干预这些进程/线程将永远无法继续执行。死锁的四个必要条件Coffman 条件条件说明互斥条件一段时间内资源仅被一个进程占用请求和保持进程因请求新资源而阻塞时对已获得的资源不释放非剥夺条件进程已获得的资源只能在使用完成后才能被释放不能被强制抢占循环等待发生死锁时必然存在一个进程-资源的循环等待链死锁的预防策略策略方法预防死锁设置限制条件破坏四个必要条件中的一个或多个避免死锁动态分配资源时用算法如银行家算法防止系统进入不安全状态检测与恢复允许死锁发生定期检测并强制剥夺资源或终止进程忽略死锁鸵鸟策略假设死锁不会发生如大多数操作系统采用银行家算法核心在资源分配前模拟分配检查系统是否仍处于安全状态存在安全序列若安全则分配否则拒绝。3. 乐观锁与悲观锁悲观锁Pessimistic Locking核心思想假设冲突一定会发生每次访问数据时先加锁确保其他线程无法同时修改。实现方式数据库中的SELECT ... FOR UPDATE、Java 的synchronized、ReentrantLock适用场景写多读少、并发冲突激烈的场景优点数据安全性高不会出现脏读、幻读缺点加锁开销大容易引发死锁降低并发性能// 悲观锁示例Javasynchronized(obj){// 临界区只有获得锁的线程能执行balance-amount;}乐观锁Optimistic Locking核心思想假设冲突很少发生先不加锁执行操作提交时检查数据是否被其他线程修改过若被修改则重试或报错。实现方式版本号Version、时间戳Timestamp、CASCompare-And-Swap适用场景读多写少、并发冲突较少的场景优点无锁开销不会死锁并发性能高缺点冲突频繁时重试开销大存在 ABA 问题CAS 特有// 乐观锁示例版本号机制UPDATEaccountSETbalancebalance-100,versionversion1WHEREid1ANDversion#{currentVersion};// 若返回影响行数为0说明数据已被修改需重试// CAS 示例Java AtomicIntegerAtomicIntegercounternewAtomicInteger(0);counter.compareAndSet(0,1);// 期望值0更新值1对比总结维度悲观锁乐观锁思想先加锁再操作先操作提交时校验锁机制真正的锁互斥锁、行锁无锁版本号、CAS适用场景写多读少、冲突频繁读多写少、冲突稀少性能冲突多时更稳定冲突少时性能极高死锁风险有无ABA 问题无CAS 实现需注意面试扩展Redis 分布式锁是悲观锁思想的延伸StampedLock是 Java 8 引入的乐观读锁实现。三、算法与数据结构1. 哈希表定义通过哈希函数将键Key映射到数组下标实现快速数据存取的数据结构。本质是空间换时间。时间复杂度平均情况O(1)查找、插入、删除最坏情况O(n)所有键冲突退化为链表冲突Collision不同键通过哈希函数计算后得到相同的数组下标。解决冲突的方法方法原理链地址法Separate Chaining每个槽位维护一个链表/红黑树冲突元素链入其中开放寻址法Open Addressing冲突时按探测序列线性探测、二次探测、双重哈希寻找下一个空槽再哈希法Rehashing使用多个哈希函数冲突时换另一个函数计算JavaHashMap实现数组 链表 红黑树链表长度 ≥ 8 时转为红黑树提升最坏情况性能。2. 二叉树遍历与重建三种遍历方式遍历方式顺序前序遍历Pre-order根 → 左 → 右中序遍历In-order左 → 根 → 右后序遍历Post-order左 → 右 → 根重建二叉树核心条件必须包含中序遍历因为中序可以确定左右子树的边界。前序 中序→ 可重建唯一二叉树后序 中序→ 可重建唯一二叉树前序 后序→ 无法重建唯一二叉树无法确定左右子树边界⚠️例外若树是满二叉树或所有节点度为 0/2完全二叉树则前序后序可重建。复杂度时间O(n)空间O(n)递归栈 哈希表存储中序索引。3. 栈与队列特性栈Stack队列Queue原则先进后出LIFO先进先出FIFO操作端仅在栈顶插入/删除队尾插入队首删除实现数组 / 链表数组循环队列/ 链表典型应用场景数据结构应用场景栈函数调用栈、表达式求值、括号匹配、DFS 深度优先遍历、递归回溯算法队列操作系统进程调度、消息队列、BFS 广度优先遍历、缓存实现LRU4. 快速排序基本思想基于分治Divide and Conquer选择一个基准值pivot将数组划分为小于 pivot和大于 pivot的两部分递归排序。复杂度分析情况时间复杂度空间复杂度最好O(n log n)O(log n)递归栈平均O(n log n)O(log n)最坏O(n²)已排序数组pivot 选端点O(n)优化策略随机选 pivot避免最坏情况三数取中法取头、中、尾的中位数小区间改用插入排序三路快排处理大量重复元素5. 动态规划DP核心思想将复杂问题分解为重叠子问题通过记忆化或递推避免重复计算以空间换时间。适用问题类型最优化问题求最大/最小值如背包问题计数问题求方案数如爬楼梯存在性问题判断是否可行如单词拆分经典例题问题状态定义转移方程0/1 背包dp[i][w]前 i 个物品容量 w 的最大价值dp[i][w] max(dp[i-1][w], dp[i-1][w-weight[i]] value[i])最长递增子序列LISdp[i]以 nums[i] 结尾的最长递增子序列长度dp[i] max(dp[j] 1)其中j i且nums[j] nums[i]最长公共子序列LCSdp[i][j]text1[0…i] 和 text2[0…j] 的 LCS 长度若相等dp[i][j] dp[i-1][j-1] 1否则max(dp[i-1][j], dp[i][j-1])旅行商问题TSP状态压缩 DPdp[mask][i]枚举子集转移解题步骤定义状态 → 找状态转移方程 → 确定初始条件和边界 → 确定遍历顺序 → 优化空间可选。6. 最短路径算法Dijkstra vs Floyd问题定义给定带权图G(V, E)寻找从起点到终点或所有点对之间的路径权重之和最小的路径。算法DijkstraFloyd-Warshall核心思想贪心策略每次选择距离源点最近的未确定顶点松弛其邻边动态规划逐轮允许经过更多中间顶点更新所有点对距离适用图非负权图任意权图可处理负权但不能有负权环时间复杂度O((VE) log V)优先队列优化O(V³)空间复杂度O(V)O(V²)求解目标单源最短路径全源最短路径Dijkstra 伪代码dist[inf]*n dist[start]0pq[(0,start)]# (距离, 节点)whilepq:d,uheappop(pq)ifddist[u]:continueforv,wingraph[u]:ifdist[u]wdist[v]:dist[v]dist[u]w heappush(pq,(dist[v],v))Floyd 核心递推式dp[k][i][j] min(dp[k-1][i][j], dp[k-1][i][k] dp[k-1][k][j])表示从 i 到 j只允许经过前 k 个顶点作为中间点的最短距离。可滚动数组优化为二维。7. 拓扑排序问题背景拓扑排序Topological Sort是对**有向无环图DAG, Directed Acyclic Graph**的节点进行线性排序使得对于图中的每一条有向边(u, v)节点u在排序结果中始终位于节点v之前。典型应用课程选修计划先修课问题、任务调度依赖关系、编译顺序、Makefile 依赖解析。核心思想repeatedly find vertices with no incoming edges一个 DAG 中入度为 0 的节点表示没有前置依赖可以最先执行。每处理完一个节点将其所有邻接节点的入度减 1新的入度为 0 的节点继续入队。算法步骤Kahn 算法BFS 实现1. 计算所有节点的入度indegree 2. 将所有入度为 0 的节点加入队列 3. while 队列不为空 a. 取出队首节点 u加入结果列表 b. 遍历 u 的所有邻接节点 v - 将 v 的入度减 1 - 若 v 的入度变为 0将 v 入队 4. 若结果列表中节点数 总节点数则排序成功 否则图中存在环无法进行拓扑排序代码实现Pythonfromcollectionsimportdequedeftopological_sort(n,edges):# 建图 计算入度graph[[]for_inrange(n)]indegree[0]*nforu,vinedges:graph[u].append(v)indegree[v]1# 入度为 0 的节点入队queuedeque([iforiinrange(n)ifindegree[i]0])result[]whilequeue:uqueue.popleft()result.append(u)forvingraph[u]:indegree[v]-1ifindegree[v]0:queue.append(v)# 判断是否有环iflen(result)!n:return[]# 图中存在环returnresult复杂度分析时间复杂度O(V E)每个节点和边各访问一次空间复杂度O(V E)邻接表 入度数组 队列DFS 实现思路deftopological_sort_dfs(n,edges):graph[[]for_inrange(n)]foru,vinedges:graph[u].append(v)visited[0]*n# 0未访问, 1访问中, 2已访问result[]defdfs(u):ifvisited[u]1:# 遇到访问中的节点说明有环returnFalseifvisited[u]2:returnTruevisited[u]1# 标记访问中forvingraph[u]:ifnotdfs(v):returnFalsevisited[u]2# 标记已访问result.append(u)# 后序遍历加入结果returnTrueforiinrange(n):ifvisited[i]0:ifnotdfs(i):return[]# 有环returnresult[::-1]# 逆序输出BFS vs DFSKahnBFS更直观适合求字典序最小的拓扑序用优先队列DFS 利用后序遍历特性代码更简洁。面试常考点拓扑排序可以检测有向图是否存在环若要求所有可能的拓扑排序需用回溯法。四、人工智能1. 过拟合及防止方法定义模型在训练集上表现很好但在测试集上表现很差的现象。本质是模型学到了训练数据中的噪声和特异性而没有学到数据的通用规律。防止过拟合的方法方法原理正则化RegularizationL1/L2 正则化在损失函数中增加对模型参数的惩罚迫使参数趋向简单Dropout训练时以概率p随机关闭部分神经元强制网络不依赖特定路径仅用于训练阶段早停Early Stopping当验证集性能连续多轮不再提升时提前终止训练数据增强Data Augmentation通过旋转、翻转、裁剪等变换扩充训练样本多样性降低模型复杂度减少网络层数、神经元数量或使用更简单的模型交叉验证Cross-ValidationK 折交叉验证更充分地利用数据评估模型泛化能力集成学习EnsembleBagging、Boosting通过多个模型投票降低方差2. 卷积神经网络CNN定义一种专门处理图像、时间序列等网格结构数据的深度学习框架核心在于用卷积运算代替全连接层通过局部感知和参数共享高效提取特征。核心组成层级作用卷积层Convolutional Layer通过卷积核滤波器提取局部特征边缘、纹理、形状等激活层Activation Layer引入非线性ReLU、Sigmoid、Tanh增强模型表达能力池化层Pooling Layer降采样Max Pooling / Average Pooling减少参数量增强平移不变性全连接层Fully Connected Layer将提取到的高层特征映射到分类空间输出最终预测结果批归一化Batch Normalization加速训练收敛起到一定正则化效果Dropout 层防止过拟合核心优势参数共享同一个卷积核在整个输入上滑动大幅减少参数量局部连接每个神经元只连接输入的局部区域符合图像局部相关性平移不变性池化操作使模型对目标位置变化具有一定鲁棒性层次化特征提取浅层提取边缘/纹理深层提取语义/部件/物体经典架构LeNet → AlexNet → VGGNet → ResNet残差连接解决梯度消失→ EfficientNet。 面试建议理解原理优于背诵能画图解释三次握手、能手写快排代码、能推导 DP 转移方程结合项目经验回答时关联自己的科研或项目经历体现深度思考关注前沿了解 HTTP/3QUIC、eBPF、Transformer 架构等最新技术趋势准备手撕代码拓扑排序、二叉树重建、最短路径等高频题建议熟练默写
