计算机考研 921 的考试内容通常包括以下四个部分:
数据结构
线性表 :要求考生理解线性表的定义和特点,掌握顺序表和链表的存储结构及基本操作,熟练掌握顺序表和单链表的插入、删除等算法设计。
栈和队列 :理解栈和队列的基本概念和性质,熟练掌握栈和队列的顺序存储结构和链式存储结构,以及栈和队列的基本操作算法设计。
树和二叉树 :理解树的基本概念和性质,掌握二叉树的概念、性质,熟练掌握二叉树的顺序存储结构和链式存储结构、二叉树的遍历和应用,熟练掌握树的存储结构、树和森林与二叉树间的转换,掌握树和森林的遍历,熟练掌握哈夫曼树及其应用。
图 :理解图的基本概念、术语,熟练掌握图的邻接矩阵存储、邻接表存储,图的邻接多重表存储和十字链表存储结构及基本操作,熟练掌握图的深度优先和广度优先遍历算法设计及其应用,掌握求最小 (代价) 生成树的相关算法及求解过程,理解有向无环图的概念,掌握拓扑排序和关键路径的相关算法及求解过程,了解带权最短路径的概念,掌握求最短路径的相关算法及求解过程。
查找 :理解查找的概念及其效率的评价方法,熟练掌握顺序、折半和分块查找法,熟练掌握二叉排序树 (二叉搜索树) 的概念、查找与操作算法设计,了解和掌握平衡二叉树的概念与操作,了解和掌握 B 树及其基本操作、B + 树的基本概念,理解散列 (Hash) 表的概念,掌握哈希函数的构造和处理冲突的基本方法,掌握查找算法的分析及应用。
内部排序 :了解排序的基本概念,掌握直接插入排序、折半插入排序、希尔排序 (shell sort) 算法,掌握冒泡排序 (bubble sort)、快速排序算法,简单选择排序、堆排序算法,二路归并排序 (merge sort) 算法、基数排序算法,了解外部排序方法,掌握以上各种内部排序算法的比较,对排序算法是否稳定,对各种排序时间和空间方面进行简单分析,熟练掌握各种排序算法的应用。
计算机组成原理
计算机系统概述 :要求考生了解冯・诺依曼式计算机的结构组成及特点,掌握评价计算机硬件的技术指标,掌握计算机系统的工作过程,掌握计算机的层次结构,了解计算机的发展史及计算机的分类方式。
系统总线 :了解总线的分类和计算机系统总线连接方式,熟练掌握不同总线结构的优缺点,熟练掌握总线判优控制三种方法的优缺点,掌握总线的通信控制方式。
存储器 :了解存储器的分类方法,掌握主存储器的基本组成和工作原理,熟练掌握主存储器与 CPU 的连接方式,熟练掌握 Cache 与主存三种映射方式的优缺点,能够根据需求设计 Cache 与主存映射方式,并分析系统性能,了解提高访存速度的措施,了解计算机硬盘存储器的原理和记录方式,掌握存储器的校验方法。
计算机输入输出系统 :了解计算机输入输出系统的发展概况,掌握中断的概念、掌握中断的处理过程,熟练掌握多重中断及中断屏蔽技术,了解 DMA 的工作过程。
计算机的运算方法 :掌握有符号数、无符号数、定点数及浮点数的表示方法,掌握定点数的四则运算规则和浮点的加减运算规则,掌握加法器和乘法器的硬件结构设计方法和进位链的结构组成。
指令系统 :了解常见系统机器指令格式,掌握常用的十种指令寻址方式的特点,能够熟练辨别指令的各种寻址方式,掌握指令系统设计方法,能够根据需求设计指令系统并分析指令系统的局限性,了解 RISC 和 CISC 的特点。
CPU 的结构和功能 :掌握 CPU 内各个部分的作用及相互关系,掌握指令流水的设计原理及性能指标,能够根据性能指标对指令流水性能进行分析和评价,了解指令流水的并发实现技术。
控制单元的功能及设计 :掌握控制单元的功能和各个微操作的节拍安排,掌握指令周期、机器周期和节拍多级时序的相互关系,了解组合逻辑控制单元和微程序控制单元的特点,掌握组合逻辑控制单元设计方法,并能够根据实际需求设计模型机。
操作系统原理
操作系统概述 :要求考生了解操作系统的概念、特征、功能和设计目标,了解操作系统的发展阶段与分类,了解操作系统体系结构。
进程管理 :理解进程的概念,掌握进程的状态与转换原因,掌握进程控制原语,掌握进程通信的基本机制,包括共享存储系统、消息传递系统、管道通信,理解线程概念与多线程模型,了解调度的基本概念、调度时机、切换与过程,理解调度的基本准则,掌握典型调度算法,包括先来先服务调度算法、短作业 (短进程、短线程) 优先调度算法、时间片轮转调度算法、优先级调度算法、高响应比优先调度算法、多级反馈队列调度算法,理解进程同步的基本概念,掌握实现临界区互斥的基本方法,包括软件实现方法、硬件实现方法,熟练运用信号量机制解决同步和互斥问题,掌握经典同步问题,包括生产者 - 消费者问题、读者 - 写者问题、哲学家进餐问题的常见解法,了解死锁的概念,掌握死锁处理策略,熟练掌握死锁预防和死锁避免方法,能够判定系统安全状态,理解银行家算法,了解死锁检测和解除方法。
内存管理 :了解内存管理概念,理解程序装入与链接方式,掌握连续分配管理方式,包括单一连续区、固定分区、动态分区,掌握非连续分配管理方式,包括分页管理方式、分段管理方式、段页式管理方式,了解虚拟内存基本概念,掌握请求分页管理方式,掌握页面置换算法,包括**置换算法 (OPT)、先进先出置换算法 (FIFO)、最近最少使用置换算法 (LRU)、时钟置换算法 (CLOCK),了解页面分配策略,了解工作集和抖动的概念。
文件管理 :了解文件概念,理解文件的逻辑结构,掌握目录结构,包括文件控制块和索引节点、单级目录结构和两级目录结构、树形目录结构,了解文件共享和文件保护机制,了解文件系统层次结构,掌握目录实现方式和文件的物理组织方式,了解磁盘的结构,掌握磁盘调度算法。
输入输出 (I/O) 管理 :了解 I/O 控制方式和 I/O 软件层次结构,了解 I/O 调度概念,了解高速缓存与缓冲区管理方式,掌握设备分配与回收过程,理解设备无关和假脱机技术 (SPOOLing)。
计算机网络
计算机网络体系结构 :要求考生了解计算机网络的概念、组成与功能,了解计算机网络的分类,掌握电路交换、报文交换、分组交换的特点及数据传送时间的计算,理解计算机网络主要性能指标,了解计算机网络分层结构,理解计算机网络协议、接口、服务概念,理解计算机网络体系结构,了解 OSI 参考模型、TCP/IP 参考模型。
物理层 :理解带宽、码元、速率等基本概念,掌握数据传输速率极限控制原理及公式 (奈氏定理、香农定理),理解编码与调制方法,了解双绞线、同轴电缆、光纤与无线传输介质特点,理解频分多路复用、时分多路复用、波分多路复用的概念和基本原理,掌握码分多路复用的基本原理。
数据链路层 :理解数据链路层需要解决的三个基本问题 (数据封装、透明传输、差错检测) 方法,了解 PPP 协议的协议结构,理解 PPP 协议工作原理,理解经典以太网协议 (CSMA/CD) 控制原理,掌握以太网帧格式、征用期、最小帧长、二进制指数退避算法,了解经典以太网参数在协议控制中的作用,理解以太网效率分析,了解以太网扩展方案,了解高速以太网的发展趋势,理解了解集线器、局域网交换机的原理和区别。
网络层 :了解异构互联网络和两种服务、两个层面的概念,理解引入网络层后数据传输的流程,了解 IP 地址及其表示方法,掌握无分类域间路由选择 CIDR 的构成形式,掌握 IP 地址到 MAC 地址转换的地址解析协议 ARP 的工作原理,理解 IP 数据报的格式,理解 IP 层转发分组的过程,掌握路由协议中自治系统内部路由协议 (OSPF) 的工作原理,理解自治系统之间路由协议 (BGP 边界网关协议) 的特点,理解网际控制报文协议 ICMP 协议工作原理,了解网络地址转换技术及虚拟专用网 vpn 技术实现,理解 IPv6 基本构成。
传输层 :掌握运输层端口作用,掌握运输层 TCP 协议特点,掌握 TCP 协议运输连接的管理,理解 TCP 可靠传输协议中停止等待协议基本原理,理解停止等待协议改进协议 ARQ 协议及滑动窗口机制,掌握利用滑动窗口机制实现的流量控制过程,理解 TCP 协议中 RTT 往返时延在超时重传计时器计算及拥塞控制中的作用,掌握 TCP 拥塞控制的基本方法,理解 UDP 协议的工作原理、UDP 特点。
应用层 :掌握 DNS 系统的工作原理,掌握域名解析过程,掌握 HTTP 协议的工作流程,了解 WWW 组成,理解电子邮件的组成结构,了解 FTP 协议的工作原理,了解 DHCP 协议工作流程。