新祥旭考研官网 http:/www.xxxedu.net/833“计算机学科专业基础综合”复习参考提纲一、 考察目标计算机学科专业基础综合考试涵盖数据结构和计算机组织与体系结构等学科专业基础课程。要求考生比较系统地掌握上述专业基础课程的基本概念、基本原理和基本方法，能够综合运用所学的基本原理和基本方法分析、判断和解决有关理论问题和实际问题。二、 考试形式和试卷结构1、 试卷满分及考试时间：本试卷满分为 150，考试时间为 180 分钟2、 答题方式：闭卷，笔试3、 试卷内容结构：数据结构 75 分、计算机组织与体系结构 75 分三、 考察范围数据结构：【总体要求】“数据结构”要求学生掌握常用数据结构的构造和实现，具备应用数据结构分析、设计和求解实际问题的能力。要求掌握数据结构的基本概念、基本原理和基本方法；掌握线性结构、树和图的逻辑结构、存储（物理）结构，以及基本操作在不同存储结构上的实现，并能够对基本算法进行时间复杂度和空间复杂度分析；掌握基本的查找和排序方法及其算法实现，并能够利用这些方法对实际问题进行分析和求解，具备采用 C 或 C+或 Java 等编程语言设计与实现算法的能力。新祥旭考研官网 http:/www.xxxedu.net/（一）线性表1）线性表的基本概念和基本操作2）线性表的顺序存储及实现3）线性表的链式存储及实现4）线性表的应用（二）栈和队列1）栈和队列的基本概念和基本操作2）栈和队列的存储结构与实现（1）栈的顺序存储及实现（2）栈的链式存储及实现（3）队列的链式存储及实现（4）循环队列的定义及实现3）栈和队列的应用（三）串1）串的基本概念和基本操作2）串的顺序存储、链式存储及实现3）串的模式匹配（1）基本的模式匹配算法（2）KMP 模式匹配算法（模式串的 next 函数计算）（四）数组和广义表1）数组的基本概念和基本操作新祥旭考研官网 http:/www.xxxedu.net/2）数组的顺序存储3）特殊矩阵的压缩存储、稀疏矩阵的压缩存储4）广义表的基本概念和存储结构（五）树与二叉树1）树的基本概念2）二叉树（1）二叉树的定义及性质（2）二叉树的顺序存储和链式存储（3）二叉树的先序、中序、后序遍历和层序遍历运算（4）线索二叉树的定义与基本运算3）树和森林（1）树的存储结构（2）树（森林）与二叉树的相互转换（3）树和森林的遍历4）哈夫曼（Huffman）树的构造与应用（六）图1）图的基本概念和基本操作2）图的存储结构（1）数组表示法（邻接矩阵表示法）（2）邻接表表示法、逆邻接表表示法（3）邻接多重表（4）十字链表新祥旭考研官网 http:/www.xxxedu.net/3）图的遍历（1）深度优先遍历（DFS）算法（2）广度优先遍历（BFS）算法4）图的应用（1）最小生成树求解方法（Prim 算法、Kruskal 算法）（2）最短路径求解方法（Dijkstra 算法、Floyd 算法）（3）AOV-网和拓扑排序方法（4）AOE- 网和关键路径求解方法（七）查找1）查找的基本概念2）静态查找表（1）无序顺序表、有序顺序表（2）顺序查找算法（3）折半查找算法、折半查找判定树的构造3）动态查找表（1）二叉查找树（二叉检索树、二叉排序树）的构造及查找、插入和删除运算（2）平衡二叉树的构造及查找运算（3）B- 树的特点及查找运算（4）B+树的基本概念4）哈希表（1）哈希表的基本概念新祥旭考研官网 http:/www.xxxedu.net/（2）哈希表的构造及查找运算5）查找算法的分析（平均查找长度计算）及应用（八）排序1）排序的基本概念（排序过程中的基本操作、排序算法的时空复杂度及稳定性）2）简单排序方法（1）直接插入排序算法（2）冒泡排序算法（3）简单选择排序算法3）快速排序4）堆排序5）归并排序6）基数排序（1）多关键排序方法（2）链式基数排序方法及特点7）外部排序的基本概念计算机组织与体系结构:【总体要求】“计算机组织与体系结构” 要求学生掌握单处理器计算机系统中各部件的内部工作原理、组成结构以及相互连接方式，具有完整的计算机系统的整机概念。新祥旭考研官网 http:/www.xxxedu.net/要求掌握计算机系统层次化结构概念，熟悉硬件与软件之间的界面；掌握计算机数据表示的方法，包括定点数和浮点数的表示；掌握运算器的原理和实现电路；掌握存储层次的概念，掌握不同类型存储器特性，包括SRAM、 DRAM、ROM；掌握主存结构及基本设计方法；会解决 Cache 存储的一些基本问题；掌握磁盘基本原理及 RAID；掌握指令集体系结构的基本知识和基本实现方法；熟悉中央处理器的时序逻辑，即指令周期、CPU 周期、节拍周期、时钟周期之间的关系；掌握中央处理器控制器的基本设计方法，即硬布线和微程序控制，能够根据模拟 CPU 及系统框架设计控制信号逻辑或者编写简单微操作流程；掌握计算机输入输出系统的基本概念，程序查询方式、中断方式和直接存储器存取方式；掌握总线的仲裁方式和特点；基本掌握并行计算机的原理和发展趋势；基本掌握对称多处理器系统、多计算机系统的结构及特点；掌握流水线技术，能够计算各种流水线的性能指标参数，分析流水线的特点，解决数据相关的方法等；能够运用计算机组成的基本原理和基本方法，对有关计算机硬件系统中的理论和实际问题进行计算、分析，并能对一些基本部件进行简单设计。研究生课程考试是所学知识的总结性考试，考试水平应达到或超过本科专业相应的课程要求水平。（一）计算机系统概论 1.复习内容计算机的基本组成，冯.诺依曼计算机原理，计算机系统的层次结构，计算机的分类及性能描述，计算机的发展历程2.具体要求新祥旭考研官网 http:/www.xxxedu.net/*计算机的基本组成*硬件组成*软件组成*冯 .诺依曼计算机工作原理*冯.诺依曼计算机结构及工作过程*冯.诺依曼计算机特点*计算机系统的层次结构*层次结构图*各层的含义和界面定义*计算机体系结构、组成和实现定义*计算机的分类及性能描述*Flynn 分类法*Amdahl 定律和应用*吞吐量、响应时间*CPU 时钟周期、主频、CPI、CPU 执行时间*MIPS、MFLOPS（二）计算机系统中的数据表示 1.复习内容数制与编码，定点数据表示，浮点数据表示，纠错和校验2.具体要求*数制与编码*数制及相互转换新祥旭考研官网 http:/www.xxxedu.net/*真值和机器数* BCD 码*字符与字符串*汉字的表示*定点数据表示*无符号数的表示*有符号数的表示*原码、反码、补码、移码*浮点数据表示*格式定义*规格化*数据范围*IEEE754 标准*纠错和校验*奇偶校验*汉明编码*循环冗余校验（三）运算方法与运算器1.复习内容定点数的位移运算，原码定点数的加/减运算，补码定点数的加/ 减运算，定点数的乘/ 除运算，溢出概念和判别方法，浮点数的加/ 减运算，浮点数的乘/除运算，算术逻辑单元 ALU新祥旭考研官网 http:/www.xxxedu.net/2.具体要求*原码定点数的加/减运算*方法，应用*补码定点数的加/减运算*方法，应用*行波进位、先行进位加法器*移位处理*溢出处理和判断*定点数的乘/除运算*原码乘法，补码乘法*恢复余数，不恢复余数除法*阵列乘法器*阵列除法器*浮点数的加/减运算*对阶*尾数加减*规格化*溢出处理*浮点数的乘/除运算*方法*应用*规格化新祥旭考研官网 http:/www.xxxedu.net/*算术逻辑单元 ALU*组成*类型（四）存储系统1.复习内容存储器的分类，存储器的层次化结构，半导体随机存取存储器，主存储器与 CPU 的连接，双口 RAM 和多模块存储器，高速缓冲存储器，虚拟存储器，硬盘存储器2.具体要求*存储器的分类*按照不同方式进行分类的方法*存储器容量、速度、可靠性*存储系统的层次化结构*具体层次化形式*各种存储器的位置*半导体随机存取存储器*SRAM 存储器的工作原理*DRAM 存储器的工作原理*ROM 存储器的工作原理*主存储器的构成方法*字扩展方式*位扩展方式