第四章 树和二叉树——树与二叉树的应用 ★★★★★ 1、重点掌握二叉搜索树的定义和基本概念，二叉搜索树的搜索、插入和删除过6-8小时 程。 2、掌握平衡二叉树的定义、概念和性质，以及平衡二叉树的插入删除过程，平衡二叉树的平衡旋转方法。 3、掌握哈弗曼树的定义和基本概念，哈弗曼树的构造算法和哈弗曼编码。 第五章 图——图的基本概念与存储结构 ★ 1、掌握图的定义与术语，边，顶点，有向图，无向图，完全图，子图，连通图，2-4小时 生成树等。 2、掌握图的两种基本存储结构：邻接矩阵表示法和邻接表表示法， 3、掌握在两种表示方法上进行搜索，插入和删除操作，了解两种表示方法之间的互相转换。 第五章 图——图的遍历 ★ 1、掌握图的两种遍历方式：深度优先遍历和广度优先遍历，能够针对给出的图第5周 16-26小时 2-4小时 写出两种遍历方式的序列。 2、掌握递归的方法对图进行深度优先遍历，和使用队列对图进行广度优先遍历。 3、掌握两种遍历方法的时间复杂度和空间复杂度。 第五章 图——图的基本应用 ★★★★ 1、掌握最小代价生成树的基本概念，掌握构造最小代价生成树的两种算法：Prim算法和Kruskal算法。了解两种算法的适用场合和各自的时间复杂度。 12-14小时 2、掌握求最短路径的两种算法：Dijkstral算法和Floyd算法，理解算法的原理，并能根据算法写出求解过程，掌握两种算法各自适用的场合和时间复杂度。 3、掌握拓扑排序的基本概念，拓扑排序算法及其时间复杂度。了解深度优先算法求解拓扑排序问题。 4、掌握关键路径的定义和基本概念，会求AOE网络的最短路径。 2-4小时 第六章 查找——基本概念 掌握查找的基本概念，内搜索，外搜索，静态查找，动态查找等。 第六章 查找——查找方法 ★★★★ 1、掌握顺序查找和折半查找的基本概念和算法时间复杂度。掌握二叉判定树的第6周 12-20小时 8-10小时 基本概念。 2、掌握B-树的定义和基本概念，以及B-树的基本操作，查找，插入和删除。结点的分裂和合并。 3、掌握B+树的定义和基本概念，以及B+树的基本操作，查找，插入和删除。结点的分裂和合并。 4、比较和掌握B-树和B+树的相同点和不同点，B+树的顺序检索和B+树的双索引。 6 / 18 5、掌握散列(Hash)表的定义和基本概念，散列表的散列函数和处理冲突的方法。掌握散列表的装填因子的定义和概念。 第六章 查找——方法的应用与比较 ★ 2-6小时 对各种查找方法进行时间和空间复杂度进行比较分析，能根据具体的应用先用不同的查找方法解决问题。 2-4小时 第七章 内部排序——基本概念 ★★ 了解排序的基本概念。包括稳定性，时间复杂度等。 第七章 内部排序——基本方法 ★★★★★ 1、掌握插入排序的基本概念和性质，包括直接插入排序和折半插入排序，掌握它们各自的优缺点和时间复杂度，以及稳定性。 2、掌握起泡排序的基本概念和性质，算法过程，时间复杂度，以及稳定性。 3、掌握简单选择排序的基本概念和性质，算法过程，时间复杂度，以及稳定性。 第周 24-32小时 7-816-18小时 4、掌握希尔排序的基本概念和性质，算法过程，时间复杂度，以及稳定性。 5、掌握快速排序的基本概念和性质，算法过程，时间复杂度，以及稳定性。 6、掌握堆排序的基本概念和性质，算法过程，时间复杂度，以及稳定性。 7、掌握二路归并排序的基本概念和性质，算法过程，时间复杂度，以及稳定性。 8、掌握基数排序的基本概念和性质，算法过程，时间复杂度，以及稳定性。了解其适用场合。 第七章 内部排序——方法的应用与比较 ★★★★★ 1、掌握8种排序方法各自的稳定性能和时间复杂度。 6-10小时 2、掌握时间复杂度为O（nlog2n）的三种算法各自的优缺点，以及适用的场合。 3、掌握简单选择排序、起泡排序和插入排序的各自适用场合和特点。 4、能够在实际应用场合根据需要选择合适的排序算法。 2、4月2日—5月20日，共7周 复习资料：《组成原理》 周次 建议学习时间 学习内容（章节要求、知识点） 第一章 计算机系统概述 ★ 1、了解计算机发展历程，从电子管计算机到晶体管计算机到集成电路计算机的第1周 4-8小时 4-8小时 发展历程以及集成电路发展历程。 2、掌握计算机系统层次结构，包括计算机硬件的基本组成，计算机软件的分类以及计算机的工作过程。 3、掌握冯·诺依曼体系计算机的特点。 4、掌握计算机的各项性能指标的含义，包括：吞吐量、响应时间，CPU时钟周期、主频、CPI、CPU执行时间，MIPS、FLOPS。 第2周 8-14小时 第二章 数据的表示和运算 ★ 7 / 18 8-14小时 1、掌握数制与编码规则，包括进位计数制及其相互转换、真值和机器数的概念以及相互转换，BCD码、字符与字符串的编码与表示。 2、了解校验码规范，包括检错码和纠错码，如海明码、奇偶校验码、循环冗余码等。 3、重点掌握定点数的表示和运算，包括无符号和有符号数的表示、定点数的移位运算、原码和补码的加减乘除运算，溢出的判别方法。 4、掌握浮点数的表示和运算，重点掌握IEEE754标准的浮点数表示方法，掌握浮点数的加减运算。 5、了解算术逻辑单元ALU，了解ALU的功能和结构，串行加法器以及快速进位链。 第三章 存储器层次机构 ★★★★★ 1、了解存储器的分类，包括按存储介质分类，按存储方式分类，按在计算机中的作用分类等。 2、掌握存储器的层次化结构，其主要体现在缓存—主存和主存—辅存这两个存储层次上。 3、了解半导体随机存取存储器的工作原理，包括静态RAM和动态RAM。了10-14小时 解只读存储器、Flash存储器的工作原理。 4、掌握主存储器与CPU的连接，重点掌握存储容量的扩展，包括位扩展与字扩展。 5、了解双口RAM和多模块存储器的工作原理。 6、重点掌握高速缓冲存储器（Cache）的工作原理，包括局部性原理，主存块替换算法等。重点掌握和比较Cache的几种“写”策略（写回法和写直达法）。 7、掌握虚拟存储器的基本概念和原理，包括页式、段式以及段页式虚拟存储器，掌握TLB快表的工作原理。 第四章 指令系统 ★★★★★ 1、掌握指令的一般格式，包括定长操作码指令格式和扩展操作码指令格式。 2、重点掌握寻址方式，包括指令寻址和数据寻址。掌握8种常见的数据寻址方6-8小时 式，如立即寻址，直接寻址，隐含寻址，间址寻址等。 3、掌握CISC和RISC的基本概念和主要特征，了解二者的产生和发展， 能够比较两者的特点。 4、掌握指令的设计方法，能够根据要求自行设计指令格式。 第五章 中央处理器（CPU） ★★ 1、掌握CPU的功能和基本结构。CPU包括运算器和控制器两大部分，其基本功能是取指令，分析指令和执行指令。 10-12小时 2、掌握指令的执行过程，包括取指令，分析指令和执行指令。 3、掌握数据通路的功能和基本结构。 4、掌握指令流水线的基本概念和原理，理解影响流水线性能的因素，包括结构相关，数据相关和控制相关。 8 / 18
第3周 10-14小时 第周 4-526-32小时 5、掌握常见的多发技术的概念和原理，包括超标量技术，超流水线技术和超长指令字技术。 第五章 中央处理器（CPU）——控制器 ★★ 1、掌握CU的时序控制方法，包括同步控制、异步控制、联合控制和人工控制。 2、掌握硬布线控制器的概念和基本原理。掌握组合逻辑的设计方法，能够根据操作写出节拍安排。 10-12小时 3、重点掌握微程序控制器的工作原理，包括微程序，微指令和微命令的概念、以及他们之间的区别和联系。掌握微指令的格式（水平型、垂直型）和编码方式（直接编码、字段直接编码、字段间接编码、混合编码），微地址的形成方式。 4、重点掌握微程序设计的方法，能够根据机器指令写出对应的全部微操作及节拍安排。 第六章 总线 ★★ 第6周 6-8小时 6-8小时 1、掌握总线的基本概念，总线的分类（片内总线、系统总线、通信总线），总线的组成以及总线的性能指标（带宽、同步/异步、控制方式等）。 2、掌握总线的仲裁方式，包括集中仲裁方式和分布仲裁方式。 3、掌握总线的操作和定时方式，包括同步定时方式和异步定时方式。 4、了解总线标准，如:ISA、EISA、USB等。 第七章 输入输出（I/O）系统 ★★★★ 1、掌握I/O系统的基本概念。了解I/O系统的发展概况，掌握I/O系统的组成。 2、了解I/O设备的分类，了解外部设备的工作原理，包括输入设备、输出设第7周 8-10小时 8-10小时 备、外存储器等。 3、掌握I/O接口功能（选址、传送命令、传送数据、反应状态）和组成，掌握接口的类型。 4、重点掌握4种I/O方式，包括程序查询方式、程序中断方式、DMA方式和通道方式。掌握这4种方式的工作原理，能够分辨它们之间的区别和各自适用的场合。 5、重点理解和掌握中断的过程和原理。 3、5月21日—7月1日，共5周 复习资料：《操作系统》 周次 第1-2周 20-24小时 2-4小时 建议学习时间 学习内容（章节要求、知识点） 第一章 操作系统概述 ★ 1、了解操作系统的基本概念，理解操作系统的特征（并发、共享、异步、虚拟），掌握操作系统的功能（处理器管理、存储管理、设备管理、文件管理、提供接口），并了解操作系统所提供的服务（程序接口和用户接口）。 9 / 18 2、了解操作系统的发展与分类。重点理解单道批处理操作系统、多道批处理操作系统、分时系统和实时系统，了解它们适用的场合，以及各自的特点。 3、理解操作系统的运行环境，重点掌握几个概念：核心态（管态）、用户态（目态）。 4、理解操作系统的体系结构。 第二章 进程管理 ★★★★ 1、进程管理是操作系统非常重要的知识点，同样，也是考研计算机操作系统这一科目的重点，也是必考点，考生应当多看书，多理解，将进程管理这一知识点弄明白，不留任何死角。 2、掌握进程的概念，进程的组成（数据、代码、PCB等），需要重点掌握并且理解进程的状态和转换过程，掌握进程间的3种通信机制：共享存储方式，消息传递方式和管道通信。 3、掌握线程的概念和运用的目的，理解多线程模型，重点掌握线程和进程之间的关系。 4、掌握调度的基本概念、调度的时机与切换过程、调度的基本准则。重点掌握调度的方式（作业调度、内外存调度和进程调度）和典型的调度算法（FCFS、18-20小时 SJF等）。 5、掌握进程之间同步的概念，临界区的概念，了解实现临界区互斥的基本方法，包括软件方法和硬件方法。重点掌握使用信号量PV操作实现临界区的互斥（这是统考中非常有可能出大题的地方）。理解什么是管程。 6、重点理解并掌握经典的同步问题（生产者-消费者、读者-写者、哲学家进餐问题等），能够使用信号量PV操作描述解决方案，以这些经典同步问题的解决方案为蓝本，举一反三，去解决其他的同步问题。 7、关于死锁，也是统考中经常会考到的一个知识点，需要掌握死锁的概念，产生死锁的四个必要条件。掌握死锁的处理策略（死锁预防、死锁避免、死锁检测和解除）。 8、重点掌握死锁避免中的银行家算法，会使用该算法解题，判断是否处于安全状态，找出安全序列，这也是统考中非常有可能出大题的知识点。 第三章 内存管理 ★★★★★ 1、掌握内存管理的概念，理解程序的装入和链接过程，以及重定位技术。理解逻辑地址空间与物理地址空间。了解内存保护（读写控制、键控制）方法。 2、掌握并理解交换与覆盖技术。 10-12小时 3、重点掌握连续分配管理方式（固定分区、可变分区）和非连续分配管理方式（段式、页式、段页式）。分辨段式管理和页式管理的联系和区别。 4、重点掌握虚拟内存管理的概念和原理，理解请求分页管理方式，请求分段管理方式和请求段页管理方式。分辨三者之间的区别和联系。 5、掌握何为抖动，抖动的原因及解决方法，页面的分配策略。重点掌握页面的置换算法（如：OPT、FIFO等）。 10 / 18
第3周 10-12小时
计算机统考专业课核心学习方案 - 图文
