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