813计算机专业基础数据结构(120分)考查内容：数据结构主要考查考生以下几个方面：1.理解数据结构的基本概念；掌握数据的逻辑结构、存储结构及其差异，以及各种基本操作的实现。2.掌握基本的数据处理原理和方法的基础上，能够对算法进行设计与分析。3.能够选择合适的数据结构和方法进行问题求解。应掌握的具体内容为：一、线性表(一)线性表的定义和基本操作(二)线性表的实现1.顺序存储结构2.链式存储结构3.线性表的应用

二、栈、队列和数组(一)栈和队列的基本概念(二)栈和队列的顺序存储结构(三)栈和队列的链式存储结构(四)栈和队列的应用(五)特殊矩阵的压缩存储

三、树与二叉树(一)树的概念(二)二叉树1.二叉树的定义及其主要特征2.二叉树的顺序存储结构和链式存储结构3.二叉树的遍历4.线索二叉树的基本概念和构造5.二叉排序树6.平衡二叉树(三)树、森林1.书的存储结构2.森林与二叉树的转换3.树和森林的遍历(四)树的应用1.等价类问题2.哈夫曼(Huffman)树和哈夫曼编码

图图的概念图的存储及基本操作邻接矩阵法邻接表法图的遍历深度优先搜索广度优先搜索图的基本应用及其复杂度分析最小(代价)生成树最短路径拓扑排序关键路径

查找查找的基本概念顺序查找法折半查找法B-树散列(Hash)表及其查找查找算法的分析及应用

内部排序排序的基本概念插入排序直接插入排序折半插入排序起泡排序(bubble sort)简单选择排序希尔排序(shell sort)快速排序堆排序二路归并排序(merge sort)基数排序各种内部排序算法的比较内部排序算法的应用

题型和分值填空题15%、选择题20%、问答题40%、算法题25%参考书目数据结构 ( C语言版)严蔚敏 吴伟民 清华大学出版社

计算机组成原理?(30分)考查目标1.?????理解单处理器计算机系统中各部件的内部工作原理、组成结构以及相互连接方式，具有完整的计算机系统的整机概念。2.?????能够运用计算机组成的基本原理和基本方法，对有关计算机硬件系统中的理论和实际问题进行计算、分析???并能对一些基本部件进行简单设计。

考查内容一、概述1.???存储程序概念2. ?计算机硬件的基本组成3. 计算机系统的层次结构4.??计算机的主要性能指标二、数据的机器层次表示(一)?数值数据的表示1.????无符号数2. 带符号数(真值和机器数)(二)???机器数的定点表示与浮点表示1.?????定点数的表示2.?????浮点数的表示(包括IEEE 754标准浮点数)(三)非数值数据的表示1.????字符的表示2.????汉字的表示(四)十进制数的编码(五)数据校验码三、?????指令系统(一)???指令格式1.?????指令的基本格式2.?????定长操作码指令格式3.?????扩展操作码指令格式(二)???指令的寻址方式1.?????有效地址的概念2.?????数据寻址和指令寻址3.?????常见寻址方式(三)堆栈与堆栈操作(四)指令类型1.????程序控制类指令2.????输入输出类指令(五)???CISC和RISC的基本概念四、数值的机器运算(一)基本算术运算的实现1.?????串行加法器和并行加法器2.???进位的产生和传递3. 并行加法器的快速进位(二)?定点数的运算1. 补码定点数的加/减运算2. 溢出概念和判别方法3. 定点数的移位操作4. 定点数的乘/除运算(三)??浮点数的运算五、?存储系统与结构(一)??存储系统的组成(二)???主存储器的组织1．主存储器的存储单元2．数据在主存中的存放(三)???半导体随机存储器和只读存储器1.?????SRAM存储器的工作原理2.?????DRAM存储器的工作原理3. 只读存储器(四)???主存储器的连接与控制1. 主存容量的扩展2. 存储芯片的地址分配和片选3. 主存储器与CPU的连接(五)???高速缓冲存储器(Cache)1.?????Cache的基本工作原理2.?????Cache和主存之间的映射方式3.?????Cache中主存块的替换算法(六)???虚拟存储器1.?????虚拟存储器的基本概念2.?????页式虚拟存储器3.????快慢表六、?????中央处理器(一)???CPU的功能和基本结构1. CPU中的主要寄存器2. CPU的组成(二)控制器的组成和实现方法1.控制器的基本组成2.??硬布线控制器和?微程序控制器的区别(三)??时序系统与控制