833或834数据结构和计算机组成原理考研复习考纲重点提纲

834"数据结构、计算机组成原理“复习参考提纲考察目标834数据结构、计算机组成原理要求考生比较系统地棠握上述专业基础课程的基本概念、基本原理和基本方法，能够综合运用所学的基本原理和基本方法分析判断和解决有关理论问题和实际间题”二、 考试形式和试卷结构1、 试卷满分及考试时间：本试卷满分为150,考试时间为180分钟2、 答题方式：闭卷，笔试3、 试卷内容结构：数据结构75分、计算机组成原理75分三、 考察范围数据结构：【总体要求】“数据结构”要求学生掌握数据结构的基本理论和基本方走，使学生具备基本的数据结构分析、设计、求解实际问题的能力。要求掌握数据结构的基本概念、基本原理和基本方掌；握线性表、树与二叉树、图的逻辑结构、物理结构、基本操作，以及基本操作在不同的物理结构上的实现，并能够对操作算庄进行基本的时间复杂度和空间复杂度进行分析；掌握基本查找和排序方法，并能够利用这些方法对实际问题进行分析和求解，具备采用C或C++语言没计与实现算层的能力。（833的同学建议用834的考纲，834的考纲比较全）初试代码可以用伪代码CI。++语言，复试上机可以用C或者C++（建议C++）（-）数据结构基本概念题型：选择题为主高频考点求经典算法的时间复杂度&空间复杂度难点：时间复杂度、空间复杂度复习内容数据结构、算法的基本定义，数据结构的逻辑结构和物理结构，算庄的性能评价方法。具体要求数据结构的定义数据结构的逻辑结构数据结构的物理结构算法的概念和算法的性能评价（二） 线性表题型：选择题、大题都有高频考点链表的基本操作（头插、尾插等）、顺序表的基本操作（入、删除等）、链表的相关算法（约瑟夫循环、链表逆置等）、时间复杂度、空间复杂度等难点：链表的相关算法复习内容线性表的概念和基本运算，线性表的顺序存储和链式存储，线性表的基本运算在顺序存储和链式存储结构上的实现。具体要求线性表的概念和基本运算线性表的顺序存储线性表的链式存储线性表的应用（三） 栈和队列题型：选择题、大题都有高频考点栈的基本操作（入栈、出栈等）、队列的基本操作（入队列、出队列）栈的相关算法（元素逆置、递归等）、时间复杂度、空间复杂度等难点：栈的相关算法复习内容栈和队死的基本概念、基本操作和存储结构。具体要求栈和队列的基本概念和基本操作栈和队列的顶序存储结构栈和队列的链式存储结构栈和队列的应用（四） 串题型：选择题（主要）、大题（概率小）都有高频考点：朴素模式匹配、KMP模式匹配、求解nex数组难点:KMP代码实现复习内容串的基本概念、存储结构和模式匹程算庄具体要求串的基本概念和基本操作串的顺序存储结构串的链式存储结构模式匹配算法（五） 数组和广义表题型：选择题（主要）、大题（概率小）都有高频考点：三个特殊矩阵、稀疏矩阵、广义表（画图、求Head.Tail）难点：三个特殊矩阵求原来位置（A[i][j]）压缩之后的B[i]位置、广义表做图复习内容数组和广义表的基本概念、数组的顶序存储和特殊矩阵的压缩存储。具体要求数组的基本概念和基本操作数组的顺序存储和实现特殊矩阵的尸缩存储广义表的基本概念和存储（六） 树与二叉树题型：选择题、大题都有高频考点:二叉树相关算法（先序、中序、后序递归与非递归法等）、二叉树与树的转换、线索二叉树、哈夫曼树（求解WPL、画图、代码实现）难点：哈夫曼树、先序、中序、后序非递归算法复习内容树与二叉树的基本概念、存储结构和性质，树与二叉树约遍历，树、森林与二叉树的转换，哈夫曼（Huffman）树的概念和应用。具体要求（一） 树的概念（二） 二叉树二叉树的定义及主要特征二叉树的顺序存储结构二叉树的链式存储结构二叉树的遍历线索二叉树的基本概念和构造（三） 树、森林树的存储结构树、森林与二叉树的转换析和森林的遍历（四） 树与等价问题（五） 哈夫曼（Huffman）树和哈夫曼编码（七）图题型：选择题、大题都有高频考点：图的基本操作（求结点的度、拓扑排序、求出关键路径、最小生成树、最短路径等）、图的相关算法（邻接阵、邻接表、广度优先搜索、深度优先搜索、拓扑排序等算法）难点：广度优先搜索、深度优先搜索、拓扑排序算法笥复习内容图的基本概念和存储结构、图的遍历、图的基本应用算法。2.具体要求（-）图的基本概念（二） 图的存储结构邻接矩阵法邻接表法逆邻接表法十字链表邻接多重表（三） 图的遍历深度优先遍历广度优先遍历（四） 图的基本应用算法连通分量与最小生成树拓扑排序关钳路径最短路径（七）查找题型：选择题、大题都有高频考点查找的基本操作（平衡二叉树插入删除结点、求ASL成功、ASL失欢、画出哈希表（开放地址发、链地址法、再哈希法）、B树性质等）、查找的相关算法（顺序表查找、折半查找算法等）难点：平衡二叉树插入删除结点、哈希表、ASL失”等复习内容查找的基本概念、静态查找表和动态查找表、哈希表。具体要求（-）查找的基本概念（二）静态查找表顺序查找庄折半查找法索引顺序查找庆（三）动态查找表二叉排序树及其基本操作严衡二叉树概念B树及其基本操作B+树的基本概念（五） 哈希（Hash）表哈希表的基本概念哈希函数的构造冲突的解决方法（六） 查找算法的分析及应用（九）排序题型：选择题、大题都有高频考点:排序的基本操作（算法的稳定性、时间复杂度、空间复杂度等）、排序的相关算法（直接插入、折半插入、归并算法、快速排序、堆排序等）难点：归并算法、快速排序、堆排序等复习内容排序的基本概念、排序算法和性能分析。具体要求（-）排序的基本概念（二） 插入排序直接插入排序折半插入排序2-路插入排序表插入排序希尔排序（三） 交换排序起泡排序快速排序（四） 选择排序简单选择排序堆排序（五） 归升排序（六） 基数排序（七） 竹部排序计算机组成原理：【总体要求】“计算机组成原理要求学生掌握单处理器计算机系统中各部件的内部工作原理、组成结构以及相互连接万武，具有完整的计算机系统的整机概念。要求掌握计算机系统层次化结构概念，熟悉硬件与软件之间的界面；掌握计算机数据表示的万庆，包括定点数和浮点数的表示；掌握运算器的原理和实现电路；掌握存储层次的概念，掌握不同类型存储器特性S包M、DRAM、ROM;掌握王存结构及基本设计万年会解决Cache存储的-些基本问题；掌握炖盘基本原理及日人］D掌握指令集体系结构的基本知识和基本实现万庆；熟悉中央处理器的时序逻辑，即指令周期、CPU周期、节拍周期、时钟周期之间的关系；掌握中央处理器控制器的基本设计万庆，即硬布线和微程序控制，能够根据模拟CPU及系统框架设计控制信号逻辑或者编写简单微操作流程；掌握计算机输入输出系统的基本概念，程序查询万武、中断万式和直接存储器存取万式；掌握总线的仲裁万式和特点；基本掌握升行计算机的原理和发展趋势；基本掌握对种多处理器系统、多计算机系统的结构及特点；掌握流水线技术能够计算各种流水线的性能指标参数，分析流水线的特点，解决数据相关的万庆等；能够运用计算机组成的本原理和基本万庆，对有关计算机硬件系统中的理论和实忻问题进行计算、分析，并能对些基本部件进行简单设计。研究生课程考试是所学知识的总结性考试，考试水平应达到或超过本科专业相应的课程要求水平。（-）计算机系统概论题型：选择题（主要）、大题（概率小）都有高频考点：冯诺依曼特性、控制流、数据流、阿姆达尔定律等难点：可能会出超纲问题（例如我国天河二号排2020年排名？）1复习内容计算机的基本组成，冯.诺依曼计算机原理，计算机系统的层次结构，计算机的分类及性能描述，计算机的发展历程2.具体要求*计算机的基本组成***件组成***软组成*冯诺依曼计算机二作原理**冯诺依曼计算机结构及工作过程**冯诺依曼计算机特点＊计算机系统的层次结构*层次结构图计算机的分类及性能描述***Flynn分类法***Amdahl定律和应用**春旺量，响应时间***CPU时钟周期主频、CPI、CPU执行时间***MIPSMFLOPS、（二）计算机系统中的数据表示题型：选择题、大题都有高频考点原码、补码、反码之间的转换、BCD码、浮点数表示、定点数表示、IEEE754表示、三种纠错校验等难点：浮点数表示、IEEE754表示、三种纠错校验L复习内容数制与编码，定点数据表示，浮点数据表示，纠错和校验2,具体要求*数制与编码**数制及相互转换**真值和机器数***BCD码＊定点数据表示* ■.士-无符号数的表示*有符号数的表示*原码、反码补码、移码浮点数据表示*格式定义***规格化*数据范围***IEEE754标准纠错和校验*奇偶校验*汉明编码*循环冗余校验（三）运算方法与运算器题型：选择题、大题都有高频考点定点数加法运算、乘法运算、除法运算、浮点数加减法运算等难点：定点数乘法运算、除法运算、全加器电路图、浮点数加减法运算L复习内容定点数的位移运算，原码定点数的加减运算，补码定点数的加减运算，定点数的乘除运算，溢出概念和判别方法，浮点数的加I减运算，浮点数的乘I除运算，算大逻辑单元ALU2,具体要求*原码定点数的加I减运算方法，应用*补码定点数的加/减运算方法，应用**行波进位、先行进位加法器*移位处理*溢出处理和判断*定点数的乘I除运算*原码乘法，补码乘法*恢复余数，不恢复余数除法*阵死乘法器*阵列除法器*浮点数的加/减运算*对阶*尾数加减*规格化溢出处理*浮点数的乘I除运算**方法应用规格化算术逻辑单元ALU*组成*类^（四）存储系统题型：选择题、大题都有高频考点:存储器相关性之、三种相联映射方式硬盘记录方式、格式化容量、非格式化容量、数据传输速率等难点：三种相联映射方式、硬盘记录方式、格式化容量、非格式化容量、数据传输速率等1.复习内容存储器的分类，存储器的层次化结构，半导体随机存取存储器王存^器与CPU的连接，双口RAM和多模块存储器，高速缓冲存储器，虚拟存储器，硬盘存储器2,具体要求*存储器的分类***按照不同万式进行分类的万庆***存储器容量、速度、可靠性*存储系统的层次化结构***具体层次化形式***各种存储器的位置*半导体随机存取存储器***SRAM存储器的工作原理***DRAM存储器的工作原理***ROM存储器的工作原理*王存储器的构成万庆***字扩展万武**位扩展万武*多端口、多模块、相联存储器***多端口存储器■-多端口组织形式***多模块存储器--交叉存储万式***相联存储器-按内容访问的存储器＊高速缓冲存储器***程序局部性及Cache工作原理***Cache与王存地址映射与变换万武***Cache替换算庆***Cache写策略＊虚拟存储器***虚拟存储器的基本概念＊硬盘存储器***;it记录原理***勤记录方式**癌盘的基本参数及计算***RAID（五）指令系统题型：选择题、大题都有高频考点:指令设计、寻址方式、RISC、CISC知识点、地址范围等难点：指令设计、寻址方式等1复习内容指令格式，寻址方式，CISC和RISC基本概念。2.具体要求＊指令格式**指令的基本格***定操作码计*扩展操作码设计*存储器操作数的大/小端存储、边界对齐、堆栈操作、哈佛存储结构*操作数的寻址方式**有效址的概念*数据寻址和指令寻址**常用寻址方式*CISC和RISC的基本概念***RISC的发展历程***CISC和RISC的技术特点（六）中央处理器题型：选择题、大题都有高频考点：微操作、硬布线控制器、微程序控制器、CPU执行时间、吞吐量、CPI,MIPS难点：硬布线控制器、CPU执行时间、吞吐量、CPI、MIPS等复习内容CPU的功能和基本结构，指令执行过程，数据通路的功能和基本结构，控制器的功能和工作原理。具体要求*CPU的功能和基本结构***CPU的主要构成部件***CPU内的常见寄存器***CPU内部的数据通路*指令执行过程**时时序发生器***CPU内部时序概念***典型指令的执行过程＊数据通路的功能和基本结构＊控制器的功能和工作原理***硬布线控制器结构及设计方法***微程序控制器结构及设计方法***微操作微命令、微指令、微程序***微操作和微命令序死（流程）设计***微命令的互斥和相容（七）流水线技术与指令级并行题型：选择题、大题都有高频考点：流水线时空图、吞吐率、效率、加速比、数据重定向、超标量处理器等、超长指令字处理器等难点：流水线时空图、吞吐率、效率、加速比等1复习内容流水线概念，流水线分类，流水线性能指标，流水线相关处理，超标量处理，VLIW,多核处理器的基本概念。2.具体要求*流水线概念*流水线分类**不同方式的送***静态多功能流水线'*流水线性能指标、E***吞吐率**效率*雌匕*时空图*流水线相关判定及处理*结构相关*数据相关**控相关*相关处理方式：等待（停顿）、直接通路、分支预测等*超标量处理器概念及特点*VLIW处理器概念及特点*多核处理器的基本概念（八）总线与输入输出系统题型：选择题、大题都有高频考点：总线仲裁、DMA、1/0通道方式计算、中断方式等难点：DMA、中断方式等复习内容总线概述，总线仲裁，总线操作和定时，总线标准，I/O系统基本概念，房部设备，I/O接口，1/0方式。具体要求*总线概述**总线的基:概念***总线的分类***总线的组成及性能指标*总线仲裁*集中仲裁方式：菊花链方式、轮询计数、独立请求方式*分布仲裁方式*总线操作和定时***总线读写操作*伺步定时方式*户，土r-L-J U异步定时方式*总线标准*1/0系统基本概念*外部设备**输入设备**轮出设备1/0接日***1/0接口的功能和基本结构*