数据结构与算法设计(45分核心模块)
808专业课中数据结构部分占比最高,要求掌握从基础线性结构到高级图算法的完整知识链,并能灵活运用于算法设计与复杂度分析。真题高频考点包括:
- 线性表:循环链表的环检测(Floyd判圈算法)、双向链表的O(1)删除、顺序表与链表的适用场景对比(内存局部性原理影响);
- 栈与队列:用两个栈实现队列、用队列模拟栈、表达式求值(中缀→后缀→计算)、单调栈解“直方图最大矩形”类问题;
- 树与二叉树:二叉搜索树的插入/删除(含双亲结点处理)、AVL树的LL/RR/LR/RL四种旋转、哈夫曼树构造与WPL计算、树的遍历(递归/非递归/Morris);
- 图论:邻接矩阵vs邻接表存储结构选择、DFS/BFS的拓扑排序与关键路径应用、最短路径(Dijkstra/Bellman-Ford/Floyd)、最小生成树(Prim/Kruskal)、并查集(路径压缩+按秩合并);
- 算法设计范式:分治法(归并排序/快速排序/大整数乘法)、动态规划(背包问题/最长公共子序列/矩阵链乘)、贪心算法(活动选择/霍夫曼编码)、回溯法(N皇后/子集和问题)。
典型真题示例:【2023年电子科大808】设计一个支持getMin()操作的栈,要求所有操作时间复杂度为O(1),空间复杂度O(n)。请写出数据结构定义与算法流程。
操作系统原理(35分重点模块)
808科目操作系统部分强调“进程—内存—文件—设备”四大管理机制的原理理解与对比分析,近年真题明显增加对Linux内核机制的考查(如CFS调度、VFS抽象层)。高频考点包括:
- 进程管理:进程 vs 线程(地址空间隔离性、切换开销对比)、进程通信方式(管道/信号量/共享内存/消息队列)、死锁的四个条件(互斥/占有申请/不可剥夺/循环等待)、银行家算法的安全性检查流程;
- 内存管理:连续分配(单/多分区)、非连续分配(分页/分段/段页式)、页表机制(多级页表/页表项结构)、缺页中断处理流程、页面置换算法(FIFO/Optimal/LRU/时钟)、TLB(快表)的作用与命中率影响;
- 文件系统:文件控制块(FCB)结构、目录结构(单级/两级/树形/无环图)、文件共享(基于索引节点的链接计数)、文件保护(访问控制列表ACL vs 权限位)、磁盘管理(分区/引导块/超级块);
- 设备管理:I/O控制方式(程序查询/中断驱动/DMA/通道)、设备驱动程序功能、设备树(Device Tree)在嵌入式系统中的应用。
典型真题示例:【2022年西电808】某系统采用二级页表机制,页大小为4KB,页目录项与页表项均为4字节,虚拟地址32位。求:①页目录项数;②页表项数;③若某进程页目录基址为0x100000,虚拟地址0x08048000对应的物理地址(假设页目录项与页表项均有效)。
计算机网络(30分核心模块)
808专业课网络部分紧扣OSI七层模型与TCP/IP四层模型,近年增加对HTTP/3(QUIC协议)、IPv6、网络安全机制的考查。高频考点包括:
- 物理层:编码方式(曼彻斯特/差分曼彻斯特)、信道复用(FDM/TDM/WDM/CDMA)、香农定理与奈奎斯特准则;
- 数据链路层:PPP协议帧结构、CSMA/CD工作原理(以太网冲突检测)、MAC地址学习与交换表维护、VLAN划分与Trunk技术;
- 网络层:IP地址分类与子网划分(CIDR)、ARP/RARP协议流程、ICMP报文类型(Echo/TimeExceeded/DestinationUnreachable)、路由选择算法(距离矢量vs链路状态)、MPLS标签转发机制;
- 传输层:TCP三次握手/四次挥手(含TIME_WAIT作用)、滑动窗口机制(GBN/SR)、拥塞控制(慢开始/拥塞避免/快重传/快恢复)、UDP与TCP适用场景对比;
- 应用层:DNS查询流程(递归/迭代)、HTTP/1.1长连接与管线化、HTTPS握手流程(非对称加密+对称加密混合)、Cookie/Session机制、RESTful API设计原则。
典型真题示例:【2023年北邮808】某HTTP客户端向服务器发送GET请求,服务器返回304 Not Modified。请描述从DNS解析到浏览器渲染完成的完整过程,并指出304响应如何减少网络开销。
数据库系统(25分模块)
808科目数据库部分侧重原理性理解而非SQL语法,近年增加对NoSQL(如MongoDB、Redis)、分布式数据库(如TiDB)基础概念的考查。高频考点包括:
- 关系模型:范式理论(1NF~BCNF)、函数依赖、候选键与主属性、分解无损连接性与保持依赖性判断;
- SQL语言:复杂查询(嵌套查询/集合查询/聚集函数)、视图定义与更新限制、完整性约束(实体/参照/用户定义);
- 关系数据库理论:ER图到关系模式的转换规则、多值依赖与第四范式(4NF)、JOIN操作的物理实现(嵌套循环/哈希连接/归并连接);
- 事务处理:ACID特性详解(原子性/一致性/隔离性/持久性)、隔离级别(Read Uncommitted/Read Committed/Repeatable Read/Serializable)、锁协议(1PL/2PL/保守2PL)、死锁检测与恢复;
- 查询优化:查询树重写(交换σ/π顺序、合并σ条件)、索引选择(B+树索引适用场景)、统计信息与成本估算模型。
典型真题示例:【2021年华科808】设有关系模式R(A,B,C,D,E),函数依赖集F={AB→C, BC→AD, D→E}。求:①R的候选键;②R属于第几范式;③若R不满足3NF,将其分解为3NF且保持函数依赖。
计算机组成原理(15分基础模块)
808专业课组成原理部分虽分值较低,但作为计算机体系结构的基石,常与操作系统、网络模块交叉考查。高频考点包括:
- 数据表示:定点/浮点数表示(IEEE 754标准)、补码运算(溢出检测)、BCD码与ASCII编码;
- 存储系统:主存与Cache的地址映射(直接/全相联/组相联)、替换算法(FIFO/LRU)、多级存储体系(寄存器→Cache→主存→辅存);
- 指令系统:RISC vs CISC特征对比、指令格式(定长/变长)、寻址方式(立即/直接/寄存器/寄存器间接/基址/变址);
- ALU与运算器:加法器(半加/全加/超前进位)、定点运算(原码/补码加减法)、浮点运算(阶码/尾数分离处理);
- 总线与I/O:总线仲裁(链式/计数器查询/独立请求)、中断处理流程(中断向量、优先级排队)、DMA传输过程。
典型真题示例:【2020年中科院808】某计算机字长32位,采用单总线结构,Cache块大小为64字节,主存容量为4GB。若采用直接映射方式,求:①Cache行数;②主存地址划分(Tag/Index/Offset);③当访问地址为0x12345678时,其Tag字段值(十六进制表示)。