23年山东大学考研832计算机综合考试大纲
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语言)中的相关问题进行分析。
二、考试范围
(一)计算机系统概述计算机发展历程计算机系统层次结构（1）计算机系统的基本组成（2）计算机硬件的基本组成（3）计算机软件的分类（4）计算机的工作过程计算机性能指标（1）CPU时钟周期、主频、CPI、CPU执行时间、MIPS、MFLOPS（2）字长（3）容量（4）总线宽度
(二)数据的表示和运算1.数制与编码（1）进位计数制及其相互转换（2）真值和机器数（3）BCD码（4）字符与字符串（5）校验码2.定点数的表示和运算（1）定点数的表示无符号数的表示及范围；有符号数的表示及其相互转换。（2）定点数的运算定点数的移位运算；补码定点数的加/减运算；定点数的乘/除运算；溢出概念和判别方法。3.浮点数的表示和运算（1）浮点数的表示浮点数的表示范围；浮点机器数与真值间的相互转换。（2）浮点数的加/减运算4.算术逻辑单元ALU（1）并行加法器（2）算术逻辑单元ALU的功能和结构（3）快速进位链设计原理
(三)存储器层次机构1.存储器的分类2.存储器的层次化结构3.半导体随机存取存储器（1）SRAM存储器的工作原理（2）DRAM存储器的工作原理；刷新方式。（3）只读存储器、Flash存储器（4）主存储器的基本组成、存储单元的属性、数据的存放模式（5）存储器的技术指标4.存储器的扩展方式及存储器与CPU的连接5.多体并行存储器系统6.高速缓冲存储器（Cache）（1）Cache的基本工作原理（2）Cache和主存之间的映射方式及其地址转换（3）Cache中主存块的替换算法（4）Cache读、写策略
(四)指令系统1.指令格式（1）指令的基本格式（2）定长操作码指令格式（3）扩展操作码指令格式2.指令的寻址方式（1）有效地址的概念（2）数据寻址和指令寻址（3）常见寻址方式3.CISC和RISC的基本概念
(五)中央处理器（CPU）1.CPU的功能和基本结构2.指令执行过程3.数据通路的功能和基本结构基于数据通路，指令周期流程及取指、间址、执行和中断周期的数据流。4.控制器的功能和工作原理（1）微操作命令的分析取指周期、间址周期、执行周期和中断周期的微操作命令及其节拍安排。（2）组合逻辑（硬布线）控制器组合逻辑控制器的组成结构、设计步骤。（3）微程序控制器微程序、微指令、微命令、微操作、控制存储器的基本概念；微程序控制器的设计思想、组成结构、工作原理；微指令的编码方式；微地址的形式方式。5.指令流水线（1）指令流水线的基本概念（2）指令流水线的基本实现影响指令流水线性能的因素：结构相关、数据相关、控制相关；流水线的主要性能：吞吐率、加速比、效率。（3）流水线的多发技术超标量处理机、超流水线处理机、超长指令字处理机的基本概念。
(六)总线1.总线概述（1）总线的基本概念（2）总线的分类（3）总线的组成及性能指标2.总线仲裁（1）集中仲裁方式（2）分布仲裁方式3.总线操作和定时（1）同步定时方式（2）异步定时方式4.总线标准
(七)输入输出（I/O）系统1.I/O系统基本概念2.I/O接口（I/O控制器）（1）I/O接口的功能和基本结构（2）I/O端口及其编址3.I/O方式（1）程序查询方式（2）程序中断方式中断的基本概念；中断响应过程；中断处理过程；多重中断和中断屏蔽的概念；中断处理顺序。（3）DMA方式DMA控制器的组成；DMA传送过程。（4）通道方式
三、参考书目
(一)唐朔飞，计算机组成原理（第3版），高等教育出版社， 2020.10，十二五”普通高等教育本科国家级规划教材。
(二)白中英戴志涛，计算机组成原理（第6版），科学出版社，2019.8，十二五”普通高等教育本科国家级规划教材。
变动：无。
2022年硕士研究生招生考试大纲：考试大纲 | 山东大学832计算机综合考试大纲
页:
[1]