【四川省26年部分92计算机博士面试题汇总】-酒店常州论坛

计算机博士面试题汇总（计算机网络 | 操作系统 | 算法与数据结构 | 人工智能）

说在前面：西南交大和成电的面试心得，西南交大老师和蔼一点，专业课抽两道题，有主观的题，也有问文件系统的题；电科老师比较严肃，专业课是计组、操作系统、数据结构及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 Floyd）
- 7. 拓扑排序
四、人工智能
- 1. 过拟合及防止方法
- 2. 卷积神经网络（CNN）

一、计算机网络

1. TCP 和 UDP 的主要区别及应用场景

特性	TCP	UDP
连接方式	面向连接	无连接
可靠性	可靠传输（确认、重传、排序）	不可靠传输
传输效率	较低（开销大）	较高（开销小）
数据边界	字节流，无边界	报文保留边界
拥塞控制	有	无

应用场景：

TCP：文件下载（FTP）、网页浏览（HTTP/HTTPS）、邮件传输（SMTP）
UDP：实时音视频通话、在线游戏、DNS 查询、直播推流

2. OSI 七层模型 vs TCP/IP 四层模型

OSI 七层模型

层级	名称	主要功能
7	应用层	为应用程序提供网络服务接口（HTTP、FTP、SMTP）
6	表示层	数据格式转换、加密解密、压缩解压（SSL/TLS）
5	会话层	建立、管理、终止会话（同步、断点续传）
4	传输层	端到端可靠/不可靠传输、端口寻址、流量控制（TCP/UDP）
3	网络层	主机到主机的逻辑寻址、路由选择、分组转发（IP）
2	数据链路层	相邻节点间可靠传输、物理寻址（MAC）、帧同步
1	物理层	比特流的物理传输（电压、接口、线缆）

TCP/IP 四层模型

层级	对应 OSI	主要功能	常见协议
应用层	应用层+表示层+会话层	直接面向用户程序	HTTP、FTP、DNS、SSH、SMTP
传输层	传输层	端到端通信	TCP、UDP
网络层	网络层	跨网络路由、IP 寻址	IP、ICMP、IGMP
网络接口层	数据链路层+物理层	物理传输+帧封装	Ethernet、WiFi、ARP

3. TCP/IP 协议栈结构及常见协议

┌─────────────────────────────────────┐ │ 应用层（报文） │ HTTP/HTTPS/FTP/SSH/DNS/SMTP ├─────────────────────────────────────┤ │ 传输层（段/数据报） │ TCP（可靠、滑动窗口、拥塞控制） │ │ UDP（无连接、快速） ├─────────────────────────────────────┤ │ 网络层（包/分组） │ IP（无连接、尽力交付） │ │ ICMP（控制报文）/ IGMP（组管理） ├─────────────────────────────────────┤ │ 网络接口层（帧/比特流） │ Ethernet、WiFi、ARP（IP→MAC） └─────────────────────────────────────┘

核心要点：

发送方：自上而下逐层添加首部（封装）
接收方：自下而上逐层解封装，提取首部后交付上层
本质：链路层传帧 + 网络层寻址路由 + 传输层端到端 + 应用层定语义

4. TCP 拥塞控制算法

算法	核心思想
慢启动（Slow Start）	初始拥塞窗口`cwnd=1`，每轮 RTT 翻倍，慢慢探测网络可用带宽，避免一开始就洪泛网络
拥塞避免（Congestion Avoidance）	当`cwnd`达到慢启动阈值`ssthresh`后，改为线性增长，接近网络容量时保守增长
快重传（Fast Retransmit）	收到3 个重复 ACK时，立即重传丢失报文段，不等待超时
快恢复（Fast Recovery）	配合快重传，将`ssthresh`设为当前`cwnd`的一半，`cwnd`也设为一半，直接进入拥塞避免阶段，替代慢启动

💡面试常考点：快重传和快恢复是配套使用的，目的是避免一丢包就回到慢启动，提高网络吞吐量。

5. TCP 三次握手与四次挥手

三次握手（建立连接）

客户端 A 服务端 B │ ─────── SYN, seq=x ───────> │ │ │ │ <── SYN-ACK, seq=y, ack=x+1 ─ │ │ │ │ ─────── ACK, ack=y+1 ──────> │ │ │ │◄──────── ESTABLISHED ───────►│

第一次：客户端发送SYN，携带初始序列号seq=x
第二次：服务端回复SYN-ACK，携带自己的初始序列号seq=y，并确认ack=x+1
第三次：客户端回复ACK，确认ack=y+1，连接建立

❓为什么是三次？防止历史重复连接请求造成错误，同时确保双方收发能力正常。

四次挥手（断开连接）

客户端 A 服务端 B │ ─────── FIN, seq=u ────────> │ │ │ │ <──────── ACK, ack=u+1 ────── │ （服务端继续发送剩余数据） │ │ │ <── FIN, seq=w, ack=u+1 ──── │ （服务端数据发完，请求关闭） │ │ │ ─────── ACK, ack=w+1 ──────> │ │ │ │ 等待 2MSL 后彻底关闭 │

第一次：客户端发送FIN，请求关闭发送通道
第二次：服务端回复ACK，但可能还有数据要发
第三次：服务端数据发完，发送FIN请求关闭自己的发送通道
第四次：客户端回复ACK，进入TIME_WAIT状态，等待2MSL后彻底关闭

💡2MSL 的作用：确保最后一个 ACK 能被服务端收到；让网络中滞留的旧报文段全部消失。

6. HTTP 与 HTTPS 的区别

特性	HTTP	HTTPS
全称	超文本传输协议	超文本传输安全协议
安全性	明文传输	加密传输（TLS/SSL）
端口	80	443
证书	无需	需要 CA 证书
握手过程	TCP 三次握手后直接传输	TCP 握手 + TLS 握手后传输
层级	应用层 → TCP	应用层 → TLS/SSL → TCP

🔐TLS 握手简述：客户端和服务端协商加密算法、交换公钥、生成会话密钥，后续通信使用该密钥对称加密。

二、操作系统

1. 进程与线程的区别及线程优势

特性	进程（Process）	线程（Thread）
基本单位	资源分配的基本单位	CPU 调度的基本单位
地址空间	独立的地址空间	共享所属进程的地址空间
切换开销	大（需切换页表、刷新 TLB）	小（只需保存寄存器、栈）
通信方式	IPC（管道、消息队列、共享内存等）	直接读写共享变量
崩溃影响	不影响其他进程	可能导致整个进程崩溃

线程引入的优势：

创建开销小：无需分配独立地址空间
资源共享：线程间可直接共享内存数据
响应性提高：单进程多线程模型中，某线程阻塞时，其他线程仍可响应请求
并发性提升：多核 CPU 上可真正实现并行计算

⚠️代价：线程以共享地址空间换取效率，但也带来了线程安全问题（竞态条件、死锁等）。

2. 死锁及预防

什么是死锁？

一组线程/进程因循环等待对方持有的资源而永久阻塞的现象。若无外力干预，这些进程/线程将永远无法继续执行。

死锁的四个必要条件（Coffman 条件）

条件	说明
互斥条件	一段时间内，资源仅被一个进程占用
请求和保持	进程因请求新资源而阻塞时，对已获得的资源不释放
非剥夺条件	进程已获得的资源只能在使用完成后才能被释放（不能被强制抢占）
循环等待	发生死锁时，必然存在一个进程-资源的循环等待链

死锁的预防策略

策略	方法
预防死锁	设置限制条件，破坏四个必要条件中的一个或多个
避免死锁	动态分配资源时，用算法（如银行家算法）防止系统进入不安全状态
检测与恢复	允许死锁发生，定期检测并强制剥夺资源或终止进程
忽略死锁	鸵鸟策略，假设死锁不会发生（如大多数操作系统采用）

💡银行家算法核心：在资源分配前模拟分配，检查系统是否仍处于安全状态（存在安全序列），若安全则分配，否则拒绝。

3. 乐观锁与悲观锁

悲观锁（Pessimistic Locking）

核心思想：假设冲突一定会发生，每次访问数据时先加锁，确保其他线程无法同时修改。

实现方式：数据库中的SELECT ... FOR UPDATE、Java 的synchronized、ReentrantLock
适用场景：写多读少、并发冲突激烈的场景
优点：数据安全性高，不会出现脏读、幻读
缺点：加锁开销大，容易引发死锁，降低并发性能

// 悲观锁示例（Java）synchronized(obj){// 临界区：只有获得锁的线程能执行balance-=amount;}

乐观锁（Optimistic Locking）

核心思想：假设冲突很少发生，先不加锁执行操作，提交时检查数据是否被其他线程修改过，若被修改则重试或报错。

实现方式：版本号（Version）、时间戳（Timestamp）、CAS（Compare-And-Swap）
适用场景：读多写少、并发冲突较少的场景
优点：无锁开销，不会死锁，并发性能高
缺点：冲突频繁时重试开销大，存在 ABA 问题（CAS 特有）

// 乐观锁示例：版本号机制UPDATEaccountSETbalance=balance-100,version=version+1WHEREid=1ANDversion=#{currentVersion};// 若返回影响行数为0，说明数据已被修改，需重试

// CAS 示例（Java AtomicInteger）AtomicIntegercounter=newAtomicInteger(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 广度优先遍历、缓存实现（LRU）

4. 快速排序

基本思想：基于分治（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])`
最长递增子序列（LIS）	`dp[i]`：以 nums[i] 结尾的最长递增子序列长度	`dp[i] = max(dp[j] + 1)`，其中`j < i`且`nums[j] < nums[i]`
最长公共子序列（LCS）	`dp[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）	状态压缩 DP：`dp[mask][i]`	枚举子集转移

📝解题步骤：定义状态 → 找状态转移方程 → 确定初始条件和边界 → 确定遍历顺序 → 优化空间（可选）。

6. 最短路径算法（Dijkstra vs Floyd）

问题定义：给定带权图G=(V, E)，寻找从起点到终点（或所有点对之间）的路径权重之和最小的路径。

算法	Dijkstra	Floyd-Warshall
核心思想	贪心策略：每次选择距离源点最近的未确定顶点，松弛其邻边	动态规划：逐轮允许经过更多中间顶点，更新所有点对距离
适用图	非负权图	任意权图（可处理负权，但不能有负权环）
时间复杂度	`O((V+E) log V)`（优先队列优化）	`O(V³)`
空间复杂度	`O(V)`	`O(V²)`
求解目标	单源最短路径	全源最短路径

Dijkstra 伪代码：

dist=[inf]*n dist[start]=0pq=[(0,start)]# (距离, 节点)whilepq:d,u=heappop(pq)ifd>dist[u]:continueforv,wingraph[u]:ifdist[u]+w<dist[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. 若结果列表中节点数 = 总节点数，则排序成功 否则图中存在环，无法进行拓扑排序

代码实现（Python）

fromcollectionsimportdequedeftopological_sort(n,edges):# 建图 + 计算入度graph=[[]for_inrange(n)]indegree=[0]*nforu,vinedges:graph[u].append(v)indegree[v]+=1# 入度为 0 的节点入队queue=deque([iforiinrange(n)ifindegree[i]==0])result=[]whilequeue:u=queue.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 DFS：Kahn（BFS）更直观，适合求字典序最小的拓扑序（用优先队列）；DFS 利用后序遍历特性，代码更简洁。

📝面试常考点：拓扑排序可以检测有向图是否存在环；若要求所有可能的拓扑排序，需用回溯法。

四、人工智能

1. 过拟合及防止方法

定义：模型在训练集上表现很好，但在测试集上表现很差的现象。本质是模型学到了训练数据中的噪声和特异性，而没有学到数据的通用规律。

防止过拟合的方法：

方法	原理
正则化（Regularization）	L1/L2 正则化，在损失函数中增加对模型参数的惩罚，迫使参数趋向简单
Dropout	训练时以概率`p`随机关闭部分神经元，强制网络不依赖特定路径（仅用于训练阶段）
早停（Early Stopping）	当验证集性能连续多轮不再提升时提前终止训练
数据增强（Data Augmentation）	通过旋转、翻转、裁剪等变换扩充训练样本多样性
降低模型复杂度	减少网络层数、神经元数量，或使用更简单的模型
交叉验证（Cross-Validation）	K 折交叉验证，更充分地利用数据评估模型泛化能力
集成学习（Ensemble）	Bagging、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/3（QUIC）、eBPF、Transformer 架构等最新技术趋势
准备手撕代码：拓扑排序、二叉树重建、最短路径等高频题建议熟练默写

企业官网建设流程全解析