832-计算机综合
计算机综合包括数据结构、计算机组成原理两部分内容，每部分内容各占1/2。
I 数据结构
考试基本要求
要求考生系统地理解线性结构（线性表、数组和矩阵、栈、队列、跳表和散列表）、树型结构（森林（树）、二叉树、优先队列、搜索树）、图结构等各种主要数据结构的基本概念，掌握各种数据结构的定义、实现算法和应用；掌握基本算法设计方法（递归、贪婪算法、分而治之、动态规划）及应用；掌握程序性能分析方法。要求考生具有抽象思维能力，逻辑推理能力，和综合运用所学的知识分析问题和解决问题的能力。
考试范围
预备知识
1. C++基本语法结构和应用
2. 递归思想和方法
程序性能分析
1. 复杂性（时间复杂性和空间复杂性）的表示和计算方法
2. 插入排序、选择排序、冒泡排序、按名次排序方法
3. 顺序搜索、折半搜索方法
线性表
1. 线性表的数组描述、链表描述等存储方法
2. 线性表的插入、删除、合并等基本操作实现方法
3. 遍历器的作用、实现方法和应用
4. 线性表结构应用：箱子排序、基数排序、并查集（在线等价类）等
数组和矩阵
1. 一般矩阵存储方法和基本运算实现
2. 特殊矩阵的特征、存储方法和基本运算实现
3. 稀疏矩阵的存储方法和基本运算实现
栈
1. 栈的基本概念、基本操作和实现方法
2. 栈结构应用：括号匹配、列车车厢重排、迷宫老鼠、离线等价类等
队列
1. 队列的基本概念、基本操作和实现方法
2. 队列结构应用：列车车厢重排、电路布线、图元识别等
跳表和散列
1. 字典结构基本概念和表示结构
2. 跳表的基本概念、基本操作和实现方法
3. 散列表的基本概念、基本操作和实现方法
4. LZW压缩思想
二叉树和其他树
1. 树（以及森林）和二叉树的基本概念、存储方法、常用操作和特性
2. 二叉树的前序、中序、后序、层次遍历方法及应用
3. 树（以及森林）的存储方法
4. 树和二叉树结构的应用：基于树存储的并查集（在线等价类）等
优先队列
1. 优先队列基本概念和表示结构
2. 堆结构基本概念，堆的插入、删除和初始化等操作实现方法
3. 堆结构应用：堆排序、霍夫曼树、霍夫曼编码
4. 左高树基本概念和插入、删除、合并、初始化等操作的实现思想
搜索树
1. 二叉搜索树(排序树)基本概念和插入、删除、搜索等操作的实现方法
2. 二叉平衡树（AVL树）基本概念和插入、删除、搜索等操作的实现方法
3. m叉搜索树和B-树基本概念以及插入、删除、搜索等操作的实现方法
图
1. 图基本概念和特性
2. 图的邻接矩阵和邻接链表存储方法及各种基本操作和实现方法
3. 图的深度优先搜索（DFS）和广度优先搜索（BFS）算法
4. DFS/BFS应用：寻找路径、连通图及连通构件、生成树等
贪婪算法
1. 贪婪算法基本思想
2. AOV网的拓扑排序算法
3. 单源最短路径Dijkstra算法
4. 最小成本生成树的概念、Prim算法和Kruskal算法
5. AOE网的关键路径算法
分而治之
1. 分而治之思想
2. 归并排序、快速排序方法
3. 选择问题实现方法
动态规划
1. 动态规划思想
2. 所有顶点对之间的最短路径算法
参考文献
《数据结构，算法与应用----C++语言描述》（原书第2版），Sartaj Sahni 著 王立柱，刘志红译 ，机械工业出版社 2015年出版
《数据结构》（用面向对象方法与C++语言描述 第二版）?殷人昆 著 清华大学出版社
II 计算机组成原理
课程基本要求
理解单处理器计算机系统中各部件的内部工作原理、组成结构以及相互连接方式，具有完整的计算机系统的整机概念；
理解计算机系统层次化结构概念，熟悉硬件与软件之间的界面，掌握指令集体系结构的基本知识和基本实现方法；
能够综合运用计算机组成的基本原理和基本方法，对有关计算机硬件系统中的理论和实际问题进行计算、分析，对一些基本部件进行简单设计，并能对高级程序设计语言(如C语言)中的相关问题进行分析。
考试范围
计算机系统概述
计算机发展历程
计算机系统层次结构
计算机系统的基本组成
计算机硬件的基本组成
计算机软件的分类
计算机的工作过程
计算机性能指标
CPU时钟周期、主频、CPI、CPU执行时间、MIPS、MFLOPS
字长
容量
总线宽度
数据的表示和运算
数制与编码
进位计数制及其相互转换
真值和机器数
BCD码
字符与字符串
校验码
定点数的表示和运算
定点数的表示
无符号数的表示及范围；有符号数的表示及其相互转换。
定点数的运算
定点数的移位运算；补码定点数的加/减运算；定点数的乘/除运算；溢出概念和判别方法。
浮点数的表示和运算
浮点数的表示
浮点数的表示范围；浮点机器数与真值间的相互转换。
浮点数的加/减运算
算术逻辑单元ALU
并行加法器
算术逻辑单元ALU的功能和结构
快速进位链设计原理
存储器层次机构
存储器的分类
存储器的层次化结构
半导体随机存取存储器
SRAM存储器的工作原理
DRAM存储器的工作原理；刷新方式。
只读存储器、Flash存储器
主存储器的基本组成、存储单元的属性、数据的存放模式
存储器的技术指标
存储器的扩展方式及存储器与CPU的连接
多体并行存储器系统
高速缓冲存储器（Cache）
Cache的基本工作原理
Cache和主存之间的映射方式及其地址转换
Cache中主存块的替换算法
Cache读、写策略
指令系统
指令格式
指令的基本格式
定长操作码指令格式
扩展操作码指令格式
指令的寻址方式
有效地址的概念
数据寻址和指令寻址
常见寻址方式
CISC和RISC的基本概念
中央处理器（CPU）
CPU的功能和基本结构
指令执行过程
数据通路的功能和基本结构
基于数据通路，指令周期流程及取指、间址、执行和中断周期的数据流。
控制器的功能和工作原理
微操作命令的分析
取指周期、间址周期、执行周期和中断周期的微操作命令及其节拍安排。
组合逻辑（硬布线）控制器
组合逻辑控制器的组成结构、设计步骤。
微程序控制器
微程序、微指令、微命令、微操作、控制存储器的基本概念；
微程序控制器的设计思想、组成结构、工作原理；
微指令的编码方式；
微地址的形式方式。
指令流水线
指令流水线的基本概念
指令流水线的基本实现
影响指令流水线性能的因素：结构相关、数据相关、控制相关；
流水线的主要性能：吞吐率、加速比、效率。
流水线的多发技术
超标量处理机、超流水线处理机、超长指令字处理机的基本概念。
总线
总线概述
总线的基本概念
总线的分类
总线的组成及性能指标
总线仲裁
集中仲裁方式
分布仲裁方式
总线操作和定时
同步定时方式
异步定时方式
总线标准
输入输出（I/O）系统
I/O系统基本概念
I/O接口（I/O控制器）
I/O接口的功能和基本结构
I/O端口及其编址
I/O方式
程序查询方式
程序中断方式
中断的基本概念；中断响应过程；中断处理过程；多重中断和中断屏蔽的概念；中断处理顺序。
DMA方式
DMA控制器的组成；DMA传送过程。
通道方式
三、参考书目
唐朔飞，计算机组成原理（第3版），高等教育出版社， 2020.10，十二五”普通高等教育本科国家级规划教材。
白中英 戴志涛，计算机组成原理（第6版），科学出版社，2019.8，十二五”普通高等教育本科国家级规划教材。
