核心内容深度解析
逐模块拆解重点难点,结合真题示例强化理解
重点模块精讲
- 数据结构与算法:链表操作需掌握双指针技巧(如快慢指针找中点)、递归转迭代;图算法中Dijkstra与Floyd必须手写实现;动态规划题常考背包、最长公共子序列,需构建状态转移方程。
- 计算机组成原理:浮点数表示(IEEE 754)是高频难点;Cache映射(直接/组/全)需熟练计算块号、组号、偏移;ALU设计涉及补码加减法与溢出判断;RISC-V指令集近年考查增多。
- 操作系统:PV操作是必考内容,需熟练编写生产者-消费者、读者-写者等经典模型;页表转换(页表项结构、页大小、虚拟地址分解)需计算训练;死锁检测与银行家算法要掌握步骤。
- 计算机网络:TCP状态机(ESTABLISHED、TIME_WAIT等)需熟记;IP分片与MTU限制要会计算;路由算法(RIP、OSPF)对比;HTTP/HTTPS握手流程、HTTPS加密机制(对称+非对称)是热点。
给定一个无向图G,顶点集V={1,2,3,4,5},边集E={(1,2,3),(1,3,5),(2,3,1),(2,4,2),(3,4,4),(3,5,6),(4,5,7)}(格式:u,v,weight),要求:
- 用Kruskal算法构造最小生成树,画出每一步选择的边及当前森林结构;
- 若从顶点1出发,用Prim算法构造最小生成树,列出边的加入顺序;
- 比较两种算法的时间复杂度,说明适用场景。
解题关键:Kruskal需按权排序+并查集判环;Prim可用邻接矩阵+数组记录最小边权;两者时间复杂度分别为O(E log E)与O(V²),稀疏图Kruskal更优,稠密图Prim更优。此题融合数据结构(树/并查集)+算法设计+系统思维,体现408命题趋势。