山东大学2024年考研初试大纲：832计算机综合

考研专业课大纲对备考具有重要价值。大纲可以帮助考生了解考试的整体结构和考查重点，在备考过程中起到明确方向的作用。大纲所列出的考试范围和知识要点，可以帮助考生建立知识体系，明确重难点，有针对性地进行备考。同时，弄清大纲要求可以让考生事先了解复习的时间分配和备考要求，避免在备考过程中盲目浪费时间和精力。以下是山东大学2024年硕士研究生招生考试《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.计算机系统层次结构

（1）计算机系统的基本组成

（2）计算机硬件的基本组成

（3）计算机软件的分类

（4）计算机的工作过程

3.计算机性能指标

（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）通道方式

（5）

三、参考书目

计算机组成原理（第3版），高等教育出版社，2020.10，十二五”普通高等教育本科国家级规划教材。

计算机组成原理（第6版），科学出版社，2019.8，十二五”普通高等教育本科国家级规划教材。

原文链接：https://www.yz.sdu.edu.cn/info/1024/5678.htm