2012年研究生入学考试计算机统考大纲

### 2012年研究生入学考试计算机统考大纲知识点解析 #### 数据结构部分 **考查目标** - **基础知识理解**：理解数据结构的基本概念，包括数据的逻辑结构与存储结构的区别，掌握基本操作的实现。 - **算法设计与分析**：在掌握基本的数据处理原理和方法的基础上，能够进行算法的设计与分析。 - **问题解决能力**：能够根据具体问题选择合适的数据结构和方法来解决问题。 **具体内容** 1. **线性表** - **定义和基本操作**：了解线性表的基本概念及其常见的操作（如插入、删除等）。 - **实现方式** - **顺序存储结构**：掌握顺序存储的特点和应用场景。 - **链式存储结构**：理解链表的结构特点，包括单链表、循环链表、双向链表等。 - **应用实例**：学会如何利用线性表解决实际问题。 2. **栈、队列和数组** - **基本概念**：掌握栈和队列的基本特性，理解它们作为后进先出（LIFO）和先进先出（FIFO）数据结构的意义。 - **存储结构** - **顺序存储**：了解栈和队列的顺序存储实现。 - **链式存储**：理解栈和队列的链式存储实现。 - **应用实例**：学习栈和队列在实际编程中的应用，如括号匹配、队列调度等。 3. **树与二叉树** - **树的概念**：理解树的基本结构，包括节点、边、根节点、叶子节点等术语。 - **二叉树** - **定义与特征**：掌握二叉树的定义及其性质。 - **存储结构**：了解二叉树的顺序存储和链式存储方法。 - **遍历方法**：学习前序、中序、后序遍历以及层序遍历。 - **特殊类型**：掌握线索二叉树、二叉排序树和平衡二叉树的概念和应用场景。 - **树、森林** - **存储结构**：理解树的存储方式。 - **转换与遍历**：学习森林与二叉树之间的转换方法，掌握树和森林的遍历方法。 - **应用实例**：例如等价类问题、哈夫曼树和哈夫曼编码等。 4. **图** - **基本概念**：掌握图的基本概念，如顶点、边、权值等。 - **存储方式** - **邻接矩阵**：适用于稠密图的存储。 - **邻接表**：适用于稀疏图的存储。 - **遍历方法** - **深度优先搜索**：通过递归或栈实现。 - **广度优先搜索**：使用队列实现。 - **应用实例** - **最小生成树**：了解普里姆算法和克鲁斯卡尔算法。 - **最短路径**：掌握迪杰斯特拉算法和弗洛伊德算法。 - **拓扑排序**：适用于有向无环图的排序。 - **关键路径**：在项目管理中的应用。 5. **查找** - **基本概念**：理解查找的基本思想。 - **查找方法** - **顺序查找**：适用于未排序的序列。 - **折半查找**：适用于有序序列。 - **B-树**：一种自平衡的查找树。 - **散列表**：基于哈希函数实现高效查找。 - **算法分析**：学会评估不同查找方法的时间复杂度。 6. **内部排序** - **基本概念**：理解排序的基本思想。 - **排序方法** - 插入排序、选择排序、冒泡排序等简单排序方法。 - 希尔排序、快速排序、堆排序等高级排序方法。 - 归并排序、基数排序等非比较排序方法。 - **算法分析**：掌握各种排序算法的时间复杂度和空间复杂度。 #### 计算机组成原理部分 **考查目标** - **计算机系统理解**：理解单处理器计算机系统中各部件的内部工作原理、组成结构以及相互连接方式。 - **层次化结构认知**：理解计算机系统层次化的结构概念，掌握硬件与软件之间的界面，熟悉指令集体系结构的基本知识和实现方法。 - **设计与分析能力**：能够运用计算机组成的基本原理和方法，对有关计算机硬件系统中的理论和实际问题进行计算、分析，并能对一些基本部件进行简单设计。 **具体内容** 1. **计算机系统概述** - **发展历程**：了解计算机的发展历程，包括早期电子管计算机到现代高性能计算机的演变。 - **层次结构**：掌握计算机系统的层次化结构，包括硬件层、操作系统层、应用程序层等。 - **基本组成**：熟悉计算机硬件的基本组成，包括输入设备、输出设备、存储器、运算器和控制器等。 - **工作过程**：理解计算机的工作原理，包括指令的获取、解码、执行等步骤。 - **性能指标**：掌握衡量计算机性能的主要指标，如吞吐量、响应时间、CPU时钟周期、主频、CPI等。 2. **数据的表示和运算** - **数制与编码** - **进位计数制**：理解二进制、八进制、十进制和十六进制之间的转换方法。 - **真值与机器数**：掌握有符号数和无符号数的表示方法，包括原码、反码和补码等。 - **BCD码**：了解二进制编码十进制码的基本概念。 - **字符与字符串**：掌握ASCII码和其他字符编码方案。 - **校验码**：学习奇偶校验码等错误检测方法。 - **定点数运算** - **表示方法**：理解定点数的表示方式。 - **运算规则**：掌握定点数加减乘除运算的具体步骤。 - **溢出判断**：学习溢出的概念和判断方法。 - **浮点数运算** - **表示方法**：了解浮点数的标准化表示方式。 - **IEEE754标准**：熟悉IEEE754浮点数的标准格式。 - **加减运算**：掌握浮点数加减运算的步骤。 3. **存储器层次机构** - **分类**：了解存储器的基本分类，如主存储器、辅助存储器等。 - **层次化结构**：理解高速缓存、主存和辅存之间的层次关系。 - **SRAM和DRAM**：掌握静态随机存取存储器和动态随机存取存储器的工作原理。 - **只读存储器**：了解ROM的种类和用途。 - **Cache原理**：掌握高速缓冲存储器的工作原理，包括替换算法、映射方式等。 - **虚拟存储器**：理解虚拟存储器的基本概念，包括页面置换算法、快表（TLB）等。 4. **指令系统** - **指令格式**：理解指令的基本格式，包括操作码、操作数等。 - **寻址方式**：掌握常见的寻址方式，如直接寻址、间接寻址、相对寻址等。 - **CISC与RISC**：了解复杂指令集计算机与精简指令集计算机的区别。 5. **中央处理器（CPU）** - **功能与结构**：掌握CPU的基本功能和组成部分，如运算器、控制器等。 - **指令执行过程**：理解指令的取指、译码、执行等阶段。 - **数据通路**：掌握数据通路的基本结构和功能。 - **控制器工作原理**：学习硬连线控制和微程序控制的不同。 - **指令流水线**：理解指令流水线的基本概念和优缺点。 6. **总线** - **基本概念**：了解总线的基本概念，包括数据总线、地址总线、控制总线等。 - **仲裁方式**：掌握集中式仲裁和分布式仲裁的方法。 - **总线操作**：学习同步定时和异步定时的总线操作机制。 通过以上内容的学习，考生可以全面地掌握数据结构与计算机组成原理的基础知识，为后续的深入学习和技术研究打下坚实的基础。