2025 408 考研大纲
数据结构
考察目标
- 掌握数据结构的基本概念、原理和方法。
- 掌握数据的逻辑结构、存储结构及基本操作的实现，能对算法进行基本的时间与空间复杂度分析。
- 能够运用数据结构原理和方法分析与求解问题，具备采用 C 或 C++ 语言设计与实现算法的能力。
一、绪论
（一）数据结构的基本概念（新增）
（二）算法的基本概念（新增）
二、线性表
（一）线性表的基本概念
（二）线性表的实现（顺序存储、链式存储）
（三）线性表的应用
三、栈、队列和数组
（一）栈和队列的基本概念
（二）栈和队列的顺序存储结构
（三）栈和队列的链式存储结构
（四）多维数组的存储
（五）特殊矩阵的压缩存储
（六）栈、队列和数组的应用
四、树与二叉树
（一）树的基本概念
（二）二叉树
- 定义及主要特征
- 顺序与链式存储结构
- 遍历
- 线索二叉树的基本概念与构造
（三）树、森林
- 树的存储结构
- 森林与二叉树的转换
- 树和森林的遍历
（四）树与二叉树的应用
- 哈夫曼树与哈夫曼编码
- 并查集及其应用
- 堆及其应用（新增）
五、图
（一）图的基本概念
（二）图的存储及基本操作（邻接矩阵、邻接表、邻接多重表、十字链表）
（三）图的遍历（深度优先搜索、广度优先搜索）
（四）图的基本应用（最小生成树、最短路径、拓扑排序、关键路径）
六、查找
（一）查找的基本概念
（二）顺序查找法
（三）分块查找法
（四）折半查找法
（五）树型查找（二叉搜索树、平衡二叉树、红黑树）
（六）B树及其基本操作、B+树的基本概念
（七）散列表
（八）字符串模式匹配
（九）查找算法的分析及应用
七、排序
（一）排序的基本概念
（二）直接插入排序
（三）折半插入排序
（四）起泡排序
（五）简单选择排序
（六）希尔排序
（七）快速排序
（八）堆排序
（九）二路归并排序
（十）基数排序
（十一）外部排序
（十二）排序算法的分析和应用
计算机组成原理
考察目标
- 理解单处理器计算机系统中主要部件的工作原理、组成结构及互连方式。
- 掌握指令集体系结构的基本知识与实现方法，能对计算机硬件问题进行分析与部件设计。
- 理解计算机系统的整机概念，能综合运用组成原理和方法分析高级语言（C语言）程序中的相关问题，具备软硬件协同分析与设计能力。
一、计算机系统概述
（一）计算机系统层次结构
- 计算机系统的基本组成
- 计算机硬件的基本结构
- 软硬件关系
- 计算机系统的工作原理（“存储程序”工作方式）
- 高级语言程序与机器语言程序的转换
- 程序和指令的执行过程
（二）计算机性能指标（吞吐量、响应时间、CPU时钟周期、主频、CPI、CPU执行时间、MIPS、MFLOPS等）
二、数据的表示和运算
（一）数制与编码（进位计数制及转换、定点数编码表示）
（二）运算方法和运算电路（加法器、ALU、补码加/减运算器、标志位生成、乘/除运算原理及电路）
（三）整数的表示和运算（无符号整数、带符号整数）
（四）浮点数的表示和运算（IEEE 754标准、浮点数加/减运算）
三、存储器层次结构
（一）存储器的分类
（二）层次化存储器的基本结构
（三）半导体随机存取存储器（SRAM、DRAM、Flash）
（四）主存储器（DRAM芯片与内存条、多模块存储器、主存与CPU连接）
（五）外部存储器（磁盘存储器、固态硬盘）
（六）高速缓冲存储器（Cache基本原理、映射方式、替换算法、写策略）
（七）虚拟存储器（基本概念、页式/段式/段页式虚拟存储器、页表、地址转换、TLB）
四、指令系统
（一）指令系统的基本概念
（二）指令格式
（三）寻址方式
（四）数据的对齐和大/小端存放方式
（五）CISC和RISC的基本概念
（六）高级语言程序与机器级代码的对应（编译器、汇编器、链接器基本概念；选择、循环、过程调用的机器级表示）
五、中央处理器
（一）CPU的功能和基本结构
（二）指令执行过程
（三）数据通路的功能和基本结构
（四）控制器的功能和工作原理
（五）异常和中断机制（基本概念、分类、检测与响应）
（六）指令流水线（基本概念、实现、结构/数据/控制冒险的处理、超标量与动态流水线基本概念）
（七）多处理器基本概念（SISD、SIMD、MIMD、向量处理器、硬件多线程、多核处理器、共享内存多处理器）
六、总线
（一）总线（基本概念、组成及性能指标、总线事务和定时）
（二）I/O接口（功能与基本结构、I/O端口及其编址）
（三）I/O方式（程序查询、程序中断、DMA方式）
操作系统
考察目标
- 掌握操作系统的基本概念、方法和原理，了解其结构、功能和服务，理解相关策略、算法和机制。
- 能从计算机系统角度理解并描述应用程序、操作系统内核和硬件协作完成任务的过程。
- 能运用操作系统原理分析与解决计算机系统中与操作系统相关的问题。
一、操作系统概述
（一）操作系统的基本概念
（二）操作系统的发展历程
（三）程序运行环境（CPU运行模式、中断与异常处理、系统调用、程序链接与装入、内存映像与地址空间）
（四）操作系统结构（分层、模块化、宏内核、微内核、外核）
（五）操作系统引导
（六）虚拟机
二、进程管理
（一）进程与线程
- 基本概念
- 状态与转换
- 线程的实现（内核支持、线程库支持）
- 组织与控制
- 进程间通信（共享内存、消息传递、管道、信号）（新增）
（二）CPU调度与上下文切换
- 调度的基本概念、目标与实现
- CPU调度算法（新增）
- 多处理机调度（新增）
- 上下文及其切换机制
（三）同步与互斥
- 基本概念
- 实现方法（软件、硬件）
- 锁、信号量、条件变量
- 经典同步问题（生产者-消费者、读者-写者、哲学家进餐）
（四）死锁（基本概念、预防、避免、检测和解除）
三、内存管理
（一）内存管理基础（基本概念、连续分配、页式、段式、段页式管理）
（二）虚拟内存管理
- 虚拟内存基本概念
- 请求页式管理
- 页框分配与回收（新增）
- 页置换算法
- 内存映射文件
- 虚拟存储器性能的影响因素及改进
四、文件管理
（一）文件（基本概念、元数据与inode、操作、保护、逻辑与物理结构）
（二）目录（基本概念、树形目录、操作、硬链接与软链接）
（三）文件系统（全局结构、外存空闲空间管理、虚拟文件系统、挂载）
五、输入输出（I/O）管理
（一）I/O管理基础（设备概念与分类、I/O接口与端口、控制方式、软件层次结构、应用程序接口）
（二）设备独立软件（缓冲区管理、设备分配与回收、假脱机技术、设备驱动程序接口）
（三）外存管理（磁盘结构、格式化、分区、磁盘调度方法；固态硬盘的读写特性与磨损均衡）
计算机网络
考察目标
- 掌握计算机网络的基本概念、原理和方法。
- 掌握典型计算机网络的结构、协议、应用以及典型网络设备的工作原理。
- 能够运用网络基本概念、原理和方法进行网络系统的分析、设计和应用。
一、计算机网络概述
（一）计算机网络基本概念（定义、组成、功能、分类、主要性能指标）
（二）计算机网络体系结构（分层结构、协议、接口、服务、ISO/OSI参考模型和TCP/IP模型）
二、物理层
（一）通信基础（信道、信号、带宽、码元、波特、速率、信源与信宿、奈奎斯特定理与香农定理、编码与调制、电路/报文/分组交换、数据报与虚电路）
（二）传输介质（双绞线、同轴电缆、光纤、无线传输介质）
（三）物理层设备（中继器、集线器）
三、数据链路层
（一）数据链路层的功能
（二）组帧
（三）差错控制（检错编码、纠错编码）
（四）流量控制与可靠传输机制（流量控制、可靠传输与滑动窗口、停止-等待、后退N帧、选择重传协议）
（五）介质访问控制（信道划分、随机访问、轮询访问）
（六）局域网（基本概念与体系结构、以太网与IEEE 802.3、IEEE 802.11无线局域网、VLAN）
（七）广域网（基本概念、PPP协议）
（八）数据链路层设备（以太网交换机及其工作原理）
四、网络层
（一）网络层的功能（异构网络互联、路由与转发、SDN基本概念、拥塞控制）
（二）路由算法（静态与动态路由、距离-向量、链路状态、层次路由）
（三）IPv4（IPv4分组、IPv4地址与NAT、子网划分、路由聚集、子网掩码与CIDR、ARP、DHCP、ICMP协议）
（四）IPv6（主要特点、地址）
（五）路由协议（自治系统、域内与域间路由、RIP、OSPF、BGP）
（六）IP组播（概念、IP组播地址）
（七）移动IP（概念、通信过程）
（八）网络层设备（路由器的组成和功能、路由表与分组转发）
五、传输层
（一）传输层提供的服务（功能、寻址与端口、无连接与面向连接服务）
（二）UDP协议（UDP数据报、校验）
（三）TCP协议（TCP段、连接管理、可靠传输、流量控制、拥塞控制）
六、应用层
（一）网络应用模型（C/S模型、P2P模型）
（二）DNS系统（层次域名空间、域名服务器、域名解析过程）
（三）FTP（工作原理、控制连接与数据连接）
（四）电子邮件（组成结构、格式与MIME、SMTP与POP3协议）
（五）WWW（概念与组成结构、HTTP协议）