计算机408考研真题权威解析
全面掌握数据结构｜算法｜操作系统｜网络｜数据库

算法模块强调“设计+分析”双能力，2025年真题中算法题占比显著提升，选择题侧重复杂度判断，综合题要求完整代码实现与正确性证明。

动态规划：最长公共子序列（LCS）
第42题给出字符串X="ABCB"、Y="BDCAB"，要求写出LCS动态规划表并输出一个LCS。关键点在于状态转移方程：
当xi=yj时，c[i][j]=c[i-1][j-1]+1；
否则c[i][j]=max(c[i-1][j], c[i][j-1])。
最终c[4][5]=3，LCS可为"BCB"或"BAB"。考生常见错误是未进行回溯直接输出长度，或回溯路径错误。

贪心算法：活动选择问题
选择题第28题要求根据结束时间最早优先策略选择最多活动。给定10个活动的起止时间，需先按结束时间排序，再贪心选择。此题陷阱在于部分活动起止时间重叠但不冲突，考生易误将时间区间完全包含的活动同时选入。

分治策略：归并排序非递归实现
综合题第42题第二问要求用非递归方式实现归并排序。需设计迭代式合并过程：第一轮两两合并（子序列长度2），第二轮四四合并（子序列长度4），直至长度≥n。特别注意尾部不足时的边界处理，如n=7时，第三轮合并长度为4与3的子序列。

复杂度分析要点：掌握主定理适用条件（T(n)=aT(n/b)+f(n)），区分最好/最坏/平均复杂度。如快速排序平均O(nlogn)，最坏O(n²)；堆排序始终O(nlogn)；计数排序O(n+k)（k为数据范围）。

操作系统模块考查进程同步、内存管理、文件系统三大核心，2025年真题突出对真实场景的建模能力。

进程同步：哲学家进餐问题
第44题给出五位哲学家围坐圆桌，每两人之间有一把筷子，要求用P/V操作避免死锁。标准解法有两种：① 最多允许4人同时拿筷子；② 奇数号先左后右，偶数号先右后左。2025年真题增设“每人需先拿左筷再拿右筷”的约束，此时必须引入信号量限制同时进餐人数≤4，否则5人同时拿起左筷后全部等待右筷，必然死锁。

内存管理：页面置换算法
第45题给出页面访问序列{7,0,1,2,0,3,0,4,2,3,0,3}，内存物理块数为3，要求计算FIFO、LRU、OPT算法的缺页率。OPT算法因需未来信息，本题中最优，缺页12次；LRU次之缺页14次；FIFO缺页15次（注意Belady异常：增加物理块数反而缺页率上升的情况未出现）。

文件系统：索引结构计算
选择题第36题给出文件系统采用混合索引，直接地址10项，单级索引1项（每块1KB，地址占4字节），要求计算最大文件长度。直接寻址10块×1KB=10KB；单级索引块可存256个地址（1024÷4），寻址256块×1KB=256KB；总计266KB。常见错误是误将地址位数当作块数（如按16位算得65536块）。

死锁处理策略：需熟练掌握预防（破坏四个必要条件）、避免（银行家算法）、检测与恢复三种策略。2025年真题中银行家算法题要求根据当前资源分配状态判断安全序列，关键在于模拟资源分配过程，不可仅凭初始状态武断结论。

网络模块强调协议原理与数据流过程，2025年真题新增对IPv6特性与网络安全机制的考查。

TCP三次握手与四次挥手
第46题要求分析TIME_WAIT状态的作用。正确答案包括：①保证TCP全双工连接可靠关闭；②防止旧连接数据干扰新连接；③确保延迟到达的报文段被丢弃。考生易忽略第三点，误认为仅用于确认最后ACK。2025年真题进一步提问：若主动关闭方发送最后一个ACK后立即重启，TIME_WAIT是否仍必要？答案是肯定的——因网络可能延迟交付此前的FIN，新连接可能误接收旧连接数据。

BGP路由选择
选择题第24题给出AS路径{AS100, AS200, AS300}、本地优先级100、MED 50、起源IGP，要求选择最优路径。根据BGP决策规则：①优先选择本地优先级最高；②再比较AS路径长度；③再比较MED。本题中若另一路径本地优先级为50，则无论AS路径多短均次优，体现“本地优先级>AS路径”原则。

网络安全：IPSec与SSL/TLS
第27题考查IPSec的AH与ESP协议区别。AH提供数据源认证、完整性、抗重放但不加密；ESP提供加密与有限完整性。2025年真题要求判断“某场景需加密传输但无需完整性保护”，此时应选ESP（无认证头模式）。常见误区是认为完整性保护不可或缺，忽略加密本身已隐含部分完整性保障。

CDN工作原理：理解内容分发网络的核心是“就近访问”。用户请求时，DNS将域名解析为最优边缘服务器IP（基于地理位置、负载等），而非源站IP。2025年真题中某题要求计算CDN减少的传输延迟，需结合源站距离与边缘节点分布估算。

数据库模块考查关系模型、SQL编写、事务处理、索引优化四大维度，2025年真题强化了性能调优的实践性。

ER图到关系模式转换
第47题给出“学生-课程-教师”ER图，含学生（学号、姓名）、课程（课程号、名称）、教师（工号、姓名），关系为学生选修课程由教师授课。要求转换为3NF。正确答案应为三张关系：Student(S#, Sname)，Course(C#, Cname, T#)，Enroll(S#, C#)。常见错误是将T#直接放入Enroll，导致教师信息冗余；或单独建Teacher表但未在Enroll中引用，破坏完整性。

SQL优化：索引失效场景
第48题给出表结构：Orders(order_id, user_id, order_date, amount)，索引idx_user_date(user_id, order_date)，要求优化查询“SELECT FROM Orders WHERE user_id=1001 AND order_date BETWEEN '2024-01-01' AND '2024-01-31' ORDER BY amount DESC LIMIT 10”。错误做法是在amount上建独立索引，因复合索引最左前缀原则，user_id条件后order_date可走索引，但amount无法利用索引排序。正确优化是建立覆盖索引idx_user_date_amount(user_id, order_date, amount)，避免回表与额外排序。

事务隔离级别与并发问题
第49题要求分析可重复读（RR）级别下，事务T1执行“SELECT COUNT() FROM Account WHERE balance>1000”，同时T2插入一条balance=1500的记录。T1再次执行相同查询时结果是否变化？在RR下，T1首次查询时建立一致性视图，T2插入对T1不可见，结果不变；但若T2已提交且T1执行了新查询，则可见新数据。此题考查MVCC实现细节，需区分“同一事务内多次查询”与“不同事务查询”。

数据库设计范式：掌握1NF~3NF及BCNF。2025年真题中某题给出关系R(A,B,C,D)，函数依赖集F={AB→C, C→D}，要求分解为3NF。步骤：①求候选码（AB）；②判断2NF（C,D对候选码部分依赖？否）；③判断3NF（C→D中D非主属性，C非超键→不满足3NF）。最终分解为R1(A,B,C)，R2(C,D)。